ЧНГ! Задачка за изтрезняване (фейсбук)

[Bibi]

Значи ако решим задачата с 672 приятели (след като виждаме, че 673 вече не става), ще сме открили точната граница, нали така.

Това, което се опитвах да кажа в #20 е как се решава задачата при 672.
Намерих 57 групи от по 5 числа във всяка от тях.
Нито едно число не се повтаря.
Вътре във всяка група числата са подредени по големина и разликата между две съседни е поне 154.
И казвам, че това е невъзможно, ако най-голямото от числата не надвишава 672.

Но чак довечера ще мога да пиша подробно по задачата.

[dedis]

Аз пък се помъчих емпирично да намеря подредба без 77 за 672, но не успях. Възможно е Wise да я пребори, де...

[Wise]

Опс...май трябва вместо 78 да запишем 79 и тогава стават 677, а не -673

Не...78 си е добре! Това е нарастък и е различен от 77. Бариерата 673 остава, засега....

Как се тълкува това:
"период от последователни дни"
1 ден период ли е? Или минимум 2 дни трябва да имаме?

[dedis]

Да, но ние търсим най-малкото (долната граница), над което е възможно да няма период със 77. Така че, съсредоточи се върху 672 !

[Bibi]

И един ден е период. Поне аз така я решавам и не виждам причина да е по друг начин.

А за 672 не мисля, че могат да се намерят примери без 77. Тясно става мястото.

[dedis]

Ами то и Wise смята 1 ден за период, щом е наслагал 78-ици, а не 77-ици.
За 672 изглежда така, но не е зле да се докаже.

Или да я захвърляме тази задача, че много се разтегли във време и пространство? В края на краищата, нали я решихме, а това сега са допълнителни мозъчни сърбежи...

[Bibi]

Аз я считам за решена в смисъл, че точно 672 е най-голямото число, за което можем със сигурност да твърдим, че някъде има сума 77. Но нямах време да пиша тия дни.
Сега малко по малко смятам да опиша намирането на периода.

Имаме 365 дена и във всеки от тях поне по един нов приятел:

a1, a2, ..., a365;      като ai ≥ 1

Правим 365 суми, показващи колко приятели сме добавили до i-тия ден включително:

S1, S2, ..., S365;      като Si > Si-1, S1 = a1, S365 = 672.

Всяка от тези суми делим на 77 и запомняме остатъка, с което получаваме 365 остатъка:

r1, r2, ..., r365

1. Можем да кажем, че поне 5 от тези остатъци са равни.
Това следва от Дирихле и фактa, че 4*77 < 365.
Ще направя пауза, докато всички се уверят, че няма начин 365 числа да се пъхнат в 77 чекмеджета и при това във всяко чекмедже да има по-малко от 5 чисълца.

[dedis]

...Ще направя пауза, докато всички се уверят, че няма начин 365 числа да се пъхнат в 77 чекмеджета и при това във всяко чекмедже да има по-малко от 5 чисълца.

Е оно си е така, де...
Чакам продължението. И ако ти се чопли нататък (още повече няма друга текуща задачка), колко минимум и колко максимум 77-ци може да композираме в подредбата на 672 приятели. Примерно една 76-ца и единици отпред и отзад биха генерирали два 77-мични периода, а 70 и няколко единици около него, дори повече...
ПП: А минимумът би трябвало да е само един 77-мичен период (когнитив байс свързан с понятието граница).

[Bibi]

Добре.
Нека да си изберем оня остатък, който се среща най-често.
Както казахме, той се повтаря поне 5 пъти. Но може да е и повече от 5.
Затова разделям нещата на два случая:
I. най-често срещания остатък го има повече от 5 пъти.
II. няма такъв - т.е. всички остатъци се срещат 5 или по-малко пъти.

По отделно и в двата клона може да се намери период със 77 нови приятели.

I. имаме остатък, който присъства 6 или повече пъти. Достатъчни са ми само първите му 6 срещания.
Нека стойността му да е някаква (R) и 6-те първи позиции, на които го намираме да кръстим b, c, d, e, f, g.
Сега да се върнем нагоре към сумите, които дават тия остатъци. Какво можем да разберем за тях.
Да погледнем кои да е две суми, примерно Sb и Sc.
Sb = B.77 + R
Sc = C.77 + R
Sc - Sb = нещо.77
С други думи разликата на две такива суми винаги се дели на 77.

Надебелих го, понеже това е най-важното нещо в целия ми метод.
Ако две суми имат равни остатъци, то разликата между тях се дели на 77.
Тогава приятелите, набрани през периода [b+1, c] е число, което се дели на 77.

До решението ни остава само една стъпка. И тя е да намерим разлика, която не е 2*77, или 7*77, или коя да е подобна, а да е тъкмо 1*77.

[dedis]

Извини ме за многото редакции. Някои се оказаха, неволно, след твоя отговор.

[Bibi]

Нямам проблем с многото ти редакции.
Но аз нямам намерение да го правя конструктивно - като подреждам групи от 1 из интервала и да ги нагаждам. Защото този начин е с много случаи и е трудоемко.

Сега да довършим решението в случай I.
Имаме 6 суми с равни остатъци. Ако допуснем, че никои две от тях не са на разстояние 77, вече знаем, че разстоянията между тях ще са поне 2*77 = 154.
Но тогава:
1 ≤ Sb
155 ≤ Sb + 154 ≤ Sc
309 ≤ Sc + 154 ≤ Sd
463 ≤ Sd + 154 ≤ Se
617 ≤ Se + 154 ≤ Sf
771 ≤ Sf + 154 ≤ Sg

Получихме, че последното от 6-те числа трябва да е много по-голямо от 672, което е противоречие.
Този интервал е тесен за 6 числа, ако те са на разстояние поне 154 едно от друго.
Значи някъде все пак е имало по-малко разстояние, а именно 1*77!

[dedis]

Къде е тук конкретното число 672? Тези разсъждения не важат ли и за 673?

[Bibi]

Няма го тук нашето число. Случай I. е по-очевидния и той важи за всяко число по-малко от 771.
Но ни остана още един случай и точно в него се вижда защо точно 672 ни трябва.

Аз се чудя дали описвам нещата разбираемо.
Другия случай е много подобен на този и ако не съм ясна, ще опитам него да го кажа с други думи?

[dedis]

Мисля, че на мен ми се изясни до тук. И то гледайки мачовете в ГБ висшата лига .
Така че - в същия дух карай...

[Bibi]

Ами то и аз съм на вълна Висша лига, явно сме в синхрон с теб

Сега остана случай II.
Имаме 77 различни остатъка и всеки от тях се повтаря най-много по 5 пъти в онази редичка {r}.
Но дори да гледаме да ги разпределим колкото може по-балансирано, след като във всяко чекмедже сложим по 4 числа, пак ще ни артисат цели 57. Тях трябва да ги пръснем на различни места, за да не става никъде по повече от 5. Така стигаме до извода, че в този случай имаме поне 57 групи във всяка от които има по най-малко 5 числа.

Сега от всяка от тези групи взимам само първия (най-малкия) лидер. И тях ги подреждам по големина:
1 ≤ Sx1 < Sx2 < ... < Sx57
От където ми излиза, че има група, която започва от число, равно най-малко на 57.
Вече останалите групи не ми трябват, ще използвам само тази - последната.

Тук разсъжденията се повтарят както в миналия случай.
Само дето вече имаме първи член не 1, а поне 57, но пък в групата има 5, а не 6 суми.
57 ≤ Sb
211 ≤ Sb + 154 ≤ Sc
365 ≤ Sc + 154 ≤ Sd
519 ≤ Sd + 154 ≤ Se
673 ≤ Se + 154 ≤ Sf

Значи петия елемент на тази специално подбрана група се получава равен поне на 673.
Е, ако имахме 673 приятели, щяхме да можем да ги подредим през различните дни така, че никъде да няма 77. Wise показа такова нареждане. Ние обаче имаме само 672 и стигаме до противоречие.
То ни казва, че в най-късно започващата група не всички разлики са 154, а поне една е 77.
Така и тук намерихме мечтания интервал от дни.