Задача 1
Evan Chen / USAMO Solution Notes
155 задачи от базата, подредени за бързо решаване по година или клас. Показаните източници са тези, записани към самите задачи.
Избран клас
11-12
Открити липси за попълване от източника
- 2026 · 11-12: липсва задача 2, 3
- 2025 · 11-12: липсва задача 4
- 2021 · 11-12: липсва задача 2, 3
- 2019 · 11-12: липсва задача 2
- 2017 · 11-12: липсва задача 3, 4, 5
- 2016 · 11-12: липсва задача 3
- 2015 · 11-12: липсва задача 2
- 2014 · 11-12: липсва задача 4, 5
- 2013 · 11-12: липсва задача 3
- 2012 · 11-12: липсва задача 5
- 2011 · 11-12: липсва задача 3, 5
- 2010 · 11-12: липсва задача 4
- 2009 · 11-12: липсва задача 5
- 1999 · 11-12: липсва задача 3
- 1998 · 11-12: липсва задача 2
1996
6 задачиЗадача 2
Условие
Нека е множество от положителни цели числа. Да се докаже, че сборовете на непразните подмножества на могат да бъдат разбити на класа така, че във всеки клас отношението между най-големия и най-малкия сбор да е най-много .Решение
Ще докажем твърдението с индукция по . Нека елементите на са подредени намаляващо:а . Съществува индекс , за койтоНаистина, ако за всяко имахме , тогавакоето е невъзможно. Разглеждаме всички сборове на подмножества, които съдържат поне един от елементите . Всеки такъв сбор е по-голям от , следователно е по-голям от , а разбира се не надминава . Затова тези сборове могат да се поставят в класа:Във всеки от тези интервали отношението между най-големия и най-малкия възможен сбор е най-много . Останалите сборове използват само елементите . По индукционното предположение те могат да бъдат разбити на класа със същото свойство. Общо получаваме класа, което доказва задачата.Задача 3
Условие
Нека е триъгълник. Докажете, че в равнината на триъгълника съществува права , такава че сечението на вътрешността на триъгълника и вътрешността на образа му при отражение спрямо има лице, по-голямо от от лицето на триъгълника .Решение
Първо ще докажем следното по-точно твърдение. Ако за триъгълник имамето ъглополовящата на върши работа. Нека тя пресича в . При отражение спрямо тази ъглополовяща общата част на двата триъгълника има лице . По теоремата за ъглополовящатаСледователнопонеже . В произволен триъгълник нека страните са . От неравенството на триъгълника имаме , откъдетоИзбираме върха, при който прилежащите страни имат дължини и , и прилагаме доказаното твърдение за неговата ъглополовяща.Задача 4
Условие
Нека е броят на двоичните редици с дължина , които не съдържат блока , а е броят на двоичните редици с дължина , които не съдържат нито , нито . Да се докаже, че .Решение
Ще построим точно двукратно съответствие. Нека е двоична редица, която не съдържа и . От нея образуваме редица чрезС други думи , когато съседните членове са равни, и , когато са различни. Ако в редицата се появи блок , тогава имаме , и . Значи съответните четири члена на са или , или , което е забранено. Следователно всяка допустима редица дава допустима редица . Обратно, нека е дадена двоична редица , която не съдържа . Ако изберем началната стойност , останалите се определят еднозначно от равенствата . Има точно два избора за , а именно и . Получената редица не може да съдържа или , защото тогава съответните три последователни стойности на биха били . Така всяка допустима редица има точно две прообразни редици . Следователно броят на допустимите с дължина е два пъти броя на допустимите с дължина , тоест .Задача 5
Условие
Нека е триъгълник, а е вътрешна точка, за която , , и . Докажете, че триъгълникът е равнобедрен.Решение
НекаПонеже е вътрешна точка, имаме . Прилагаме тригонометричната форма на теоремата на Чева за правите , и в триъгълника :Това е еквивалентно наЛявата страна на (1) е строго растяща за , а дясната е строго намаляваща. Следователно (1) има най-много едно решение. Ще проверим, че е решение. Наистина,Значи . Тогаваа оттук . Следователно , така че и триъгълникът е равнобедрен.Задача 6
Условие
Съществува ли множество от цели числа със следното свойство: всяко цяло число може да се представи по единствен начин във вида където ?Решение
Отговорът е да. Ще използваме представяне в отрицателна основа. НекаТоест се състои от всички крайни суми на различни степени на . Ще използваме факта, че всяко цяло число има единствено представяне в основа с цифри . Това се доказва по същия начин както при обикновените основи: при деление на остатъкът се избира еднозначно сред , а повтарянето на процеса завършва, защото абсолютната стойност на частното намалява за достатъчно големи числа; единствеността следва от същото деление с остатък. Некае това единствено представяне. Всяка цифра се записва по единствен начин катоТогаваПървата сума е елемент , а втората е елемент , така че . Единствеността също следва веднага. Ако за , то коефициентите на и пред всяка степен на са съответно и от множеството . Значи цифрата на в основа е , а представянето в основа е единствено. Следователно и двойката е единствена.1997
6 задачиЗадача 1
Условие
Нека са простите числа в нарастващ ред и нека е реално число с . За всяко положително цяло число дефинираме така: ако , то ; иначе е дробната част на . Намерете всички начални стойности , за които от някой член нататък всички са равни на .Решение
Отговорът е: точно рационалните числа в интервала . Първо нека е ирационално. Ще докажем с индукция, че докато членовете са ненулеви, всички те остават ирационални. Ако е ирационално, то също е ирационално. Ако дробната му част беше рационална, тогава щеше да е сума от цяло и рационално число, тоест рационално, което е невъзможно. Следователно е ирационално и в частност не може да бъде . Значи ирационално начално число никога не води до нулев член. Остава да видим, че всяко рационално работи. Нека е ненулев член, записан в несъкратим вид, където . Тогава . Дробната част на това число е или , или рационално число със знаменател най-много след съкращаване. Понеже , при всеки ненулев преход знаменателят строго намалява. Не може да има безкрайна строго намаляваща редица от положителни цели знаменатели, затова след краен брой стъпки се получава дробна част . Оттам нататък по дефиниция всички следващи членове са .Задача 2
Условие
Нека е триъгълник. Точките лежат съответно върху симетралите на отсечките и не са колинеарни. Докажете, че правите през , перпендикулярни съответно на , са конкурентни.Решение
Разглеждаме три окръжности с центрове . Понеже лежи на симетралата на , имаме ; следователно има окръжност с център , която минава през и . По същия начин има окръжност с център , която минава през и , и окръжност с център , която минава през и . Радикалната ос на окръжностите с центрове и минава през , защото лежи и на двете окръжности. Тази радикална ос е перпендикулярна на правата на центровете , така че тя е точно правата през , перпендикулярна на . Аналогично радикалната ос на окръжностите с центрове и е правата през , перпендикулярна на , а радикалната ос на окръжностите с центрове и е правата през , перпендикулярна на . Трите центъра не са колинеарни, затова трите окръжности имат радикален център. По теоремата за радикалния център трите им радикални оси са конкурентни. Но това са точно трите прави от условието, което доказва твърдението.Задача 3
Условие
Докажете, че за всяко цяло число съществува единствен многочлен с коефициенти от множеството , за който .Решение
Ще опишем цифрите на от свободния член нагоре. По-общо, за двойка цели числа ще търсим многочлен с цифри от до , за който и . Ако , където е свободният член, тогава Следователно трябва да удовлетворява По китайската теорема за остатъците има точно една цифра с тези две свойства. След като тази цифра е избрана, следващата двойка е принудително Обратно, ако за двойката вече имаме подходящ многочлен , то е подходящ многочлен за . Така едновременно доказваме и построяването, и единствеността, стига да покажем, че започвайки от този процес стига до . Забележете първо, че условието се запазва от прехода . Наистина, ако , то също се дели на , понеже числителят се дели и на , и на . Началната двойка очевидно има това свойство. Нека . Понеже , ако , то следващата двойка има координати по абсолютна стойност най-много и , тоест новият максимум е строго по-малък от . Следователно след краен брой стъпки стигаме до . След още най-много две стъпки втората координата има абсолютна стойност най-много , а първата остава с абсолютна стойност най-много . Остава само малка крайна проверка за двойките с , и . Пряко от правилото за цифрата всяка такава двойка или е , или след една стъпка попада в множеството . А тези двойки завършват веднага по веригите и Значи процесът винаги спира в . При обръщане на стъпките получаваме търсения многочлен, а понеже всяка цифра беше принудително определена, този многочлен е единствен.Задача 4
Условие
Нека отрязване на изпъкнал -ъгълник означава следната операция: избираме две съседни страни и и ги заменяме с трите отсечки , и , където е средата на , а е средата на . С други думи, отрязваме триъгълника и получаваме изпъкнал -ъгълник. Правилен шестоъгълник с лице се отрязва и се получава седмоъгълник . После се отрязва по един от седемте възможни начини, за да се получи осмоъгълник , и т.н. Докажете, че независимо от избора на отрязванията лицето на е по-голямо от за всяко .Решение
Нека първоначалният правилен шестоъгълник е в този ред и некаТова е централният правилен шестоъгълник в звездата, образувана от двата равностранни триъгълника и . Неговото лице е точно една трета от лицето на първоначалния шестоъгълник, тоест . Ще докажем, че всяко отрязване оставя цялата област вътре в многоъгълника. За целта на всяка страна на текущия многоъгълник приписваме основа, която е множество от страни на първоначалния шестоъгълник. В началото страните имат за основа самите себе си. Когато отрязваме две съседни страни и се появи новата страна , за основа на вземаме обединението на основите на двете страни, които са били отрязани. Ще използваме малко по-силен инвариант: за всеки две съседни страни на текущия многоъгълник обединението на основите им съдържа най-много две съседни първоначални страни. В началото това е очевидно. При едно отрязване двете части от старите страни запазват старите си основи, а новата страна получава обединението на основите на двете отрязани съседни страни. Затова новите съседни двойки около отрязването имат същото обединение на основи като старата отрязана двойка, а всички останали съседни двойки не се променят. Инвариантът се запазва, и в частност основата на всяка отделна страна съдържа най-много две съседни първоначални страни. Сега разгледайте страна, чиято основа е например подмножество на . Тогава тази страна лежи в триъгълника : началните страни очевидно имат това свойство, а при отрязване новата отсечка свързва точки от две такива страни и остава вътре в същия триъгълник по изпъкналост. Следователно отрязаният триъгълник при върха е изцяло от страната на правата , която не съдържа , и дори не пресича отсечката . Аналогично всяко възможно отрязване е затворено в един от шестте ъглови триъгълникаи не достига съответната страна на триъгълника или , която отделя този ъгъл от областта . Значи никога не отрязваме точка от . След краен брой отрязвания многоъгълникът съдържа и освен това има ненулева част извън около всяка своя страна, така че лицето му е строго по-голямо от . Това доказва твърдението.Задача 5
Условие
Нека са положителни реални числа. Докажете, чеРешение
Ще оценим всеки от трите знаменателя отдолу. За положителни и имаме следователно Значи Същото разсъждение, приложено циклично, дава и Като съберем тези три неравенства, получаваме Но така че дясната страна е точно . Това доказва исканото неравенство.Задача 6
Условие
Нека редицата от неотрицателни цели числа удовлетворява за всички с . Докажете, че съществува реално число , такова че за всяко .Решение
Ще докажем малко по-общо твърдение, като заменим с произволно положително цяло число . За всяко условието е еквивалентно на Следователно е достатъчно да покажем, че Ще докажем по индукция по следното по-силно твърдение. Нека е най-малкият индекс, при който се достига максимумът на дробите , а е най-малкият индекс, при който се достига минимумът на дробите . Тогава и тези две несъкратими дроби са съседни в редицата на Фарей от ред , тоест между тях няма друга рационална дроб със знаменател най-много . Базата е ясна. Нека твърдението е доказано за и добавим члена . За старите крайни дроби пишем По индукционната хипотеза те са съседни в редицата на Фарей от ред , следователно . Първо нека . Между две съседни Фарейови дроби с тези знаменатели няма дроб със знаменател във вътрешността на интервала . Затова съществува цяло число , за което От левия край и от това, че е най-малкият стар десен край, получаваме откъдето, понеже числата са цели, . Аналогично, от това, че е най-големият стар ляв край, и от десния край получаваме откъдето , тоест . Сега условието на задачата дава и Значи всъщност . Следователно новият ляв край не надминава , а новият десен край не е по-малък от . Двойката не се променя, а понеже , същите две дроби остават съседни и в редицата на Фарей от ред . Остава случаят . Тогава медиантата лежи строго между и . Освен това условието за дава Ако , новият десен край е така че двойката крайни дроби става . Ако , новият ляв край е така че двойката става . Стандартното свойство на редиците на Фарей казва, че медиантата на две съседни дроби е несъкратима и е съседна на всяка от тях в новия ред. Следователно индукционното твърдение се запазва. Така за имаме . Избираме например . За всяко е изпълнено което е еквивалентно на . Следователно за всички .1998
2 задачиЗадача 1
Условие
Числата са разбити на двойки. Във всяка двойка разликата между двете числа е или , или . Да се докаже, че сборът на разликите във всички двойки завършва на цифрата .Решение
Нека е броят на двойките, в които разликата е , а е броят на двойките, в които разликата е . Тогава . Търсеният сбор е Следователно е достатъчно да докажем, че е нечетно число, защото тогава и получаваме . Остава само да видим защо е нечетно. В двойка с разлика едното число е четно, а другото е нечетно. В двойка с разлика двете числа имат една и съща четност. Сред числата има точно нечетни и четни числа. След като премахнем -те двойки с разлика , са останали четни и нечетни числа, които трябва да се разбият на двойки от числа с една и съща четност. Това е възможно само ако е четно. Следователно е нечетно. Както вече видяхме, това дава , тоест сборът завършва на цифрата .Задача 3
Условие
Нека са числа от интервала , за които Докажете, че .Решение
Полагаме Тогава и Нека още Тогава , а условието става защото . Освен това Остава да докажем, че ако и , то Понеже , имаме за всяко , така че е достатъчно да оценим За фиксирано по AM-GM получаваме Умножаваме тези неравенства за всички . Под корените всеки множител се появява точно пъти в числителя и точно пъти в знаменателя, следователно всички те се съкращават. Получаваме Оттук следва и което доказва задачата.1999
5 задачиЗадача 1
Условие
В някои от квадратчетата на дъска са поставени пулове. Всяко празно квадратче има обща страна с поне едно квадратче, в което има пул, а квадратчетата с пулове образуват свързана фигура чрез общи страни. Да се докаже, че броят на пуловете е поне .Решение
Нека броят на пуловете е . Ще броим съседствата по обща страна между квадратче с пул и празно квадратче. От условието всяко от празните квадратчета има поне едно такова съседство, следователно броят на тези съседства е поне . От друга страна, всяко квадратче с пул има най-много четири страни, така че всички страни, излизащи от квадратчета с пулове, са най-много . Тъй като квадратчетата с пулове са свързани чрез общи страни, графът, чиито върхове са тези квадратчета и чиито ребра свързват две съседни квадратчета с пулове, е свързан. Затова той има поне ребра. Всяко такова вътрешно ребро използва две страни, които не водят към празно квадратче. Следователно броят на съседствата между пул и празно квадратче е най-много Събирайки двете оценки, получаваме Оттук следва тоест . Това е точно исканото твърдение.Задача 2
Условие
Нека е изпъкнал вписан четириъгълник. Докажете, чеРешение
Нека диагоналите и се пресичат в . Понеже е вписан, от теоремата за пресичащите се хорди имамеИзбираме положителни числа така, чеТова е възможно точно заради горното равенство. Триъгълниците и са подобни: имат равни вертикални ъгли при , а също , защото са вписани ъгли, стъпващи на една и съща дъга. Следователнотака че за някакво можем да запишемПо същия начин от подобието на триъгълниците и получаваме, че за някакво Сегаа същоВ триъгълника страните, разделени на , са , затова от триъгълното неравенство . СледователноАналогично, в триъгълника страните, разделени на , са , така че иКато съберем последните две неравенства, получаваме точноЗадача 4
Условие
Нека и нека са реални числа, за които и Да се докаже, че поне едно от числата е не по-малко от .Решение
Да допуснем противното: за всяко . Поставяме , така че всички са положителни. Нека От условието за сумата на получаваме следователно . Сега пресмятаме сумата от квадратите чрез . Имаме затова Понеже всички са положителни и има поне две от тях, получаваме Следователно Остава да оценим последния израз. Понеже и , имаме Това е равносилно на Така получаваме което противоречи на условието. Следователно допускането е невъзможно и някое е поне .Задача 5
Условие
Играта Y2K се играе върху таблица по следния начин. Двама играчи последователно записват буквата или в празно квадратче. Печели първият играч, който получи три последователни квадратчета, образуващи думата . Ако всички квадратчета се запълнят без да се появи , играта завършва наравно. Докажете, че вторият играч има печеливша стратегия.Решение
Ще наричаме конфигурация от вида капан. Ако някой играч запише буква в едно от двете празни квадратчета на капана, другият веднага може да запълни другото празно квадратче така, че да получи . Първо вторият играч може да си осигури такъв капан. На първия си ход тя поставя достатъчно далеч от краищата и от първия ход на противника. На втория си ход избира една от двете посоки и поставя още едно на разстояние квадратчета; поне едната посока остава свободна, защото първият играч е направил само един междинен ход. Така се получава капан. Следователно играта не може да завърши наравно, ако вторият играч успява винаги да не загуби преди това. Остава да покажем, че вторият играч винаги има безопасен ход. В началото на всеки неин ход броят на празните квадратчета е нечетен. Разглеждаме максималните блокове от празни квадратчета, като двата края на дъската мислим като запълнени. Не може всички блокове да имат дължина , защото тогава общият брой празни квадратчета би бил четен. Следователно има празно квадратче, чиито две съседни места са едновременно празни или едновременно запълнени. Вторият играч записва в такова квадратче. Този ход не дава на противника непосредствен чрез новозаписаната буква; ако самият ход вече образува , вторият играч е спечелил. Значи вторият играч може на всеки свой ход да избягва загуба. Понеже вече е създал капан, равенство е невъзможно: рано или късно първият играч е принуден да влезе в капана, а вторият печели на следващия ход.Задача 6
Условие
Нека е равнобедрен трапец с . Вписаната окръжност на триъгълника се допира до в . Нека е точка върху вътрешната ъглополовяща на , такава че . Окръжността, описана около триъгълника , пресича правата в и . Докажете, че триъгълникът е равнобедрен.Решение
Ще докажем първо, че е допирната точка на -външновписаната окръжност на триъгълника със страната . Понеже трапецът е равнобедрен, имаме и . Ако вписаната окръжност на триъгълника се допира до в , тоОт друга страна, ако -външновписаната окръжност на триъгълника се допира до правата в , тогава от равенството на допирателните от към тази външновписана окръжност получавамеДвете стойности са равни, понеже и , следователно . Точката лежи върху вътрешната ъглополовяща на и правата е перпендикулярна на в допирната точка на -външновписаната окръжност. Затова е центърът на тази -външновписана окръжност на триъгълника . Следователно е външна ъглополовяща при върха на триъгълника . Понеже лежи на правата , същото твърдение в насочени ъгли казва, че е външна ъглополовяща на . Сега лежат на една окръжност. Равенството на ъглитесе превежда върху тази окръжност като равенство на дъгите и , откъдето хордите им са равни:Значи триъгълникът е равнобедрен.2000
6 задачиЗадача 1
Условие
Наричаме реалнозначна функция силно изпъкнала, акоза всички реални числа и . Да се докаже, че силно изпъкнала функция не съществува.Решение
По-общо, за ще казваме, че е -изпъкнала, акоза всички реални . Ще покажем, че ако , от -изпъкналост следва -изпъкналост; повторение на това ще даде невъзможност. Нека са пет последователни члена на аритметична прогресия и нека . От -изпъкналостта за двойките , и получавамеСъбирайки първите две неравенства и два пъти третото, след съкращаване получавамеТова е точно условието за -изпъкналост за двойката . Следователно от -изпъкналост следва -изпъкналост, оттам -изпъкналост и т.н. При силно изпъкнала функция имаме . Фиксираме различни и ; тогава горното повторение би принудило да е поне за всяко , което е невъзможно, защото лявата страна е фиксирано реално число. Противоречието доказва твърдението.Задача 2
Условие
Нека е множеството от всички триъгълници , за коитокъдето е радиусът на вписаната окръжност, а са точките, в които тя се допира съответно до страните . Да се докаже, че всички триъгълници от са равнобедрени и подобни помежду си.Решение
Полагаме , , . Тогава страните на триъгълника са , , , полупериметърът е , а от Хероновата формула получавамеДостатъчно е да докажем неравенствотокато равенство има точно при . Наистина, ако например е най-малкото от , лявата страна в условието на задачата е точно ; останалите случаи са същите след преименуване. След повдигане на квадрат и замяна , , неравенството се свежда доТова следва от две приложения на AM-GM:Равенство и в двете има точно когато и , т.е. . В първоначалните променливи това означава . Следователно в условието на задачата равенство е възможно само когато най-малкият от трите допирателни отрязъка е в отношение с другите два. Значи два от тях са равни, така че триъгълникът е равнобедрен, а отношението на допирателните отрязъци е фиксирано. Затова всички такива триъгълници са подобни.Задача 3
Условие
Пасианс се играе с червени, бели и сини карти. Играчът изиграва всички карти една по една и при всяко изиграване получава наказание. Ако изиграе синя карта, наказанието е броят на белите карти, които още държи. Ако изиграе бяла карта, наказанието е два пъти броят на червените карти, които още държи. Ако изиграе червена карта, наказанието е три пъти броят на сините карти, които още държи. Да се намерят, като функция на , най-малкото възможно общо наказание и броят на редовете на игра, с които този минимум се постига.Решение
Минималното общо наказание еЕстествено е да се досетим, че е оптимално първо да се изхвърлят всички карти от един цвят; горната формула казва точно коя от трите възможности е най-добра. Доказателството е пряка индукция по . Нека . След първия ход получаваме рекурсиятаПроверка на трите случая показва, че дясната страна наистина е ; началният случай, когато един от броевете е , е очевиден. Остава да преброим оптималните редове. Ако едно от числата е строго по-малко от другите две, оптималният ред е единствен. Акоима оптимални реда: може първо да се изиграят от до бели карти, след което да се изиграят всички сини карти. Акоима оптимални реда: може първо да се изиграят от до червени карти, след което да се изиграят всички бели карти. Акоима оптимални реда: може първо да се изиграят от до сини карти, след което да се изиграят всички червени карти. Накрая, акопървата карта ни поставя в един от трите предишни случая, така че общият брой оптимални редове е .Задача 4
Условие
Да се намери най-малкото положително цяло число със следното свойство: ако квадрата от шахматна дъска са оцветени, то съществуват три оцветени квадрата, чиито центрове образуват правоъгълен триъгълник със страни, успоредни на страните на дъската.Решение
Отговорът е . Първо ще дадем строеж с оцветени квадрата без такава тройка. Оцветяваме всички квадрати в първата колона и всички квадрати в последния ред, но не оцветяваме общия им ъглов квадрат. Получава се пробито Г-образно множество с квадрата; в него няма оцветен квадрат, който едновременно да има друг оцветен квадрат в своя ред и друг оцветен квадрат в своята колона. Сега доказваме, че повече не може. Нека в някакво оцветяване няма търсения правоъгълен триъгълник. Тогава за всеки оцветен квадрат е вярно поне едно от двете: той е единственият оцветен квадрат в своя ред или е единственият оцветен квадрат в своята колона. Нека е множеството от редовете с точно един оцветен квадрат, а е множеството от колоните с точно един оцветен квадрат. Всеки оцветен квадрат се брои от някой ред в или от някоя колона в , затова броят на оцветените квадрати е най-многоАко има повече от оцветени квадрата, не всички редове са единични и не всички колони са единични. Следователно и , откъдето броят на оцветените квадрати е най-много . Така при оцветени квадрата търсената тройка задължително съществува.Задача 5
Условие
Нека е триъгълник и нека е окръжност в неговата равнина, минаваща през и . Да предположим, че съществуват окръжности такива, че за окръжността се допира външно до и минава през и , където индексите се вземат по модул . Да се докаже, че .Решение
Ще следим ъгъла, под който съответната окръжност се вижда от върха на страната. НекаНека е центърът на и полагамеПонеже последователните окръжности се допират външно, центровете им и точката на допиране лежат на една права. Оттук, с насочени ъгли, последователно получавамеАко положим , същото пресмятане още веднъж даваОкръжност през и е определена от положението на центъра си върху перпендикулярния симетрал на , а този насочен ъгъл връща центъра в същата позиция. Следователно и значи .Задача 6
Условие
Нека са неотрицателни реални числа. Да се докаже, чеРешение
По непрекъснатост можем да допуснем за всички и да запишем . Тогава трябва да докажемНека , ако , и иначе, а . Ключовото преобразуване еТо превръща двойния минимум в един отделен минимум. След стандартно опростяване получаваме, че е достатъчно да се докаже следното твърдение: за произволни реални и неотрицателни имамеЗа доказателство на твърдението подреждаме . Тогавакъдето . Това доказва желаното неравенство. Еквивалентно, може да се използва и интегралната идентичностслед което сумата става интеграл от квадрат. И в двата варианта получаваме неотрицателност и задачата е решена.2001
6 задачиЗадача 1
Условие
Във всяка от осем кутии има по шест топки. Всяка топка е оцветена в един от цвята така, че в една и съща кутия няма две топки с еднакъв цвят и никои два цвята не се срещат заедно в повече от една кутия. Да се намери с доказателство най-малката възможна стойност на .Решение
Отговорът е . Диаграмата дава строеж с цветовете : всяка колона е една кутия. Лесно се проверява, че във всяка колона цветовете са различни и че всяка двойка цветове се среща заедно в най-много една колона. Остава да докажем, че по-малко от цвята не стигат. Разглеждаме таблицата от кутии по топки. За всяка топка нека е броят на топките със същия цвят като . Тогавазащото всеки цвят, използван пъти, допринася общо . Фиксираме една кутия . За всяка топка в нея броят е броят на други кутии, в които се появява нейният цвят. Понеже всяка друга кутия може да сподели с най-много един цвят, получавамеследователно . При шест положителни цели числа със сума най-много сумата на реципрочните им стойности е най-малка при разпределение , откъдетоСумирайки по осемте кутии, получавамеЗатова , а строежът показва, че е постижимо.Задача 2
Условие
Нека е триъгълник и нека е неговата вписана окръжност. Нека и са точките, в които се допира съответно до страните и . Нека и са точки съответно върху страните и , за които и , а е пресечната точка на отсечките и . Окръжността пресича отсечката в две точки; по-близката до върха от тях е . Да се докаже, че .Решение
Точката е точката на Нагел на триъгълника, т.е. в барицентрични координатикъдето , , , а е полупериметърът. Оттук върху чевианата получавамеОт друга страна, е антиподната на точка върху вписаната окръжност. Хомотетията с център , която праща в , праща вписаната окръжност в -външновписаната окръжност. Нейният коефициент екоето се вижда от равните допирателни отсечки от . Следователнои значи .Задача 3
Условие
Нека са неотрицателни реални числа, за коитоДа се докаже, чеРешение
Лявото неравенство е лесно. Нека например . ТогаваАко , това е очевидно неотрицателно. Ако , понеже , получавамеЗа горната оценка ще използваме метода на множителите на Лагранж. Понеже , множеството на допустимите тройки е компактно и максимум съществува. Понеже от условието , неравенството е равносилно наНа границата, например при , имаме иНека сега и нека имаме вътрешен максимум. За уравненията на Лагранж даватИзваждайки по двойки, получавамеи аналогичните равенства. Ако , условието дава и . Ако са две по две различни, трите равенства принуждават , противоречие. Остава случаят, например . Тогава от условиетотоести понеже , имаме . Затовазащото . Така горната оценка е доказана.Задача 4
Условие
Нека е триъгълник и е точка такава, че , , са страните на тъпоъгълен триъгълник, като е най-дългата страна. Да се докаже, че е остър.Решение
Прилагаме неравенството на Птолемей към четириъгълника , а след това неравенството на Коши-Шварц:Понеже , , са страните на тъпоъгълен триъгълник и е най-дългата страна, имамеСледователноа значиПо обратната посока на косинусовата теорема това точно означава, че е остър.Задача 5
Условие
Нека е такова, че: (a) съществуват с ; (b) ако и са елементи на (възможно е ), то също принадлежи на . Да се докаже, че .Решение
Ще наричаме положително цяло число период на , ако . Първо забелязваме, че ако , то за всяко имамеСледователно всяка разлика е период в съответната посока. От условието лесно следва, че съществува ненулев период. Ще докажем, че е период. Да допуснем противното. Тогава положителните периоди са точно кратните на някое . Твърдим, че всички елементи на имат квадрат, конгруентен на една и съща стойност по модул . Наистина, ако и , то би бил период, който не е кратен на , противоречие. Вземаме от условие (a). Понеже и и принадлежат на , получавамеНека е прост делител на . Отследватака че или . Аналогично или . Но от следва, че или , или (и за това също е вярно). В първия случай дели , а във втория дели - противоречие. Следователно е период на . Понеже е непразно, това дава .Задача 6
Условие
На всяка точка в равнината е съпоставено реално число. Да предположим, че за всеки недегенериран триъгълник числото в неговия инцентър е средното аритметично на числата в трите му върха. Да се докаже, че на всички точки в равнината е съпоставено едно и също число.Решение
Ще означаваме точките с главни букви, а съответните им числа със съответните малки букви. Първо твърдим, че ако е равнобедрен трапец, тоДействително, без ограничение нека лъчите и се пресичат в точка . Тогава триъгълниците и имат една и съща вписана окръжност, следователно един и същ инцентър . От условието получавамекоето дава . Сега вземаме произволни две точки и и построяваме правилен петоъгълник . От приложението на твърдението към петте равнобедрени трапеца в него получавамеОт тези равенства следва . Значи всякакви две произволни точки и имат еднакви числа, откъдето всички числа в равнината са еднакви.2002
6 задачиЗадача 1
Условие
Нека е множество с елемента и нека е цяло число с . Да се докаже, че е възможно всяко подмножество на да се оцвети в черно или бяло така, че: (a) обединението на всеки две бели подмножества е бяло; (b) обединението на всеки две черни подмножества е черно; (c) има точно бели подмножества.Решение
Ще докажем малко по-общото твърдение: ако и , то подмножествата на могат да се оцветят по желания начин с точно бели множества. Доказателството е с индукция по . При има само едно подмножество и случаите са очевидни. Нека твърдението е доказано за . Ако , оцветяваме подмножествата на с точно бели множества според индукционното предположение, а всички подмножества, които съдържат , оцветяваме в черно. Тогава обединение на две бели множества пак не съдържа и остава бяло, а обединение, в което участва черно множество със , автоматично е черно. Останалите случаи следват от индукционното оцветяване. Ако , оцветяваме подмножествата на така, че белите да са , а всички подмножества, които съдържат , правим бели. Същата проверка показва, че условията за обединение са запазени. Така индукцията завършва доказателството.Задача 2
Условие
Нека е триъгълник, за койтокъдето е полупериметърът, а е радиусът на вписаната окръжност. Да се докаже, че е подобен на триъгълник , чиито страни са положителни цели числа без общ делител, и да се намерят тези числа.Решение
Нека страните срещу са съответно и положим по обичайния начинПонеже и аналогично за другите два ъгъла, даденото равенство ставаОт неравенството на Коши-Шварц имамеНо , а даденото равенство прави това неравенство равенство. Следователно е изпълнено условието за равенство в Коши-Шварц:ЗатоваСтраните на триъгълника саТези три числа са взаимно прости като тройка, така че търсеният триъгълник има страни .Задача 3
Условие
Да се докаже, че всеки моничен многочлен от степен с реални коефициенти може да се представи като средно аритметично на два монични многочлена от степен , всеки от които има реални корена.Решение
Първо ще използваме следната лема. Ако е моничен многочлен от степен ито има реални корена. Наистина, теоремата за междинните стойности дава по един корен във всеки интервал . Последният корен се намира извън този отрязък: ако е четно, при , а и са с противоположни знаци; ако е нечетно, крайните граници при и са с противоположни знаци, докато и са с един и същи знак. Нека сега е даденият моничен многочлен. Избираме число толкова голямо, че . За всяко избираме реални числа , за коитоТова е възможно, като първо изберем с достатъчно голяма абсолютна стойност и нужния знак, а после положим . Съществуват единствени монични многочлени и от степен със стойности и за . По избора на знаците и лемата и двата многочлена имат реални корена. Освен това многочленът и са монични от степен и съвпадат в точките . Разликата им има степен най-много и има корена, следователно е нулевият многочлен. Значи , както се искаше.Задача 4
Условие
Да се намерят всички функции , за коитоза всички реални числа и .Решение
Отговорът еи тези функции очевидно удовлетворяват условието. Поставяйки съответно и , получавамеОттук е нечетна функция и в частност . Първоначалното равенство може да се запише катоПонеже всяко неотрицателно число е квадрат и е нечетна, следва, че е адитивна: за всички реални . Сега използваме едновременно адитивността и равенството . ИмамеЛявата страна еа дясната страна еСлед съкращаване получаваме за всяко реално . Това дава точно посочените линейни решения.Задача 5
Условие
Нека са цели числа, по-големи от . Да се докаже, че съществуват положително цяло число и крайна редица от положителни цели числа такива, че , и дели за всяко .Решение
Разглеждаме граф с върхове , като два върха са свързани с ребро точно когато дели . Задачата е еквивалентна на това да докажем, че този граф е свързан. Първо, всяко е свързано последователно сНапример е свързано с , защото сумата им е , а произведението им е кратно на ; същата проверка работи на всяка следваща стъпка, тъй като вече натрупаното произведение съдържа нужния нов делител. Остава да видим, че факториелите са в една компонента. За числото е свързано с така: ако е четно, тогава , а дели , така че има ребро ; ако е нечетно, използваме пътяПървото ребро е валидно, понеже дели , а второто следва от и факта, че дели . Следователно всеки връх е свързан с някой факториел, а факториелите са свързани помежду си. Графът е свързан и исканата редица съществува.Задача 6
Условие
Имам лист с марки с размер , от който трябва да откъсвам блокове от три съседни марки в един ред или в една колона. Мога да късам само по перфорациите между съседни марки и всеки блок трябва да излезе от листа цял. Нека е най-малкият брой блокове, които мога да откъсна така, че след това да е невъзможно да се откъсне още един блок. Да се докаже, че съществуват реални константи и , за коитоза всички .Решение
За долната оценка броим всички възможни места, на които би могъл да стои един блок. Те са : по хоризонтални и вертикални. След като вече не може да се откъсне нов блок, всяко такова място трябва да пресича поне един откъснат блок. Един фиксиран откъснат блок пресича най-много възможни блока със същата ориентация и най-много възможни блока с другата ориентация, общо най-много . СледователнотоестТова дава лявото неравенство. За горната оценка използваме периодичен строеж с период . Номерираме редовете и колоните и във всяка колона късаме вертикални блокове от три марки с начални редове . В безкрайната периодична картина във всяка колона се редуват три откъснати и две останали клетки, така че няма три последователни останали клетки вертикално. Във всеки фиксиран ред откъснатите клетки заемат три последователни класа колони по модул , така че няма три последователни останали клетки и хоризонтално. В краен квадрат вземаме всички цели вертикални блокове от тази периодична схема, които се побират в листа. Те са най-много . Възможните проблеми са само в няколко гранични реда и колони; там можем да добавим още вертикални блока и да унищожим всички останали възможни тройки. Следователно за някоя абсолютна константа имаме , което завършва доказателството.2003
6 задачиЗадача 1
Условие
Да се докаже, че за всяко положително цяло число съществува -цифрено число, което се дели на и всички негови цифри са нечетни.Решение
Доказателството е индукция по . За вземаме числото . Нека за дадено вече имаме подходящо -цифрено число . Разглеждаме петте числаВсички те са -цифрени, всички имат само нечетни цифри и всички се делят на . Освен това числата са с различни остатъци по модул , защото при промяна на разликата се променя с ненулево кратно на по модул . Следователно точно едно от тях се дели още веднъж на , т.е. точно едно се дели на . Това завършва индукцията.Задача 2
Условие
Изпъкнал многоъгълник в равнината е разрязан на по-малки изпъкнали многоъгълници чрез прекарване на всичките му диагонали. Дължините на всички страни и всички диагонали на са рационални числа. Да се докаже, че дължините на всички страни на всички многоъгълници в разрязването също са рационални числа.Решение
Нека е страна на някой от малките многоъгълници в разрязването и нека тя лежи върху диагонала на първоначалния многоъгълник, като са в този ред. ТогаваЗатова е достатъчно да докажем твърдението за четириъгълник: ако всички шест разстояния между четирите върха са рационални, то отсечките, на които диагоналите и страните се разрязват от пресечните си точки, също са рационални. Ще използваме тригонометричен аргумент. Вземаме четириъгълник и разглеждаме всички ъгли, които се получават от три негови върха. Законът за косинусите показва, че е рационално число за всеки такъв ъгъл ; следователно и е рационално. Ще казваме, че два от тези ъгли са еквивалентни, ако отношението на синусите им е рационално. Първо, ъглите , и са еквивалентни. Наистина, отследва, че произведението е рационално; понеже квадратите на двата синуса са рационални, това дава еквивалентност на и . Формулата за синус на сбор после дава същото и за . В триъгълника законът за синусите показва, че , и са еквивалентни. Като повтаряме този аргумент около четирите върха, получаваме, че всички разглеждани ъгли са еквивалентни. Накрая нека две отсечки между върхове се пресичат в точка . Прилагаме закона за синусите в двата триъгълника, които имат връх . Тъй като съответните отношения на синуси са рационални, всяка част от дадена рационална страна или диагонал има рационална дължина. Така всички страни на малките многоъгълници в разрязването са рационални.Задача 3
Условие
Нека е положително цяло число. За всяка редица от цели числакоято удовлетворява за , дефинираме друга редицакато е броят на членовете на редицата , които стоят преди члена и са различни от . Да се докаже, че започвайки от произволна такава редица , след по-малко от приложения на трансформацията се получава редица , за която .Решение
Ще докажем твърдението със силна индукция по . Случаите и се проверяват директно. Разглеждаме два случая. Първо, ако и , тогава за всяко имаме . Затова след едно приложение на можем да махнем първия член и да извадим от останалите членове, получавайки редицаот същия тип, но с параметър . Индукционната хипотеза завършва този случай. В противен случай некакъдето . Ако няма такъв , твърдението е очевидно. За всеки имаме , а следователно . Сега гледаме редицатаТя отново е от същия тип, но с параметър . Прилагането на върху тази скъсена редица съвпада с прилагането на върху опашката на първоначалната редица след вече направените две стъпки, само че всички стойности са намалени с . По индукционната хипотеза са нужни по-малко от допълнителни приложения, така че общият брой приложения е по-малък от . За ориентация, неподвижните редици на тази трансформация могат да се опишат като блокове от равни числа, напримеркъдето числото във всеки блок е индексът на първия член в блока.Задача 4
Условие
Нека е триъгълник. Окръжност, минаваща през и , пресича отсечките и съответно в и . Правите и се пресичат в , а правите и се пресичат в . Да се докаже, че тогава и само тогава, когато .Решение
Ключът е теоремата на Чева в триъгълника , заедно с подобни триъгълници. Понеже правите , и са конкурентни в точката , Чева в триъгълника даваОт друга страна, е равносилно на , тоест на . Следователно от Чева получавамеСега използваме вписания четириъгълник . Имаме безусловноЗатоваПоследното условие е точно подобието на триъгълниците, което даваПолучихме верига от еквивалентности, така че твърдението е доказано.Задача 5
Условие
Нека са положителни реални числа. Да се докаже, чеРешение
Това е класически пример за метода на допирателната права. Хомогенизираме и можем да приемем, че . Тогава исканото неравенство ставаЩе докажем за оценкатаТя се проверява директно, защотоПрилагайки това за и използвайки , получавамекоето доказва неравенството.Задача 6
Условие
Във върховете на правилен шестоъгълник са записани шест неотрицателни цели числа със сума . Берт има право да прави ходове от следния вид: избира връх и заменя записаното там число с абсолютната стойност на разликата между числата в двата съседни върха. Да се докаже, че Берт може да направи редица от ходове, след която числото е записано във всичките шест върха.Решение
Ще наричаме добра всяка конфигурация, която до завъртане и отражение има видакъдето са нечетни положителни числа. Първо твърдим, че от всяка конфигурация с нечетна сума може да се стигне до добра конфигурация. Понеже сумата е нечетна, един от двата равностранни триъгълника, образувани от презвръхните върхове на шестоъгълника, има нечетна сума. Работейки по модул , с няколко хода можем да получим редуване . След това, ако нечетните числа през връх са в нарастващ ред, правим ходове върху междинните върхове и ги заменяме съответно с , и . Така получаваме добра конфигурация. Остава да покажем, че всяка добра конфигурация може да се занули. Ако , имаме конфигурация и просто зануляваме последователно трите върха с число . Ако не всички от са равни, правим трите хода, показани в диаграмата. Те превръщат добра конфигурация с нечетни членове в добра конфигурация с нечетни членове . Понеже освен в случая , сумата на числата намалява. Индукция по сумата завършва доказателството.2004
6 задачиЗадача 1
Условие
Нека е четириъгълник, описан около окръжност, чиито вътрешни и външни ъгли са поне . Да се докаже, че Кога се достига равенство?Решение
Достатъчно е да докажем лявото неравенство; дясното следва от него чрез размяна на ролите на двойките страни. Понеже четириъгълникът е описан около окръжност, от теоремата на Пито имамеследователно . Затова е достатъчно да докажемТъй като всеки вътрешен и външен ъгъл е поне , всеки вътрешен ъгъл е между и . СледователноОт друга страна,Накраякоето е равносилно на . Това доказва неравенството. Равенство се достига точно когато е хвърчило с и .Задача 2
Условие
Нека са цели числа с най-голям общ делител . Нека е множество от цели числа със следните свойства: (a) за ; (b) за , не непременно различни; (c) ако и , то и . Да се докаже, че .Решение
Идеята е да докажем, че всяка целочислена линейна комбинация на числата принадлежи на . Тогава лемата на Безу веднага ще даде . Първо забелязваме две прости неща. Имаме , като вземем в (b). Освен това тогава и само тогава, когато : това следва от (c), приложено с . Ще използваме следната лема: за всеки цели и всеки индекси е вярно, че . Достатъчно е да разгледаме , защото знаците се обръщат с предишното наблюдение. Доказваме по индукция по . Например, ако , и са в , прилагаме (c) към и ; понеже е в , получаваме . Сега доказваме по индукция по , че за произволни ненулеви цели и различни индекси имамеСлучаят е току-що доказан. За индукционната стъпка можем да пишем индексите като . Ако някой коефициент е четен, нека без ограничение е четен. По индукционната хипотезаа по първата лемаСъщо по индукционната хипотеза . От (c) следваОстава случаят, когато всички са нечетни. НекаТогава и са взаимнопрости; без ограничение е нечетно. Имамезащото . Новият коефициент пред е четен, така че се свеждаме до предишния случай. Следователно всяка целочислена линейна комбинация на принадлежи на . По лемата на Безу за всяко цяло число има цели , за които . Значи всяко цяло число е в , тоест .Задача 3
Условие
За кои реални стойности на е възможно правоъгълник да се разреже на два подобни, но неконгруентни многоъгълника?Решение
Отговорът е: за всяко , освен . Първо даваме конструкция. Поради симетрията е достатъчно да разгледаме случая , защото при завъртане на правоъгълника стойността се заменя с . За цяло число и реално число построяваме правоъгълна фигура по следния начин. Започваме с правоъгълник с ширина и височина . Отляво към него залепяме правоъгълник с височина и ширина . После под получената фигура залепяме правоъгълник с ширина и височина , а отляво към получената фигура залепяме правоъгълник с височина и ширина . Продължаваме по същия начин: следващият правоъгълник отдолу има ширина и височина , следващият отляво има височина и ширина , и така нататък, докато сме добавили общо правоъгълника. По построение цялата фигура е правоъгълник, разрязан на два подобни стълбищни многоъгълника. Те не са конгруентни, понеже коефициентът на подобие е . Отношението на страните на еЗа всяко фиксирано функцията е непрекъсната за иСледователно тя приема всяка стойност, по-голяма от . Ако е дадено , избираме достатъчно голямо , така че , и после избираме с . Така получаваме търсеното разрязване на правоъгълник . Остава да докажем, че квадратът не може да се разреже по такъв начин. Да допуснем, че квадрат е разрязан на два подобни многоъгълника . Нека е общата им граница. От броене на страните на и следва, че трябва да свързва две противоположни страни на квадрата; възможно е някой от краищата на тази граница да е връх на квадрата. Завъртаме картината така, че да върви от горната към долната страна, като е вляво от нея, а е вдясно. Нека е най-голямата дължина на отсечка от . Тогава най-дългата страна на има дължина : страните на , които не са по , са лявата страна на квадрата с дължина и евентуални части от горната и долната страна, всяка с дължина най-много . Същият аргумент важи и за . Значи най-дългите страни на двата подобни многоъгълника имат една и съща дължина. Следователно коефициентът на подобие е , тоест и са конгруентни. Това противоречи на условието, така че е невъзможно.Задача 4
Условие
Алиса и Боб играят игра върху решетка . На своя ход играчът избира рационално число, което още не се среща в решетката, и го записва в празно квадратче. Алиса започва, след което играчите се редуват. Когато всички квадратчета са запълнени с числа, във всеки ред квадратчето с най-голямото число в този ред се оцветява в черно. Алиса печели, ако тогава може да начертае линия от горната страна на решетката до долната страна, която остава в черни квадратчета; Боб печели, ако това е невъзможно. Ако две квадратчета имат общ връх, Алиса може да прекара линията от едното към другото, оставайки в тези две квадратчета. Да се намери, с доказателство, печеливша стратегия за един от двамата играчи.Решение
Боб има печеливша стратегия. Ще използва само първите два реда като бариера. Означаваме квадратчетата в тези два реда така:Получават се шест двойки квадратчета: , , , . Боб ще поддържа следния инвариант: редът на големина на буквите в първия ред е същият като реда на големина на съответните букви с прим във втория ред. С други думи, за всеки две букви например и трябва да е вярноАко Алиса запише число в едно от първите дванадесет квадратчета, Боб играе в другото квадратче от същата двойка. Нека редът, в който Алиса е играла, вече има няколко попълнени означени квадратчета, а заема определено място сред техните стойности. В другия от първите два реда Боб избира неизползвано рационално число , което заема същото място сред вече попълнените стойности там. Такова съществува: достатъчно е да се вземе рационално число в съответния отворен интервал между две съседни вече записани стойности, като се избегнат крайно многото числа, които вече се срещат в решетката. След този ход новата двойка има същите сравнения с всички стари двойки в двата реда, така че инвариантът се запазва. Ако Алиса играе извън първите два реда, Боб също записва произволно неизползвано рационално число някъде в редове . Така инвариантът за първите два реда се запазва до края на играта. След като решетката се запълни, най-голямото число в първия ред и най-голямото число във втория ред са в съответна двойка: ако например най-голямата буква в първия ред е , то по инварианта най-голямата буква с прим във втория ред е . Но във всяка двойка двете квадратчета са отместени с три стълба, следователно не се допират дори във връх. Значи черното квадратче в първия ред не се допира до черното квадратче във втория ред, а всяка линия от горната страна на решетката към долната трябва да премине от черно квадратче в първия ред към допиращо се черно квадратче във втория ред. Това е невъзможно, така че Боб печели.Задача 5
Условие
Нека са положителни реални числа. Да се докаже, чеРешение
За всяко положително реално число имамезащотоСледователноСега записваме и аналогично за другите два множителя. Неравенството на Хьолдер давапонеже трите суми в скобите се събират съответно от колоните , и . Така получаваме исканото неравенство.Задача 6
Условие
Окръжност е вписана в четириъгълник . Нека е центърът на . Да се предположи, че Да се докаже, че е равнобедрен трапец.Решение
Ще дадем алгебрично доказателство. Чрез хомотетия можем да приемем, че радиусът на е . Нека са дължините на допирателните отсечки от върховете към . Тогаваи понеже радиусът към допирната точка е перпендикулярен на страната,От сумата на половинките на ъглите на четириъгълника и формулата за тангенс на сбор получаваме стандартното тъждествоСледователно условието на задачата ще принуди равенство в следното неравенство:НекаСлед разкриване на квадратите неравенство (2) е равносилно наОт (1), чрез директно разкриване, имаме ощеКато повдигнем (3) на квадрат и използваме (4), получаваме, че е достатъчно да докажемЗа да опростим дясната страна, използваме отново (1). След събиране на еднаквите членове неравенство (5) се свежда доТова вече следва непосредствено от AM-GM:както иТака доказахме (2). Понеже в условието на задачата има равенство, във всички използвани неравенства трябва да има равенство. ПолучавамеЗначи , и . Тогава , а половинките на ъглите при и са равни, както и половинките на ъглите при и . Освен товаоткъдето , тоест . Следователно и, понеже , четириъгълникът е равнобедрен трапец.2005
6 задачиЗадача 1
Условие
Да се определят всички съставни положителни цели числа , за които е възможно всички делители на , по-големи от , да се подредят в кръг така, че никои два съседни делителя да не са взаимно прости.Решение
Отговорът е: всички съставни положителни цели числа, освен числата от вида , където и са различни прости числа. Ако с различни прости и , делителите, по-големи от , са само . В кръг делителите и неизбежно са съседни, а те са взаимно прости, така че такова подреждане е невъзможно. Ако е степен на просто число, всяко подреждане работи. Ако има поне три различни прости делителя , първо поставяме около кръга , а после поставяме всеки делител, кратен на , в дъгата между и . Така всяка съседна двойка има общ прост делител. Остава случаят . Ако поне един от показателите е по-голям от , например , поставяме първо и на кръга. В едната дъга поставяме останалите делители, кратни на , а в другата - останалите делители, кратни на . Единственият неизключен случай е , който вече е невъзможен.Задача 2
Условие
Да се докаже, че системата от уравнения няма целочислени решения.Решение
Ще докажем невъзможността по модул . Нека . Тогава може да бъде само или по модул . Първото уравнение става Проверка на петте възможности за дава само следните случаи: а при първото уравнение е невъзможно. От второто уравнение трябва да имаме Деветите степени по модул са само . За четирите останали двойки стойността на е съответно , така че би трябвало да е съответно по модул . Никое от тези числа не е девета степен по модул , противоречие.Задача 3
Условие
Нека е остроъгълен триъгълник, а и са две точки върху страната . Построена е точка така, че изпъкналият четириъгълник е вписан, , а и са от различни страни на правата . Построена е точка така, че изпъкналият четириъгълник е вписан, , а и са от различни страни на правата . Да се докаже, че точките лежат на една окръжност.Решение
Достатъчно е да докажем, че са колинеарни. Тогава от успоредностите и вписаните четириъгълници следва което дава, че лежат на една окръжност. Нека е втората пресечна точка на правата с окръжността . От вписаността на получаваме . Понеже , това дава, че са вписани. Оттук следва , а по единствеността в построението . Значи са колинеарни.Задача 4
Условие
Краката на квадратна маса имат дължина , където е положително цяло число. За колко наредени четворки от неотрицателни цели числа можем да отрежем парче с дължина от края на крака и масата все още да бъде стабилна? Масата е стабилна, ако може да бъде поставена така, че краищата на всичките четири крака да докосват пода. Позволено е отрязан крак да има дължина .Решение
Отговорът е Да обърнем масата с плота към пода. Тогава искаме краищата на скъсените крака да са копланарни. Това става точно когато е успоредник. Наистина, ако е успоредник, четирите точки очевидно лежат в една равнина. Обратно, ако са копланарни, нека е точката, за която е успоредник. Тогава лежи в същата равнина, но е разположена точно над , защото горната част на масата е квадрат. Следователно . Остава само да преброим решенията на условиетотоест НекаБроят на решенията с е , затова общият брой еЗадача 5
Условие
Нека е цяло число. Дадени са точки в равнината, никои три от които не са колинеарни. Нека от точките са оцветени в синьо, а останалите - в червено. Една права се нарича балансираща, ако минава през една синя и една червена точка и от всяка страна на правата броят на сините точки от тази страна е равен на броя на червените точки от същата страна. Да се докаже, че съществуват поне две балансиращи прави.Решение
Нека е изпъкналата обвивка на дадените точки. Разглеждаме два случая. Първо, ако върховете на не са всички от един и същи цвят, по границата на има поне две страни с разноцветни краища. Продълженията на тези страни са балансиращи прави: от едната страна на такава права няма точки, а от другата остават точно сини и червени точки. Остава случаят, когато всички върхове на са от един цвят; без ограничение нека са сини. Ще докажем, че през всеки връх на минава балансираща права. Нека са три последователни сини върха на . Завъртаме права през , започвайки от правата и стигайки до правата , като я въртим през вътрешността на фигурата. Във всеки момент гледаме точките от същата страна на като и означаваме с броя на червените минус броя на сините точки от тази страна. Когато срещне синя точка, се увеличава с , а когато срещне червена точка, намалява с . В началото , а непосредствено преди края . Следователно в първия момент, в който , правата минава през и през червена точка, и е балансираща. Така получаваме балансираща права през всеки връх на . Тези прави са различни, понеже никои три от дадените точки не са колинеарни. Следователно има поне две балансиращи прави.Задача 6
Условие
За положително цяло число нека означава сумата на десетичните цифри на . Множество от положителни цели числа наричаме -стабилно, ако за всяко непразно подмножество . За всяко цяло число нека е най-малкото , за което съществува -стабилно множество с цели числа. Да се докаже, че съществуват константи , такива чеРешение
Първо ще построим достатъчно голямо стабилно множество. Нека е положително цяло число, за коетои разгледамеАко е непразно подмножество на , сумата на елементите на има вида , където . За всяко такова числото има сума на цифрите : при то се записва като , последвано от последните цифри на , а при получаваме . И в двата случая сумата на цифрите е . Следователно е -стабилно. Избирайки , получаваме горната оценка , а значи за подходяща абсолютна константа . Остава долната оценка. Ще докажем следното твърдение: ако в мултимножество има повече от положителни цели числа, то съществува непразно подмножество, за което сумата на цифрите на сбора на елементите е по-голяма от . Това веднага дава за всяко -стабилно множество с елемента, тоест . Да докажем твърдението. Записваме числата на дъска и поддържаме текуща сума , първоначално равна на . Ще запазваме инварианта, че всяко число на дъската, както и , е сума на някои от първоначалните числа, като използваните групи са разединени. На -тата стъпка искаме в края всички числа на дъската да се делят на . Ако -тата цифра отдясно на е ненулева, разделяме произволно числата на дъската на групи по и изтриваме остатъка, ако има такъв. Във всяка група има непразно подмножество със сума, деляща се на : след деление на това е стандартният факт, че сред цели числа има непразно подмножество със сума, деляща се на . Заменяме всяка група с тази сума. Ако -тата цифра отдясно на е нула, но на дъската има число, което не се дели на , изтриваме едно такова число и го прибавяме към . После правим същото групиране по . Ако пък -тата цифра отдясно на е нула и всички числа на дъската вече се делят на , не правим нищо и преминаваме нататък. Процесът свършва, когато на дъската не останат числа. При всяка нетривиална стъпка броят на числата на дъската намалява с фактор най-много , затова, щом началният брой е по-голям от , първите два случая се случват поне пъти. Всеки път при тях в се появява нова ненулева десетична цифра, която по-нататък не се променя, защото следващите прибавяни числа са делими на все по-високи степени на . Следователно накрая . По инварианта е сума на непразно подмножество от първоначалните числа, което доказва твърдението и долната оценка.2006
6 задачиЗадача 1
Условие
Нека е просто число и нека е цяло число с . Да се докаже, че съществуват цели числа и с и тогава и само тогава, когато не дели .Решение
Условието е равносилно на това остатъците при деление на да удовлетворяват . Случаят е ясен, затова нека . За всяко дефинираме като единственото число от , за коетоТърсените не съществуват точно когато тези прообрази се появяват в строго обратен ред, тоестИзбираме така, че и . Тогавакъдето представителят е взет между и . Следователно горната верига от неравенства е равносилна наТова просто означава, че числата не преминават през кратно на , докато . Понеже , получаваме за всички тези . Освен това , а от и следва . Значи . И така не съществуват точно когато , което е равносилно на . Следователно съществуват точно когато не дели .Задача 2
Условие
Нека е фиксирано цяло число. Да се намери най-малкото цяло число като функция от , за което съществува множество от различни положителни цели числа със сума, по-голяма от , но всяко негово -елементно подмножество има сума най-много .Решение
Отговорът еПример за равенство се дава отСумата на всички елементи е , а сумата на най-големите елемента е точно . Следователно това множество показва, че посоченото е достижимо. Остава да докажем, че по-малко е невъзможно. Нека даденото множество еОт условието получавамеизащото това са най-големите елемента. Като извадим два пъти второто неравенство от първото, следваПонеже числата са различни положителни цели числа и са подредени, имаме за . Затова . ТогаваИзползвайки , получавамекоето е равносилно на . Това доказва минималността.Задача 3
Условие
За цяло число нека е най-големият прост делител на . По дефиниция поставяме и . Да се намерят всички полиноми с цели коефициенти, за които редицата е ограничена отгоре. (В частност това изисква за всяко .)Решение
Отговорът е: всички полиноми от видакъдето е ненулево цяло число, а всички са нечетни цели числа. Празното произведение е позволено. Първо да проверим, че тези полиноми работят. За цяло имамеПонеже е нечетно, този множител не се занулява при цяло . Всеки прост делител на него дели един от двата линейни множителя и следователно по абсолютна стойност е най-много . Простите делители на константата са фиксирани. Значи има константа , зависеща само от , такава че за всички , тоест редицата е ограничена отгоре. Остава да докажем, че други полиноми няма. Разлагаме над целите числа и разглеждаме ненулев неприводим неконстантен множител . Достатъчно е да покажем, че ако не е от вида , то стойностите са неограничени отгоре. Нека е произволно положително цяло число. По теоремата на Шур съществуват безкрайно много нечетни прости числа , които делят някоя стойност . За такова можем да изберем представител с , защото квадратите и са сравними по модул . Твърдим, че само краен брой от тези прости могат да ни принудят всички такива да лежат в последните възможни позиции, тоест да са от вида с . Наистина, тогаваСлед умножаване с фиксирана степен на получаваме, че дели едно от крайно много фиксирани цели числа, освен ако някоя от стойностите не е нула. В този изключителен случай линейният множител дели над рационалните числа, а по неприводимост е точно такъв множител, с точност до ненулева константа. Следователно, ако не е от този вид, за всяко намираме просто и с . Тогавакоето е неограничено, понеже е произволно. Значи всеки неконстантен неприводим множител на е от вида . Накрая, ако е четно, тогава се занулява при , което е забранено от условието. Затова всички са нечетни, а остава само произволният ненулев цял константен множител .Задача 4
Условие
Да се намерят всички положителни цели числа , за които съществуват цяло число и положителни рационални числа , удовлетворяващиРешение
Отговорът са всички положителни цели числа с изключение на . Първо ще докажем, че сред числата работи само . Числото наистина работи, защото . Нека имаме решение с . Ако , то от следваДясната страна е цяло число и квадрат на рационално число, следователно е точен квадрат. За тя лежи строго между квадратите и , а при пряката проверка оставя само . Значи, за всяко друго решение с трябва да имаме . Но от неравенството между средноаритметичното и средногеометричното получавамеоткъдето . За това е , за е , а за е още по-голямо от . Това противоречи на , така че малките изключения са точно . Сега даваме конструкции за всички останали . Ако е четно, вземамекъдето единиците са на брой. Сумата и произведението са равни на . Ако е нечетно, вземамекъдето единиците са на брой; отново сумата и произведението са . Остава специалният случай , за който работипонеже и сумата, и произведението на тези три числа са равни на .Задача 5
Условие
Математическа жаба скача по числовата права. Тя започва от и скача по следното правило: ако се намира в цялото число , може да скочи или до , или до , където е най-голямата степен на , която дели . Да се докаже, че ако е положително цяло число и е неотрицателно цяло число, то минималният брой скокове, нужни за достигане на , е по-голям от минималния брой скокове, нужни за достигане на .Решение
Ще мислим за един път като за крайна редица от дължини на скокове . Ако позициите сато . Ще наричаме такава редица валидна, ако за всяко е изпълнено или , където е степента на в разлагането на . Нужна ни е следната лема. Нека в някаква валидна редица изберем момент и число , след което изтрием всички по-късни скокове, чиито дължини се делят на . Получената редица пак е валидна. Доказателството е локално. След изтриването всяка останала стартова точка след избрания момент е изместена наляво с кратно на . Ако останалият скок има дължина , той винаги е позволен. Ако има дължина по-голяма от , тя е степен на и не се дели на , следователно е по-малка от . Затова старата стартова точка има -адична валуация, по-малка от , а добавянето или изваждането на кратно на не променя тази валуация. Следователно същият скок остава позволен и след изтриването. Сега вземаме валиден път до . Ще го съкращаваме до път до . Започваме от най-големите дължини на скокове и слизаме надолу: за всяко изтриваме всички скокове с дължина , които завършват вдясно от . Понеже позициите само нарастват, тези изтривания са от вида, позволен от лемата, така че пътят остава валиден. Твърдим, че след като са изтрити всички скокове с дължина, по-голяма от , текущият край на пътя е поне и се дели на . Доказваме това с обратна индукция по . При изтриване на скок с дължина краят на пътя преди изтриването е бил строго по-голям от ; освен това по индукционната хипотеза той е кратен на , защото го променяме само с кратни на . Най-малкото кратно на , което е по-голямо от , е . Следователно новият край пак е поне и има нужната делимост. Когато процесът приключи, вече няма скок, който завършва вдясно от , така че крайният пункт е най-много . От твърдението той е поне , значи е точно . Понеже началният път е завършвал в , при процеса е изтрит поне един скок. Така от всеки път до получаваме по-къс валиден път до . Следователно минималният брой скокове до е строго по-голям от минималния брой скокове до .Задача 6
Условие
Нека е четириъгълник, а и са точки съответно върху страните и , такива че Лъчът пресича лъчите и съответно в и . Да се докаже, че описаните окръжности на триъгълниците , , и минават през една обща точка.Решение
Нека е точката на Микел на четириъгълника . Тогава е център на спирална подобност, която изпраща отсечката в отсечката : в частност тя изпраща в и в . Понеже и делят съответните отсечки в едно и също отношение,същата спирална подобност изпраща и точката в точката . Следователно е център на спирална подобност, която изпраща отсечката в отсечката . Тъй като са колинеарни и са колинеарни, това означава, че лежи едновременно на описаните окръжности на и . Аналогично, от същата спирална подобност имаме, че се изпраща в , а - в . Понеже са колинеарни и са колинеарни, получаваме, че лежи и на описаните окръжности на и . Значи и четирите окръжности , , и минават през една и съща точка , както се искаше.2007
6 задачиЗадача 1
Условие
Нека е положително цяло число. Дефинираме редица, като поставяме , а за всяко избираме да бъде единственото цяло число в интервала , за което се дели на . Например при получената редица започва с . Да се докаже, че за всяко редицата е константна от някой член нататък.Решение
За всяко поставямеПо условие е неотрицателно цяло число. Ще докажем, че редицата е невъзходяща. Наистина, понеже , имамеЛявата страна е цяло число, следователно . Така е невъзходяща редица от неотрицателни цели числа и затова е константна от някой член нататък. Нека . Тогава за всяко получавамеТази формула показва не само стабилизиране, а и точната стойност на всички достатъчно късни членове. Следователно и редицата е константна от някой член нататък, както се искаше.Задача 2
Условие
Възможно ли е всички решетъчни точки в да бъдат покрити от безкрайно семейство кръгове, чиито вътрешности са две по две непересичащи се, ако радиусът на всеки кръг е поне ?Решение
Отговорът е не. Да допуснем противното. Избираме кръг , който не пресича никой от дадените кръгове, и го разширяваме, докато стане максимален с това свойство. Нека радиусът му е . Тъй като всички решетъчни точки са покрити от дадените кръгове, нашият празен кръг не съдържа решетъчна точка. А всяка точка от равнината е на разстояние най-много от някоя решетъчна точка, следователно трябва да е . От максималността на той трябва да се допира до поне три от дадените кръгове; иначе центърът му може леко да се премести и радиусът да се увеличи. Нека три такива кръга имат центрове . Сред трите ъгъла около центъра на има поне един, който е най-много ; без ограничение нека това е . Нека радиусите на са съответно . Тогава , а понеже вътрешностите на дадените кръгове са непересичащи се, имаме . От косинусовата теорема и следваСлед опростяване това даваНо от получавамеЗа неравенството е невъзможно. Следователно всъщност . Това обаче означава, че съдържа решетъчна точка, защото центърът му е на разстояние най-много от такава точка. Получаваме непокрита решетъчна точка, противоречие.Задача 3
Условие
Нека е множество с елемента. Всички -елементни подмножества на са разделени в два класа. Да се докаже, че има поне две по две непресичащи се множества, които принадлежат на един и същ клас.Решение
Ще наричаме едно -елементно множество полезно, ако сред неговите -елементни подмножества има представители и от двата класа. Вземаме максимална фамилия от две по две непресичащи се полезни множества и нека броят им е . Нека е множеството от всички елементи, които не лежат в избраните полезни множества. Първо ще покажем, че всички -елементни подмножества на са от един и същ клас. Ако имаше две такива подмножества и от различни класове, бихме могли да заменяме елементите на един по един, докато получим . В някоя стъпка цветът трябва да се смени; тогава обединението на двете съседни -елементни множества има най-много елемента и съдържа -елементни подмножества от двата класа. Допълвайки при нужда до точно елемента в , получаваме полезно множество в , което противоречи на максималността. Следователно всички -елементни подмножества на са, без ограничение, от първия клас. От всяко избрано полезно множество можем да вземем по едно -елементно подмножество от първия клас, а от можем да извадим още две по две непресичащи се -елементни подмножества от същия клас. Ако , вече сме готови. Затова нека . Тогаваи следователноТака общо получаваме поне две по две непресичащи се -елементни подмножества от един и същ клас, както трябваше да се докаже.Задача 4
Условие
Животно с клетки е свързана фигура, съставена от еднакви квадратни клетки, тоест полимино с клетки. Динозавър е животно с поне клетки. Наричаме динозавър примитивен, ако клетките му не могат да бъдат разделени на два или повече динозавъра. Да се намери, с доказателство, максималният възможен брой клетки в примитивен динозавър.Решение
Отговорът е . Ще използваме графа на съседство на клетките и ще вземем негово покриващо дърво . Всеки връх на това дърво има степен най-много , защото една квадратна клетка има най-много четири странични съседи. Ако дървото можеше да се раздели на две или повече свързани части, всяка с поне върха, това би дало съответно разделяне на динозавъра. Затова е достатъчно да разсъждаваме върху . Ще докажем, че в има връх , такъв че след изтриването му всички компоненти имат най-много върха. Да допуснем противното. Тогава за всеки връх има компонент на с поне върха; насочваме от реброто към съседа, който лежи в такъв голям компонент. Получаваме ориентация, в която от всеки връх излиза една стрелка. Ако следваме стрелките, понеже дървото е крайно, в някакъв момент ще се получи повторение. Единственият възможен цикъл в дърво с такава ориентация е двуцикъл по едно ребро, да кажем . Но тогава компонентът на , който съдържа , има поне върха, и компонентът на , който съдържа , също има поне върха. Тези два компонента са точно двете части, получени при премахване на реброто , и са свързани. Това разделя динозавъра на два динозавъра, противоречие с примитивността. Следователно такъв връх съществува. След изтриването на има най-много компонента и всяка има най-много върха. Значи общият брой клетки е най-многоОстава конструкция. Вземаме една централна клетка и към всяка от четирите нейни страни залепяме права лента от клетки. Получаваме динозавър с клетки. Всяка свързана част с поне клетки трябва да съдържа централната клетка, защото всяка от четирите ленти без центъра има само клетки. Следователно не могат да се отделят два динозавъра, понеже и двата биха трябвало да съдържат централната клетка. Конструкцията е примитивна и границата е точна.Задача 5
Условие
Да се докаже, че за всяко неотрицателно цяло число числото е произведение на поне прости числа, които не е задължително да са различни, т.е. броят се с повторения.Решение
Ще докажем твърдението с индукция по . При имаме , така че твърдението е вярно. Да предположим, че вече има поне прости множителя. ПоставямеТогаваПървият множител е точно предишното число. Достатъчно е да покажем, че вторият множител е съставен, защото тогава при преминаване от към се добавят поне два нови прости множителя. НекаИмаме тъждествотоПонеже , числото е квадрат, защото е четно. Следователное разлика на два квадрата. За двата получени положителни множителя са по-големи от , затова е съставно число. Така всеки индукционен преход добавя поне два прости множителя, а от трите множителя при получаваме поне прости множителя за всяко .Задача 6
Условие
Нека е остроъгълен триъгълник, а , и са съответно неговата вписана окръжност, описана окръжност и радиусът на описаната окръжност. Окръжността се допира вътрешно до в и външно до . Окръжността се допира вътрешно до в и вътрешно до . Нека и са съответно центровете на и . Аналогично дефинираме точките . Да се докаже, че като равенство има тогава и само тогава, когато е равностранен.Решение
Нека , , , , е лицето, е радиусът на вписаната окръжност и е височината от . Ще пресметнем дължината . Правим инверсия с център и радиус , а след това отражение спрямо ъглополовящата на . Ще означаваме образите след тези две операции със звезда и после с плюс. Инверсията е избрана така, че вписаната окръжност остава неподвижна. Окръжността , която минава през , се превръща в права, успоредна на образа на и перпендикулярна на правата ; освен това тази права е допирателна към . Понеже е правата , а изогоналният образ на е височината от , след отражението тази допирателна е точно . Следователно образът на второто пресичане на с е петата на височината от към . По същия начин образът на второто пресичане на с лежи на правата и е такъв, че . От инверсията получавамеиЗатоваПонеже и , това се опростява доАналогично,Следователно желаното неравенство е еквивалентно наИзползваме и формулата на Херон . Получаваме, че последното неравенство е еквивалентно наТова е точно неравенството на Ойлер за триъгълник, защото , където и са центровете на вписаната и описаната окръжност. Равенство има тогава и само тогава, когато , което за остроъгълен триъгълник означава, че триъгълникът е равностранен. Така получаваме и търсеното условие за равенство.2008
6 задачиЗадача 1
Условие
Да се докаже, че за всяко положително цяло число съществуват взаимно прости две по две цели числа , всички строго по-големи от , такива че е произведение на две последователни цели числа.Решение
Ще построим една безкрайна редица, от която после вземаме първите члена. Използваме тъждествотоПоставяме и . Ще дефинираме рекурсивно и така, чеАко това е вярно за някое , поставямеТогава горното тъждество даваСледователно за всяко имамекоето е произведение на две последователни цели числа. Остава да проверим взаимната простота. При построението винаги е четно и поне , така че е нечетно и по-голямо от . Освен товаРазликата на двата аргумента е , затова този най-голям общ делител дели . Но е нечетно и е взаимно просто с , понеже . Следователно делителят е . Така всеки нов член е взаимно прост с произведението на предишните, което доказва твърдението.Задача 2
Условие
Нека е остроъгълен разностранен триъгълник, а са съответно средите на , като симетралите на и пресичат лъча съответно в точките и . Правите и се пресичат в точка вътре в триъгълника . Да се докаже, че точките лежат на една окръжност.Решение
Нека , , и работим с барицентрични координати спрямо . Ще използваме стандартното означение . Понеже лежи на медианата , имаме за някакво . Условието , тъй като е върху симетралата на , дава следователно Аналогично От пресичането на правите и получаваме Нека е образът на при централна симетрия с център , тоест е средата на . Сумата на барицентричните координати на е Затова Точката лежи на описаната окръжност на , защото уравнението ѝ в барицентрични координати е а координатите на го удовлетворяват. Сега при хомотетия с център и коефициент описаната окръжност на се превръща в окръжността през , средата на и средата на . Тъй като е средата на , от следва . Следователно лежат на една окръжност.Задача 3
Условие
Нека е положително цяло число. Нека е множеството от точките с цели координати, за които Път е редица от различни точки от , такава че за всяко разстоянието между и е . Да се докаже, че точките от не могат да бъдат разделени на по-малко от пътя.Решение
Ще използваме оцветяване в два цвята. Разделяме фигурата на горна и долна половина спрямо хоризонталната ос между редовете и . В горната половина оцветяваме точките шахматно в синьо и червено така, че крайната точка да е синя, а долната половина оцветяваме като огледален образ на горната. При това оцветяване съседни точки почти винаги имат различни цветове. Единственото изключение е по хоризонталната ос на симетрия: там може да се появи ребро между две сини точки. Освен това сините точки са точно с повече от червените. Да допуснем, че е разделено на пътя. Разрязваме всеки път по всяко ребро, което свързва две сини точки. Такива ребра има само по оста на симетрия, и там има най-много възможни разреза. Следователно след разрязването получаваме най-много пътя. От друга страна, след тези разрези всеки получен път редува цветовете си, освен че може да съдържа двойки от две червени съседни точки. Във всеки такъв път броят на сините точки надвишава броя на червените с най-много . Понеже общо сините точки са с повече от червените, трябва да има поне пътя след разрязването. Значи откъдето . Това доказва твърдението.Задача 4
Условие
За кои цели числа може да се намери триангулация на правилен -ъгълник, съставена само от равнобедрени триъгълници? Тук триангулация означава разрязване чрез непресичащи се диагонали на триъгълници, чието обединение е целият многоъгълник.Решение
Отговорът е: точно за числата където са неотрицателни цели числа, не и двете нули. Нека правилният многоъгълник е с индекси по модул . Ще наричаме страните къси. Всяка къса страна участва в точно един триъгълник от триангулацията. Ако е четно, единствените равнобедрени триъгълници, които могат да използват дадена къса страна без пресичане, са малките триъгълници с трети връх или . Следователно за всички къси страни трябва да се групират по двойки в такива малки триъгълници; след премахването им остава правилен -ъгълник. Значи за четно числото работи тогава и само тогава, когато работи. Понеже очевидно работи, това свежда четния случай до нечетния, като позволява произволен множител степен на . Нека сега е нечетно. Поради паритет не всички къси страни могат да участват в малки триъгълници. Следователно поне една къса страна участва в голям равнобедрен триъгълник. Такъв голям триъгълник съдържа центъра на многоъгълника, затова в триангулацията може да има най-много един такъв триъгълник. След премахването му останалите къси страни трябва да се сдвоят чрез малки триъгълници, а същият аргумент се повтаря рекурсивно в двете получени половини. Това е възможно точно когато е степен на , тоест когато за някое положително цяло число . Комбинирайки нечетния случай с многократното делене на две в четния случай, получаваме точно числата с и не едновременно нули. Конструкциите се получават, като обръщаме описаните редукции: за нечетното ядро вземаме един голям триъгълник и запълваме двете половини симетрично, а при умножаване по добавяме външен слой от малки равнобедрени триъгълници.Задача 5
Условие
На дъската са записани три неотрицателни реални числа . Известно е, че съществуват цели числа , не всички нулеви, за които Разрешена е следната операция: избират се две числа на дъската с , изтрива се и на негово място се записва . Да се докаже, че след краен брой такива операции можем да получим поне една нула на дъската.Решение
Ако на дъската вече има нула, няма какво да доказваме. Затова предполагаме, че всички са положителни. Ще използваме дадената целочислена зависимост и ще намаляваме величинатаАко някой от коефициентите вече е нула, например , тогава , така че е рационално число. Пишем и с положителни цели и реално . Обикновеният алгоритъм на Евклид, приложен чрез разрешената операция върху и , за краен брой стъпки дава нула. Остава да покажем, че докато всички коефициенти са ненулеви, можем да намалим . След пренареждане некаако две от числата са равни, една операция веднага дава нула. Умножавайки зависимостта по при нужда, можем да считаме, че . Първо нека поне един от е положителен. Те не могат и двата да са положителни, защото тогава всички членове с положителни коефициенти не могат да се компенсират. Ако , то иСледователно , откъдето . Извършваме операцията . Новата зависимост еи сумата на абсолютните стойности на коефициентите намалява. Случаят е същият, като вместо това използваме операцията . Остава случаят и . Ако , използваме операцията и намаляваме ; ако , използваме . Да допуснем, че нито едно от тези две неравенства не е вярно. Тогава от следва, че и са неотрицателни, а дориКато съберем, получаваме . От друга страна, понеже , , и , имамекоето дава . Това е противоречие. Следователно, докато няма нулев коефициент, можем с разрешена операция да получим нова ненулева целочислена зависимост с по-малка стойност на . Това не може да продължава безкрайно, защото е положително цяло число. След краен брой стъпки някой коефициент става нула, а тогава, както видяхме, алгоритъмът на Евклид довършва доказателството.Задача 6
Условие
На една математическа конференция всеки двама математици са или приятели, или непознати. По време на хранене всеки участник яде в една от две големи зали. Всеки математик настоява да бъде в зала, в която има четен брой негови приятели. Да се докаже, че броят на начините участниците да бъдат разпределени между двете зали е степен на , тоест има вида за някое положително цяло число .Решение
Разглеждаме граф, чиито върхове са математиците, а ребрата свързват двойките приятели. Разпределение между двете зали е същото като оцветяване на върховете с два цвята. Нека върховете са и работим над полето . Ако е цветът на върха , условието за върха казва, че броят на съседите , за които , е четен. Понеже над индикаторът на равенството е , това условие може да се запише като линейно уравнение. Нека е матрицата, която извън диагонала има матрицата на съседство на графа, а на диагонала в ред има степента на върха по модул . Ако е векторът от тези диагонални елементи, всички добри оцветявания са точно решенията нанад . Следователно множеството от решения е или празно, или е транслация на , така че броят му е степен на . Остава само да докажем, че поне едно добро оцветяване винаги съществува. Ще го докажем с минимален контрапример. Нека е граф с най-малък брой върхове, за който добро оцветяване не съществува. Ако всички върхове имат четна степен, оцветяването, при което всички са в една и съща зала, е добро. Значи има връх с нечетна степен. Премахваме и сред неговите съседи обръщаме съседството: всяка двойка съседи на , която е била свързана, става несвързана, а всяка несвързана двойка става свързана. Получаваме по-малък граф, следователно той има добро оцветяване. Ще го продължим до добро оцветяване на . Сред съседите на броим колко са от първия и колко от втория цвят. Тъй като степента на е нечетна, точно един от тези два броя е четен. Даваме на цвета, за който броят на съседите с този цвят е четен. Тогава условието за е изпълнено. За връх, който не е съсед на , нищо не се променя. За съсед на промяната в паритета идва от обръщането на ребрата към другите съседи на със същия цвят като , а ако има цвета на , и от новия съсед . Изборът на цвета на прави тази обща промяна четна, така че условието за също остава изпълнено. Получихме добро оцветяване на , противоречие с минималността. Значи добро оцветяване винаги има. Понеже допълнителната размяна на двете зали също дава добро разпределение, броят е степен с положително .2009
4 задачиЗадача 2
Условие
Нека е положително цяло число. Да се определи най-големият възможен брой елементи на подмножество на , което не съдържа три елемента , не непременно различни, за които .Решение
Отговорът е при четно и при нечетно . Конструкцията е да вземем всички нечетни числа в интервала: сборът на три нечетни числа е нечетен, следователно не може да е . При четно тези числа са , а при нечетно са . Остава да докажем, че това е максимумът. Достатъчно е да разгледаме четно , защото ако е нечетно, всяко допустимо множество в е също допустимо подмножество на , а е четно. Ще докажем твърдението за четно с индукция по . Базата е непосредствена. Нека е допустимо множество. Акото от индукционното предположение за интервала получавамеЗатова можем да предположим, че сред четирите крайни числа са избрани поне три. Ако и , и са в , тогава не може да е в , а за всяко не можем едновременно да изберем и , нито едновременно и . При това означава, че и изобщо не могат да се изберат. Следователно извън има най-много елемента и пак . Остава случаят, в който точно едно от числата и е избрано. След смяна на знаците можем да считаме, че и . Понеже са избрани поне три крайни числа, трябва да имаме . Тогава и не могат да принадлежат на . Освен това от числата можем да изберем най-много по едно от всяка двойка със сбор , а от числата можем да изберем най-много по едно от всяка двойка със сбор ; при средната стойност това дори забранява съответното число. Така към трите вече избрани крайни числа могат да се добавят най-много други елемента. Следователно . Индукцията завършва доказателството за четно , а с това и цялото твърдение.Задача 3
Условие
Наричаме шахматен многоъгълник прост многоъгълник, чиито страни лежат върху прави от вида или , където и са цели числа. Тези прави разделят вътрешността му на единични квадратчета, оцветени последователно в сиво и бяло така, че съседни квадратчета имат различни цветове. Замощаване с домина означава точно покриване на многоъгълника с неприпокриващи се правоъгълници . Накрая наричаме едно замощаване изящно, ако в никой квадрат не се среща някоя от следните две лоши локални конфигурации: два хоризонтални домина, когато долното ляво квадратче на този квадрат е бяло, или два вертикални домина, когато долното ляво квадратче е черно. Докажете, че: (а) ако шахматен многоъгълник може да бъде замощен с домина, то той може да бъде замощен изящно; и (б) такова изящно замощаване е единствено.Решение
Първо ще докажем съществуването с индукция по броя квадратчета. Избираме най-долното ляво квадратче на многоъгълника; без ограничение можем да приемем, че то е бяло, защото иначе разменяме имената на цветовете. Ако съществува някакво замощаване, в което е покрито от вертикално домино, изтриваме това домино и прилагаме индукционното предположение към останалия шахматен многоъгълник. Когато върнем вертикалното домино, не се появява лоша локална конфигурация, защото около най-долното ляво квадратче няма квадратчета отдолу и отляво. Остава случаят, в който във всяко замощаване квадратчето е покрито от хоризонтално домино. Изтриваме това домино и отново прилагаме индукция. Когато го върнем, единствената възможна нова лоша конфигурация би била друго хоризонтално домино точно над него в същия квадрат . Но тогава тези две хоризонтални домина могат да се заменят с две вертикални, което би дало замощаване, в което е покрито вертикално. Това противоречи на предположението за случая. Следователно изящно замощаване съществува. Сега доказваме единствеността. Да допуснем, че има две различни изящни замощавания. Наслагваме ги; там, където се различават, домината образуват една или повече затворени вериги. Избираме една такава верига , която огражда област , и я обхождаме обратно на часовниковата стрелка. Изместваме координатите така, че най-долният ляв връх на да е . В двете замощавания доминото при е различно: в едното е хоризонтално, а в другото вертикално. Проследяваме замощаването, което започва с вертикалното домино при . Условието за изящност принуждава следващите домина да образуват стълбицакато домината се редуват вертикално, хоризонтално, вертикално, хоризонтално и т.н. Началото на тази принудена стълбица е показано на диаграмата. Нека е правата . Веригата пресича първо в точката , а след това в някаква точка по пътя си. Домината от стълбицата са принудени да следват от към . При точката следващото принудено домино трябва едновременно да остане вътре в и да спази ориентацията на граничната верига ; това е невъзможно, защото тогава или получаваме една от забранените локални конфигурации, или пресичаме по-рано от избора на . Полученото противоречие показва, че две различни изящни замощавания не могат да съществуват. Заедно със съществуването това доказва, че изящното замощаване е точно едно.Задача 4
Условие
За нека са положителни реални числа, за които Да се докаже, чеРешение
Нека е най-голямото, а най-малкото от числата, и поставяме . Тогава и трябва да докажем . В лявата страна на даденото неравенство просто подреждаме първата сума като . По неравенството на Коши-Шварц получавамеВсички величини са положителни, следователноАко означим , то и последното неравенство даватоестПонеже , оттук следва , а значи . Това е точно исканото неравенство.Задача 6
Условие
Нека е безкрайна неконстантна редица от рационални числа, тоест не е вярно, че . Да предположим, че също е безкрайна неконстантна редица от рационални числа със свойството, че е цяло число за всички и . Да се докаже, че съществува рационално число , такова че и са цели числа за всички и .Решение
Първо изключваме един граничен случай. Ще покажем, че има индекси , за коитоАко това не е така, избираме ; тогава непременно . Понеже редицата е неконстантна, има индекс с . От условието за двойките и следва едновременно и , противоречие. След преномериране некаПо условие е цяло число. Сега правим нормализация, която не променя произведенията на разликите: изваждаме и и умножаваме редицата по , а редицата по . Така можем да работим приАко намерим подходящо число в тази нормализирана ситуация, после връщането на мащаба дава търсеното рационално в първоначалната задача. От условието с получавамеОсвен това, като разпишем и използваме вече доказаното, намирамеВ частност при имамеЩе докажем, че и за всяко . Нека е просто число и нека . От и следва следното. Ако , то , така че има неотрицателна -адична оценка; тогава сумата би имала отрицателна оценка, противоречие. Значи е цяло число. Ако пък , тоест , тогава от следва ; тогава отново би имало отрицателна -адична оценка, противоречие. Следователно също е цяло число. Нека е положителният най-голям общ делител на всички цели числа . Ще докажем, че за всяко . За просто число поставяме и избираме индекс , за който минимумът се достига. От следва . Да допуснем, че за някой имаме . Тогава от следва . Но в целия сборпървият член има -адична оценка , а вторият има оценка поне . Следователно самият сбор би имал отрицателна -адична оценка, противоречие. Значи за всяко , тоест . В нормализираната задача вече сме готови: понеже е цяло число за всички , то е цяло число за всички ; а понеже дели всяко , числото също е цяло. Така можем да вземем в нормализираните означения, а след връщане на първоначалното мащабиране получаваме рационално число за изходните редици.2010
4 задачиЗадача 2
Условие
В кръг стоят ученици, един зад друг. Височините им са . Ако ученик с височина стои непосредствено зад ученик с височина или по-малка, двамата ученици могат да разменят местата си. Да се докаже, че не е възможно да се направят повече от такива размени, преди да се стигне до разположение, при което повече размени не са възможни.Решение
Ще докажем по-силно твърдение: учениците с височини и могат да разменят местата си най-много пъти. Това очевидно е вярно при , защото двама ученици със съседни индекси по височина никога не могат да бъдат разрешена двойка за размяна. Нека и . Допускаме индукционно, че твърдението вече е доказано за по-малки стойности на . Проследяваме само тримата ученици , като игнорираме всички останали. След първата размяна между и техният относителен ред около кръга става такъв, че трябва първо да размени място с , преди отново да може да размени място с . По индукционното предположение двойката се разменя най-много пъти. Следователно двойката се разменя най-много1+igl(j-(i+1)-1igr)=j-i-1пъти, както искахме. Всяка размяна е размяна на някаква двойка ученици. Затова общият брой размени е най-многоЗа всяка тройка индекси тя се брои точно веднъж в тази сума, именно като един от избори за средния индекс . Следователно сумата е , което завършва доказателството.Задача 3
Условие
положителни реални числа удовлетворяват неравенството за всички . Определете, с доказателство, най-голямата възможна стойност на произведението .Решение
Отговорът еГорната оценка е непосредствена: групираме членовете по двойки и използваме даденото неравенство:Остава да покажем, че тази стойност може да се достигне. За полагамеТогава , така че произведението на всички е точно търсеното. Ще проверим, че всички неравенства са изпълнени. Ако и са четни, топо AM-GM. Ако е нечетно, а е четно, от следва . След повдигане на квадрат желаното неравенство е еквивалентно наРазликата между лявата и дясната страна, умножена по , етака че и този случай е доказан. Остава случаят , , където . Нека . След повдигане на квадрат трябва да докажемСлед умножаване на разликата на квадратите по получавамеПри имаме . Освен това за понеже . Следователно за всеки , което завършва проверката на конструкцията. Така най-голямата възможна стойност на произведението е .Задача 5
Условие
Нека , където е нечетно просто число, и нека Да се докаже, че ако за цели числа и , то дели .Решение
Използваме разлагането на прости дробиТъй като , последният член в сумата е с първи множител , а броят на членовете е . Следователно\left(\frac12+\frac13+\cdots+\frac1{q+2} ight)-\left(1+\frac12+\cdots+\frac1{(q+1)/3} ight).Изваждаме члена от първата хармонична сума и добавяме от двете страни, за да получим\left(1+\frac12+\cdots+\frac1{p-1} ight)+\left(\frac1{p+1}+\frac1{p+2}+\cdots+\frac1{q+2} ight)-\left(1+\frac12+\cdots+\frac1{(q+1)/3} ight).Сега работим по модул ; всички знаменатели в последния израз са взаимно прости с . ПонежеимамеЗатова втората и третата сума се съкращават по модул . Оставазащото членовете и имат реципрочни стойности, чиято сума е по модул . СледователноАко тази рационална стойност е , последното сравнение означава , тоест .Задача 6
Условие
На дъската са записани наредени двойки, не непременно различни, от ненулеви цели числа. Известно е, че не съществува цяло число , за което едновременно да са записани двойките и . Ученик изтрива някои от -те записани числа така, че никои две изтрити числа да нямат сума , и получава една точка за всяка наредена двойка, в която е изтрито поне едно число. Какъв е най-големият брой точки, който ученикът може да си гарантира?Решение
Отговорът е . Ще преведем задачата на езика на мултиграфите. Групираме всяко ненулево число с противоположното му: за всяка такава двойка пишем върхове и , където . Всяка наредена двойка от дъската разглеждаме като ребро между съответните върхове; ориентацията не влияе на това дали реброто носи точка. Условието за двойките и позволява да означим върховете така, че примките да са само при върхове от вида . Ученикът може да избере точно един от двата върха за всяко : ако не е избрал нито един, добавянето на един от тях не нарушава условието и не намалява резултата. Точките са точно ребрата, инцидентни с избраните върхове. Първо доказваме, че винаги могат да се гарантират поне точки. Избираме независимо с вероятноста с вероятност . Тогава . Всяка примка при се брои с вероятност . Всяко ребро между два върха от вида се брои с вероятност . Всички останали ребра се броят с вероятност поне . Следователно математическото очакване на броя точки е поне . Азащото е еквивалентно след повдигане на квадрат на . Значи съществува избор с поне точки, понеже броят точки е цяло число. Остава да покажем, че не може да бъде подобрено. Даваме пример. Нека имаме двойки върхове . Поставяме по пет примки при всеки , общо ребра, и поставяме по едно ребро между всяка двойка различни върхове , тоест граф върху върховете , с още ребра. Общо ребрата са , а примки при няма, така че условието на задачата е изпълнено. Ако ученикът избере точно от върховете и съответно от върховете , резултатът му еТова е , чиято максимална стойност за е (при или ). Следователно в този пример не могат да се гарантират повече от точки. Значи търсеният максимум е .2011
4 задачиЗадача 1
Условие
Нека са положителни реални числа, за които Да се докаже, чеРешение
Условието е еквивалентно на ЗатоваВъв всяка циклична дроб числителят вдясно се преобразува катоСледователноПо AM-GM за трите положителни члена имамезащото произведението под корена е . Така дясната страна е поне , откъдето след деление на получаваме исканото неравенство.Задача 2
Условие
На всеки връх на правилен петоъгълник е записано цяло число така, че сумата на петте числа е . Един ход в играта се състои в това да се избере цяло число , не непременно положително, да се извади от числата в два съседни върха и да се прибави към противоположния връх, който не е съседен на нито един от първите два. Числото и избраните върхове могат да се променят от ход на ход. Казваме, че играта се печели във връх, ако след краен брой ходове в този връх стои числото , а в останалите четири върха стоят нули. Да се докаже, че при всяко начално разпределение има точно един връх, в който играта може да се спечели.Решение
Номерираме върховете последователно с и нека текущите числа са . Величинатае инвариант. Наистина, ако в един ход противоположният връх е , тогава промяната в претеглената сума е , където индексите са по модул . Това веднага показва, че може да има най-много един печеливш връх: ако накрая единственото ненулево число е във връх , то . Остава да докажем, че този единствен възможен връх наистина е достижим. Без ограничение нека той е връх , тоест началните числа удовлетворяватНека е сумата на всички избрани стойности в ходовете, при които връх е противоположният връх и получава . Търсим цели , за които крайното състояние да е печелившо във връх . Това дава систематаПървото уравнение следва от останалите четири и от запазването на общата сума. Освен това можем да прибавим една и съща константа към всички , без да променим нито едно от крайните числа; затова поставяме . От третото и четвъртото уравнение получавамеСлед заместване във второто и петото оставатИзваждайки, намирамеДробта е цяло число, защото числителят е сравним с по модул . Ако го означим с , една целочислена система решения еПонеже може да е отрицателно, всяка такава целочислена петорка се реализира чрез съответните ходове. Следователно печалбата в единствения връх, определен от инварианта, винаги е възможна.Задача 4
Условие
Да се разгледа твърдението: за всяко положително цяло число остатъкът при деление на на е степен на . Да се докаже твърдението или да се намери контрапример с доказателство.Решение
Ще покажем, че е контрапример. По модул имаме , затова степените на имат период, който дели . Следователно показателят може да се намали по модул :понеже . Числото наистина е остатъкът, защото . Но не е степен на , тъй като всяка степен на има вида с четен показател. Значи твърдението е невярно.Задача 6
Условие
Нека е множество с . Да предположим, че съществуват единадесет подмножества на , за които за и за . Да се докаже, че и да се даде пример, при който има равенство.Решение
Числото почти не играе роля в оценката. Да означим елементите на обединението с , и нека е броят на множествата , в които участва . ТогаваОт друга страна, ако броим по двойки множествата , в които се среща един и същ елемент, получавамеПонеже , оттук следваПо неравенството на Коши-ШварцследователноТочно това е исканото, защото е размерът на обединението. За пример с равенство вземаме като обединение всички триелементни подмножества на ; те са . Ако държим самото множество да има точно елемента, добавяме още произволни елемента, които не участват в нито едно . Нека е множеството от всички триелементни подмножества, които съдържат . Тогаваа за множеството се състои от триелементните подмножества, съдържащи едновременно и , така че третият елемент може да се избере по начина. Получаваме равенство.2012
5 задачиЗадача 1
Условие
Да се намерят всички цели числа със следното свойство: измежду всеки положителни реални числа , за които съществуват три, които са дължини на страни на остроъгълен триъгълник.Решение
Отговорът е: всички . Нека и са числата на Фибоначи. Ще използваме простия факт, че тогава и само тогава, когато . Това се проверява директно за първите стойности: , а и ; за индукцията дава Нека първо и да допуснем противното: няма три от числата, които да са страни на остроъгълен триъгълник. Подреждаме ги така, че . Тогава за всяко тройката не е остроъгълна, следователно Оттук по индукция получаваме за всички . В частност . От условието на задачата обаче , затова , което противоречи на . Остава да покажем, че за свойството не е вярно. Вземаме Тогава и , така че условието е изпълнено. Но ако , то следователно тези три числа не могат да бъдат страни на остроъгълен триъгълник. Значи точно работят.Задача 2
Условие
Окръжност е разделена на равни дъги от точки. Точките са оцветени в четири цвята така, че точки са червени, са зелени, са сини, а останалите са жълти. Да се докаже, че могат да се изберат по три точки от всеки цвят така, че четирите триъгълника, образувани от избраните точки с един и същи цвят, да са конгруентни.Решение
Ще използваме ротации и осредняване. Разглеждаме -те нетъждествени ротации на окръжността и броим колко червени точки попадат върху зелени. При случайно избрана такава ротация всяка фиксирана червена точка попада върху зелена с вероятност . Следователно математическото очакване на броя съвпадения е По принципа на Дирихле съществува ротация, при която поне червени точки попадат върху зелени точки. Така намираме червен -ъгълник и зелен -ъгълник, които са образи един на друг при ротация. Сега вземаме този червен -ъгълник и го сравняваме със сините точки. Изключваме двете ротации, които дават вече намерените червена и зелена конфигурация, и разглеждаме останалите ротации. По същата сметка очакваният брой попадения върху сини точки е Следователно можем да изберем червен, зелен и син -ъгълник, които са ротационни образи един на друг. Накрая повтаряме аргумента с жълтите точки. От -те допустими ротации очакваният брой попадения е затова съществуват поне попадения. Получаваме по три точки от всеки от четирите цвята, като четирите тройки са ротационни образи на една и съща тройка. Следователно образуваните четири триъгълника са конгруентни.Задача 3
Условие
Определете за кои цели числа съществува безкрайна редица от ненулеви цели числа, такава че за всяко положително цяло число е изпълненоРешение
Отговорът е: всички . За равенството става . Оттук рекурентно получавамекоето е невъзможно за ненулеви цели числа при всички : числото би трябвало да се дели на произволно големи степени на . Нека сега . Ще построим напълно мултипликативна редица, тоест за всички положителни цели . Тогава , а условието за всяко ще следва от едно-единствено равенство:така че е достатъчно да изберем стойностите върху простите числа така, чеПърво разглеждаме . По постулата на Бертран съществуват прости числа и , за коитоТогава , , , , и . Полагаме за всяко просто число . Остава да изберем ненулеви цели стойности за и . В сумата единствените членове, които могат да се различават от обикновената сума , са кратните на и кратното . Понеже , кратните на сред са само , евентуално , евентуално . Съответно трябва да решим едно от трите линейни уравненияилиспоред това дали , само , или само . Във всеки случай коефициентът пред е взаимнопрост с , тъй като е просто и е различно от , , . По лемата на Безу има цели решения; понеже решенията образуват безкрайна аритметична прогресия, можем да изберем решение, при което и , и са ненулеви. Това дава търсената напълно мултипликативна редица за всички . Остават малките стойности . Те се проверяват с явни напълно мултипликативни редици. За вземаме . За вземаме . За вземаме . За вземаме . За вземаме . За можем да използваме предишната конструкция с ; например изборът и за останалите прости дава . Лесна проверка показва, че във всеки от изброените случаи сумата е нула. Следователно нужната редица съществува точно за .Задача 4
Условие
Да се намерят всички функции , за които за всяко положително цяло число и дели за всички различни положителни цели числа .Решение
Отговорът е: , и тъждествената функция . Те очевидно удовлетворяват условията; ще докажем, че други няма. От и следва . Освен това, прилагайки делимостта към и , получаваме Разглеждаме случаите според и . Ако , то за имаме Числото е четно, а ако , тогава е нечетно, което е невъзможно. Значи за всички , а от следва и . Получаваме . Ако , то от следва . После за имаме Делителят се дели на , а ако , то , невъзможно. Така за всички , тоест . Остава случаят и . От лесно се получава . Ще докажем по индукция, че за всички . Да приемем, че . Тогава откъдето и Последното изключва , защото произведението би се деляло на . Значи . От първоначалната делимост с получаваме . Единственото число между и , което е по модул , е . Следователно и индукцията е завършена.Задача 6
Условие
За цяло число нека са реални числа, за които За всяко подмножество дефинираме ; ако , то . Да се докаже, че за всяко положително число броят на множествата , за които , е най-много . Да се намерят случаите на равенство.Решение
Избираме случайно подмножество чрез независими случайни величини , където , и пишем Тогава Понеже и , получаваме От следва , а от получаваме Следователно Всяко множество се сдвоява с допълнението си, като . Затова сумата на само по множествата с е точно половината от общата сума, тоест Ако е броят на множествата с , то всяко от тях дава принос поне , следователно което е търсената оценка. Да разгледаме равенството. То изисква всяка положителна стойност на да е точно ; иначе или ще има положителна стойност под , която не се брои, или някоя броена стойност ще дава принос по-голям от . Значи всички суми принадлежат на множеството . В частност всяко е едно от тези три числа. Не може да има две положителни , защото сумата им би била , и аналогично не може да има две отрицателни. Понеже общата сума е и сумата от квадратите е , трябва, след пермутация, и тогава . Лесно се проверява, че точно тези случаи наистина дават равенство.2013
3 задачиЗадача 2
Условие
За положително цяло число са разположени равноотдалечени точки върху окръжност. Една от тях е означена с , а в е поставен маркер. На всеки ход маркерът може да се премести напред по часовниковата стрелка или до следващата точка, или до точката след нея. Така има общо различни хода, по два от всяка точка. Нека е броят на начините маркерът да обиколи окръжността точно два пъти, започвайки и завършвайки в , без да повтаря ход. Докажете, че за всяко .Решение
Ще заменим движението по окръжността с движение по множествотокато започваме от , завършваме в и правим скокове с дължина или . Нека , ако точката е посетена, и иначе. Записваме тези данни в матрицатаИмаме , а горният десен и долният ляв елемент са равни. Условието, че скоковете са само с дължина или и че никой ход не се повтаря, е еквивалентно на това в матрицата да не се срещат съседни подматрици от видоветеЗатова можем да гледаме само трите възможни стълбови вектораВалидните матрици са точно редици от такива стълба, в които няма два съседни еднакви стълба, и граничното условие е едно от следните две:Фиксираме началния стълб. Нека е броят на редиците от стълба, които завършват в един предварително фиксиран различен от началния стълб, а е броят на редиците, които завършват в началния стълб. Тогава по симетрияОсвен това имаме рекурентните зависимостиНаистина, за да завършим в фиксиран различен стълб, предишният стълб може да е началният или третият стълб; а за да завършим в началния стълб, предишният стълб може да бъде който и да е от двата различни стълба. Ще използваме още, чеТова може да се докаже от рекурсиите и началните стойности , , но има и директно броене: след първия стълб всеки от следващите стълба има точно два избора, защото не може да бъде равен на предишния. Лявата страна брои всички възможни крайни стълбове - двата различни дават по , а началният дава . Накрая получавамеСлед замяна на с това е точно за всяко .Задача 4
Условие
Да се намерят всички реални числа , за коитоРешение
Нека , , , където . Поради симетрия можем да приемем, че , така че и минимумът вляво е първият член. Трябва да имаме Ще докажем неравенството в правилната посока и после ще проследим кога има равенство. Имаме като равенство има точно когато . Следователно От друга страна, след повдигане на квадрат, е еквивалентно на тоест на Равенство във второто неравенство има точно когато . Значи равенство в първоначалното уравнение е възможно и необходимо точно при условията след евентуална пермутация на . Нека и за някое . Тогава Следователно всички решения са всички пермутации на тройките Обратно, всяка такава тройка удовлетворява двете условия за равенство, затова действително е решение.Задача 5
Условие
Нека и са положителни цели числа. Да се докаже, че съществува положително цяло число , така че и да имат едни и същи ненулеви цифри в десетичния си запис.Решение
Ще построим множител , който върши работа. Първо ще намерим положителни цели числа и такива, че , и Нека и . Избираме толкова голямо, че Тогава и , понеже се дели на по-високи степени на и от тези, които делят . Поставяме Получаваме , , а от следва исканото сравнение . Понеже е взаимно просто с , съществува положително цяло число , за което . Нека Тъй като , произведенията и са по-малки от , затова можем да ги разглеждаме като блокове от точно десетични цифри, допускайки водещи нули. Умножавайки сравнението по , получаваме Сравнение по модул има точно следния смисъл за блокове от цифри: умножението по премества цифрите циклично, а умножението по прави такива циклични премествания. Значи и имат едни и същи цифри като -цифрени блокове, евентуално в различен цикличен ред и с водещи нули. След премахване на водещите нули, нулите може да се появяват на различни места, но всички ненулеви цифри са едни и същи. Следователно търсеното число е .2014
4 задачиЗадача 1
Условие
Нека са реални числа, за които , и всички корени на полинома са реални. Да се намери най-малката възможна стойност на произведениетоРешение
Отговорът е . Тази стойност се достига при : тогава произведението е , а за полинома имаме , , следователно . Остава да докажем, че по-малка стойност е невъзможна. Ще покажем тъждеството Нека . Понеже корените на са , получаваме От друга страна Следователно , както твърдяхме. От условието следва , затова Така най-малката възможна стойност е .Задача 2
Условие
Да се намерят всички функции , за които за всички с .Решение
Отговорът е и ; директна проверка показва, че и двете функции удовлетворяват условието. Слагаме . Получаваме Първо ще докажем, че . Ако , избираме просто число , което не дели , и полагаме . От последното равенство следва, че , следователно , а тогава и . Връщайки се в равенството, получаваме , противоречие. Значи . Тогава от същото равенство следва за всяко . Аналогично получаваме и . Ако за някое имаме , след изваждане и разлагане се стига до . Замяната в двете равенства дава което е невъзможно. Следователно е четна и , тоест за всяко е изпълнено Да допуснем, че съществува ненулево цяло число с . Ще докажем, че тогава . Полагаме в условието и получаваме за всяко , следователно е нула върху всички четни цели числа. Сега полагаме и имаме Ако за някое нечетно е вярно , то При това би наложило за произволно , абсурд. Значи за всяко . Понеже е нечетно, , така всички цели числа с изключение евентуално на имат стойност . Но тогава дава . Остава възможността , а всички други стойности да са ; тя се изключва, като заместим и в първоначалното равенство. Следователно, ако някъде има ненулево с , то . В противен случай за всяко трябва да е , а и , тоест . Така решенията са точно двете посочени функции.Задача 3
Условие
Да се докаже, че съществува безкрайно множество от точки в равнината със следното свойство: за всеки три различни цели числа точките лежат на една права тогава и само тогава, когато .Решение
Даваме явна конструкция. За всяко цяло число полагаме Ще използваме следния факт: ако са различни реални числа, то точките , и са колинеарни тогава и само тогава, когато . Наистина, по формулата за лице с детерминанта трите точки са колинеарни точно когато Този детерминант е равен на Понеже са различни, първите три множителя са ненулеви, затова колинеарността е еквивалентна на . Сега за вземаме Тогава . Следователно лежат на една права точно когато , както се искаше.Задача 6
Условие
Да се докаже, че съществува константа със следното свойство: ако са положителни цели числа и за всички , тоРешение
Нека . Първо ще докажем твърдението за достатъчно големи ; накрая ще намалим константата , за да покрием и крайно многото малки стойности на . Разглеждаме таблица с клетки , където . Във всяка клетка избираме едно просто число , което дели . Основното твърдение е, че за големи поне половината клетки са запълнени с прости числа, по-големи от . Наистина, за фиксирано просто броят на клетките, в които може да се появи , е най-много защото трябва едновременно да дели някое от числата и някое от числата . Следователно броят на клетките, които могат да бъдат запълнени с просто , е най-много Последната сума е където сумираме по простите . Имаме , а ако , то и по теоремата за простите числа. Затова за достатъчно голямо малките прости числа покриват по-малко от клетки. Следователно поне половината клетки съдържат избрано просто число, по-голямо от . Тогава в някой стълб има поне такива клетки. Всички съответни прости числа делят едно и също число . Освен това те са различни: ако едно и също просто делеше и , и с , то би деляло , което е възможно само при . Следователно Понеже , оттук за достатъчно голямо следва за някоя положителна абсолютна константа . Същият аргумент, приложен към редовете вместо към стълбовете, дава след евентуално още едно намаляване на . Остава само да се погрижим за крайно многото малки стойности на , които не попадат в асимптотичния аргумент. Намаляваме достатъчно, така че неравенството да е вярно и за тях. Така получаваме исканото2015
5 задачиЗадача 1
Условие
Да се реши в цели числа уравнението .Решение
Поставяме Тогава са с еднаква четност и , . Уравнението става Тъй като лявата страна е цяло число, от следва . Нека . След умножение и опростяване получаваме Следователно трябва да е квадрат на нечетно число, да кажем . Обратно, всеки такъв избор на нечетно дава и откъдето За нечетно тези числа са цели, така че получаваме всички решения. Ако запишем , по-чистата форма е за произволно , както и двойката с разменени координати. Това са точно всички целочислени решения.Задача 3
Условие
Нека , където . Всяко от -те подмножества на се оцветява в червено или синьо; оцветява се самото подмножество, а не отделните му елементи. За всяко означаваме с броя на сините подмножества на . Да се намери броят на оцветяванията, за които за всеки две подмножества е изпълненоРешение
Отговорът е . Нека за дадено оцветяване разгледаме носителя Едното оцветяване, при което всички подмножества са червени, очевидно работи. За всяко друго оцветяване носителят не е празен. Ако са в него, то лявата страна в условието е положителна, следователно и , и са в носителя. Освен това носителят е нагоре затворен: ако е в него и , то всяко синьо подмножество на е синьо подмножество и на , така че . Затова носителят има вид за някое фиксирано . Остава да преброим оцветяванията с такъв носител. Първо разглеждаме случая , тоест е синьо. Тогава изборът кои едноелементни множества са сини определя всичко: ако тези елементи образуват множество , единствената възможност е сини да са точно подмножествата на . Тогава и условието следва от тъждеството . Единствеността се доказва индуктивно, защото от стойностите на за по-малки множества се възстановява цветът на следващото множество. Следователно при пълен носител има оцветявания. В общия случай, ако носителят е , след премахване на задължителните елементи на получаваме оцветяване с пълен носител върху . Ако , тези оцветявания са , а изборите на са . Следователно броят на нетривиалните оцветявания е Заедно с изцяло червеното оцветяване получаваме .Задача 4
Условие
Стив поставя неразличими камъчета върху квадратчетата на решетка . Върху едно квадратче може да има произволно голяма купчина. След това той може да прави ходове с камъчета по следния начин. Избират се четири квадратчета, които са върхове на правоъгълник, тоест имат координати , , , за , , . Един ход премахва по едно камъче от и и ги премества съответно в и , или обратно. Две разположения са еквивалентни, ако едното може да се получи от другото чрез поредица от такива ходове. Колко различни нееквивалентни начина има Стив да постави камъчетата?Решение
Отговорът е За всяко разположение записваме броя камъчета във всеки ред и във всеки стълб. Един ход само разменя две камъчета по диагоналите на правоъгълник, затова тези числа не се променят. Значи двойката от редови и стълбови суми е инвариант. Броят на възможните редови суми е броят на слабите композиции на в части, тоест ; същото важи и за стълбовите суми. Така получаваме най-много класа. Остава да докажем, че този инвариант е пълен и че всяка такава двойка суми се реализира. Мислим за камъчетата като за мултимножество от наредени двойки , където е редът, а е стълбът. Фиксираните редови и стълбови суми са точно две мултимножества и от координати. Дадено разположение е получено, като съчетаем елементите на с елементите на по някакъв ред. Един ход с камъчета просто разменя две различни -координати между две камъчета с различни -координати; такива размени пораждат всяка пермутация на спрямо (ако редовете съвпадат, размяната не променя разположението). Следователно всички разположения с една и съща сигнатура са еквивалентни. Накрая, всяка сигнатура се реализира: подреждаме елементите на и в произволен ред и поставяме камъче в за всяко . Така класовете са точно колкото двойките редови и стълбови суми.Задача 5
Условие
Нека са различни положителни цели числа, за които Да се докаже, че е съставно число.Решение
Да допуснем противното: е просто число. От получаваме Понеже и , след заместване следва тоест Имаме : наистина, . Значи , откъдето . Следователно Аналогично, разменяйки ролите по симетричния начин, получаваме и Така Първото неравенство дава а второто дава или еквивалентно От равенството следва, че и имат един и същи знак, защото функцията е строго растяща за положителни . Ако и двете са положителни, последното неравенство е невъзможно; ако и двете са отрицателни, първото е невъзможно. Случаят и двете да са нули би дал и , противоречие с различността. Полученото противоречие показва, че не е просто, а понеже е по-голямо от , то е съставно.Задача 6
Условие
Фиксираме и нека е мултимножество от положителни цели числа. Нека , като елементите се броят с кратност. Да предположим, че за всяко мултимножеството съдържа най-много числа. Докажете, че съществуват безкрайно много , за които сумата на елементите на е най-много .Решение
За краткост ще означава броя на елементите на мултимножеството , с кратности. Полагаме Ще допуснем противното, а именно че твърдението е невярно за всички достатъчно големи . Тогава за тези имамеСледователно за всички достатъчно големи , да кажем за , е изпълнено С други думи, всеки достатъчно късен член е по-малък от средното аритметично на всички предишни членове. Остава да използваме целочисленото условие. За всяко разликата се различава от на разстояние поне защото е цяло неотрицателно число. Значи всеки два съседни члена на редицата се различават по абсолютна стойност поне с . Нека е средното аритметично на числата . От предишното неравенство веднага следва по индукция, че за всяко : ако всички предишни членове са по-малки от , тогава и средното им е по-малко от . Но щом съседните членове се различават поне с , за имаме Следователно средното аритметично на достатъчно дълга начална част на редицата пада под ; крайните първи членове вече не могат да компенсират безкрайната опашка от двойки със средно под . Отново от неравенството получаваме, че за някое е вярно Повтаряме същия аргумент. След достатъчно далечен индекс всички са по-малки от , после от , и така нататък. След краен брой повторения получаваме за всички достатъчно големи , което противоречи на . Следователно допускането е невярно и желаното неравенство за сумата на елементите на е изпълнено за безкрайно много стойности на . Забележка. Условието е съществено; при например мултимножеството показва, че заключението може да се провали.2016
5 задачиЗадача 1
Условие
Нека е редица от различни непразни подмножества на множество . Всеки две съседни множества и са непресичащи се и обединението им не е цялото множество , тоест и за всички . Да се намери най-малкият възможен брой елементи на .Решение
Отговорът е . Първо, понеже са нужни различни непразни подмножества, имаме , откъдето . Ще покажем, че е невъзможно. Ако , всяко подмножество с поне елемента може да бъде съседно само на подмножество с най-много елемента: съседът трябва да е непресичащ се с него, а ако запълни целия допълнителен остатък, обединението ще бъде . Подмножествата с размер или са Затова в редицата може да има най-много подмножества с размер поне . Подмножествата с размер са само , така че общият брой членове е най-много , противоречие. Остава конструкция за . Ще построим за всяко редица с дължина от непразни различни подмножества на със същото свойство. За работи редицата Да предположим, че имаме такава редица за . Изтриваме един неин член, така че дължината да стане четна, правим две копия на получената редица, поставяме между двете копия и после добавяме елемента към множествата на нечетните позиции. Съседните множества остават непресичащи се, защото се добавя само към едното от всеки две съседни множества; обединението им не е цялото ново множество, защото старото обединение е пропускало стар елемент, а около средното множество съседът не е цялото старо множество. Двете копия също не създават повторения, понеже едното копие получава в точно обратните позиции спрямо другото. Така получаваме редица с дължина . При тя има члена, от които можем да вземем първите .Задача 2
Условие
Да се докаже, че за всяко положително цяло число числото е цяло.Решение
Достатъчно е да докажем, че показателят на всяко просто число в разлагането на даденото число е неотрицателен. По формулата на Льожандр показателят на в е Следователно е достатъчно за всяка степен на просто число да имаме Тъй като двете страни са цели числа, стига да докажем малко по-силното неравенство със строг запас : Ако означава дробната част на , това е равносилно на Но е остатъкът на при деление на . Сумата от остатъците на по модул е не по-голяма от сумата от остатъците на . Наистина, ако и , разликата между втората и първата сума е при и при . Понеже , последното веднага дава исканото строго неравенство. Значи всеки прост показател е неотрицателен и числото е цяло.Задача 4
Условие
Да се намерят всички функции , за които за всички реални числа и е изпълненоРешение
Отговорите са и ; директна проверка показва, че и двете функции работят. Поставяйки , получаваме . После при имаме , а след замяна на с получаваме и . Следователно е четна функция. Сега поставяме . Понеже и е четна, следва Значи за всяко реално е вярно, че или , или . Ще докажем още, че При началното уравнение дава Ако , то , откъдето чрез контрапозиция следва . За обратната посока, ако , предишната алтернатива дава , а вече доказаната посока чрез контрапозиция дава . Това е точно контрапозицията на . Комбинирайки тази еквивалентност с алтернативата по-горе, получаваме за всяко , че е или , или . Ако няма ненулево с , тогава веднага за всички . Нека сега има и . Ще докажем, че тогава . Нека е произволно реално число; поради четността можем да приемем , а случаят вече е ясен. От еквивалентността за нулите получаваме за всяко , затова избираме . Вземаме така че , и . След заместване в началното уравнение получаваме Всички стойности на са неотрицателни, а , следователно първият множител е положителен и оттук . Значи всяко е нула на , тоест .Задача 5
Условие
Равностранен петоъгълник е вписан в триъгълник така, че , и . Нека е пресечната точка на правите и . С означаваме ъглополовящата на . Докажете, че , където е центърът на описаната окръжност на триъгълника , а е инцентърът на триъгълника .Решение
Първо решение, с комплексни числа. Всъщност е достатъчно да имаме и . Работим с комплексни числа така, че описаната окръжност на да е единичната окръжност с център , като без ограничение върховете са подредени обратно на часовниковата стрелка. Нека са комплексните числа на средите на дъгите , , съответно; тогава инцентърът има посока от . Нека е общата дължина . Понеже и , получавамеАналогичноКато съберем трите равенства, намирамеПонеже , векторът е по външната ъглополовяща на ъгъла, образуван от правите и , и следователно е перпендикулярен на . От друга страна умножението по завърта на , така че е успоредно на . Но има същата посока като , следователно . Второ решение, с тригонометрия, от Danielle Wang. Нека и . Да нормализираме страната на равностранния петоъгълник до и да използваме стандартните означения , , . Ще разгледаме случая ; другият е симетричен. От проекции върху правата имамеПонеже също , следваОт синусовата теорема в триъгълниците и получавамеа оттук, използвайки ,Формулите за сума и разлика даватследователноПравата сключва с ъгъл . Ако правата пресича под ъгъл , токъдето и са съответно радиусите на вписаната и описаната окръжност на . Затова остава да проверимСлед заместване и това се свежда точно докоето е стандартната формула на Карно за триъгълник. Следователно .Задача 6
Условие
Дадени са цели числа и , като . Играете следната игра срещу зъл магьосник. Магьосникът има карти; за всяко има две карти с надпис . Първоначално магьосникът поставя всички карти с лице надолу в редица, в неизвестен ред. На всеки ход можете да посочите произволни карти. Магьосникът обръща тези карти с лице нагоре. Ако някои две от тях съвпадат, играта приключва и печелите. Иначе трябва да погледнете настрани, докато магьосникът произволно размества избраните карти и после отново ги обръща с лице надолу. След това е ваш ред. Казваме, че играта е печеливша, ако съществуват положително цяло число и стратегия, която гарантира победа за най-много хода, независимо как отговаря магьосникът. За кои стойности на и играта е печеливша?Решение
Играта е печеливша точно когато . Първо нека . Последователно питаме за интервалите от позиции Ако на някой ход се появят две еднакви карти, вече сме спечелили. Ако това не стане, всеки отговор съдържа различни надписа. Сравнявайки видените надписи в първия прозорец с надписите на общите позиции при следващия прозорец, определяме надписа на картата, която напуска прозореца. Това остава вярно и когато двата пълни прозореца имат един и същ набор от надписи, защото общите позиции пак показват точно кой надпис е излязъл и после е заместен от същия надпис. Така научаваме надписите на карти, които повече няма да бъдат местени. Понеже , имаме , следователно сред тези карти има две с еднакъв надпис. На следващ ход посочваме тези две карти заедно с произволни още карти и печелим. Остава да покажем, че при няма гарантирана победа. След първия ход, ако играчът не е спечелил, избраните карти имат всички различни надписа, а останалите карти също имат по една карта от всеки надпис. Магьосникът може да поддържа следната неопределеност: във всяка от двете половини редът на надписите е напълно неизвестен за играча. Ако играчът избере само карти от една от половините, той не може да получи съвпадение, защото в нея има по една карта от всеки надпис. Ако избере част от едната и част от другата половина, магьосникът може да е подредил неизвестната половина така, че избраните надписи от едната страна да са точно допълнение на избраните надписи от другата; тогава отново няма съвпадение. След показването той размества избраните карти и същата неопределеност се запазва. Значи при магьосникът може да избягва победата неограничено дълго, а играта не е печеливша.2017
3 задачиЗадача 1
Условие
Да се докаже, че съществуват безкрайно много двойки взаимно прости положителни цели числа , за които дели .Решение
Ще дадем явно безкрайно семейство. За всяко цяло поставяме Тогава и така че числата са взаимно прости. Нека . Понеже , получаваме защото е нечетно. Но , а което се дели на . Следователно , откъдето . Така всяко дава допустима двойка , а тези двойки са безкрайно много.Задача 2
Условие
Нека е колекция от положителни цели числа, не непременно различни. За всяка последователност от цели числа и всяка пермутация на наричаме -инверсия на двойка членове с , за която е изпълнено едно от условията Да се докаже, че за всеки две последователности от цели числа и и за всяко положително цяло число броят на пермутациите на с точно -инверсии е равен на броя на пермутациите с точно -инверсии.Решение
Ще докажем, че за фиксиран избор на генериращата функция където е броят -инверсии, всъщност не зависи от . Броим пермутациите с кратност: ако например мултимножеството е , то имаме пермутации на трите дадени позиции. Нека различните стойности в мултимножеството са а е броят появявания на , така че . За обикновените инверсии е стандартно, че генериращата функция е където . Това се вижда, като първо разграничим леко равните елементи и получим , а после за всяка група от равни елементи премахнем вътрешните инверсии, което дели на и умножава по . Сега доказваме по индукция по , че същата формула важи за всеки избор на . Нека първият праг лежи между и , тоест , като допускаме или . Ако първият член на пермутацията е с , тогава -инверсиите, които използват този първи член, са точно Ако , броят им е След избора на първия член остава същата задача с едно по-малко появяване на , затова по индукционното предположение получаваме рекурсията Делим тази рекурсия на явната формула за . От остава да се провери тъждеството Двете суми телескопират съответно до и , така че тъждеството е вярно. Следователно за всяко , а коефициентът пред е независим от . Това доказва твърдението и за всяка друга последователност .Задача 6
Условие
Да се намери най-малката възможна стойност на ако са неотрицателни реални числа и .Решение
Отговорът е . Тази стойност се достига например при и при цикличните му размествания. Основната оценка е допирателната права към функцията при : за всяко имаме защото след умножение с положителното това е еквивалентно на Прилагаме тази оценка циклично и получаваме Но тъй като . Следователно Равенство има при : тогава ненулевите членове дават Значи най-малката възможна стойност е точно .2018
6 задачиЗадача 1
Условие
Нека са положителни реални числа, за които . Да се докаже, чеРешение
Без ограничение нека . Понеже условието и неравенството са хомогенни, можем да мащабираме така, че . Тогава трябва да докажема условието ставаПоставяме . Тогава и исканото неравенство се свежда доСлед пренасяне това е точнокоето е вярно за . Следователно първоначалното неравенство е доказано. Равенство настъпва, когато , тоест при нормировката имаме и , а след това можем да върнем мащаба. Изборът на като минималното число е единствената загуба на общност; ако минимумът се достига при друг член, просто преименуваме променливите.Задача 2
Условие
Да се намерят всички функции , за коитоза всички с .Решение
Ще докажем, че всички решения саТези функции се проверяват директно. Нека , , , където . Тогава уравнението е еквивалентно наДефинираме чрезПолучавамеза всички положителни с . Оттук следва, че удовлетворява уравнението на Йенсен върху интервалите, където то има смисъл: ако , тоТъй като е ограничена отдолу, стандартният извод за уравнението на Йенсен дава, че е афинна: . Замествайки , получаваме , тоестПонеже има положителни стойности върху , същото важи за върху , откъдето се получава . Връщането към дава точно посоченото семейство.Задача 3
Условие
Нека е цяло число и нека са всички положителни цели числа, по-малки от и взаимно прости с . Да се предположи, че всеки прост делител на дели и . Да се докаже, че делиза всяко положително цяло число .Решение
За некаЩе докажем по-силното твърдение: ако , тоза всяко . Прилагано към простите , които делят , а по условие делят и , това веднага дава . Първо разглеждаме . За нечетно вземаме примитивен корен по модул и получаваме геометрична прогресияАко , знаменателят в сумата на прогресията не се дели на , така че сумата е по модул . Ако , лемата за повдигане на показателя дава точно поне множителя . За случаят с нечетно се получава чрез сдвояване на и , а при четно се използва, че поражда квадратичните остатъци по модул . Ще използваме и следствие: за всички и просто е вярнокоето следва от предишния абзац, като отделим членовете, делящи се на , и приложим индукция. Сега добавяме простите делители на един по един. Да предположим, че твърдението е доказано за , и да разгледаме . Ако , тоСлед разлагане с бинома получавамеПървият член носи вече наличните множители от и допълнителните от , а във всеки член на сумата следствието дава множителя, докато добавя поне още един множител , когато е нужно. Ако , формулата е същата без изваждането на и няма нов множител на за покриване. Така индукцията доказва силното твърдение, а оттам и задачата.Задача 4
Условие
Нека е просто число и нека са цели числа. Да се докаже, че съществува цяло число , за което числатадават поне различни остатъка при деление на .Решение
Достатъчно е да разгледаме . За всяко такова построяваме граф с върхове , като свързваме и тогава и само тогава, когатоЗа фиксирана двойка това сравнение определя единствено по модул , понежеСледователно всяко ребро се появява в точно един от графите . Общо има ребра, така че по принципа на Дирихле някой граф има най-многоребра. Всеки граф с върха и ребра има поне свързани компоненти, следователно този граф има понесвързани компоненти. В една свързана компонента всички съответни числа имат един и същ остатък, а различните компоненти могат само да увеличат броя на различните остатъци. Значи за избраното има поне , в частност поне , различни остатъка.Задача 5
Условие
Нека е изпъкнал вписан четириъгълник с , и . Окръжността, описана около , пресича правата в точките и , а окръжността, описана около , пресича правата в точките и . Да се предположи, че са колинеарни в този ред, както и в този ред. Ако , да се докаже, че .Решение
Ще използваме точка на Микел и теоремата на Пап. Първо доказваме две прости наблюдения. По степен на точката имамеследователно самопресичащият се четириъгълник е вписан. Освен това лежи на , защото с насочени ъглиНека . От стандартното свойство на точката на Микел за пълния четириъгълник с върхове по правите , , , следва, че е точката на Микел и че е петата на перпендикуляра от към . Затова , а понеже лежи на , получаваме . Остава да свържем с дадената точка . Прилагаме теоремата на Пап към двете колинеарни тройки и . Трите пресечни точки на съответните противоположни страни лежат на една права; в нашите означения това са , и . Следователно са колинеарни. Понеже , същото важи и за , тоест .Задача 6
Условие
Нека е броят на пермутациите на , за които отношениятаса две по две различни. Да се докаже, че е нечетно за всяко .Решение
Разглеждаме пермутациите като биекции на множеството , където . Ако има исканото свойство, то и обратната пермутация го има: отношенията при обратната пермутация са реципрочните на отношенията при . Следователно пермутациите, които не са равни на обратните си, се сдвояват по двойки. За паритета на остава да преброим само инволюциите, тоест пермутациите, чиито цикли са с дължина най-много . Една такава инволюция се състои от размени на двойки и евентуално една неподвижна точка. Не може да има две неподвижни точки, защото всяка от тях дава отношение . Значи при четно получаваме перфектно съчетание на върховете на , а при нечетно - максимално съчетание с един непокрит връх. За ребро , , поставяме етикет . Инволюцията е допустима точно когато етикетите на всички ребра в съответното максимално съчетание са различни; ще наричаме такова съчетание добро. Сега въвеждаме операция върху максималните съчетания. Ако две несрещащи се ребра и имат един и същ етикет, където и , тогава , откъдето след подходящо подреждане на четирите върха. Затова можем да заменим ребрата с и пак получаваме две ребра с един и същ етикет. За дадено съчетание наричаме негови съседи всички съчетания, които се получават, като за всеки етикет изберем няколко несрещащи се двойки ребра с този етикет и извършим описаната размяна. Това отношение е симетрично и всяко съчетание е съсед на самото себе си. Да преброим броя на съседите на фиксирано по модул . Ако даден етикет се среща пъти сред ребрата на , броят начини да изберем двойки ребра с този етикет и да ги разменим еПо модул това екоето е нечетно точно когато . Умножавайки по всички етикети, получаваме: броят на съседите на , включително самото , е нечетен точно за добрите съчетания. Накрая сумираме тези бройки съседи по всички максимални съчетания. Понеже съседството е симетрично, всяка двойка различни съчетания се брои два пъти, а всяко съчетание се брои веднъж като съсед на себе си. Следователно сумата по модул е равна на броя на всички максимални съчетания. Този брой еследователно е нечетен. Но по предишния абзац същата сума по модул е точно броят на добрите съчетания по модул . Значи броят на допустимите инволюции е нечетен. Тъй като всички останали допустими пермутации се сдвояват с обратните си, заключаваме, че е нечетно за всяко .2019
5 задачиЗадача 1
Условие
Функция удовлетворява за всяко положително цяло число , където означава -кратно прилагане на . Какви са всички възможни стойности на ?Решение
Отговорът е: всяко четно положително цяло число. По-точно всички решения са функциите, които фиксират всяко нечетно число и върху четните числа действат като произволна инволюция. Така може да бъде произволно четно число, и всяка такава стойност се реализира. Първо доказваме инективност. Ако , то от условието следва значи . Сега показваме по индукция, че всяко нечетно е неподвижна точка. Ако вече са фиксирани по-малките нечетни числа, в равенството двата множителя не могат да бъдат сред тях поради инективността; следователно и двата са . Така , а ако , прилагане на условието към дава , откъдето . Следователно праща четните числа в четни числа. Нека . Тогава за четно имаме . Функцията вече фиксира нечетните числа и е инективна; същата индукция върху четните показва, че . Значи за всяко : върху четните числа е инволюция, а върху нечетните е тъждествена. Обратно, всяка такава функция очевидно удовлетворява условието.Задача 3
Условие
Нека е множеството от положителните цели числа, чието десетично представяне не съдържа цифрата . Да се определят всички многочлени с неотрицателни коефициенти, за които за всяко .Решение
Отговорът е точно очевидното семейство: константните многочлени с , многочлените и многочлените , където , и . Ще наричаме един многочлен стабилен, ако праща всяко число от отново в . Първата стъпка е редукция до мономи. Ако е стабилен, то всеки моном е стабилен: за фиксирано избираме толкова голямо, че в десетичния запис на приносите да стоят в отделни блокове, разделени с достатъчно нули. Ако някой блок съдържаше цифрата , цялото число също щеше да я съдържа. Сега разглеждаме линейния моном . От следва . Ако не е степен на , според първите му цифри може да се избере число , така че да започва с цифрата : например интервалите , , се разбиват чрез , а останалите интервали се покриват с кратките избори или с число от вида . Следователно стабилен линеен моном има коефициент . Ако е стабилен с , тогава и е стабилен. По редукцията неговият линеен член трябва също да е стабилен, следователно коефициентът трябва да е степен на , което е невъзможно при . Остава само или константа. Условието е точно това, което гарантира, че се добавя като долен десетичен блок без пренос към цифрите на , и така изброените многочлени наистина работят.Задача 4
Условие
Нека е неотрицателно цяло число. Да се намери броят на начините да се изберат множества за всички и (не непременно различни), така че и винаги когато и .Решение
Отговорът е . Първо фиксираме една гранична верига. Понеже и , по някой монотонен път от долния ляв до горния десен ъгъл елементите се добавят един по един; това дава множителя . След преименуване можем да приемем, че по горната и дясната граница множествата са стандартните начални сегменти. Остава да запълним вътрешните клетки. По-силното твърдение е следното. Ако изберем форма от клетки, затворена нагоре и наляво, тоест диаграма на Юнг, броят на допустимите частични запълвания на тези клетки е . Доказваме това с индукция по . При добавяне на нова ъглова клетка имаме локална картина с вече избрани множества и търсено множество , като , и . Пишем и . Тогава за има точно две възможности: и , и двете запазват всички включвания и правилната големина. Следователно всяка добавена клетка в диаграмата на Юнг дава независим фактор . За пълния квадрат имаме , откъдето получаваме запълвания след фиксираната граница и общо .Задача 5
Условие
Нека и са взаимно прости положителни цели числа. На дъската са написани числата и . На всяка стъпка Евън може да избере две написани числа и и да запише или тяхното средно аритметично , или тяхното хармонично средно . За кои двойки Евън може да запише числото след краен брой стъпки?Решение
Това е възможно тогава и само тогава, когато е степен на . Нека , така че началните числа са и . За невъзможността нека е нечетен прост делител на . Понеже и са взаимно прости, не дели , и получаваме . Ако две числа и са по модул , то и , и са по модул , защото и са обратими. Следователно всички числа на дъската завинаги остават по модул , а не може да се появи. Значи няма нечетен прост делител, тоест е степен на . Обратно, нека . Достатъчни са само средноаритметични операции. Чрез последователно вземане на средни аритметични можем да построим всяка двоична изпъкнала комбинация с : това е обикновено делене на интервала наполовина, повторено пъти. Избираме и . Тогава понеже . Така конструкцията е завършена.Задача 6
Условие
Да се намерят всички многочлени с реални коефициенти, такива че за всички ненулеви реални числа , удовлетворяващи .Решение
Отговорът е Първо умножаваме даденото равенство по и получаваме полиномиалното условие винаги когато . Нека разликата между двете страни е . Понеже дава реални решения за отворено множество от двойки , рационалната функция, получена след заместването, е тъждествено нула. Следователно същото полиномиално тъждество важи и над комплексните числа за всички тройки с . Вземаме комплексната тройка . Тя удовлетворява условието и дава , така че е четен многочлен. Сега вземаме и ; тогава за всяко комплексно . От тъждеството и четността на следва, че е константа. Лявата страна е втора крайна разлика на с ненулева стъпка, затова ако , нейният водещ член има степен . Щом тази разлика е константна, получаваме . Понеже е четен, имаме . Остава само да наложим условието. При равенството се свежда, след използване на , до . Така всички решения са . Обратно, пряко заместване показва, че всеки многочлен от този вид работи, защото за е валидно тъждеството Това доказва и достатъчността.2020
4 задачиЗадача 3
Условие
Нека е нечетно просто число. Цяло число се нарича квадратичен неостатък по модул , ако не дели за никое цяло число . Нека е множеството от всички с , за които и , и са квадратични неостатъци. Да се намери остатъкът по модул на произведението на елементите на .Решение
Отговорът е по модул . Работим в и пишем КО за квадратичен остатък и КНО за квадратичен неостатък. Нека е множеството от , за които и са КНО, а е множеството от , за които и са КО. Тогава са точно ненулевите , за които е КО. Разглеждаме върху . Понеже , образът лежи в . Обратно, за всяко уравнението има дискриминанта , тоест два корена и . Значи е двукратно покритие на . Умножавайки произведенията на двата прообраза, получаваме . Лявата страна е , така че след съкращаване .Задача 4
Условие
Нека са различни решетъчни точки с неотрицателни координати. Нека е броят на двойките , за които . Да се намери най-голямата възможна стойност на .Решение
Отговорът е . По-общо за точки максимумът е . Конструкцията е . Добри триъгълници са за и за , общо . За горната граница нека е най-далечната избрана решетъчна точка от началото. Ако , тя не участва в добър триъгълник, защото общият делител дели всеки детерминант . Ако , решетъчните точки с лице лежат върху двете прави , успоредни на . На всяка такава права решетъчните точки се различават с кратно на ; поради избора на най-далечна точка най-много една от всяка права може да присъства. Значи е в най-много два добри триъгълника. Изтриваме и прилагаме индукция: получаваме най-много . При това дава .Задача 5
Условие
Крайно множество от точки се нарича свръхопределено, ако и има ненулев реален многочлен от степен най-много , който минава през всички точки на . За всяко да се намери най-голямото , за което има множество от различни точки, което не е свръхопределено, но има свръхопределени подмножества.Решение
Отговорът е . За конструкция избираме различни ненулеви и точките . Цялото множество не е свръхопределено: ако многочлен от степен най-много минава през всички точки, то има корени , но не е нулев, защото . От друга страна всяко подмножество от последните точки с поне два елемента лежи върху константния многочлен , следователно е свръхопределено; техният брой е . За горната граница наричаме множество свободно, ако не е свръхопределено. Ако свободно -множество има две свръхопределени -подмножества, съответните многочлени от степен най-много съвпадат върху общи точки и по единствеността от интерполация са един и същ многочлен; тогава цялото множество би било свръхопределено. Значи всяко свободно -множество има поне свободни подмножества от размер . Низходяща индукция дава поне свободни -подмножества, откъдето свръхопределените са най-много .Задача 6
Условие
Нека и нека , са реални числа, за които сумите на всяка от двете редици са , а сумите на квадратите им са . Да се докаже, че .Решение
Нека е равномерно случайна пермутация и . От условията следва . Освен това , а при имаме , защото сумата на квадратите на е и сумата им е . Следователно, използвайки и , получаваме . Това е дисперсията. Ако и са съответно най-голямата и най-малката стойност на , всяка случайна величина в интервал с дължина има дисперсия най-много , например от . Значи . По неравенството за пренареждане максимумът е , а минимумът е . Разликата им е точно лявата страна, което доказва твърдението.2021
3 задачиЗадача 1
Условие
Външно за остроъгълния триъгълник са построени правоъгълниците , и . Да се предположи, чеДа се докаже, че правите , и се пресичат в една точка.Решение
Нека , и са описаните окръжности съответно на трите правоъгълника , и . Условието за сумата на трите ъгъла е точно насочената форма на теоремата на Микел за тези три правоъгълника: трите окръжности имат обща точка освен върховете върху страните на . Понеже лежи на окръжността на правоъгълника , имаме . Понеже лежи и на окръжността на правоъгълника , имаме . Следователно правите и са една и съща права, т.е. . Същият аргумент, приложен към другите две общи страни, дава и . Значи трите прави , и са конкурентни, както се искаше.Задача 4
Условие
Крайно множество от положителни цели числа има следното свойство: за всяко и за всеки положителен делител на съществува единствен елемент , за койтоЕлементите и може да съвпадат. Да се намерят всички възможни стойности на броя на елементите на .Решение
Отговорът е: е степен на ; ако празното множество се допуска, възможна е и стойността . Първо даваме конструкция. За произволно избираме различни прости числаи вземаме всички произведения, в които от всяка двойка е избрано точно едно просто число. Така получаваме числа. Ако е едно от тях и , то за всяка двойка избираме в същото просто число като в точно когато това просто число участва в , а иначе избираме другото просто число от двойката. Тогава , и изборът е единствен. Остава да докажем, че други размери няма. За фиксирано съответствието е биекция между елементите на и положителните делители на . Следователно за всяко . Ще покажем, че никой прост множител не може да влиза в някой елемент със степен поне . Да допуснем, че и за някое и . От биекцията за следва, че делът на елементите на , които се делят на , е , защото точно толкова от делителите на се делят на . От друга страна, съществува с , следователно дели , но не дели . Прилагайки същото броене към , получаваме, че точно половината от елементите на се делят на . Това противоречи на за . Значи всички елементи на са свободни от квадрати. Тогава за всяко броят на делителите му е , следователно е степен на . Това завършва доказателството.Задача 5
Условие
Нека е цяло число. Индексите се разглеждат по модул . Да се намерят всички положителни реални решения на систематаРешение
Единственото решение еТо се проверява непосредствено. Ще докажем, че всички четни членове са равни. От уравненията получаваме, за всеки ,НекаЗа индекс , при който , имамеЗа индекс , при който , имамеСледователноа понеже по дефиниция , получаваме . Значи редицата от четните членове е константна; нека . Тогава от горното равенство , така че . Накраяза всяко . Следователно посоченото решение е единствено.2022
6 задачиЗадача 1
Условие
Нека и са положителни цели числа. Всяка клетка на таблица е оцветена или в кехлибарено, или в бронзово, като има поне кехлибарени клетки и поне бронзови клетки. Да се докаже, че могат да се изберат кехлибарени клетки и бронзови клетки така, че никои две от избраните клетки да не лежат в един и същ ред или в един и същ стълб.Решение
Ще наричаме трансверсал избор на клетки, по една от всеки ред и по една от всеки стълб. Първо ще докажем, че съществува трансверсал с поне кехлибарени клетки. Ако изберем трансверсал равновероятно, всяка клетка попада в него с вероятност , затова очакваният брой кехлибарени клетки е поне Следователно някой трансверсал има поне кехлибарени клетки. По същия начин съществува трансверсал с поне бронзови клетки, тоест с най-много кехлибарени клетки. Остава да преминем от към . Всеки два трансверсала могат да се свържат чрез последователност от стандартни размени: избираме две избрани клетки в различни редове и стълбове и ги заменяме с другите два върха на определения от тях правоъгълник. Това запазва свойството да имаме трансверсал. При една такава размяна броят на кехлибарените клетки се изменя с най-много . В началото този брой е поне , а в края е най-много ; следователно в някой момент по пътя той е равен на или на . Ако е равен на , избраният трансверсал съдържа бронзови клетки и изхвърляме една от тях. Ако е равен на , той съдържа бронзови клетки и изхвърляме една кехлибарена клетка. И в двата случая остават точно кехлибарени и бронзови клетки, без две от тях да са в един ред или стълб.Задача 2
Условие
Нека и са фиксирани цели числа и нека . Дадени са еднакви черни пръчки и еднакви бели пръчки, всяка с дължина . От тях сглобяваме правилен -ъгълник така, че успоредните страни да имат един и същ цвят. След това чрез пренасяне на черните пръчки се образува изпъкнал -ъгълник , а чрез пренасяне на белите пръчки - изпъкнал -ъгълник . Да се докаже, че разликата между лицата на и зависи само от числата и , а не от начина, по който е сглобен правилният -ъгълник.Решение
Ще докажем, че може да се разменят съседна черна и бяла пръчка, заедно със срещуположните им успоредни пръчки, без да се променя величината , където означава лицето на многоъгълника . Такива съседни размени свързват всички допустими сглобявания с даден брой черни и бели двойки страни, така че това ще докаже инвариантността. Нека и са съответно черният и белият вектор на двете съседни страни, които ще разменяме. Нека е сумата на всички други черни вектори между и по обиколката, а - аналогичната сума за белите вектори между и . Единствената промяна в лицата идва от съответните успоредници. С означението за ориентирано лице на успоредник трябва да проверимТова е еквивалентно натоест на това и да са успоредни. Двата вектора наистина са успоредни, защото и двата са перпендикулярни на . Първо, , понеже и имат една и съща дължина. Второ, векторът свързва две срещуположни точки на описаната окръжност на правилния -ъгълник, т.е. описва диаметър. Точката, получена след изминаване на , лежи върху същата полуокръжност, затова по теоремата за вписания ъгъл имаме . Следователно и са успоредни, равенството за лицата е вярно и разликата не се изменя при размяната. Понеже всяка подредба на цветовете с черни и бели двойки страни може да се получи от всяка друга чрез такива съседни размени, разликата между лицата зависи само от и .Задача 3
Условие
Да се реши в положителните реални числа функционалното уравнениеза всички положителни реални числа и .Решение
Отговорът еТези функции се проверяват непосредствено. Ще докажем, че други решения няма. Нека означава даденото равенство, а - -кратната итерация на . Първо въвеждаме помощното твърдениеНаистина, ако , поставяме в . Тогава първият член вдясно е , а вторият е положителен, така че получаваме , противоречие. От следва за всяко . При получаваме . Освен това при и имаме . Затова можем да приложим и получаваме обратното неравенство . Следователноза всяко . Следващата стъпка е инективност. Да допуснем, че за някои . От и следва и . Сравнявайки равенствата и за и използвайки и , получавамеза всяко . Сега сравняваме и ; отново понеже , следваза всяко . Значи е периодична с период . Но тогава твърдението за произволно големи би изисквало , което е невъзможно. Следователно е инективна. От и инективността получаваме . Тогава първоначалното уравнение се опростява доПри това даваза всяко , така че за всички . Нека . Ако , от последното опростено равенство получавамеследователно . Като оставим отношението да пробягва всички положителни стойности, получаваме за всяко .Задача 4
Условие
Да се намерят всички наредени двойки прости числа , за които и са точни квадрати.Решение
Отговорът е единствено , което очевидно работи: и . Ще докажем, че други двойки няма. Случаят не дава решение, затова можем да пишем с положителни цели числа и . Имаме и . Изваждаме двете равенства и получаваме Понеже и , простото число не може да дели и затова трябва да дели . Единствената възможност е а от горното равенство следва Тогава и имат една и съща четност. Това е възможно само при . При условията стават и . Ако , тогава , невъзможно. Ако , тогава , също невъзможно. Следователно се дели на , а понеже е просто, . Получаваме единственото решение .Задача 5
Условие
Една функция ще наричаме съществено растяща, ако винаги когато са реални числа, за които и . Да се намери най-малкото цяло число със следното свойство: за произволни реални числа съществуват съществено растящи функции , такива чеза всяко .Решение
Отговорът е . По-общо, ако се замени с , отговорът е . Тъй като , това дава . Първо доказваме долната оценка. Да предположим, че , и избираме за . За всяко некаМножеството е непразно, защото сумата е . Има само непразни подмножества на , затова по принципа на Дирихле съществуват с . За всеки индекс от това общо множество условието за съществено растене дава , а за останалите индекси и двете стойности са нула. Следователно , което противоречи на . Значи непременно . Остава конструкцията при ; по-малките следват, като просто пренебрегнем излишните места. Подреждаме непразните подмножества на в стандартния рекурсивен ред, получен от двоичния отразен код на Грей. На позиция ще бъдат ненулеви точно функциите с индекси от съответното множество . Този ред има важната особеност, че конструкцията за функции се появява първо с малки стойности, после се обръща с добавен нов индекс и с много по-големи стойности. Избираме число толкова голямо, че всички дадени да са пренебрежимо малки в сравнение с последователните степени на . В първата половина използваме по индукция вече построените функции. В средната позиция даваме на първите функции много големи положителни стойности , а стойността на избираме така, че сумата да стане нужното . В последната половина повтаряме обърнатата конструкция за първите функции, но всички нейни ненулеви стойности са изместени в диапазон от много големи положителни числа; остатъкът отново се поема от . Понеже е избрано достатъчно голямо, ненулевите стойности на всяка от функциите се появяват в нарастващ ред. Така на всяко от числата сумата е точно предписаното , а всяка функция е съществено растяща върху ненулевите си стойности. Извън тези цели точки дефинираме функциите да са нула. Това не нарушава условието, понеже то сравнява само двойки точки, в които и двете стойности са ненулеви. Конструкцията завършва доказателството.Задача 6
Условие
В социалната мрежа Mathbook има потребители, като някои двойки от тях са приятели. В Mathbook приятелството е взаимно и веднъж възникнало, остава валидно. От този момент нататък Mathbook позволява ново приятелство между двама потребители само ако те имат поне двама общи приятели. Кой е най-малкият брой приятелства, които трябва вече да съществуват, така че да е възможно в крайна сметка всеки потребител да стане приятел с всеки друг?Решение
Ще решим по-общата задача за потребители. Отговорът еа за това е . В езика на графите започваме с граф върху върха. Разрешената операция е: ако имаме цикъл , можем да добавим двата му диагонала, т.е. да допълним този до . Търсим най-малкия брой начални ребра, при който чрез такива операции може да се стигне до . Първо даваме конструкция. Ако е четно, започваме с ребро и построяваме копия на , всяко от които използва реброто . Всяко копие добавя две нови върхови точки и три нови ребра, така че общият брой ребра е . Допълваме първо всички тези четириъгълници до . След това всеки два върха, които не са и , вече имат общи приятели и , така че можем да добавим ребрата между тях и да завършим до . Ако е нечетно, правим същата конструкция за върха и добавяме още един връх, свързан с и ; броят на ребрата става , а допълването е аналогично. Остава долната оценка. Ще опишем алгоритъм, който добавя всички ребра, които могат да бъдат принудени, докато повече няма възможна операция. Поддържаме списък от клики и етикетиране на ребрата: всяко ребро носи етикета на една клика от , която го съдържа. В началото всяко начално ребро е отделна клика и носи собствения си етикет. Когато има цикъл , чиито четири страни не всички имат един и същ етикет, вземаме всички клики, чиито етикети се появяват по тези четири страни, и нека е обединението на върховете им. Добавяме всички ребра, нужни за да стане клика, и сливаме тези клики в една нова клика . Ребрата с използваните етикети, както и новите ребра, получават етикета . Спираме, когато всеки има един и същ етикет по четирите си страни; тогава вече няма операция, която да създаде нова информация. Ако началният граф изобщо може да се допълни до , този алгоритъм трябва накрая да има една единствена клика . За клика нека е броят на началните ребра, които в момента носят етикета . Твърдим, че през целия алгоритъмВ началото това е вярно, защото всяка клика е едно ребро: . При сливане на две, три или четири клики стойността на е сумата от старите стойности. От друга страна, при сливането върховете от избрания вече се срещат в старите клики с припокриване: при четири слети клики има поне четири повторения на върхове, при три слети клики - поне три, а при две слети клики - поне две. Следователно размерът на новата клика е достатъчно по-малък от сумата на старите размери, за да се запази неравенството ; в случаите с две или три клики дори получаваме запас. Ако графът е допълним до , накрая алгоритъмът дава клика . Тогава броят на началните ребра е поне . Понеже броят на ребрата е цяло число, получаваме долната оценка . Заедно с конструкцията това доказва формулата, а при отговорът е .2023
6 задачиЗадача 1
Условие
В остроъгълен триъгълник нека е средата на . Нека е петата на перпендикуляра от към . Да предположим, че описаната окръжност на триъгълника пресича правата в две различни точки и . Нека е средата на . Да се докаже, че .Решение
Нека е петата на височината от към . Ще докажем, че е образът на при централна симетрия спрямо . Понеже , четириъгълникът е вписан. Прилагаме степен на точката спрямо окръжностите и , като дължините по правата се вземат насочено: Тъй като е среда на , имаме , следователно с правилна посока по правата . Значи е среда на . Сега в триъгълника точките и са среди съответно на и , затова . Но , следователно . Понеже е средата на , правата през , перпендикулярна на , е симетралата на . Точката лежи на нея, откъдето .Задача 2
Условие
Да се реши в положителните реални числа функционалното уравнениеза всички положителни реални числа и .Решение
Отговорът еПроверката е непосредствена: ако , тогаваНека означава даденото равенство. Първо ще докажем, че не намалява. Да допуснем противното: нека , но . ИзбирамеТогава . От и левите страни са равни, следователнокоето е невъзможно, понеже и . Значи е ненамаляваща. Поставяме . От получавамеза всяко . Следователно стойностите на върху аритметичните прогресии със стъпка растат с точно . Заедно с ненамаляването това дава линейна оценка с ограничена грешка:където . Наистина, ако , то , а двете крайни стойности се различават само с . По-точно същото разсъждение може да се приложи след преместване с достатъчно голямо кратно на , така че грешката в оценката остава ограничена с абсолютна константа, която не зависи от . Тази равномерност е важна: тя позволява да сравняваме главните линейни членове в уравнението, без неизвестната ограничена част да влияе след деление на . Сега фиксираме произволно и пускаме в . От вече получената оценка имамедокато дясната страна е . СледователноТъй като е фиксирано, това е възможно при неограничено големи само акоЗначи е линейна на цялата положителна полуос. Остава да намерим . Замествайки в първоначалното уравнение, получавамеСлед съкращаване оставаПонеже , а функцията е строго растяща за , единственото решение е . Следователно за всяко , което вече проверихме.Задача 3
Условие
Разглеждаме дъска от единични квадратчета, където е нечетно положително цяло число. Казваме, че колекция от еднакви домина е максимална конфигурация, подравнена по мрежата, ако се състои от домина, всяко от които покрива точно две съседни квадратчета и домината не се застъпват; тогава покрива всички квадратчета освен едно. Позволено е да плъзнем, без да завъртаме, едно домино така, че то да покрие непокритото квадратче; получава се нова максимална конфигурация с друго непокрито квадратче. Нека е броят на различните максимални конфигурации, които могат да се получат от чрез последователни плъзгания на домина. Да се намерят всички възможни стойности на като функция на .Решение
Отговорът еНомерираме квадратчетата с координати , където . Наричаме квадратче специално, ако е празното квадратче или ако двете му координати имат същата четност като координатите на празното квадратче. При всяко допустимо плъзгане празното квадратче се премества от едно специално квадратче в друго, а паритетният клас на специалните квадратчета не се променя. Построяваме насочен граф върху специалните квадратчета. Ако едно домино лежи върху специално квадратче , насочваме ребро от към специалното квадратче, към което това домино сочи; празното квадратче няма изходящо ребро. В свързаната компонента , която съдържа празното квадратче, всички стрелки сочат към него. Плъзгането на домино точно обръща едно ребро по пътя в тази компонента. Следователно достижимите конфигурации са точно изборите на връх на , който да бъде новото празно квадратче, и затоваОстава да разберем какви размери може да има . Ако специалните квадратчета са с две нечетни координати, те са . В този случай всеки цикъл в ненасочения граф огражда нечетен брой квадратчета от дъската: това следва от теоремата на Пик, приложена към центровете на квадратчетата по и вътре в цикъла, заедно с паритетното броене на домината по границата. Затова компонентата на празното квадратче е дърво, освен ако е затворена от цикъл. Ако тя не е цялото множество от специални квадратчета, такъв ограждащ цикъл я отделя от най-външния ред и най-външната колона, откъдето . Ако обаче е обхващащо дърво, получаваме единствената голяма стойност ; тя се реализира от змиевидна конфигурация, която минава през всички специални квадратчета. Ако специалните квадратчета са с две четни координати, те са . Същото графово описание дава , този път без възможност за по-голяма стойност. За всяко вземаме змиевиден път от специални квадратчета и ориентираме съответните домина към избраното празно квадратче; останалите специални квадратчета се затварят в малки локални блокове, които не са достижими от празното квадратче. Това дава конфигурация с точно достижими положения. Така получаваме всички стойности от първия интервал и единствената допълнителна голяма стойност, както беше твърдяно.Задача 4
Условие
Фиксирани са положителни цели числа и , а на дъска са написани положителни цели числа. Алиса и Боб играят следната игра. На ход Алиса трябва да замени някое число на дъската с , а на ход Боб трябва да замени някое четно число на дъската с . Алиса започва и двамата се редуват. Ако на свой ход Боб няма валиден ход, играта приключва. След като разглежда -те числа на дъската, Боб разбира, че независимо какви ходове прави Алиса, той може да наложи играта в крайна сметка да приключи. Да се докаже, че всъщност за това и тези числа играта гарантирано приключва независимо от ходовете и на Алиса, и на Боб.Решение
Нека означава показателя на в разлагането на положителното цяло число . При няма какво да се доказва: във всеки момент всеки играч има най-много един възможен ход, така че няма избор на стратегия. Нека оттук нататък , а е множеството от числата на дъската, броени с кратности. Първо, ако за всяко , играта приключва независимо от ходовете. Наистина, при такова имаме , така че ходът на Алиса не променя този показател. Всеки ход на Боб, когато е възможен, намалява сумата на всички показатели точно с . Играта приключва точно когато всички тези показатели станат нула, така че в този случай броят на ходовете на Боб е предварително определен. Сега да допуснем, че на дъската има число с . Тогава Алиса може да направи играта безкрайна. Следим първото число на дъската и пак го означаваме с . Ако , Алиса играе върху първото число; тогава новото първо число е и има . Ако пък , Алиса играе върху някое друго число, което е възможно понеже . С двустъпкова индукция получаваме, че непосредствено преди всеки ход на Боб е изпълнено , а непосредствено след всеки ход на Боб е изпълнено . Значи Боб никога не остава без валиден ход, защото първото число винаги е четно преди неговия ход. Но по условие Боб може да наложи край независимо от ходовете на Алиса. Следователно този втори случай е невъзможен, така че първоначално за всички числа на дъската. По първата част играта тогава приключва независимо от ходовете и на двамата играчи.Задача 5
Условие
Нека е цяло число. Да наречем разполагане на числата в таблица валидно по редове, ако числата във всеки ред могат да се пренаредят така, че да образуват аритметична прогресия. Аналогично, да го наречем валидно по стълбове, ако числата във всеки стълб могат да се пренаредят така, че да образуват аритметична прогресия. За кои стойности на е вярно, че всяко валидно по редове разполагане може да се превърне във валидно по стълбове чрез пренареждане на числата във всеки ред?Решение
Отговорът е: точно за простите . Първо нека е просто. В аритметична прогресия с члена остатъците по модул са или всички различни, ако разликата не се дели на , или всички са еднакви, ако разликата се дели на . Да разгледаме кратните на в дадена валидна по редове таблица. Във всеки ред има или точно едно такова число, или точно такива числа. Понеже общо кратните на са , има два случая. Ако всички кратни на са в един ред, тогава всеки ред се състои от числата с един и същ остатък по модул . Следователно можем да пренаредим числата във всеки ред така, че -тият стълб да съдържа точно числата от до , които образуват аритметична прогресия. Ако кратните на са в различни редове, тогава всеки ред съдържа всеки остатък по модул точно по веднъж. Пренареждаме числата във всеки ред така, че -тият стълб да съдържа всички числа, които дават остатък по модул (с остатък за последния стълб). Тези числа образуват аритметична прогресия с разлика . Значи при просто желаното винаги е възможно. Остава да покажем, че при съставно свойството не е вярно. Нека е прост делител на . Построяваме валидна по редове таблица така: първият ред съдържа числата ; следващите реда съдържат числата от до , разбити на аритметични прогресии с разлика ; останалите редове съдържат оставащите числа в естествения им ред. Така всеки ред е аритметична прогресия след евентуално пренареждане. Да допуснем, че чрез пренареждане във всеки ред сме получили валидна по стълбове таблица. Всеки стълб тогава съдържа аритметична прогресия от члена, чийто най-малък член е в интервала , а най-големият е в интервала : това следва от числото в първия ред и числото в последния ред на съответния стълб. Тези два крайни члена трябва да са сравними по модул . Разглеждаме стълба, който съдържа числото . В него най-малкият член е точно , защото числото е в същия ред и не може да е в същия стълб. Единственото число в интервала , което е сравнимо с по модул , е . Следователно най-големият член на този стълб е , а общата разлика на прогресията е . Значи същият стълб трябва да съдържа и числата и . Но в построената таблица тези две числа лежат в един и същ ред: понеже дели , те имат един и същ остатък по модул , а следващите реда бяха точно прогресии с разлика . Невъзможно е две числа от един ред да попаднат в един и същ стълб след пренареждане само вътре в редовете. Получихме противоречие, така че при съставно исканото свойство не може да важи.Задача 6
Условие
Нека е триъгълник с инцентър и ексцентрове , , съответно срещу върховете , и . Дадена е произволна точка върху описаната окръжност на , която не лежи върху нито една от правите , или . Описаните окръжности на и се пресичат в две различни точки и . Ако , да се докаже, че .Решение
Нека е средата на малката дъга на описаната окръжност на , а е втората пресечна точка на окръжностите и . Понеже и лежат на правата , от теоремата за радикалните оси следва, че правите , и се пресичат в една точка; да я означим с . Нека . Първо ще докажем, че , тоест че правите и са изогонални спрямо ъгъла при . По лемата за изстрелването четириъгълникът е вписан. СледователноТъй като са колинеарни, това е точно равенството . Остава да покажем, че съвпада с дадената точка . Ще сравним степени към двете окръжности. Построяваме успоредник . От стандартното равенство за дъговата среда имаме . Получаваметака че лежи на окръжността . Освен товаЗначи степента на спрямо е . Същият аргумент, приложен към окръжността , дава същата степен на спрямо нея. Следователно лежи на радикалната ос на двете окръжности, тоест на правата . Понеже лежи и на , получаваме . От първата част следва , както се искаше.2024
6 задачиЗадача 1
Условие
Да се намерят всички цели числа със следното свойство: ако делителите на са подредени във възходящ ред катотоРешение
Отговорът е . Това се проверява директно: за делителите са , а за саЩе докажем, че други стойности няма. Числата отпадат директно: за имаме , за имаме , а за числата са последователни делители около липсващото просто число , така че . Нека . ТогаваПо постулата на Бертран съществува просто число такова, чеЧислатаиса две последователни цели числа, които делят . Между тях обаче има просто число , което не дели . Това нарушава монотонността на разликите между съседни делители. Следователно единствените решения са и .Задача 2
Условие
Нека са крайни множества от цели числа, чието сечение е непразно. За всяко непразно подмножество броят на елементите в сечението на множествата от се дели на . Да се намери най-малкият възможен брой елементи, които принадлежат на поне от множествата.Решение
Отговорът еЩе кодираме всеки елемент с двоичен вектор : означава, че елементът лежи в . Нека е броят елементи с точно този вектор на принадлежност. Ако пишем , когато всички единици на са и единици на , условието на задачата ставаза всеки ненулев . Търсената величина еДостатъчно е да разглеждаме стойностите на за : след като те са избрани така, че е изпълнено за , стойностите за могат да се допълнят надолу по индукция, без да променят . Първо даваме конструкция. За поставямеАко , където , тогавакоето се дели на . При тази конструкцияСледователно тази стойност е достижима. Остава да докажем, че по-малка стойност е невъзможна. Ще използваме операция „сваляне“ върху вектор с и : намаляваме с , а за всеки с увеличаваме с . Тази операция запазва всички условия с . Наистина, ако , сумата в се променя са това не влияе на делимостта на . Освен това не се променя, когато , а при намалява с . Започваме с произволна допустима конфигурация. Първо сваляме вектора , докато ; това е възможно, понеже общото сечение е непразно и броят му се дели на . После сваляме последователно всички вектори с единици, докато стойностите им станат по-малки от , после всички с единици и така нататък до единици. Получаваме конфигурация с за , без да сме увеличили . Сега надолу по индукция от до условието даваПонеже и , и лежат между и , следва . Следователно след свалянията неизбежно стигаме до конструкцията , чиято стойност на е . Понеже свалянията не увеличават , началната конфигурация също има .Задача 3
Условие
Нека са положителни цели числа с и е даден правилен -ъгълник. Искаме да го триангулираме на триъгълника, като всеки триъгълник е оцветен в един от цвята, така че сборът от лицата на триъгълниците от всеки цвят да е един и същ. За кои е възможно това?Решение
Отговорът е: точно когато е собствен делител на , тоест и . Първо построяваме пример. Нека върховете на правилния -ъгълник саВземаме триангулацията с всички диагонали от върха . За удобство добавяме и двата дегенерирали триъгълника при и , чиито лица са ; това не променя задачата. Оцветяваме триъгълника с върхове според остатъка на по модул . Ще използваме следната стандартна формула: ориентираното лице на триъгълника с върхове еТя се получава директно от формулата на Гаус за лице след завъртане с . Ако фиксираме остатък по модул , сборът от лицата на този цвят еПонеже , но , имамеи също така . Следователно горният сбор екоето не зависи от . Значи всички цветове имат равни сборове от лица. Остава да докажем, че други случаи няма. Първо , защото всеки цвят трябва да има положителен общ сбор от лица, а триъгълниците са само . Да допуснем, че има валидно оцветяване. Тогава всеки цвят има общо лицеЗа всеки триъгълник от върхове на правилния -ъгълник числотое алгебрично цяло. Следователно и трябва да е алгебрично цяло. Умножаваме по и получавамеВ циклотомичното поле пръстенът на целите е , така че ако , последното число не е алгебрично цяло. Противоречие. Значи , а с получаваме точно посочените двойки.Задача 4
Условие
Нека и са положителни цели числа. Кръгова огърлица има мъниста, всяко от които е червено или синьо. Оказало се, че както и да разрежем огърлицата на блока от по последователни мъниста, блоковете имат различен брой червени мъниста. Да се намерят, с доказателство, всички възможни стойности на наредената двойка .Решение
Отговорът еНеобходимостта е непосредствена: всеки блок има между и червени мъниста, тоест има само възможни броя. Щом блока трябва винаги да дават различни броеве, необходимо е . Остава конструкцията. Първо разглеждаме граничния случай . Подреждаме огърлицата като таблица с реда и стълба, четена ред по ред. В реда с номер отдолу нагоре поставяме първо червени мъниста, а след тях сини мъниста. Ако , последното синьо мънисто в този ред означаваме с ; тези означения са само за проследяване при разместване на разрезите. След премествания на всички разрези с една позиция, където , проследяването на мънистата дава следния брой червени мъниста в реда с номер отдолу нагоре:Тези числа са точно в някакъв ред, следователно всички блока имат различен брой червени мъниста. Понеже всеки възможен разрез се получава от някое , конструкцията работи за . Ако , започваме от вече построената огърлица за двойката . След това към началото на всеки блок добавяме сини мъниста. Тези добавени сини мъниста не променят броя на червените мъниста; при преместване на разрезите те само забавят момента, в който се стига до старата конструкция. Следователно различните блокове отново имат различен брой червени мъниста за всеки разрез. Така конструкция съществува за всички , а необходимостта вече беше доказана.Задача 5
Условие
Вътре в остроъгълен триъгълник е избрана точка така, че и . Точка е избрана върху лъча така, че . Нека е средата на . Да се докаже, че правата е допирателна към описаната окръжност на триъгълника .Решение
Дострояваме равнобедрен трапец с основи и , така че лежи на диагонала ; това е точно условието . Нека е образът на при централна симетрия спрямо , т.е. е средата на . Ще докажем, че точките лежат на една окръжност. Понеже , точката лежи на симетралата на . Хомотетията с център и коефициент изпраща във и тази симетрала в правата , следователно . Оттук . В равнобедрения трапец имаме , а от условието . Следователно , което доказва, че е вписан. Накрая е средата на , а е средата на , затова в триъгълника отсечката е средна отсечка и . Следователно . Равенството между ъгъла между допирателната и хордата и вписания ъгъл показва, че е допирателна към описаната окръжност на в точката .Задача 6
Условие
Нека е цяло число и нека . Колекция от не непременно различни подмножества на се нарича -голяма, ако за всяко . Да се намери, чрез и , най-голямото реално число , за което неравенствотое изпълнено за всяко положително цяло число , всички неотрицателни реални числа и всички -големи колекции от подмножества на .Решение
Отговорът еБез ограничение можем да приемем, че . Пишем . За всяка наредена двойка дефинирамеТогава, понеже брои наредените двойки , за които , имамеСега разделяме сумата на диагонални и недиагонални членове. За диагонала получавамеПо неравенството между квадратично и аритметично средноЗа недиагоналните членове имамеОтново по същото неравенство,Следователно лявата страна на задачата е понеТова доказва, че посоченото винаги работи. Остава да покажем, че то е най-голямото възможно. Вземаме и нека множествата са всички -елементни подмножества на , всяко по веднъж. Избираме всички равни. По симетрия всички диагонални величини са равни, всички недиагонални с също са равни, и навсякъде . Затова всички неравенства в доказаната по-горе оценка стават равенства. Следователно по-голямо не може да работи, и отговорът е именно2025
5 задачиЗадача 1
Условие
Нека и са фиксирани положителни цели числа. Да се докаже, че за всяко достатъчно голямо нечетно положително цяло число всички цифри в записа на в бройна система с основа са по-големи от .Решение
Нека . Ще разгледаме най-десните цифри на в основа , тоест остатъка на при деление на . Твърдим, че съществува нечетно цяло число с такова, че Действително остатъкът е кратен на , а след деление на трябва да изберем клас по модул . Понеже е нечетно, китайската теорема за остатъците дава точно класа който е нечетен. Сега ще покажем, че прагът е достатъчен. При такова числото има точно цифри в основа , защото За всяко имаме Но -тата цифра отдясно е цялата част на , следователно тя е поне . Това важи за всички цифри на , така че всяка от тях е по-голяма от .Задача 2
Условие
Нека са цели числа. Нека е полином от степен без кратни корени и с . Да предположим, че за всякакви реални числа , за които полиномът дели , произведението е равно на нула. Да се докаже, че има нереален корен.Решение
Ще докажем контрапозицията. Ако всички корени на са реални, то ще получим делител от степен , чиито всички коефициенти са ненулеви. Първо можем да сведем задачата до случая : избираме произволни корена на и разглеждаме произведението на съответните линейни множители; всеки негов делител от степен е и делител на . Така нека където всички са реални, ненулеви и две по две различни. За всяко полиномът има степен , следователно по условие поне един негов коефициент е нула. Водещият и свободният коефициент на са ненулеви, така че нулевият коефициент трябва да е на някоя от степените . Има полинома , но само такива позиции, затова по принципа на Дирихле два от тях имат нулев коефициент на една и съща степен. Нека това са и , и нека общата степен е . Пишем като поставяме . Коефициентът пред в е , а в е . И двата са нула, следователно . Понеже , получаваме , а после и . Значи има две последователни нулеви коефициента. Остава един стандартен факт: реален полином с всички корени реални и различни не може да има две последователни нулеви коефициента. Наистина, ако коефициентите пред и са нула, то -тата производна на полинома има двоен корен в . От друга страна, ако началният полином има само реални прости корени, то по теоремата на Рол всяка негова производна също има само реални прости корени. Това е противоречие. Следователно , а значи и , има нереален корен.Задача 3
Условие
Архитектката Алис и строителят Боб играят игра. Първо Алис избира две точки и в равнината и подмножество на равнината, като те се съобщават на Боб. След това Боб отбелязва безкрайно много точки в равнината и обявява всяка от тях за град. Той няма право да поставя два града на разстояние най-много един от друг, а никои три от поставените градове не могат да бъдат колинеарни. Накрая между градовете се строят пътища по следното правило: всяка двойка градове се свързва с път по отсечката тогава и само тогава, когато е изпълнено условието: за всеки град , различен от и , съществува , така че е директно подобен (със същата ориентация) на или на . Алис печели, ако (i) получените пътища позволяват пътуване между всеки два града чрез краен брой пътища и (ii) никои два пътя не се пресичат. В противен случай печели Боб. Определете, с доказателство, кой от двамата играчи има печеливша стратегия.Решение
Отговорът е, че Алис печели. Ще наричаме множество множество на Боб, ако никои три негови точки не са колинеарни и разстоянието между всеки две негови точки е по-голямо от . За такова множество построяваме графа на Боб: върховете са точките на , а две точки са свързани с ребро тогава и само тогава, когато затвореният диск с диаметър не съдържа друга точка от нито във вътрешността си, нито върху границата си. Ще докажем, че всеки такъв граф е свързан и планарен. Това ще даде стратегия за Алис: тя избира да бъде множеството от точките извън затворения диск с диаметър . Тогава за градове и трети град съществуването на подходяща точка е точно условието да не лежи в затворения диск с диаметър . Следователно построените пътища са точно ребрата на графа на Боб. Първо доказваме свързаността. Да допуснем противното и да изберем точки и в различни свързани компоненти. Понеже не е ребро, има трета точка в затворения диск с диаметър . Точката е в различна компонента от поне една от точките ; без ограничение нека това е . Сега повтаряме същия аргумент за двойката : понеже тези две точки са в различни компоненти, отсечката не е ребро и в диска с диаметър има нова точка. Продължавайки така, получаваме безкрайна редица от разстояния между двойки точки, които лежат в различни компоненти. На всяка стъпка новата точка лежи в диска с диаметър на предишната двойка. Ако новото разстояние е , а предишното е , то другото разстояние от новата точка до краищата на предишната двойка е по-голямо от . От неравенството на Питагор за точка в диск с даден диаметър получавамеСледователно , което е невъзможно за достатъчно голямо . Значи графът на Боб е свързан. Остава планарността. Ако две ребра и се пресичат, то е изпъкнал четириъгълник. Някой от ъглите му е поне ; без ограничение нека . Тогава точката лежи в затворения диск с диаметър , което противоречи на това, че е ребро. Следователно никои две ребра не се пресичат, тоест графът е планарен. Това завършва доказателството на стратегията на Алис.Задача 5
Условие
Да се намерят всички положителни цели числа , такива че за всяко положително цяло число сумата се дели на .Решение
Отговорът е: точно четните положителни цели числа . Нека Необходимостта е кратка: при трябва да дели . Това става точно когато е четно. Сега нека е фиксирано четно число. Ще докажем, че всяка проста степен, която дели , дели и . Нека . Ще използваме следната лема: за всяко е изпълнено За доказателство записваме Ако , то и съответният множител дава само знак. Ако , тогава съответният множител е точно Произведението на тези специални множители за е което доказва лемата. Понеже е четно, знаците изчезват след повдигане на -та степен. Като групираме членовете според стойността на , всяка стойност се среща точно пъти, и получаваме Индукция по вече завършва доказателството. За дясната страна е кратна на . Ако , то , затова по индукционното предположение е кратно на , а след умножение по получаваме . Това важи за всяка проста степен в разлагането на , следователно за всяко положително .Задача 6
Условие
Нека и са положителни цели числа с . В кръг са наредени кексчета с различни вкусове и има души, които обичат кексчета. Всеки човек задава неотрицателна реална оценка на всяко кексче според това колко го харесва. Да предположим, че за всеки човек е възможно кръгът от кексчета да се раздели на групи от последователни кексчета така, че сумата от оценките на за кексчетата във всяка група да е поне . Да се докаже, че е възможно -те кексчета да се разпределят между -те души така, че всеки човек да получи кексчета с обща оценка поне според неговите оценки.Решение
Доказваме твърдението с индукция по , като случаят е очевиден. Избираме произволно един човек и ще го наричаме Пип. Фиксираме едно разделяне на кръга на дъги, което е добро за Пип, тоест всяка от тези дъги има стойност поне според Пип. Построяваме двуделен граф между хората и тези дъги: свързваме човек с дъга , ако оценява кексчетата в с обща стойност поне . Пип е свързан с всички дъги. Ще използваме лемата на Хол. Ако има съчетание, което покрива всички хора, веднага раздаваме на всеки човек съответната дъга и сме готови. Иначе има лошо множество от хора, чието съседство има по-малко от дъги. Изтриваме хората от и всички техни съседни дъги и повтаряме същата процедура върху останалия двуделен граф. Ако пак няма съчетание, което покрива всички останали хора, намираме ново лошо множество , изтриваме него и неговите съседи, и продължаваме. Процесът задължително спира. На всяка стъпка изтриваме повече хора, отколкото дъги, така че броят на оставащите дъги е поне броя на оставащите хора. Освен това Пип никога не може да лежи в лошо множество, защото е съседен на всички оставащи дъги. Следователно накрая остава непразен граф, в който по Хол има съчетание , покриващо всички останали хора. Раздаваме на тези хора съответните дъги от . Остават хората, които са били изтрити в някое от лошите множества. Нека Куин е един от тях. Куин не харесва нито една от дъгите, раздадени чрез : ако харесваше такава дъга, тя щеше да е съседна на Куин и щеше да бъде изтрита още когато е било изтрито лошото множество, съдържащо Куин. Значи всяка дъга от има стойност по-малка от според Куин. Да видим какво става със собственото добро разделяне на Куин, когато изтрием една дъга от . Понеже стойността на за Куин е по-малка от , тази дъга не може да съдържа изцяло нито една от групите на Куин, всяка от които има стойност поне . Следователно пресича най-много една граница между групите на Куин. Ако пресече такава граница, двете съседни групи се сливат; новата група има стойност поне защото сме премахнали част с обща стойност по-малка от . Ако не пресече граница, след премахването все още имаме групи със стойност поне и просто сливаме произволни две съседни групи. И в двата случая броят на групите намалява с , а всички останали групи имат стойност поне . Повтаряме това за всички дъги от . За всеки останал човек получаваме разделяне на оставащите кексчета на точно толкова последователни групи, колкото са останалите хора, и всяка група има стойност поне за съответния човек. По индукционното предположение можем да разпределим оставащите кексчета между останалите хора. Заедно с вече раздадените дъги от това дава търсеното разпределение за всички души.2026
4 задачиЗадача 1
Условие
Фиксирано е цяло число . За кои реални числа изразъте максимален и каква е тази максимална стойност?Решение
Отговорът е: максималната стойност еи тя се достига точно когато дробната част на е поне . Изразът не се променя при замяна , затова е достатъчно да разгледаме , където . Тогаваи следователно даденият израз еПресмятамеТова може да се пренапише катоили ощекъдетоЗначи е достатъчно да докажем, че , като равенство има точно при . НекаАко , то и веднага . Нека сега . ТогаваЩе използваме следното неравенство: за е изпълненоПонеже , от него следватоест . Остава да докажем неравенството. ИмамеЗатоваГрупирайки по интервалитеполучаваме горна оценкаВъв всеки от тези интервали има най-много цели числа , а всеки член в него е строго по-малък от . Следователно цялата сума е строго по-малка отТова доказва неравенството, а с него и задачата.Задача 4
Условие
Положително цяло число се нарича самотно, ако за всички неотрицателни цели числа и с поне едно от числата и съдържа цифрата . Да се намери, с доказателство, броят на самотните числа, по-малки от .Решение
Ще докажем, че едно число е самотно точно когато десетичният му запис има следния вид: цифрата се среща точно веднъж, всички цифри вляво от нея са или , а всички цифри вдясно от нея са . Например е от този вид. Първо нека има този вид. Ако последната цифра е , тогава при всяко представяне последните цифри на и се събират до , без пренос към тази позиция. Затова можем да изтрием последната цифра и да приложим същия аргумент към по-късия запис. Повтаряйки, стигаме до случая, в който единствената цифра е последна. Ако вляво има водеща цифра , то или някое от и вече има цифра в тази позиция, или едното има цифра и можем да изтрием тази еднаква водеща част и да продължим индуктивно. Ако не се появи цифра по-рано, последната позиция задължително дава цифра в едно от двете числа. Следователно всяко число от описания вид е самотно. Сега нека е самотно. Първо, като вземем , виждаме, че самото съдържа поне една цифра . Ако съдържа четен брой единици, можем да ги сдвоим отляво надясно и във всяка двойка да построим събиране без цифри чрез блокове от вида , като всички останали позиции се допълват с нули. Ако броят на единиците е нечетен и поне три, правим същото, но оставяме първата единица да бъде получена като , а останалите единици отново се елиминират по двойки чрез заеми и блокове от деветки. И в двата случая получаваме представяне , в което нито , нито съдържа цифра , противоречие. Значи в има точно една цифра . Остава да ограничим останалите цифри. Ако вдясно от единствената единица има цифра , тогава можем да използваме заем от тази единица: в междинните позиции поставяме в едното събираемо деветки, а в позицията с избираме цифра ; при вместо това използваме и цифрата . Така пак получаваме разлагане без цифра , невъзможно за самотно число. Следователно всички цифри вдясно са . Ако вляво от единицата има цифра , вземаме заем през следващите позиции, като използваме блок от деветки, и заменяме с , а единицата с в другото събираемо. Отново получаваме две числа без цифра , противоречие. Значи всяка цифра вляво е или . Накрая броим. Дописваме водещи нули, така че записът да има точно цифри. Ако единствената цифра е на -та позиция отляво, то преди нея има свободни позиции, всяка с избор или , а след нея всички цифри са . Това дава числа. Следователно общият брой еЗадача 5
Условие
Нека е триъгълник. Точките , и лежат съответно върху страните , и , катоНека , и са центровете на описаните окръжности съответно на триъгълниците , и . Нека , и са центровете на описаните окръжности съответно на триъгълниците , и . Да се докаже, че .Решение
Засега изцяло пренебрегваме точките , и ; ще се върнем към тях накрая. По теоремата на Микел описаните окръжности на , и минават през една и съща точка , която е най-важната точка в решението. Въвеждаме насочените ъглиЩе опишем явно спирална подобност с център , която изпраща в . Най-удобно е да я формулираме така: **Твърдение.** Имаме директните подобия**Доказателство.** Забелязваме, че , а . Всъщност подобен е и триъгълникът . **Твърдение.** Същите спирални подобности с център изпращат**Доказателство.** Тези триъгълници са равнобедрени и . Накрая въвеждаме точките , и , използвани само за извличане на заключението. Нашите спирални подобности изпращат триъгълниците , и един в друг, а , и са съответните им центрове на описани окръжности. Затова можем да продължим редицата от подобия доВ частност . **Забележка.** Изборът на , и като центрове на описаните окръжности на , и е несъществен за доказателството. Те могат да бъдат заменени с произволен друг център на триъгълник и доказателството остава същото. **Забележка.** Всъщносттака че по симетрия знаем ощеСледователно е така наречената втора точка на Брокар на триъгълника.Задача 6