Question

Сколькими способами из чисел 1, 2, ..., 2n можно выбрать выбрать два или больше так, чтобы никакие два выбранных числа в сумме не давали 2n+1?



СРОЧНО!!!

Answer 1

3n – 2n – 1. Разобьем все 2n чисел на пары чисел, дающих в сумме 2n + 1: (1,2n), (2,2n – 1), , (n,n + 1). Выбирая искомые числа, мы не можем брать два числа из одной пары. Поэтому из первой пары мы можем взять либо первое число 1, либо число 2n, либо не брать ничего. Те же три возможности для выбора мы имеем и для каждой из оставшихся n – 1 пар. Так как эти возможности независимы друг от друга, всего существует 3n наборов чисел, не содержащих двух чисел из одной пары. Среди них есть один пустой и 2n одноэлементных, а остальные 3n – 2n – 1 наборов нам подходят.