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

[dedis]

Здраве, късмет и забавления на всички!
Един човек завързвал много приятелства във фейсбук.
Само за миналата година броят им нарастнал с 450, като не минавал ден без поне едно ново приятелство.
Въпросът е: Има ли поне един период от последователни дни, за който броят на новите му приятели е нарастнал точно със 77 души?

[SetCombG.com]

[Bibi]

Супер си, dedis, много е интересна тази задачка!

Вероятно отговорът е "да" - както и да се подредят числата, все ще има някъде сума 77.
Но как да го докажем? Сигурно трябва да се моделира по някакъв много хитър начин, не е добре да я действаме грубиянски.
Имам идейки за 2-3 похвата, но в момента не успявам да ги продължа. Ако още някой се опитва тук, може да обменим мисли.

[Krusteva]

Нещо с допускане на противното ми се ще :-)

[Bibi]

Хаа!
Щом има живот в тая тема, ще кажа какви си ги мислех.
Едната ми идея беше да разделим числата на 5 групи по 73. И да си изберем например групата с най-малка сума за начало. Тя има обща сума между 73 и 90. И да кажем не е 77, защото тоя случай е безинтересен.

Другата хрумка е графична.
Рисуваме (наум) графика от свързани точки: броят приятели, добавени през първия ден, после плюс втория, плюс третия... до 365-тия. Тази графика може да бъде най-разнообразна, но е ясно, че е строго растяща, намира се в първи квадрант някъде над правата x = y и свързава (0, 0) с (365, 450).
Също слагаме една червена линия на y = 77.
Иска ни се двете да се пресичат в съществуваща точка от нашата графика.
Ако не - плъзгаме графиката с една стъпка надолу, така че първата точка да легне на остта x. (Това са сумите от втория ден натам.)
Пак гледаме дали се пресичат в точка от нашите.
Целта е да докажем, че все някога след поредното плъзгане ще получим пресичане в точка.

[SetCombG.com]

[Krusteva]

Втората идея е много красива, не ми беше хрумвала! Първият вариант го мислех снощи, но нямам съществен напредък.

[dedis]

Много интересна идея, Биби - с графиката. За компютър е ОК. На ръка... Ако искате, може да сметнете по колко начина се разполагат 450 души в 365 дни, без празен ден. Но сигурно са хиляди подредби. Та трудно ще обходим с 77-квантов прозорец всичките.
Все пак, това си е един алгоритъм!
Задачата се решава лесно с Принципа на Дирихле (The first formalization of the idea is believed to have been made by Johann Dirichlet in 1834 under the name Schubfachprinzip ("drawer principle" or "shelf principle"). For this reason it is also commonly called Dirichlet's box principle, Dirichlet's drawer principle or simply "Dirichlet principle"). Цитатът е от Уики - има и българска версия.
Прилага се съвместно с идеята на Кръстева!
Не трябваше да казвам "лесно". Лесно става чак като я решиш или узнаеш решението. Иска си едно досещане (част от което е подходът на Биби) за да не прибягваш до груба сила.

[Bibi]

Идеята с графиката не искам да я използвам за пълно изчерпване. Затова казах, че я рисувам наум.
Тя само ми помага да виждам проблема по друг начин.
Например с нея "видях", че ако някъде имам поредица от 4 единички, то около червената линия трябва непременно да имам дупка с големина поне 5.
И аз работя както Кръстева с допускане на противното.
А поредици от поне 4 единици е гарантирано, че имаме, ако допуснем, че числата са само 1 и 2. Мисля че точно заради Дирихле. Което е противоречие - намерихме число, различно от 1 и 2.

Казано в термините на задачата: има дни, в които човекът се е свързал с поне 3 "приятели".

[dedis]

За не-математиците (като мен) - илюстрация на "страшно" звучащия Принцип на Дирихле:
Ако трябва да разположим 12(n) гълъба в, да речем, 10(m) клетки, Дирихле казва, че поне в една клетка ще има повече от един гълъб. На академичен език: ако n>m, то... и т.н.
В тази задача трябва да впрегнем този принцип, като предположим обратното - че няма такъв отрязък от време и да докажем, че това противоречи на принципа.
Това го казвам за лаиците, за да обясня досегашните постинги.
Митето и Мъдрия май още витаят в свинско-алкохолни изпарения. Дано се появят скоро. Заради втория бях вкарал и мацки в условието, но се сетих, че не е лято.
То имаше и топки, но се усетих своевременно, слава Богу...

ПП: Хей, да не ми се обидят тези, които не споменах - Тонич, Фиъ-ми, Крис и всички участници в този раздел!!!
Хайде, народе, размърдай се!

[SetCombG.com]

[dedis]

Бяла тишина...
Хайде една по-лесна:
В равнината има пет различни точки с целочислени координати. Свързваме с отсечки всяка точка с останалите четири. Докажете, че средата на поне една от тези отсечки има също целочислени координати.

[Bibi]

Лесна е тази. Гледаме четностите на координатите...
Да не искаш да кажеш, че има връзка с основната?

[Krusteva]

Нека означим координатите на точките с Х и Y и и ги индексираме с 1 до 5.
Средата на всяка една отсечка, получена между точки с координати X_K;Y_K и X_N;Y_N, се записва с координати 0.5*(X_N-X_K); 0.5*(Y_N-Y_K).
Достатъчно е двете абсциси и ординати да са от еднаква четност, за да имаме целочислени координати на средата на отсечката.
От петте точки с принципа на Дирихле следва, че имаме поне 3 точки с еднаква четност по Х.
Разглеждаме тях, прилагаме пак Дирихле и излиза, че от трите поне две са с еднаква четност по Y.
Така си намерихме две точки с две еднакви четности на координатите по осите и практически решихме мързеливо описано задачата  

P.S.
Не знам има ли връзка с основната, но с тоя Дирихле открих какви ли не глупости по нея и пак не можахме да се разберем...

[dedis]

Лесна е тази. Гледаме четностите на координатите...
Да не искаш да кажеш, че има връзка с основната?

Ами, да. Кръстева го рече. Пак Дирихле.
Малко по-просто:
Възможни са следните координати: Ч,Ч/Ч,Н/Н,Ч/Н,Н.
Ч - четно число, Н - нечетно.
Т.е. петата точка дублира някоя от предните четири по отношение на четността.
Координатите на средата са средно-аритметични на координатите на краищата.
Тъй като всеки дубъл гарантира целочислено средно аритметично на двете координати (Ч+Ч=Ч, Н+Н=Ч и Ч/2=цяло число), то доказателството е извършено.

ПП: Многословието е за лаици като мен.

Сега пак малко за първата задача:
Очевидно, за да има думата Дирихле, е необходимо на възможните вариации на нарастване на приятелите "да им е тясно", и, щат-нещат, да предоставят периоди със сума в тях равна на 77. Дори да се мъчим да ги подредим така, че да няма такива периоди.

[Bibi]

Малко напредък.
Пиша редицата от сумите от първото до поредния ден.
Но не самите суми, а остатъците им по mod 77.
Понеже са 365 (повече от 77) числа, от Дирихле -> има поне две суми с еднакви остатъци.
Кръщавам ги M и N.
Разликата между тях се дели на 77.
Значи сумата на редицата от (M+1)-вото до N-тото се дели на 77.

Всъщност има не 2, а поне 5 числа с равни остатъци. (365/77 > 4)
И всяко е по-голямо от предното.
От тук трябва лесно да излезе, че поне 2 от тях имат разлика 1*77.

[dedis]

А защо делиш 365 на 77, като редицата расте до 450 човечета за 365дни?
Или смяташ, че числото 450 е без значение?
А то е от значение. Например, ако беше не 450, а 700, ти гарантирам, че може да няма период с 77 новопокръстени.
ПП: То аз гарантирам, ма май греша...

[SetCombG.com Forum]