Как много нечётных чисел можно вписать?

[Ktina]

Ярдена хочет вписать натуральные числа в ячейки на рисунке так, чтобы, начиная со второго снизу ряда, каждое число являлось суммой двух чисел в соседних ячейках, расположенных непосредственно снизу от него. Какое наибольшее количество нечётных чисел может вписать Ярдена?

[waxtep]

Больше $10$ не получится - в каждом "элементарном треугольнике" (ячейка и две ячейки под ней) не более двух чисел нечетно. А $10$ - можно: в нижнем ряду по центру ставим четное число, на оставшихся четырех позициях - нечетные

-- 14.04.2018, 01:31 --

+ напомнило задачу, за которую брался, но, кажется, до ума не довел

[Ktina]

waxtep
А как Вы разобьёте приведённое на катринке множество на непересе кающиеся элементарные треугольники?

[waxtep]

Да, погорячился. Мне казалось, что если треугольники пересекаются, больше, чем $\frac2 3$ не получить, что неверно:

$$\begin{tabular}{c}1 1\\1 0 1\end{tabular}$$

Тогда разобъем на неперескающиеся и посмотрим на остатки( "o" for "ostatok"):

$$\begin{tabular}{c}.\\. .\\o . o\\. . . .\\. . o . .\end{tabular}$$

Чтобы получить $11$ нечетных чисел все ostatki должны быть нечетны, т.е. должно быть так:

$$\begin{tabular}{c}0\\ \overline{xy}\, \overline{xy}\\1 xy 1\\x \overline{x}\, \overline{y}\, y\\0 x 1 y 0\end{tabular}$$

(четные числа заменены на $0$, нечетные на $1$, а сложение - на исключающее или, т.е. $xy=x\oplus y$ и $\overline x$ обозначает не-$x$). Видно, что еще $8$ единиц, вдобавок к имеющимся $3$, не получить

[Ktina]

waxtep
В принципе, там проще можно решить. Подсказываю, всё зависит от того, сколько нечётных чисел в самом нижнем ряду. Если их 5, то их и во всей этой конструкции ровно 5. Если 4, то рассматриваем 3 случая вручную, это нетрудно. А дальше очень красиво и интересно получается. И не забывайте, что задача-то для младших классов

[waxtep]

Ktina, не допираю могу вот такую разновидность разбиения на треугольники предложить, поизящнее:

$$\begin{tabular}{c}a\\a a\\b d c\\b b c c\\o d o d o\end{tabular}$$

Здесь $o$ - снова ostatki, а в каждом из треугольников, помеченных одинаковыми буквами, максимум $2$ из $3$ вершин содержат нечетные числа. Ну и тогда, в попытке получить $11$ нечетных вершин, достаточно рассмотреть нижнюю строку только одного вида $11101$, но она дает всего $9$ нечетных вершин.

Общая формула, видимо, вот она: A007980. Оттуда меня особенно заинтересовало соотношение

Цитата:

a(n) = [a(n-1) + (number of even terms so far in the sequence)].

-- 15.04.2018, 01:25 --

A004396 - элегантная разность для соседних $n$ (число ячеек в основании)

[waxtep]

Ага, и вот рецепт (доказать пока не берусь) достижения максимума для любого $n$: берем нижнюю строку вида $110110\ldots$, т.е. повторяем фрагмент $110$, покуда хватает позиций. Все строки выше будут иметь подобный вид, что дает количество нечетных чисел близким к $\frac 2 3$ от общего числа. Например, для $n=7$ нижняя строка будет $1101101$ и т.п.

[Ktina]

waxtep
Если в самой нижней строке ровно 5 или ровно 4 нечётных, что всего их будет меньше 11. Проверяется непосредственно - один случай с 5-ю и три случая с 4-мя (вернее, 5 случаев с 4-мя, но там есть две пары симметричных случаев).

Теперь, пусть в самой нижней строке не более трёх нечётных. Тогда в оставшихся четырёх строках должно быть в сумме не менее 8 нечётных, ведь мы хотим получить всего как минимум 11.

Если во второй снизу строке ровно 4 нечётных, то всего их не более 7 (ведь в самой нижней - не более трёх), а выше второй все пойдут уже чётными.

Значит, во второй строке тоже не более 3 нечётных, итого не более 6 в сумме в самой нижней и во второй снизу. А это значит, что в трёх верхних в сумме не менее 5 нечётных. Но в первой и второй сверху не может быть более 2 нечётных. Значит, третья сверху строка вся нечётная. Но тогда в трёх верхних в сумме не более 3 нечётных, а их, как мы уже упомянули, должно быть не менее 5. Противоречие.

Запутано получилось?

[waxtep]

Ktina, почему, понятно кажется, оба способа в лоб не обобщаются на призвольное $n$, значит, примерно одинаковые. Разбиение на треугольники плюс "рецепт $110$" позволяют избежать перебора в случаях, когда пирамидка полностью разбивается на непересекающиеся треугольники, например, для $n=6$:

$$\begin{tabular}{c}a\\a a\\b d c\\b b c c\\e d f d g\\e e f f g g\end{tabular}$$

(в любом "правильном" треугольнике "высотой" $2^m$ не более двух вершин нечетны, поэтому треугольник с вершинами $d$ тоже работает). Т.е. сразу получаем, что нечетных вершин не более $14$, и берем основание в виде $110110$ для построения примера, где максимум достигается