?

Log in

No account? Create an account
задачка о треугольнике паскаля - По делам сюда приплыл, а не за этим [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

задачка о треугольнике паскаля [дек. 27, 2018|08:06 am]
Anatoly Vorobey
[Tags|, ]

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

Comments:
Страница 1 из 3
<<[1] [2] [3] >>
From: Ilya Chernykh
2018-12-27 07:05 am
Любопытно.

Насколько я понимаю, "красивыми" будут все строчки (и только они), которые заканчиваются на 0. Тем самым их количество равно 2^(n-1) при n>1. Строка "1" является естественным исключением, она тоже "красивая". Тем самым при n=1 ответ 2, при n>1 --- 2^(n-1).

Подсказка 1. Пусть исходная строка имеет элементы a_1,...a_n.
В "диагональной строчке" каждый элемент в позиции i равен сумме a_i+a_n.

Подсказка 2... видимо не требуется.
(Ответить) (Thread)
[User Picture]From: avva
2018-12-27 07:29 am
>Насколько я понимаю, "красивыми" будут все строчки (и только они), которые заканчиваются на 0. Строка "1" является естественным исключением, она тоже "красивая".


Нет, это неверно; например, строка 1010 не красивая.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: microcell
2018-12-27 07:13 am
Ок, обозначим горизонтальную строчку через i1, i2, i3,... in и вертикальную через j1, j2, j3,... jn

Не сложно заметить, что in всегда равно jn, то есть, этот этомент всегда "красивый"

jn-1 является произведением in-1 + in. Не сложно заметить, что:

0 + 0 = 0
1 + 0 = 1
0 + 1 = 1
1 + 1 = 0

Или, иначе это операция не что иное, как XOR

Только первые две коибинации дадут нам "красивый" результат

Для jn-2 ситуация еще интереснее

jn-2 = (in-2 xor in-1) xor (in-1 xor in)

0, 0, 0 = 0
0, 1, 0 = 0
1, 0, 0 = 1
1, 1, 0 = 1

Я убрал варианиты, заканчивающиеся на 0, 1 и 1, 1 как заведома некрасивые. Что удевительно, все четыре варианта дают правидьный результат.

Для jn-3

0, 0, 0, 0 = 0
0, 0, 1, 0 = 1
0, 1, 0, 0 = 1
0, 1, 1, 0 = 0
1, 0, 0, 0 = 1
1, 0, 1, 0 = 0
1, 1, 0, 0 = 0
1, 1, 1, 0 = 1

Что даёт 4 красивых решения

Для jn-4

0, 0, 0, 0, 0 = 0
0, 0, 1, 1, 0 = 0
0, 1, 0, 0, 0 = 0
0, 1, 1, 1, 0 = 0
1, 0, 0, 0, 0 = 1
1, 0, 1, 1, 0 = 1
1, 1, 0, 0, 0 = 1
1, 1, 1, 1, 0 = 1

Можно продолжать и дальше, но паттерн уже виден и так.

Количество красивых решений при заданном n будет равно

1 = 1
2 = 2
3 = 4
4 = 4
5 = 8


Или 2 в степени (n + 1) / 2 при нечетных n и 2 в степени n /2 при четных

Edited at 2018-12-27 07:20 (UTC)
(Ответить) (Thread)
From: dodderbranch
2018-12-27 07:22 am
Заметим, что если в треугольнике число в одной из вершин равно сумме (по модулю 2) чисел в двух других вершинах, то это свойство справедливо для всех остальных вершин. Это значит, что если повернуть исходный треугольник на 120 градусов, он всё ещё будет треугольником Паскаля, и задача сводится к такой: с какой строки нужно стартовать, чтобы боковые строки стали одинаковы.

Понятно, что все симметричные строки подходят. И обратно: если с конфигурации в которой боковые стороны одинаковы можно подняться, то исходная строка обязана быть симметричной (поднятие осуществляется за счёт того, что сумма чисел в маленьком треугольнике, стороны которого параллельным сторонам исходного равна 0 по mod 2). Если n=2k, то симметричных строк 2^k, если n=2k-1, то их также 2^k.

Edit: То, что из разных симметричных строк будут получаться разные боковые строки почти очевидно. Предположим, что из разных начальных строк получились одинаковые боковые. Сложим поэлементно два этих треугольника. Получим треугольник Паскаля с нетривиальной первой строкой и нулевыми боковыми. Но из нулевых боковых подняться можно только до нулевой первой строки.

Edited at 2018-12-27 08:12 (UTC)
(Ответить) (Thread)
[User Picture]From: timur0
2018-12-27 07:42 am
Да вроде всего две: все нули и единица и остальные нули.
(Ответить) (Thread)
[User Picture]From: avva
2018-12-27 07:53 am
>Да вроде всего две: все нули и единица и остальные нули.

Нет, например 10 красивая строка. 010 тоже.

Edited at 2018-12-27 07:53 (UTC)
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: andronic
2018-12-27 08:02 am
Нетрудно заметить, что если "каждое число - сумма двух лежащих над ним, только все суммы делаются по модулю 2",
то
если мы складываем число и лежащее под ним направо, то получаем число слева от него,
и если мы складываем число и лежащее под ним слева, то получаем число справа от него.

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

По условию задачи мы должны найти количество "красивых" строк, которые создают треугольник Паскаля, у которого верхняя сторона идентична правой. По выясненному выше это получится тогда и только тогда когда левая сторона будет симметричной. Тогда и только тогда по правилу сложения она будет "порождать" идентичные верхнюю и правую стороны.

А симметричной она будет если n/2 правых цифр левой стороны будут зеркально отображать n/2 левых цифр левой стороны.
Таких случаев будет 2 в степени n/2. PS Это для четных. Для нечетных - 2 в степени (n+1)/2.
Это и есть ответ задачи, так как одна левая сторона может порождать одну и только одну верхнюю - "красивую" (потому что правило сложения однозначное).


Edited at 2018-12-27 08:12 (UTC)
(Ответить) (Thread)
[User Picture]From: fyz
2018-12-27 08:28 am
С нетерпением жду красивую идею. Сама смогла только перебором (ну, не все 2^n варианта перебирала конечно, а увеличивая размерность от правого уголка) - получилось размерности 6 всего 2 варианта: 010110 и 110110. Интересно что от 3 до 6 во всех размерах есть 2 варианта и только один имеет продолжение, а после 6 уже оба варианта имеют продолжение, так что размером 7 красивых строк уже 4.
(Ответить) (Thread)
[User Picture]From: avva
2018-12-27 11:04 am
>получилось размерности 6 всего 2 варианта: 010110 и 110110.

Есть еще несколько, всего 8 :)

010110
110110
011110
111110
000000
100000
001000
101000
(Ответить) (Parent) (Thread)
[User Picture]From: migmit.dreamwidth.org
2018-12-27 08:33 am
Обрезаем верхнюю строчку и правую диагональ, получаем треугольник с тем же свойством. Исходный треугольник восстанавливается однозначно, если выбрать левый верхний элемент. Так что таких последовательностей вдвое больше, чем таких же на 2 короче. Для 1 и 2 считаем руками, получаем 2^{k+1} для последовательностей длины 2k+1 и 2^k для длины 2k.
(Ответить) (Thread)
[User Picture]From: darth_mozg
2018-12-27 08:47 am
Во первых: любая красивая строка, если отрезать отрезать от нее любой кусок слева также останется красивой. И обратно, из некрасивой строки не получить красивую если добавить к ней что-нибудь слева.
То есть все красивые строки кончаются на 10 или 00 (две возможных красивых строки для n=2).
Для любого n число красивых строк можно получить лишь посмотрев как к существущим (n-1)-красивым строкам припысывается слева 0 или 1.
пронумеруем начальную строку как а^n,a^(n-1), ... , a^1
а результат как b^n,b^(n-1), ... , b^1
a^(n-1), ... , a^1 совпадает с b^(n-1), ... , b^1 так как строка исходная строка у нас уже красивая.

Для нечетных n: b^(n) = а^n + a^1. (не делал строгого вывода. Но интуиция подсказывает что так и есть). Так как a^1 у нас всегда 0 (строки 11 и 01 некрасивые), то а^n всегда будет равно b^(n). Или для нечетных n число красивых строк удваивается по отношению к n-1

Для четных n: b^(n) = a^n + a^(n-1) + ... + a^1 (то есть сумма всех a. Тут, кажется, очевидно). То есть если сумма всех предыдущих а равна 1 - то новых красивых строк не будет. Если сумма всех предыдущих а равна 0 - любая новая строка будет красивой.
Вернемся на шаг назад - на нем у нас удвоилось количество красивых строк. Половина из них слева добавилась 1. К другой половине добивлась слева 0. То есть у нас будет половина красивых строк с суммой 1 и половина с суммой 0 (опять здесь не делал строго вывода, но выглядит очевидным). То есть к половине строк мы можем добавить что угодно и строка останется красивой, к половине не можем добавить ничего.

Итого = на четных n количество красивых строк совпадает с (n-1). На нечетных удваивается. Для n=2 красивых строк 2.
Итоговая формула - K = 2^((n-1)/2) (деление на 2 с округлением вниз).

Edited at 2018-12-27 09:57 (UTC)
(Ответить) (Thread)
[User Picture]From: Я Я
2018-12-27 08:53 am
для N=0 существуют 1 красивая строка ;)
Для нечетного N число красивых строк = 2* {число красивых строк для (N-1)}
ИБО можно к любому "варианту предыдущей итерации" приписать слева хоть ноль хоть единицу и получишь вариант этой итерации. Иные новые варианты не появляются.
Для нечетного N число красивых строк = число красивых строк для (N-1)}
ИБО можно к любому "варианту предыдущей итерации" приписать справа только ноль и получишь вариант этой итерации. Иные новые варианты не появляются.

Ответ:
2^Целая_Часть_от[(N+1)/2]

(Ответить) (Thread)
[User Picture]From: utnapishti
2018-12-27 10:03 am
Если повернуть треугольник на 120 градусов, свойство "каждый элемент равен сумме двух соседей сверху, mod 2" не изменится.
Поэтому требование выполняется iff третья сторона треугольника - симметрична. Поэтому ответ - 2 в степени {n/2 округлённое в нужную сторону}.

Верно?
(Ответить) (Thread)
[User Picture]From: akho
2018-12-27 10:12 am
Этот треугольник можно строить, начиная с любой стороны. Чтобы верхняя и правая были одинаковые, левая должна быть симметричной. То есть $2^{\lceil n/2 \rceil}$.
(Ответить) (Thread)
[User Picture]From: pharmazevt
2018-12-27 10:32 am
Я стал увеличивать n и смотреть, сколько остается красивых строк. Вроде так выходит, что на каждом четном n красивых остается половина строк, а при добавлении к этим красивым строкам слева еще одной цифры (n+1, нечетное) все красивые строки остаются красивыми. Потом n+2 четное, опять половина. И так далее. Получается что-то типа 2^(n-int(n/2)) ??
(Ответить) (Thread)
[User Picture]From: lu_in_pampas
2018-12-27 10:54 am
Пока заметила только, что у красивой строки длины n правая подстрока длины n-1 тоже красивая. Но дальше что-то не получается :(
(Ответить) (Thread)
[User Picture]From: baohe
2018-12-27 11:07 am
Ровно половина треугольников будет красивыми. Утверждение доказывается по индукции, получая "новые" треугольники (размера n+1) из "старых" (размера n) построением левой диагонали (длинны n+1) из левого угла вниз. Для каждого красивого треугольника получается ровно два красивых треугольника следующего размера: один начинается и заканчивается на 0, а другой, соответственно, - на 1.
(Ответить) (Thread)
[User Picture]From: avva
2018-12-27 11:11 am
>Ровно половина треугольников будет красивыми.

Нет. Обратите внимание, например, что из 16 возможных треугольников для n=4 только 4 красивые, а именно

0110
1110
0000
1000

и никакие другие.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: lu_in_pampas
2018-12-27 11:17 am
Рассмотрим, что происходит при добавлении в начало красивой строки 1 или 0 (к некрасивым что ни добавляй, красивыми они не станут).

Если длина красивой строки нечётное число, то на выходе получатся либо две красивых строки, либо две некрасивых. Если чётное - то каждая красивая строка даёт две новых красивых строки.

В общем, из соображений симметрии я бы предположила следующую формулу: количество красивых строк длины n равно два в степени n/2 (где результат деления нужно округлять вверх).

(Ответить) (Thread)
Страница 1 из 3
<<[1] [2] [3] >>