Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

задачка о треугольнике паскаля

Организаторы IMO - международной олимпиады по математике - за 2019 год запостили в Фейсбуке красивую задачку в виде новогоднего подарка. Вот ее условие в переводе на русский, предлагаю попробовать. Сразу скажу, что задача решается без сложных выкладок и компьютерных программ, и не такая тяжелая, как задачи на международной олимпиаде :), но и не тривиальная.

Я заскриню комментарии на сутки, буду раскрывать только вопросы об условии, без подсказок. Через сутки раскрою все и напишу здесь об этом, после этого в комментариях будут правильные решения.

==================
Предположим, у нас есть строка из нулей и единиц, например, "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: раскрыл все комментарии.
Tags: задачка, математика
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 42 comments
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →