December 27th, 2018

moose, transparent

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

Организаторы 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: раскрыл все комментарии.
moose, transparent

утренние ссылки

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

  1. Алексей Цветков хорошо пишет об открытии Латвией картотеки КГБ. Борис Львин оспаривает часть сказанного.

    Если вы не читали, рекомендую также рассказ Юлия Даниэля (того, который процесс Синявского и Даниэля) "Искупление".

  2. Расщепление мозга. Рассказ нейроученого Майкла Газзаниги о знаменитых экспериментах 60-х годов с людьми, у которых для лечения эпилепсии перерезали мозолистое тело, соединяющее полушария мозга.

  3. The Statistical Rule Of Three. Как оценить шанс какого-то события, если снова и снова оно *не* происходит. Например, вы вычитываете книгу и на первых 10 страницах не обнаружили опечаток. Значит ли это, что их в книге нет вообще? Разумеется, нет, но можете ли вы предложить вероятностную оценку этого? В записи предлагается и обосновывается такая оценка.

  4. The Case of Agatha Christie. Книги Агаты Кристи написаны на удивление упрощенным, даже примитивным языком; то же касается психологической глубины персонажей, диалогов итд. Не это ли объясняет сохранение и преумножение ее писательской славы? (звучит довольно жестко, но тон этого эссе мягче и глубже, чем мой краткий пересказ). Автор сравнивает примеры из прозы Кристи и двух ее современниц. Ссылка на архивную страницу, потому что оригинал требует регистрации.

    Понравилась фраза "Her autobiographical writing is startlingly lacking in introspection [...] "Come, Tell Me How You Live", a memoir about her life with her second husband, the archaeologist Max Mallowan, is a serious contender for the least revealing autobiographical book ever written..." Понравилось также наблюдение, что именно с Кристи началась традиция, согласно которой детективный роман занимается именно убийством - Шерлок Холмс расследовал самые разные преступления: грабеж, шантаж, кража идентичности... у Агаты Кристи всегда убийство.

  5. State The Problem Before Describing a Solution. Краткая заметка Лезли Лэмпорта (знаменитого своими работами в области распределенных вычислений) относится на первый взгляд к научным работам в области компьютерных алгоритмов, но стоит задуматься над его советом и людям, далеким от этой области.

  6. Недавно в этой рубрике была ссылка на экономический анализ атаки дронов на аэропорт Гэтвик. Теперь оказывается, что вполне возможно, что никаких дронов и не было.
    Oops, did we just close an airport over a UFO sighting? Честно скажу, что вот этого я совсем не ожидал.
moose, transparent

открытая запись

Если хотите спросить меня или других посетителей о чем-то, предложить что-то, поговорить, поделиться итд. - это тут в комментах.

Я постараюсь отныне делать открытую запись регулярно раз в две недели по четвергам. Предыдущие открытые записи тут.

Возможные темы для разговора:

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