задачка о треугольнике паскаля
Dec. 27th, 2018 08:06 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaОрганизаторы IMO - международной олимпиады по математике - за 2019 год запостили в Фейсбуке красивую задачку в виде новогоднего подарка. Вот ее условие в переводе на русский, предлагаю попробовать. Сразу скажу, что задача решается без сложных выкладок и компьютерных программ, и не такая тяжелая, как задачи на международной олимпиаде :), но и не тривиальная.
Я заскриню комментарии на сутки, буду раскрывать только вопросы об условии, без подсказок. Через сутки раскрою все и напишу здесь об этом, после этого в комментариях будут правильные решения.
==================
Предположим, у нас есть строка из нулей и единиц, например, "0 0 1 1 0 1". Построим на ней "треугольник Паскаля", в котором каждое число - сумма двух лежащих над ним, только все суммы делаются по модулю 2, так что во всем треугольнике только нули и единицы. Иными словами, каждое число равно 0, если два лежащих над ним числа равны, и 1 если они неравны:
В треугольнике, что у нас получился, посмотрим на две строки: верхняя строчка слева направо, это то, с чего мы начали: 0 0 1 1 0 1, а также диагональ от низа по правому краю: 1 1 1 0 1 1 (внимание, именно в этом направлении: ОТ нижнего числа К самому крайнему справа сверху). Эти две строчки не одинаковые в нашем примере. Если для какой-то начальной строки они окажутся одинаковые, назовем такую строку "красивой".
Представьте, что вы берете все 2^n возможных строк из 0 и 1 длиной n, и каждую проверяете, красивая она или нет, построив такой треугольник. Сколько всего будет красивых строк длиной n?
Сложные вычисления не нужны для решения задачи. Используйте только красивые идеи.
==================
Update: вы все охренительно умные. В комментариях есть много, пока скрытых, правильных решений. Первым(ой) предложил(а) полное решение с док-вом юзер![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif)
dodderbranch. К полудню по Москве есть также верные решения от andronic, Migmit, darth_mozg, "Я Я", utnapishti, akho. Еще несколько человек дали правильный ответ, но без полного доказательства. Завтра раскрою все комментарии.
Update: раскрыл все комментарии.
Я заскриню комментарии на сутки, буду раскрывать только вопросы об условии, без подсказок. Через сутки раскрою все и напишу здесь об этом, после этого в комментариях будут правильные решения.
==================
Предположим, у нас есть строка из нулей и единиц, например, "0 0 1 1 0 1". Построим на ней "треугольник Паскаля", в котором каждое число - сумма двух лежащих над ним, только все суммы делаются по модулю 2, так что во всем треугольнике только нули и единицы. Иными словами, каждое число равно 0, если два лежащих над ним числа равны, и 1 если они неравны:
0 0 1 1 0 1
0 1 0 1 1
1 1 1 0
0 0 1
0 1
1
В треугольнике, что у нас получился, посмотрим на две строки: верхняя строчка слева направо, это то, с чего мы начали: 0 0 1 1 0 1, а также диагональ от низа по правому краю: 1 1 1 0 1 1 (внимание, именно в этом направлении: ОТ нижнего числа К самому крайнему справа сверху). Эти две строчки не одинаковые в нашем примере. Если для какой-то начальной строки они окажутся одинаковые, назовем такую строку "красивой".
Представьте, что вы берете все 2^n возможных строк из 0 и 1 длиной n, и каждую проверяете, красивая она или нет, построив такой треугольник. Сколько всего будет красивых строк длиной n?
Сложные вычисления не нужны для решения задачи. Используйте только красивые идеи.
==================
Update: вы все охренительно умные. В комментариях есть много, пока скрытых, правильных решений. Первым(ой) предложил(а) полное решение с док-вом юзер
dodderbranch. К полудню по Москве есть также верные решения от andronic, Migmit, darth_mozg, "Я Я", utnapishti, akho. Еще несколько человек дали правильный ответ, но без полного доказательства. Завтра раскрою все комментарии.Update: раскрыл все комментарии.
