Не вниквам напълно в логиката, но с 99% сигурност (IMHO) това е верен подход!
Почти си открила граничните условия за съществуване на 77-членен контингент, което ми дава основание за това мнение.
Не че в условието се иска такова задълбочаване, де.
"Моят" подход е друг, все пак. Но е възможно ти да му намериш дефект.
- Списък от 365 числа, като i-тото от тях ai е равно на броя приятели, добавени през i-тия ден. ai > 1
- Втори списък пак от 365 числа, като i-тото от тях Si е равно на сумата приятели, добавени от началото на първия до края на i-тия ден.
По условие тези числа Si растат, т.е. всяко е по-голямо от предното, и последното S365 = 450.
1. Искам да докажа, че има сума от приятелите, събрани през няколко поредни дни, която се дели на 77.
Всяка такава сума може да се представи като разлика на две от числата {S}
SN - SM
това са приятелите, добавени между M-тия и N-тия ден.
За да се дели това число на 77, трябва SN и SM да имат еднакви остатъци при деление на 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), горната логика се запазва.
Чак сега видях написаното от Биби.
Контролен въпрос: Ако бройката е 620 или 650, какво ще кажеш, Биби?
Ако е повече от 616, онова, което предлагам, няма да даде сума 77.
Което не е доказателство, че такава сума липсва. Но ще трябва да се търси по друга схема.
Например 5-те начални суми с равни остатъци може да са
1,...,155,...,309,...,463,...,617
Тогава които и две да извадим, разбира се пак ще получим нещо, което се дели на 77, но няма да е самото 77.
Всъщност, инстинктивно убедена съм, че бройката може да се вдигне и над 616, но не съм готова с това.
(Някъде към 670 я виждам реалната граница...)
Много близо си да границата на валидност на хер Johann Peter Gustav Lejeune Dirichlet. Сметнато по "моя" начин, де, ако не греша.
Мога да обясня как бих стигнала до 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 е най-малкото число, за което не мога да дам пример за решение.
Написах нещо, но се усъмних после...
ПП: Добре съм се усъмнил (вече ми се спеше). Сега разбирам, че съм бил подведен от прословутия и любим на Митето "когнитив байъс". Този път: Ако А, то Б съвсем не означава Ако не-А, то не-Б, както си въобразих с полузаспало съзнание.
Конкретно - след като споделя "моя" метод за решение на задачата.
Започвам, с ваше позволение, описание на моя начин.
За да провокирам раздвижване на сивите клетчици, ще го давам "на ден по лъжичка" с послеписи в този постинг.
И така:
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 души.
...........................................
Край
Разбрах твоя начин. Хубав е той
По него обаче границата ми се получава 653. Някъде съм се объркала явно.
Това е едно от нещата, които ти харесвам - разбираш от половин дума, а и от по-малко.
Точно това бях написал (№21) - 653 за граница, но после се усъмних. Има силна връзка между числата (77) и не може да се избират произволно. Надявам се, пак разбра от половин дума каква ми е мисълта.
Иначе, дължа ти поне една торта за компенсация на калориите изразходвани по тази задача, като се има предвид с каква жар се зае.
Явно задачата е или трудна или безинтересна (или и двете). Дали да пиша решението до край, щом Биби и, сигурен съм, Кръстева "загряха номера"?
Еее, пиши разбира се. Не си пести от калориите - ще ти дам парчета от тортата
Даже както беше решил - на ден по лъжичка.
Добре, ще пиша решението в пост №22 като ПП1, ПП2 и т.н.
Сега за границата.
Докато си лафехме тук се опитах експериментално да подредя редица при променени така условия:
365 --> 5, 450 --> 7 и 77 --> 4. Би трябвало Дирихле "да го д--а". Да, ама не - не успях.
Та май съмненията ми са основателни.
А по "моя" начин става така:
при 5 дена и 5 суми (5 > 4) ще има поне две суми с равни остатъци при деление на 4.
Разликата между тях ще се дели на 4, но не може да е 8, защото 8 > 7.
Значи разликата между тях е точно 4.
Така е. Но можеш ли да кажеш каква е границата при 5/граница/4, за да опитаме подредба при която няма разлика 4.
При 9 няма решение.
Ако през дните е добавал приятели така:
1 1 1 5 1
сумите са
1 2 3 8 9
Само остатък 1 се повтаря, но през 8, а не през 4.
Новини
Форум
Актуално
сървър
Отговор с цитат