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

[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 новопокръстени.
ПП: То аз гарантирам, ма май греша...

[Bibi]

Сумите са 365, а остатъците им са 77.
Затова деля така. 365 гълъба и 77 клетки.
Има клетка с поне 5 гълъба.

За числото 450 ме интересува само това, че е по-малко от 6*77.

Мисля си дори, че това е слабо условие. Истинско ограничение вичдам чак при 8*77.
Да, ако бяха 700 не е ясно нищо, но ако бяха 600, все още задачата ще е вярна.

[dedis]

Не вниквам напълно в логиката, но с 99% сигурност (IMHO) това е верен подход!
Почти си открила граничните условия за съществуване на 77-членен контингент, което ми дава основание за това мнение.
Не че в условието се иска такова задълбочаване, де.
"Моят" подход е друг, все пак. Но е възможно ти да му намериш дефект .

[Bibi]

- Списък от 365 числа, като i-тото от тях a_i е равно на броя приятели, добавени през i-тия ден. a_i > 1
- Втори списък пак от 365 числа, като i-тото от тях S_i е равно на сумата приятели, добавени от началото на първия до края на i-тия ден.
По условие тези числа S_i растат, т.е. всяко е по-голямо от предното, и последното S₃₆₅ = 450.

1. Искам да докажа, че има сума от приятелите, събрани през няколко поредни дни, която се дели на 77.
Всяка такава сума може да се представи като разлика на две от числата {S}
S_N - S_M
това са приятелите, добавени между M-тия и N-тия ден.
За да се дели това число на 77, трябва S_N и S_M да имат еднакви остатъци при деление на 77.
Но понеже остатъците са малко, а сумите - много, Дирихле ни гарантира, че има поне 2 с еднакви остатъци.

2. Искам да докажа, че има сума, която е точно равна на 77
Понеже 365/77 > 4, пак от Дирихле можем да научим, че има поне 5 суми с равни остатъци R.
Нека да са такива:
1 <= 77*p + R < 77*q + R < 77*s + R < 77*t + R < 77*u + R <= 450
от тези неравенства се вижда, че
0 <= p < q < s < t < u <= 5
Ей така като погледнеш последния ред, веднага се вижда, че поне една от двойките е с последователни числа.
например q = p + 1
И тогава разликата между техните суми ще е точно 77, което искахме.

3. Ако общо приятелите са под 616 (= 8*77), горната логика се запазва.

[dedis]

Чак сега видях написаното от Биби.
Контролен въпрос: Ако бройката е 620 или 650, какво ще кажеш, Биби?

[Bibi]

Ако е повече от 616, онова, което предлагам, няма да даде сума 77.
Което не е доказателство, че такава сума липсва. Но ще трябва да се търси по друга схема.

Например 5-те начални суми с равни остатъци може да са
1,...,155,...,309,...,463,...,617
Тогава които и две да извадим, разбира се пак ще получим нещо, което се дели на 77, но няма да е самото 77.

Всъщност, инстинктивно убедена съм, че бройката може да се вдигне и над 616, но не съм готова с това.
(Някъде към 670 я виждам реалната граница...)

[dedis]

Много близо си да границата на валидност на хер Johann Peter Gustav Lejeune Dirichlet. Сметнато по "моя" начин, де, ако не греша.

[Bibi]

Мога да обясня как бих стигнала до 673.

Тези 365 остатъци, дето ги трупам в 77-те чекмеджета, са твърде много.
Така че не само е сигурно, че има поне един, който се повтаря 5 пъти, ами и още повече неща.
Може да се разделят на 2 случая:
а. има поне един, който се повтаря 6 пъти;
б. всички участват по най-много 5 пъти.

В случай а. на този остатък, който се повтаря 6 пъти, ще му се види тясно пространството до 673.
Така че както предния път ще се намери разлика точно равна на 77.
В случай б. чекмеджетата с по 5 суми във всяко са най-малко 57. (Това е 365 - 4*77)
Дори да са разположени по най-икономичния начин, "въздържайки се" от разлика 77, това отмества предишната ми граница 616 с още 57 нагоре:
1,...,155,...,309,...,463,...,617
...,2,...,156,...,310,...,464,...,618
... ... ...
...,57,...,211,...,365,...,519,...,673

С други думи 673 е най-малкото число, за което не мога да дам пример за решение.

[dedis]

Написах нещо, но се усъмних после...

ПП: Добре съм се усъмнил (вече ми се спеше). Сега разбирам, че съм бил подведен от прословутия и любим на Митето "когнитив байъс". Този път: Ако А, то Б съвсем не означава Ако не-А, то не-Б, както си въобразих с полузаспало съзнание.
Конкретно - след като споделя "моя" метод за решение на задачата.
 

[dedis]

Започвам, с ваше позволение, описание на моя начин.
За да провокирам раздвижване на сивите клетчици, ще го давам "на ден по лъжичка" с послеписи в този постинг.
И така:
1. Правим "редичката на Биби": S1,S2,S3...S365. "Si е равно на сумата приятели, добавени от началото на първия до края на i-тия ден" (Биби).
2. Правим втора редичка: S1+77,S2+77,S3+77...S365+77. Тя съдържа също 365 нарастващи числа, но всяко от тях е със 77 по-голямо от съответното от първата редичка.
... продължението следва...
3. Ако намерим във втората редичка числа, които присъстват и в първата, това означава, че съществуват периоди с нарастък 77. Има ли такива числа?
4. Предполагаме, че няма (Кръстева). Трябва да докажем противното.
... продължението следва...
5. Обединяваме двете редички. Всяка от тях - с 365 числа. Най-голямото в първата е 450, а във втората - 450+77=527. Така че, в "торбата" имаме 730 числа, като най-голямото от тях е 527.
6. Хер Дирихле опровергава предположението в т.4. Той казва: Не може да има 730 естествени числа, като най-голямото е 527, без някои от тях да се повтарят. С което задачата е решена.
.......................................
Например, ако S(i) + 77 = Sj, то в периода от (i+1)-ия ден до j-тия ден включително, приятелите са се увеличили точно със 77 души.
...........................................
Край
 

[Bibi]

Разбрах твоя начин. Хубав е той
По него обаче границата ми се получава 653. Някъде съм се объркала явно.

[dedis]

Това е едно от нещата, които ти харесвам - разбираш от половин дума, а и от по-малко  .
Точно това бях написал (№21) - 653 за граница, но после се усъмних. Има силна връзка между числата (77) и не може да се избират произволно. Надявам се, пак разбра от половин дума каква ми е мисълта.
Иначе, дължа ти поне една торта за компенсация на калориите изразходвани по тази задача, като се има предвид с каква жар се зае.
Явно задачата е или трудна или безинтересна (или и двете). Дали да пиша решението до край, щом Биби и, сигурен съм, Кръстева "загряха номера"?

[Bibi]

Еее, пиши разбира се. Не си пести от калориите - ще ти дам парчета от тортата
Даже както беше решил - на ден по лъжичка.

[dedis]

Добре, ще пиша решението в пост №22 като ПП1, ПП2 и т.н.
Сега за границата.
Докато си лафехме тук се опитах експериментално да подредя редица при променени така условия:
365 --> 5, 450 --> 7 и 77 --> 4. Би трябвало Дирихле "да го д--а". Да, ама не - не успях.
Та май съмненията ми са основателни.

[Bibi]

А по "моя" начин става така:
при 5 дена и 5 суми (5 > 4) ще има поне две суми с равни остатъци при деление на 4.
Разликата между тях ще се дели на 4, но не може да е 8, защото 8 > 7.
Значи разликата между тях е точно 4.

[dedis]

Така е. Но можеш ли да кажеш каква е границата при 5/граница/4, за да опитаме подредба при която няма разлика 4.

[Bibi]

При 9 няма решение.
Ако през дните е добавал приятели така:
1 1 1 5 1
сумите са
1 2 3 8 9
Само остатък 1 се повтаря, но през 8, а не през 4.

[dedis]

Бих казал "има решение", когато има подредба без парциална сума 4.
Значи 653 не е вярно число, както и 7 не е граница в новото условие, а може би чак 9.

[Krusteva]

Явно задачата е или трудна или безинтересна (или и двете).

Задачата е много готина, няколко дни не можах да спя и се чудех кога толкова съм излязла от форма 

[dedis]

Радвам се, че с Биби я смятате за интересна!
..................
За другите приятели, на които не им е скучна - решението - в №22, за да е на едно място.

[tonych]

въпросче?
ясно е, че при 730 души за 1 година по двама на ден няма как да има 77 записали се в последователни дни
за да намалим тази цифра(730) трябва поне в един ден да се сдобием с един нов приятел, а не с двама
и така първия ден имаме 1 приятел след това всеки ден по двама до като стигнем до 75 приятели и тогава трябва да запишем 4
ползата от единицата отива на вятъра
случаят със 76 единици и на следващия ден 78 нови приятели е аналогичен на 77 дни по двама приятели
та въпросът ми е 730 ли е най-малкото число при което нямаме 77 приятели в последователни дни или има начин да се даде пример с поне една единица без да се надвишава 730

[Wise]

Хм...искаж да кажеш /пост22/ , че ако бяха вместо 450 - 1450 решението е валидно??

[dedis]

Тонич и Уайз, опасявам се, че сте прочели отгоре-отгоре условието и затова са възникнали тези въпроси.
Хората са 450 за една година, не 730. Последното е 2х365 - числата в двете помощни редички.
За 1450 със сигурност не е валидно (макар, че го казвам интуитивно в момента). Защото 1450+77 е далеч над 730. И има голяма свобода да "настаняваш гълъбите".

[Bibi]

Мисля, че Тонича е наясно с задачата, но се опитва да реши колко е точната граница.
Само че го прави обратно на нас: не се опитва да я вдига, започвайки от 450, а да я сваля от 730 надолу.
И е избрал точно 730 понеже при него лесно е видял, че не винаги има 77.

[dedis]

Да, сега виждам, че е така. Задачата е с възможности за допълнителни интересни въпроси.
Най-интересно е къде е границата, над която има подредби без 77.
Засега е ясно, че е между 653 и 730
Май е по-лесно с индукция да се решава - отдолу нагоре.

[tonych]

точно така къде е границата

[dedis]

Не е ясно. То предположението за 730 с нарастване по 2 важи за нечетното 77. Така че, трябва да се търси връзка и с това число.

[Bibi]

Аз упорствам, че границата е между 673 и 730.

[Krusteva]

На мен ми липсва Митко да се включи...той със сигурност щеше да има какво да каже

[Wise]

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

И още нещо - при 673 има подредба, при която няма 77 за един период:
(76х1+78)+57 = 673

[Bibi]

За 673 - чудесно! Значи това е границата.
Но аз не го разбирам: кои са 365-те числа?
4 групи от 1,1,1,... 1, 78
и след тях 57 единички
така ли?

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

[Wise]

За 673 - чудесно! Значи това е границата.
Но аз не го разбирам: кои са 365-те числа?
4 групи от 1,1,1,... 1, 78
и след тях 57 единички
така ли?

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

ами 4 числа 78 и останалите 361 единици
111..1 (78) 111...11 (78) 111...11 (78) 11..11 (78) 111...1

[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.
Сега да се върнем нагоре към сумите, които дават тия остатъци. Какво можем да разберем за тях.
Да погледнем кои да е две суми, примерно S_b и S_c.
S_b = B.77 + R
S_c = C.77 + R
S_c - S_b = нещо.77
С други думи разликата на две такива суми винаги се дели на 77.

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

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

[dedis]

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

[Bibi]

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

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

Получихме, че последното от 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 ≤ S_x1 < S_x2 < ... < S_x57
От където ми излиза, че има група, която започва от число, равно най-малко на 57.
Вече останалите групи не ми трябват, ще използвам само тази - последната.

Тук разсъжденията се повтарят както в миналия случай.
Само дето вече имаме първи член не 1, а поне 57, но пък в групата има 5, а не 6 суми.
57 ≤ S_b
211 ≤ S_b + 154 ≤ S_c
365 ≤ S_c + 154 ≤ S_d
519 ≤ S_d + 154 ≤ S_e
673 ≤ S_e + 154 ≤ S_f

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

[dedis]

Логиката ми изглежда желязна!
Хайде една за изпускане на парата. И без това си на вълна Дирихле, Люк Бесон и Брус Уилис:
Можеш ли да разположиш пет точки в квадрат със страна 2см, така, че всеки две да са на по-голямо разстояние от 2^(1/2)?

[Bibi]

Разминахме се заради Майкъл Дъглас...

Разделяме квадрата на 4 малки, всеки със страна 1.
Малките квадрати са 4, а точките 5.
Значи има 2 точки в един и същи малък квадрат.
А там няма разстояния по-големи от корен от 2.

Хайде още?
Да се докаже, че има число, което се дели на 2011 и всичките му цифри са само 0 или 1.

[dedis]

Ей Биби, ти ще го сънуваш този майн хер Д.
Ще мислим по твоята задачка.

[Wise]

Хайде още?
Да се докаже, че има число, което се дели на 2011 и всичките му цифри са само 0 или 1.

Каките май залитат по простите неща......
Имало в една ферма един Ферма...та той написал, че:
http://bg.wikipedia.org/wiki/%D0%9C%D0%B0%D0%BB%D0%BA%D0%B0_%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%BD%D0%B0_%D0%A4%D0%B5%D1%80%D0%BC%D0%B0

демек - 10^(2011-1) - 1 ще се дели на 2011, защото е просто като мен...

или 10000...00000 - 1 = 9999....9999  = 9(1111....1111) и тъй, като 9 не е нашето число, то 11111....111 ще се дели на 2011

[Bibi]

Тогава я реши същата с 2012. Нали Дирихле-мирихле тука...

[Wise]

Тогава я реши същата с 2012. Нали Дирихле-мирихле тука...

2012 е четно и не се дели на 10 - няма как да има решение - и без Дерихле е ясно 

[Bibi]

На мен нищо не ми е ясно?
12 също е четно и не се дели на 10. Но за него има решение - например 11100.

[Wise]

Да, объркал съм се

Но ще продължа с Ферма. Според него има число само от 1-ци което се дели на произволно просто число.
Ако можем да представим някое число като множители на едно просто и независимо колко 2 и 5 - то ще има число,
съставено от единици и завършващо на достатъчен брой нули, което ще се дели и на нашето.

2012 = 503.4 - значи отговаря на условието.  /дано не бъркам пак де.../

[dedis]

Май му хвана цаката, Wise!
1111110 се дели и на 14 и на 35 и на 65. Прости числа умножени по 2 или 5.

[Wise]

Май му хвана цаката, Wise!
1111110 се дели и на 14 и на 35 и на 65. Прости числа умножени по 2 или 5.

Никак не е ясно - ако има няколко множитела, различни от 2,3,5 - нямам идея какво правим
а каките си мълчат - кроят нещо......

А има и достатъчно числа само от 0 и 1 , но размесени - демек - пробита единица - е там нямам идея

[dedis]

Аз те поздравих точно за частния случай.
А дали има решение за всички числа не е ясно. А и Биби не твърди това.

[Bibi]

За всички числа важи. Надявам се, че това ще ви помогне.

[Wise]

За всички числа важи. Надявам се, че това ще ви помогне.

Надявам се, че не става дума за двоичен запис........

[Bibi]

Не, десетични са.
И още една помощ - доказва се лесно. Особено на фона на основната задача.

Някой да иска побутване??

[tonych]

число с 502 единици и 2 нули след тях ще се дели на 2012
простите числа след 5 делят единици с една по-малко от  числената им стойност без остатък
например:
111111/7=15873
111111111111/13=8547008547 в случай на повторение е ясно, че трябват по-малко единици, а именно шест.
Цифрите + двете нули 111111/13=8547
1111111111111111/17=65359477124183 и т.н.
ако има и нули ще намерим доста по-малко число може би до 8-10 цифри

[MitkoS]

Хе-Хе, върнах се !
(С голяма засилка се бях запътил към наи-студеното място и за малко да изпусна Новата Година)

Ако ви е поомръзнало от математика, ей това по-долу става и за изтрезняване и за напиване.

jaanpehechanho
jeenaaasaanho
dilkochuranewalon
aankhnachuravo
naamthobatavo..
aajkiyehshaamjavan
yunnachalijaaye
aajkiyehshaamjavan
yunnachalijaaye
phirsenaaayegiyehkisikebulaaye
phirsenaaayegiyehkisikebulaaye..
*om/watch?v=aHA_S48KRrI
*om/watch?v=hVsf82IuVLI

[Bibi]

Heineken - след като е накрая, предполагам, че с него изтрезняваш след напиването с друго?

[dedis]

Jaan Pehchaan Ho Jeena Aasaan Ho - GUMNAAM (1965)
Това е добро за сутрешна гимнастика...

[MitkoS]

Шапка им свалям на индийците от Bollywood за това което са направили преди близо 50 години. Търсех музиката от рекламата на Heineken и когато попаднах на клипа от филма, дълго време не проумявах, че става дума за много стар индийски филм.
А текста от песента - с тоя индийски език прилича на някакво специално кодиране и ми се стори удачна закачка да ви пратя за зелен хайвер.

ПП. Става и за чалга-версия

http://www.youtube.com/watch?v=aHA_S48KRrI
	Small | Large

http://www.youtube.com/watch?v=hVsf82IuVLI

[Bibi]

Понеже не мога да търпя недовършени неща, смятам да разкажа за делението.
Взимам числата 1, 11, 111, 1111,...
Те са безкрайно много. И разликата на две от тях е число, което има само 0 и 1.
Някакво такова 11...1 00...0.
И започвам да им гледам остатъка при деление на нашето число.
Правя това докато получа или остатък 0, или някой, който вече го имам. А това Дирихле ми го гарантира.
Ако получа 0, значи самото число се дели.
Ако преди това намеря две с равни остатъци - вадя ги и разликата им се дели.

[Wise]

А как ще разбереш, че остатъците са равни? До "n" знака след нулата? Или до "m" знака?

[Bibi]

@Wise,
остатъците са цели числа (и по-малки от делителя). Точно затова са краен брой.
Няма проблеми да се види дали са равни.

[Wise]

Нещо пак ми се губи...
Примерно 1111111110000 : 2011 = 552516713,07807611636.........
Може ли още малко пояснение

[Bibi]

1111111110000 = 2011.552516713 + 157

това 157 се нарича остатък

[SetCombG.com Forum]