Задача 2
EGMO
Evan Chen / EGMO Twitch Solution
59 задачи от базата, подредени за бързо решаване по година или клас. Показаните източници са тези, записани към самите задачи.
15 години1 класаИма видими липси
Избран клас
11-12
Открити липси за попълване от източника
- 2025 · 11-12: липсва задача 3, 4
- 2024 · 11-12: липсва задача 2, 4
- 2023 · 11-12: липсва задача 2
- 2022 · 11-12: липсва задача 3
- 2020 · 11-12: липсва задача 3, 5
- 2019 · 11-12: липсва задача 3
- 2018 · 11-12: липсва задача 5
- 2017 · 11-12: липсва задача 5
- 2013 · 11-12: липсва задача 5
- 2012 · 11-12: липсва задача 4
2012
4 задачиПълен запис
Задача 3
Условие
Да се реши върху функционалното уравнениеРешение
Единственото решение екоето се проверява директно. Нека означава даденото условие. От получавамеСледователно е биекция: тя е сюрективна, защото всяко реално число е от вида , и е инективна, защото от следва , тоест . Освен товаПри това дава , значи . Сега прилагаме . ПолучавамеОт вече доказаното равенство дясната страна е . Понеже е инективна, следватоест . Прилагаме и :Но от получаваме . Накрая вземаме . Тъй като и , имамеА понеже и е инективна, следваСледователно за всяко реално , както трябваше да се докаже.Задача 5
Условие
Простите числа и удовлетворяватза някое положително цяло число . Да се намерят всички възможни стойности на .Решение
Отговорът еПреобразуваме уравнението:СледователноТъй като е положително, лявата страна е положителна, значи . Оттуктака чеОсвен това . Понеже е просто число, получавамеНо тогаваОтново използваме, че е просто и ; следователноЗначи е едно от , тоестОстава да покажем, че трите стойности наистина се достигат. Например двойкитедават съответно , а формулата за дава положителни цели стойности на . Следователно това са точно всички възможности.Задача 6
Условие
В социалната мрежа Mugbook са регистрирани безкрайно много хора. Някои двойки различни потребители са отбелязани като приятели, но всеки човек има само краен брой приятели. Всеки потребител има поне един приятел. Приятелството е симетрично: ако е приятел на , то е приятел на . Всеки човек трябва да посочи един от приятелите си като свой най-добър приятел. Ако посочи за най-добър приятел, не е задължително също да посочи . Човек, който е посочен за най-добър приятел от някого, се нарича -най-добър приятел. По-общо, ако , потребител е -най-добър приятел, ако е посочен за най-добър приятел от някой, който е -най-добър приятел. Човек, който е -най-добър приятел за всяко положително цяло число , се нарича популярен. (a) Докажете, че всеки популярен човек е най-добрият приятел на популярен човек. (b) Покажете, че ако хората могат да имат безкрайно много приятели, е възможно популярен човек да не е най-добрият приятел на популярен човек.Решение
Първо ще използваме следното просто наблюдение. Ако някой е -най-добър приятел, то той е и -най-добър приятел за всяко . Наистина, свойството да бъдеш -най-добър приятел означава, че има верига от последователни посочвания на най-добър приятел, която завършва в този човек. Като вземем последните посочвания от тази верига, получаваме, че същият човек е -най-добър приятел. (a) Нека Дани е популярен. Неговите приятели са краен брой; означаваме ги сПонеже Дани е популярен, за всяко той е -най-добър приятел. Следователно за всяко има приятел на Дани, който е -най-добър приятел и е посочил Дани за свой най-добър приятел. Имаме само краен брой приятели , затова по принципа на Дирихле някой от тях е -най-добър приятел за безкрайно много стойности на . От наблюдението по-горе този човек е -най-добър приятел за всяко фиксирано , тоест е популярен. Понеже той е посочил Дани за най-добър приятел, получаваме, че Дани е най-добрият приятел на популярен човек. (b) Ако позволим безкрайно много приятели, предишният аргумент вече няма крайния избор, върху който да приложим принципа на Дирихле. Даваме явна конструкция. Нека има един човек и за всяко положително цяло число - верига от душиНай-добрите приятелства са насочени така:Тоест за всяко имаме веригаНека още посочи за свой най-добър приятел, а приятелствата са точно двойките, които се появяват в тези посочвания. Тогава всеки има поне един приятел, а единствено има безкрайно много приятели. Човекът е популярен, защото за всяко съществува верига с дължина поне , която завършва в . От друга страна, никой от хората не е популярен: зад него в неговата верига има само краен брой хора, така че той може да бъде -най-добър приятел само за крайно много стойности на . Следователно е единственият популярен човек. Но не може да бъде най-добрият приятел на популярен човек: единственият популярен човек е самият , а не посочва себе си за най-добър приятел. Това дава искания пример.2013
3 задачиЗадача 3
Условие
Нека е положително цяло число. (a) Докажете, че съществува множество от положителни цели числа, такова че най-малкото общо кратно на всеки два негови елемента е най-много . (b) Докажете, че всяко множество от положителни цели числа съдържа два елемента с най-малко общо кратно, по-голямо от .Решение
За (a) вземамеВ това множество има числа. Ако два елемента са най-много , тяхното НОК е най-много произведението им, тоест най-много . Ако единият елемент е от първия блок, а другият от втория, произведението им е най-много , следователно и НОК е най-много . Ако и двата са от втория блок, общият множител дава горна граница . Следователно този избор работи. За (b) нека елементите на множеството са подредени катокъдето . Да допуснем противното: всяко НОК на две числа е най-много , където . За всеки съседен чифт имамезащото общият делител на и дели разликата им. ЗначиСумираме това за и получавамеИзбираме и . Тогава , а , понеже е -вото положително цяло число в подредбата. Следователнокоето е невъзможно. Полученото противоречие доказва, че някои два елемента имат НОК, по-голямо от .Задача 4
Условие
Намерете всички положителни цели числа и , за които съществуват три последователни цели числа, при които полиномът приема цели стойности.Решение
Отговорът е: или , или и . Случаят е очевиден. Нека сега и нека е произволна степен на просто число, която дели . Ако трите последователни цели числа са , тоПърво не е четно, защото две последователни числа имат различна четност, а значи и петите им степени имат различна четност. Също така простият делител на не е , понеже от бихме получили . В частност е обратимо по модул . Имамеа лявата страна е . Числото е взаимно просто с , защото иначе от и би следвало по простия делител на . СледователноСъщо така от разликата на крайните пети степени получаваметоестИзползвайки , получавамеЗначи , откъдето . Понеже беше произволна проста степен, деляща , следва . Остава да намерим кога модул има три последователни числа с една и съща пета степен. Проверка на остатъците давакакто иТова са единствените такива тройки от последователни остатъци. Значи трябва и е достатъчно да имаме или , съответно. Така получаваме точно посочените решения.Задача 6
Условие
Снежанка и седемте джуджета живеят в къщичката си в гората. Във всеки от последователни дни част от джуджетата работили в диамантената мина, а останалите събирали горски плодове в гората. Никое джудже не вършило и двете работи в един и същи ден. За всеки два различни дни има поне три джуджета, всяко от които през единия ден е вършило единия вид работа, а през другия ден - другия. Освен това в първия ден всичките седем джуджета работили в диамантената мина. Докажете, че в един от тези дни всичките седем джуджета са събирали горски плодове.Решение
Ще кодираме всеки ден с вектор от : координатата е , ако съответното джудже е работило в мината, и , ако е събирало горски плодове. Условието за всеки два различни дни означава, че разстоянието на Хеминг между всеки два от получените вектора е поне . Понеже първият ден е бил изцяло в мината, нулевият вектор принадлежи на множеството. Преномерираме векторите катотака че . Трябва да докажем, че . Първо ще използваме следната лема. За всеки избор на три координати и за всеки от осемте възможни шаблона върху тях точно два от векторите в имат този шаблон. Наистина, не може три различни вектора да съвпадат върху някакви три фиксирани координати. Ако това се случи, изтриваме тези три координати. Получаваме три двоични вектора с дължина , чиито взаимни разстояния на Хеминг пак са поне . След добавяне по модул на един от тях можем да приемем, че единият е . Тогава другите два трябва да имат тегло поне ; но два различни вектора с дължина и тегло поне са на разстояние най-много един от друг. Противоречие. Значи за всяка тройка координати и всеки шаблон има най-много два вектора, а понеже шаблоните са и векторите са , броят е точно два. Същото твърдение за една или две координати следва, като сумираме по останалите координати. Игнорираме нулевия вектор . За нека е броят на единиците във . От лемата и двойно броене получавамеНапример третото равенство брои двойките, състоящи се от вектор и тройка координати, върху които този вектор има само единици. Оттук следваВсеки от тези вектора е ненулев, така че . За всяко цяло имамеСумирайки, намирамеСледователно навсякъде има равенство, т.е. всяко е едно от числата . Остава да има поне едно . Ако това не беше вярно, всички щяха да са или , а тогава за всяко . Това би далопротиворечие. Значи някой вектор има седем единици, т.е. . Това е точно денят, в който всички седем джуджета са събирали горски плодове.2014
6 задачиЗадача 1
Условие
Определете всички реални константи , такива че винаги когато , и са дължини на страните на триъгълник, числата , , също са дължини на страните на триъгълник.Решение
Отговорът еПишем , , за положителни . Поради симетрия е достатъчно да проверим едното триъгълно неравенствоСлед заместване това е еквивалентно накъдетоТук са произволни. Първо трябва ; иначе водещият коефициент е отрицателен и за достатъчно голямо неравенството се проваля. При имаметака че този краен случай работи. Нека . Дискриминантата на квадратичния тричлен екоето е положително за всички реални и положителни . Следователно има две реални корени. Понеже водещият коефициент вече е положителен, условието за всяко е равносилно всички коефициенти да са неотрицателни, като средният е очевидно положителен. Оставаза всички положителни . Понежедостатъчно и необходимо е ; ако , вземаме и получаваме отрицателен свободен член. Значи точно работи.Задача 2
Условие
Нека и са вътрешни точки съответно на страните и на триъгълника , за коитоНека правите и се пресичат във . Докажете, че инцентърът на , ортоцентърът на и средата на дъгата от описаната окръжност на са колинеарни.Решение
Нека и пресичат отново описаната окръжност съответно в и . Имаме спирална подобностзащотои , . Следователно е точката на Микел на . НекаПонеже е среден перпендикуляр на , имаметака че са вписани в една окръжност. Аналогично и лежи на тази окръжност. Носледователно (получава се равнобедрен трапец). Триъгълниците и са хомотетични. Следователно правите , и са конкурентни; по определенията на и те се пресичат в . Значи , и са колинеарни.Задача 3
Условие
Нека означава броя на положителните делители на положителното цяло число , а - броя на различните му прости делители. Нека е положително цяло число. Докажете, че съществуват безбройно много положителни цели числа , такива че и не дели за никои положителни цели числа с .Решение
Ще построим безбройно много такива . Избираме нечетно положително цяло число , което не се дели на и има ; при вземаме . После избираме достатъчно голямо нечетно просто число и поставямеТогава . Освен това , защото показателят на простото число в е . Нека и нека . Ще докажем, че ; тогава със сигурност не може да дели . Първо, . Наистина, от избора на следва , а ако , то , откъдето , противоречие. Избираме толкова голямо спрямо фиксираното , чеТака показателят на всеки нечетен прост делител на е по-малък от , следователно нито един нечетен прост фактор на не може да внесе множител в . Остава да проверим степента на в . Ако , тогава от следва , иАко , то тази обща стойност е най-много , защото се дели точно на . В този случайВъв всички случаи не се дели на . Следователно . Тъй като има безбройно много прости числа , по-големи от всяка предварително избрана граница, получаваме безбройно много такива числа .Задача 4
Условие
Да се намерят всички цели числа , за които съществуват цели числа със следното свойство: ако , , и , то .Решение
Отговорът екато условието изключва само случая . Нека пишем , ако , и . Търсените числа съществуват точно когато ориентираният граф с ребра няма насочен цикъл: ако цикъл има, получаваме невъзможна верига от строги неравенства, а ако цикъл няма, можем да подредим върховете топологично и да изберем според този ред. Да опишем кога има цикъл. Акото , следователноЗа да се върнем в началото, трябваОсвен това съседните върхове в цикъла трябва да са различни, което е равносилно наАко , първото условие принуждава , защото е нечетно и следователно е взаимно просто с . Това е невъзможно, понеже върховете са между и . Значи цикъл няма. Ако , първото условие принуждава да е кратно на . Тогава или , и в двата случая . Това нарушава условието за различни съседни върхове още при , така че отново цикъл няма. Остава да покажем, че други не работят. Ако има нечетен делител , поставяме и вземаме . Тогава , откъдетоОт друга страна съществува нечетно просто , чиято степен в е по-голяма от степента му в ; това е очевидно, ако има прост делител, различен от , а ако е степен на , използваме факта, че . Понеже множителите не променят -адичната степен, никое от числата не е кратно на . Следователно получаваме насочен цикъл, което прави желаните строги неравенства невъзможни. Значи единствените допустими са точно изброените в отговора.Задача 5
Условие
Нека е положително цяло число. Имаме кутии, като във всяка има неотрицателен брой камъчета. В един ход можем да вземем две камъчета от избрана кутия, да изхвърлим едното и да сложим другото в друга избрана кутия. Начална конфигурация се нарича разрешима, ако след краен, възможно нулев, брой ходове може да се стигне до конфигурация без празна кутия. Определете всички начални конфигурации, които не са разрешими, но стават разрешими при добавяне на едно камъче в която и да е избрана кутия.Решение
Ще характеризираме първо разрешимите конфигурации. Ако в кутиите има камъчета, твърдим, че конфигурацията е разрешима точно когатоДоказателството е по индукция по общия брой камъчета. Ако общият брой е по-малък от , очевидно не можем да получим непразни всички кутии. Нека общият брой е поне и означим горната сума с . Ако , то след един разрешен ход стойността на не може да нарасне: от кутия с махаме две камъчета, което намалява с , а в друга кутия добавяме едно камъче, което увеличава съответния член най-много с . По индукция конфигурацията не е разрешима. Ако и вече няма празна кутия, сме готови. Ако има празна кутия, понеже общият брой камъчета е поне , има кутия с поне две камъчета. Вземаме две камъчета от нея, изхвърляме едното и слагаме другото в празната кутия. Стойността на не се променя, а общият брой камъчета намалява с , така че индукционното предположение завършва доказателството на критерия. Сега търсим конфигурациите от условието. Те трябва да не са разрешими, но след добавяне на едно камъче във всяка възможна кутия да станат разрешими. По критерия това означава, че първоначалнои добавянето на камъче към която и да е кутия трябва да увеличава сумата с . Последното става точно когато всички са четни. Следователно отговорът е: всички конфигурации, в които всички броеве са четни неотрицателни числа иНаистина тогава сумата от таваните е , а добавянето на едно камъче към произволна кутия я прави равна на .Задача 6
Условие
Решете в реални числа функционалното уравнениеРешение
Ще докажем, че единствените решения саЛесно се проверява, че и двете работят. Първо показваме, че съществува единствено реално число , за което . Съществуване има, защото при дясната страна е . Ако , то от двойките получаваме съответноЗначи , откъдето . Поставяме и . Получавамеа по единствеността на нулатаСледователно и . Следва инективност. От и имамеАко и , то от единствеността на нулата последното може да се случи само при . Тогавакоето принуждава и . Но заместването на и в началното уравнение дава , което противоречи на току-що описаната единствена възможност за неинективност. Значи е инективна. Сега разменяме и в уравнението. Дясната страна е симетрична, а е инективна, затоваПри получавамеАко , от (1) следва за всички , и значи . От получаваме или . Остава да изключим . Тогава (1) се записва катоЗа ненулеви това дава с константа . Ако , функцията няма нула в ; ако , нулата е при , следователно и за . Тогава , противоречие с инективността. Значи е невъзможно, и остават само и .2015
4 задачиЗадача 3
Условие
Нека и са цели числа, по-големи от , и нека са положителни цели числа, не по-големи от . Докажете, че съществуват цели числа , не по-големи от , такива чеРешение
Всъщност ще докажем нещо по-силно: можем да изберем всички от множеството . Да допуснем противното, т.е. че за всеки избор на полученият най-голям общ делител е поне . Разглеждаме следните избора. Първо вземамеи нека съответният НОД е . След това за всяко вземаме , а всички останали равни на , и нека съответният НОД е . По предположението всички числа са поне . Освен това всяко дели , понеже във всички тези избора имаме . Ще покажем, че числата са две по две взаимнопрости. Ако , тогава дели (при това е очевидно, а при в избора за единствено е увеличено с ). От друга страна, дели . Следователно всеки общ делител на и дели и , и , значи е равен на . Така произведениетодели . Но понеже факторите са две по две взаимнопрости и всеки от тях е поне , имаме всъщност : равенство би изисквало всички да са равни на , което е невъзможно за две по две взаимнопрости числа при . Получавамекоето противоречи на условието . Следователно предположението е невярно и съществува избор на , за който НОД е по-малък от .Задача 4
Условие
Определете дали съществува безкрайна редица от положителни цели числа, такава че за всяко положително цяло число .Решение
Такава безкрайна редица не съществува. Всъщност може да има най-много пет члена; например показва, че пет члена са възможни. Да положимПонеже всички са цели числа и рекурсията трябва да дава цели числа, всички са положителни цели числа. От нататък редицата е строго растяща, следователно за и редицата е строго растяща. За пресмятамеСледователноАко съществуват поне шест члена , можем да вземем . Тогава , така че дясната страна е строго по-малка от . Но лявата страна е положително цяло число, следователно е поне . Това е противоречие. Значи не може да има шест последователни члена, удовлетворяващи рекурсията, а още по-малко безкрайна редица.Задача 5
Условие
Нека и са положителни цели числа, като . Анастасия разбива целите числа на двойки. След това Борис избира по едно число от всяка двойка и намира сумата на избраните числа. Докажете, че Анастасия може да избере двойките така, че Борис да не може да получи сума, равна на .Решение
Ще използваме няколко явни разбивания, които изключват всички възможни стойности на . Първо разглеждаме разбиванетона двойките . Ако Борис избере долното число в точно от двойките, сумата му е . Следователно възможните суми са точно числата от интервала . Ако не е в този интервал, това разбиване вече работи. Второ разглеждаме разбиванетоВсяка смяна от горното към долното число добавя , затова всички възможни суми са сравними сАко , това разбиване работи. Остава да разгледаме случаите, в които едновременно и . Ако е нечетно, тогава и значи е едно от и . Ако е четно, тогава и значи единствената останала стойност еЗа тези останали случаи използваме третото разбиванетоест двойките . Сумата на горния ред отново е . В първите двойки изборът на долното число променя сумата с кратно на , а в последната двойка я променя с . Следователно по модул всички възможни суми са самоАко е нечетно, имаметака че възможните остатъци са и . Понеже е нечетно, тези остатъци не са и . Но двете останали цели и дават остатъци съответно и по модул . Значи третото разбиване ги избягва. Ако е четно, числото се дели на , така че възможните остатъци са и . От друга странаа този остатък е различен и от , и от , понеже . Значи и в четния случай третото разбиване избягва останалата стойност на . Във всички случаи Анастасия има разбиване, при което Борис не може да получи сума .Задача 6
Условие
Нека е ортоцентърът, а - медицентърът на остроъгълен триъгълник с . Правата пресича описаната окръжност на в точките и . Нека е отражението на спрямо правата . Докажете, че тогава и само тогава, когато .Решение
Ще използваме комплексни числа. Нека описаната окръжност е единичната, а комплексните координати на са съответно . Тогава , и . От колинеарността на получаваме стандартното уравнениеоткъдетоОтражението спрямо правата се записва катои след заместване на намереното получавамеНека е средата на и нека комплексната му координата е . ТогаваУсловието означава, че лежи на симетралата на , тоест . В комплексна форма това е равносилно на това числотода е чисто имагинерно. Използвайки , и , условието след умножаване с ненулевите знаменатели се свежда доилиПонеже , не може да имаме ; иначе би била средата на дъгата и би следвало . ОставаСлед деление на получаваме, че е примитивен трети корен от единицата. Това е еквивалентно на централен ъгъл над дъгата , тоест на . Доказахме и двете посоки.2016
6 задачиЗадача 1
Условие
Нека е нечетно положително цяло число и нека са неотрицателни реални числа. Докажете, чекъдето и .Решение
Достатъчно е да намерим една двойка индекси, за коятоПонеже е нечетно, в цикличната редица не може знаците на сравненията между съседни членове да се редуват напълно. Следователно съществуват три последователни члена, в едната от двете посоки около цикъла, които можем да означим с така, че , като е средният от тях. Тогава, понеже числата са неотрицателни,Значи . Лявата страна е една от величините , а дясната е една от величините . Оттук веднага следва исканото неравенство между минимума и максимума. За сравнение, ако е четно, редица от вида показва защо нечетността е съществена.Задача 2
Условие
Нека е вписан четириъгълник, а диагоналите и се пресичат в . Нека , и са средите съответно на отсечките , и . Правите и се пресичат в , а правата пресича диагоналите и съответно в различни точки и . Докажете, че правата е допирателна към окръжността през , и .Решение
Ще дадем два подхода. Първи подход чрез лема за изогоналност. Забелязваме, че е вписан четириъгълник. По стандартната лема за изогоналност, приложена към триъгълника , правите и са изогонални спрямо триъгълника . Тогава, с насочени ъгли,Понеже , и са колинеарни, това е точно теоремата за ъгъл между допирателна и хорда за окръжността през , и . Следователно е допирателна към тази окръжност. За проверка даваме и комплексно решение. Четириъгълникът е вписан, защото . Нормализираме неговата описана окръжност до единичната окръжност и за краткост означаваме точките и с комплексните числа и . Достатъчно е да докажемкоето е равносилно на това числотода бъде реално. Нека , а е центърът на описаната окръжност на . По теоремата на Брокар имаме , така че е достатъчно да проверимОт получавамеСледователно последният израз ставаТой е равен на отрицателното на своето комплексно спрегнато, следователно е чисто имагинерен. Това доказва същото допиране.Задача 3
Условие
Нека е положително цяло число. Разглеждаме таблица от единични квадратни клетки. Две различни клетки се наричат свързани, ако лежат в един и същи ред или в един и същи стълб. Никоя клетка не е свързана със себе си. Някои клетки са оцветени в синьо така, че всяка клетка е свързана с поне две сини клетки. Да се намери минималният възможен брой сини клетки.Решение
Отговорът е . Първо даваме конструкция. По главния диагонал повтаряме пъти блокакъдето единиците означават сините клетки. Всеки блок съдържа сини клетки и лесно се проверява, че всяка клетка в блока има поне две сини клетки в своя ред или стълб. Така получаваме пример с сини клетки. Остава да докажем, че по-малко не стига. Да построим двуделен граф : едната част са редовете, другата са стълбовете, а всяка синя клетка дава ребро между съответния ред и съответния стълб. Да допуснем, че сините клетки са по-малко от , тоест . Тъй като графът има върха, броят на свързаните му компоненти е понеЗатова някоя компонента има най-много три върха. Първо, не може да има изолиран връх. Ако например някой ред няма синя клетка, то във всеки от -те стълба трябва да има поне две сини клетки, защото всяка клетка в този празен ред трябва да е свързана с поне две сини клетки. Това би дало поне сини клетки, противоречие. От друга страна, всяко синьо ребро е инцидентно с поне още две сини ребра: това е точно условието, приложено към самата синя клетка, като тя не се брои за свързана със себе си. Следователно никоя неизолирана свързана компонента не може да има по-малко от три ребра. Но прост двуделен граф върху най-много три върха има най-много две ребра, ако е свързан. Получаваме противоречие. Следователно сините клетки са поне , както трябваше.Задача 4
Условие
Две окръжности и с равни радиуси се пресичат в две различни точки и . Нека окръжност е външно допирателна до в точка и вътрешно допирателна до в точка . Докажете, че правите и се пресичат в точка, която лежи на .Решение
Ще използваме хомотетии. Нека е хомотетията с център , която изпраща в . Понеже двете окръжности са външно допирателни в , коефициентът на тази хомотетия е отрицателен. Нека е хомотетията с център , която изпраща в ; тук коефициентът е положителен, защото допирането е вътрешно.Разглеждаме композициятаТя изпраща в . Освен това произведението на коефициентите ѝ е отрицателно. Тъй като и имат равни радиуси, абсолютната стойност на този общ коефициент е . Следователно композицията е хомотетия с коефициент , тоест централна симетрия. Центърът на тази централна симетрия е средата на , защото двете равни окръжности са симетрични спрямо . В частност композицията изпраща едната им обща точка в другата обща точка . НекаТогава лежи на , понеже изпраща окръжността в . Също така лежи на правата , защото всяка точка и образът ѝ при хомотетия са колинеарни с центъра на хомотетията. От друга страна, , защото . Следователно , и са колинеарни, тоест лежи и на правата . Значи правите и се пресичат в точката , а тя лежи на . Точно тази точка е търсената, което завършва доказателството.Задача 5
Условие
Нека и са цели числа с и . Върху шахматна дъска поставяме правоъгълни плочки, всяка с размер или , така че всяка плочка покрива точно клетки и никои две плочки не се застъпват. Продължаваме, докато повече не може да се постави плочка по този начин. За всяка такава двойка определете минималния възможен брой плочки в крайна подредба.Решение
Отговорът еКонструкциите са следните. При е ясно, че трябва да се запълни цялата дъска с успоредни плочки. При започваме от случая , където четири плочки могат да блокират периметъра на квадрата; после при увеличаване на с добавяме по една нова хоризонтална и една нова вертикална плочка. Това дава плочки. При поставяме по една вертикална плочка във всеки стълб, като редуваме най-горната и най-долната възможна позиция; така получаваме плочки и не остава място за нова. Сега доказваме оптималността. Ще наричаме един ред гол, ако в него няма хоризонтална плочка, изцяло лежаща в този ред. Аналогично, един стълб е гол, ако в него няма вертикална плочка, изцяло лежаща в този стълб. **Твърдение.** Голите стълбове са последователни; същото важи и за голите редове. Доказателство. Нека вертикална плочка лежи в стълб . Ако е в лявата половина на дъската, тогава стълбът непосредствено вляво от също трябва да съдържа вертикална плочка: иначе бихме могли да поставим нова вертикална плочка точно вляво от , защото отляво няма достатъчно място за хоризонтална плочка, която да пречи. Повтаряйки това разсъждение, всички стълбове вляво от не са голи. По същия начин, ако е в дясната половина, всички стълбове вдясно от не са голи. Значи голите стълбове образуват един непрекъснат блок. За редовете доказателството е същото. Ако няма голи стълбове, то във всеки стълб има вертикална плочка, следователно плочките са поне . Аналогично, ако няма голи редове, плочките отново са поне . Остава случаят, когато има поне един гол ред и поне един гол стълб. Понеже голите стълбове са последователни, не може да има голи стълба: пресечем ли ги с един гол ред, получаваме последователни непокрити клетки и можем да добавим хоризонтална плочка, противоречие. Следователно голите стълбове са най-много , така че има поне неголи стълба, а значи поне вертикални плочки. Аналогично има поне хоризонтални плочки. Общо плочките са поне . Така всяка крайна подредба съдържа поне плочки, с изключение на специалния случай , където горната оценка не е достижима и трябват точно плочки. Това дава точно обявения отговор.Задача 6
Условие
Нека е множеството от всички положителни цели числа , за които има делител измежду числата . Докажете, че има безбройно много елементи на от всеки от видовете , , , , , и няма елементи на от видовете и , където е цяло число.Решение
Нека търсеният делител е , където . Понеже , имамеОсвен товатака че частното може да бъде само , или . Следователно трябва да има решение на едно от уравнениятаПървото няма решения при , защото тогава . Ако или , то . При второто уравнение получавамеа дискриминантата му е , което не е квадратичен остатък. При третото уравнение получавамеа дискриминантата му е , което също не е квадратичен остатък. Значи няма елементи на от класовете и . Остава да построим безбройно много примери в другите класове. От второто уравнение получавамеНека са положителните решения, зададени оти поставяме . Тогава , а от следва, че . Следователно всяко такова принадлежи на . По модул редицата се повтаря с период и дава остатъцитеТака получаваме безбройно много елементи на от класовете , и . За останалите два класа използваме третото уравнение. Некаи поставямеТогава е нечетно и от следватоест . Освен това , защото . Следователно тези също са елементи на . По модул редицата се повтаря с период и дава остатъцитеТака получаваме безбройно много елементи и от класовете и . Това завършва доказателството.2017
4 задачиЗадача 2
Условие
Да се намери най-малкото положително цяло число , за което съществуват оцветяване на положителните цели числа в цвята и функция със следните две свойства: 1. За всички едноцветни положителни цели числа е изпълнено . 2. Съществуват положителни цели числа , за които .Решение
Отговорът е . Конструкцията за е следната. Оцветяваме числата според остатъка им по модул и дефинирамеАко и са едноцветни, то лесно се проверява, че . От друга страна, , докато , така че второто свойство също е изпълнено. Остава да докажем, че два цвята не стигат. Всъщност ще докажем малко по-силно твърдение: при два цвята всяка функция , която удовлетворява първото свойство, е линейна. След умножаване с положителна константа можем да считаме, че . Цветовете ще наричаме червен и син. Първо, за всяко имамезащото е едноцветно със себе си. Ще докажем по индукция, че за всяко положително цяло . Нека вече знаем това за , и поставяме . Без ограничение нека е червено. Да допуснем, че . Числото не може да е червено, защото тогаваа лявата страна е , докато , откъдето би следвало . Значи е синьо. Тогава числото трябва да е червено; ако беше синьо, щяхме да имамепротиворечие. Понеже и са червени, получавамеАко е червено, тоНо , следователно , противоречие. Ако пък е синьо, тооткъдето пак . И в двата случая получаваме противоречие, така че наистина . Индукцията доказва за всички . Следователно при два цвята първото свойство принуждава функцията да бъде адитивна за всички двойки, което прави второто свойство невъзможно. При един цвят това е още по-ясно. Затова минималното е .Задача 3
Условие
В равнината са дадени прави, като никои три от тях не минават през една точка. Охлювът Турбо стои в точка, която лежи върху точно една от правите, и започва да се плъзга по правите по следния начин. Тя се движи по дадена права, докато стигне до пресечна точка на две прави. В пресечната точка продължава по другата права, като завива наляво или надясно, и редува избора си при всяка пресечна точка, която достигне. Тя може да сменя посоката си само в пресечни точки. Възможно ли е да съществува отсечка от права, през която Турбо минава и в двете посоки по време на своето движение?Решение
Отговорът е не. Оцветяваме областите, на които правите разделят равнината, шахматно в черно и бяло: две области с обща страна имат различни цветове. Това е възможно, защото при преминаване през права цветът просто се сменя. Да проследим движението на Турбо. Когато тя стигне до пресечна точка и мине на другата права, завиването наляво или надясно определя около коя от съседните области се движи в този момент. Понеже при следващата пресечна точка изборът се сменя, а цветът на областта от съответната страна също се сменя, получаваме следния инвариант: Турбо винаги обхожда границите на черните области с една и съща ориентация, а границите на белите области с противоположната ориентация. Ако някоя отсечка бъде премината в двете посоки, то двете области от двете страни на тази отсечка биха били обхождани веднъж в едната и веднъж в обратната ориентация. Това противоречи на описания инвариант. Следователно такава отсечка не може да съществува.Задача 4
Условие
Нека е цяло число и нека са положителни цели числа. В група от души се играят няколко партии шах. Всеки двама души могат да играят помежду си най-много веднъж. Докажете, че е възможно едновременно да са изпълнени следните две условия: 1. Броят партии, изиграни от всеки човек, е едно от числата . 2. За всяко с има човек, който е изиграл точно партии шах.Решение
Ще преведем задачата на езика на графите. Търсим прост граф с върха, така че всички степени да принадлежат на множеството и всяка от тези степени да се среща поне веднъж. Доказваме съществуването с индукция по . При вземаме пълен граф върху върха; тогава всяка степен е . При вземаме пълен граф върху върха и празен граф върху върха, след което свързваме всеки връх от първата част с всеки връх от втората част. Върховете от първата част имат степен , а върховете от втората имат степен , така че и двете степени се срещат. Нека сега . По индукционното предположение съществува пример за -торкатакойто има върха. Към него добавяме изолирани върха. Накрая добавяме още универсални върха, тоест върхове, свързани с всички останали върхове и помежду си. Сега старите върхове от индукционния пример увеличават степените си с и така дават степените . Новите изолирани върхове стават със степен , защото са свързани само с универсалните върхове. Самите универсални върхове имат степен , понеже общият брой върхове е . Следователно всички степени се срещат и други степени няма. Това завършва индукцията и доказателството.Задача 6
Условие
Нека е остроъгълен разностранен триъгълник. Отраженията на медицентъра и на центъра на описаната окръжност на спрямо страните , и се означават съответно с , , и , , . Докажете, че описаните окръжности на триъгълниците , , , , , и имат обща точка.Решение
Ще използваме комплексни числа върху единичната описана окръжност на . Нека е произволна точка. Нека и са отраженията на съответно спрямо правите и , а и са вторите пресечни точки на правите и с описаната окръжност. Ще намерим втората пресечна точка на окръжностите и . От формулата за отражение спрямо хорда на единичната окръжност имамеЗа да намерим , използваме колинеарността на , и :откъдетоАналогичноСледователно търсената пресечна точка еТози израз е симетричен по , и . Сега вземаме , т.е. , и , т.е. . В двата случая получаваме една и съща точка от описаната окръжност на ; същата формула е симетрична, затова при циклична смяна на ролите на върховете тя лежи върху всички шест окръжности, построени от отраженията на и . Следователно тези шест окръжности и описаната окръжност на имат обща точка.2018
4 задачиЗадача 2
Условие
Разгледайте множествотоЗа всяко цяло число нека означава най-малкото цяло число, за което може да се представи като произведение на елемента на (не задължително различни). Докажете, че съществуват безкрайно много двойки цели числа и , за коитоРешение
Една от многото възможни конструкции е следната. Нека , където , и вземамеТогава е цяло число, защото . Първо ще използваме две малки наблюдения. За всяко имамепонеже всеки елемент на е най-много . От друга страна,така че . Остава да знаем, че . Действително,следователно . Ако имаше представяне с най-много четири множителя, някой от множителите трябва да има числител, делящ се на ; всеки такъв множител е най-много . Но тогава останалите най-много три множителя са най-много , и произведението е най-многопротиворечие. Значи . Накрая получавамеПонеже , това дава . Такива има безкрайно много, следователно и търсените двойки са безкрайно много.Задача 3
Условие
-те състезателки на EGMO са означени с . След състезанието те се нареждат на опашка пред ресторанта по следните правила. - Журито избира началния ред на състезателките в опашката. - Всяка минута журито избира цяло число с . - Ако пред състезателката има поне други състезателки, тя плаща едно евро на журито и се премества напред в опашката с точно позиции. - Ако пред състезателката има по-малко от други състезателки, ресторантът отваря и процесът завършва. За всяко докажете, че този процес непременно завършва, и намерете най-големия брой евро, който журито може да събере чрез хитър избор на началния ред и на последователността от ходове.Решение
Максималната сума еТова число е крайно, така че едновременно ще докажем и че процесът не може да продължава безкрайно. Да наречем всеки платен ход скок и нека е броят скокове на . Забелязваме две неща. Първо, когато скача, тя прескача поне една състезателка с . Второ, фиксирана състезателка може да прескочи дадена с най-много пъти: първото прескачане може да се случи преди изобщо да се е движила, а всяко следващо изисква междувременно да е скочила обратно пред . Оттук , а за всяко имамеСледователнои по същия начин индуктивноСумирането по всички дава горната граница . Остава да построим стратегия, която я достига. Конструкцията е индуктивна. За например, ако ресторантът е отдясно, може да се получи последователносттас четири платени скока. В общия случай започваме от обратния ред. Първо прилагаме индукционната стратегия само върху , така че техният ред да се обърне. После всяка от скача веднъж през . След това повтаряме същата индукционна стратегия върху първите състезателки. Така броят събрани евро удовлетворяваоткъдето . Това съвпада с горната граница.Задача 4
Условие
Нека е цяло число. Върху дъска са поставени няколко неприпокриващи се домина. Стойността на ред или колона е броят домина, които покриват поне една клетка от този ред или тази колона. Конфигурация от домина се нарича балансирана, ако съществува , така че всеки ред и всяка колона има стойност . Докажете, че за всяко съществува балансирана конфигурация, и намерете най-малкия възможен брой домина в такава конфигурация.Решение
Отговорът еиПърво доказваме, че по-малко не може. Нека в балансирана конфигурация има домина и общата стойност на всеки ред и всяка колона е . Броим наредените двойкиОт една страна, има реда и колони общо, всеки със стойност , така че броят е . От друга страна, всяко домино докосва или един ред и две колони, или два реда и една колона; във всички случаи то допринася точно . ЗначитоестПонеже , първите възможни стойности са ; вземаме първата, която е цяло число. Това дава долната граница по-горе. Сега даваме конструкции. Ако , поставяме по главния диагонал блокове от видаВъв всеки такъв блок има две домина и , следователно общият брой е . Остава случаят . За имаме следните блокове с и съответно домина:Всеки по-голям размер може да се получи като сбор на числа от , а блоковете се поставят по главния диагонал. Така получаваме балансирана конфигурация с и точно домина за всички останали .Задача 6
Условие
Фиксирано е реално число . (a) Докажете, че съществува положително цяло число , такова че за всяко множество от положителни цели числа е изпълнено следното: съществуват различни и неотрицателно цяло число , за които(b) Определете дали съществува безкрайно множество от положителни цели числа със следното свойство: за всеки две различни и всяко положително цяло число имамеРешение
Първо доказваме (a). Да допуснем противното за някакво голямо и некаПонеже условието не трябва да се случва дори при , за всяко имамеи следователноИзбираме толкова голямо, че . Ако всяко две съседни отношения в горната редица се различаваха по множител повече от , щяхме да получимкоето противоречи на вече доказаното . Значи за някои имамеСледователнокоето е забраненият случай с , и . Това противоречие доказва (a). За (b) отговорът е да. Ще построим такова множество с жаден алгоритъм. Избираме голямо цяло число , за коетоЩе дефинирамеиндуктивно. Първо нека е произволно просто число, по-голямо от . След като вече са избрани , избираме да бъде просто число, по-голямо от , и такова чеТова е възможно по китайската теорема за остатъците и теоремата на Дирихле за прости числа в аритметични прогресии. Проверяваме свойството. Ако , тогава . Затова при , и всяко положително имамепонеже най-близкият случай е , а тогава . В обратната посока разглеждаме , . По конструкция дробната част на еТя е на разстояние повече от от всяко цяло число, защото и . Следователно за всяко положително цяло имамеТова доказва, че построеното безкрайно множество има исканото свойство.2019
5 задачиЗадача 1
Условие
Намерете всички тройки от реални числа, за които иРешение
Отговорът екакто и всички пермутации на и . Лесно се проверява, че всички тези тройки работят. Сега ще докажем, че други няма. Използваме условието , за да хомогенизираме първото равенство:След съкращаване това е еквивалентно натоестПолучаваме и двете циклични аналогични условия. Ако някоя от променливите е нула, например , тогава от следва, че и са ненулеви. Първоначалното равенство дава , откъдето или . Това дава точно пермутациите на и . Остава случаят, когато са ненулеви. Тогава имамеСумирайки, получавамеследователноЗначи . От следва , което дава двете равни тройки по-горе.Задача 2
Условие
Нека е положително цяло число. Върху дъска са поставени домино плочки така, че всяка клетка на дъската е съседна по страна на точно една клетка, покрита от домино. За всяко определете най-големия брой домино плочки, които могат да бъдат поставени по този начин.Решение
Отговорът еЩе наричаме аура на едно домино множеството от всички клетки, които са съседни по страна на клетка от това домино. По условие всяка клетка на дъската принадлежи на точно една такава аура, следователно аурите разбиват всички клетки на дъската. Конструкцията, която достига домино плочки, се получава от показания повтарящ се строеж. Цветните многоъгълници са аурите; в краищата на дъската някои от тях се отрязват от границата.Една аура може да съдържа най-много клетки, но ако границата на дъската я отреже, може да остане и с едва клетки. Нека са броевете на аурите, които съдържат съответно клетки. Търсим горна граница за . Освен товазащото аура с клетки непременно използва ъгъл на дъската. Ключовото наблюдение за отрязаните аури е следното: аурите, броени от , и , имат съответно , и между и гранични клетки, където гранични наричаме клетките, които докосват страна на дъската. Понеже общият брой гранични клетки е , получавамеОт друга страна, понеже аурите разбиват дъската,СледователноЗначиТъй като е цяло число, оттук следваТова дава исканата горна граница, а конструкцията по-горе показва, че тя се достига. Всъщност решението на IMO 1999/3 дава и друг кратък поглед към обратната оценка. Оцветете дъската на пръстени, както е показано по-долу.Всяка аура покрива точно четири сини клетки. Броят на сините клетки при това оцветяване е , следователно броят на аурите, а значи и на поставените домино плочки, не може да надминеТова съвпада с конструкцията и завършва решението.Задача 4
Условие
Нека е триъгълник с инцентър . Окръжността, която минава през и се допира до правата в , пресича страната повторно в точка . Окръжността, която минава през и се допира до правата в , пресича страната повторно в точка . Докажете, че се допира до вписаната окръжност на .Решение
Нека и са допирните точки на вписаната окръжност съответно със страните и .Работим с насочени ъгли. От теоремата за ъгъла между допирателна и хорда, приложена към окръжността през , получавамезащото лежи върху , а е ъглополовяща. Освен това , а е ъглополовяща в , следователноЗатоваСъщият аргумент за окръжността през даваНека е втората допирна точка от към вписаната окръжност, различна от , а е втората допирна точка от , различна от . Понеже двете допирателни от една външна точка са равни, триъгълниците и са правоъгълни с обща хипотенуза и равни катети . СледователноАналогичноОт друга страна, радиусите и са перпендикулярни съответно на и , така чеСледователно точките и съвпадат; означаваме общата им стойност с . Правите и са допирателни към вписаната окръжност в една и съща точка , затова те са една и съща допирателна. Значи са колинеарни и правата се допира до вписаната окръжност. С други думи, в това доказателство същественото ъглово съдържание е равенството , което следва от същото пресмятане.Задача 5
Условие
Нека е цяло число и нека са положителни цели числа. Докажете, че съществуват положителни цели числа , които удовлетворяват следните три условия: - за ; - остатъците на при деление на са две по две различни; -Решение
Първо свеждаме задачата до случая за всяко . Ако някое , можем да заменим с ; след намиране на подходящо за намалената задача добавяме обратно към съответното . Остатъкът по модул не се променя, а двете страни на желаната оценка за сумата се увеличават с едно и също число . Повтаряйки това, получаваме . Сега избираме на случаен принцип равномерна пермутация на множеството и дефинирамеТогава за всяко , а остатъците на по модул са точно остатъците на различните числа , следователно са две по две различни. Нека е броят на индексите , за които . ТогаваЗа фиксирано вероятността е , затоваСледователно съществува пермутация, за коятоЗа тази пермутация получавамекоето е точноТака исканите числа съществуват.Задача 6
Условие
Върху окръжност Алина начертава хорди, чиито краища са всички различни. Една точка се нарича маркирана, ако е или - един от -те края на хорда; или - пресечна точка на поне две хорди. От -те точки от първия вид Алина означава точки с , а останалите точки с . Всяка точка от втория вид тя означава с произволно цяло число, не непременно положително. По всяка хорда Алина разглежда отсечките между две съседни маркирани точки. (Ако върху една хорда има маркирани точки, тя дава такива отсечки.) Върху всяка такава отсечка тя записва в жълто сбора на числата в двата ѝ края, а в синьо - абсолютната стойност на тяхната разлика. Алина установява, че жълтите числа, които са на брой, приемат всяка от стойностите точно по веднъж. Докажете, че поне едно синьо число е кратно на .Решение
Ще използваме само остатъците на означенията по модул . Да допуснем противното: никое синьо число не е кратно на . Тогава двата края на всяка разглеждана отсечка имат различни остатъци по модул . За нека е броят на отсечките, чиито краища имат остатъци и по модул . Ще преброим по модул краищата на отсечки, инцидентни с върхове от даден остатък. Всяка вътрешна пресечна точка на хорди участва в четен брой такива краища, защото през нея минават поне две хорди и всяка дава по две съседни отсечки. Краят на хорда участва в точно един такъв край. Понеже има крайни точки с означение и крайни точки с означение , а няма крайни точки с означение , получавамеСледователно и имат еднаква четност, а има противоположна четност. От друга страна, жълтото число върху отсечка от тип е по модул , върху отсечка от тип е по модул , а върху отсечка от тип е по модул . Понеже жълтите числа са точно , ако е броят на отсечките, то броевете на жълтите числа с остатъци по модул са съответно: - , ако ; - , ако ; - , ако . Това означава, че е една от тези три тройки. Ако , трите числа имат еднаква четност, което противоречи на факта, че е с противоположна четност на . Ако , числата и имат различна четност, противоречие. Ако , числата и имат еднаква четност, отново противоречие. И в трите случая стигаме до невъзможност. Следователно поне едно синьо число е кратно на .2020
4 задачиЗадача 1
Условие
Нека е редица от положителни цели числа, за коятоза . Докажете, че поне един от членовете на редицата се дели на .Решение
Ще докажем по-силното твърдение: за всяко , ако положителни цели числаудовлетворяват , то някой от тези членове се дели на . При това е точно делимост на . За имаме , следователно е четно. Тогава се дели на , което доказва базата. Нека и приемем твърдението за . Отследва първо, че са четни, а после, за , че се дели на . Следователноса положителни цели числа и удовлетворяват същата рекурентна връзка. По индукционното предположение някое се дели на , така че съответният се дели на . Индукцията е завършена.Задача 2
Условие
Намерете всички списъци от неотрицателни реални числа, които удовлетворяват следните три условия:и съществува пермутация на , такава чеРешение
Отговорът е един от двата списъкаилиИ в двата случая равенството се получава, като пермутацията сдвоява всяка по-малка стойност със съответната по-голяма стойност. Ще използваме следното неравенство за неотрицателни реални числа. Ако и , токато равенство има само когато или . Наистина,Условията показват, че всеки два члена на списъка се различават с най-много ; затова неравенството може да се приложи към всяка двойка . Получавамепонеже е пермутация на . В условието има равенство, следователно във всяка отделна двойка има равенство. Значи всяка двойка е от вида или от вида . Поради в списъка не могат едновременно да присъстват и . Ако стойностите са и , всяка нула трябва да бъде сдвоена с единица и всяка единица с нула, така че броевете им са равни: по . Аналогично, ако стойностите са и , те също са по . Това дава точно двата списъка по-горе.Задача 4
Условие
Нека е цяло число. Една пермутация на числата се нарича свежа, ако не съществува положително цяло число , за което първите числа в пермутацията са точно в някакъв ред. Нека е броят на свежите пермутации на . Докажете, че .Решение
За всяка свежа пермутация на ще построим различни свежи пермутации на . Първите от тях се получават, като вмъкнем на -та позиция за . Последната се получава по друг начин: заменяме числото с и добавяме в края. Например от получаваме и . Тези пермутации са свежи. При вмъкване на всяка забранена начална част с дължина или съдържа , което е невъзможно за множеството , или не го съдържа и тогава би дала забранена начална част в старата пермутация. При последната конструкция краят е , а преди него стои на мястото на ; отново всяка забранена начална част или съдържа , или би нарушила свежестта на началната пермутация. Освен това всички построени пермутации са различни. Ако изтрием от пермутация от първите вида, получаваме обратно свежата пермутация . При последния вид обаче изтриването на оставя в края, така че получената пермутация на е несвежа, защото първите позиции са точно числата . Следователно построението е инективно и дава поне свежи пермутации.Задача 6
Условие
Намерете всички цели числа , за които редицата , зададена с , иза , съдържа само точни квадрати.Решение
Отговорът еПърво проверяваме, че тези стойности работят. При имаме , където са числата на Фибоначи; тъждеството следва от . При дефинираме , и за . Тогаватака че за всички . Остава да докажем, че няма други стойности. Първите членове саАко всички членове са точни квадрати, то също е точен квадрат. Директно пресмятане даваНекаТогава иЗа всяко цяло имаме и , следователноНо е квадрат, чийто корен се дели на . Тъй като , единствената възможност между и е коренът да бъде . Значиоткъдето . След заместване на получаваметоест или .2021
6 задачиЗадача 1
Условие
Числото е фантастично. За всяко положително цяло число , ако поне един елемент на множеството е фантастичен, то и трите елемента са фантастични. Следва ли, че числото е фантастично?Решение
Отговорът е да. Ще пишем , когато е фантастично точно тогава, когато е фантастично. От условието получаваме и за всяко положително цяло число . Освен товаСледователно и за всяко . Така всяко положително цяло число е еквивалентно на числото, което се получава след премахване на последната двоична цифра: четно число е еквивалентно на , а нечетно число е еквивалентно на . Повтаряйки този процес, стигаме до . Значи всички положителни цели числа са едновременно фантастични или едновременно нефантастични. Понеже е фантастично, всяко положително цяло число е фантастично, в частност .Задача 2
Условие
Намерете всички функции , за коитоза всички рационални числа и .Решение
Отговорите саи директната проверка е непосредствена. Да означим твърдението с . Първо ще покажем, че ако , то . Наистина, от получавамеследователно . Значи няма нулеви стойности извън . Сега нека са ненулеви. Тогава и също са ненулеви. Избираме ненулеви цели числа така, чеЗа всяко многократното използване на уравнението даваЛевите страни са равни по избора на и , затова . Следователнотоест . Значи съществува константа , така че за всяко ненулево рационално . Поставяме в началното уравнение. За всяко ненулево имамеПонеже , лявата страна е . Таказа всички ненулеви рационални , откъдето и . Следователно или , което дава точно двете решения.Задача 3
Условие
Нека е триъгълник с тъп ъгъл при . Нека и са пресечните точки на външната ъглополовяща на съответно с височините на , прекарани през и . Нека и са точки съответно от отсечките и , за коитоДокажете, че точките лежат на една окръжност.Решение
Нека и са височините, е ортоцентърът, а е средата на . Съгласно IMO Shortlist 2005 G5 правата пресича отново окръжностите , и в една и съща точка . Понежеокръжността е допирателна към в . Следователно . Тогаваследователно лежи на . По същия начин и лежи на тази окръжност. Значи са вписани в една окръжност.Задача 4
Условие
Нека е триъгълник с инцентър , а е произволна точка от страната . Правата през , перпендикулярна на , пресича в . Правата през , перпендикулярна на , пресича в . Докажете, че отражението на спрямо правата лежи на правата .Решение
Първо ще докажем следното твърдение. **Твърдение.** Четириъгълникът е вписан. **Доказателство.** Нека . ТогаваиСледователно съответно и са вписани.\qed По теоремата за линията на Симсон трите проекции на върху страните на са колинеарни. Проекциите върху и са среди на отсечките, чиито други краища са отраженията на съответно спрямо правите и . Тези отражения по определение лежат на , така че и двете проекции лежат на . Следователно и проекцията на върху лежи на . Нейният образ при централната симетрия с център тази проекция, т.е. отражението на спрямо , също лежи на .Задача 5
Условие
В равнината е дадена специална точка , наречена начало. Нека е множество от точки в равнината, такова че никои три точки от не лежат на една права и никои две точки от не лежат на права, минаваща през началото. Наричаме триъгълник с върхове от обхващащ, ако е строго вътре в него. Намерете максималния възможен брой обхващащи триъгълници.Решение
Максималният брой еЗа всяка двойка точки насочваме ребро , ако при завъртане от лъча към лъча по часовниковата стрелка се изминава ъгъл, по-малък от . Понеже никои две точки от не лежат на права през , за всяка двойка се получава точно една посока. Така получаваме турнир върху върха. Един триъгълник обхваща точно когато трите насочени ребра между върховете му образуват насочен цикъл. Следователно задачата се свежда до максималния брой насочени -цикли в турнир с върха. По стандартния резултат от Canada 2006/4 този брой е най-многоза върха. При получаваме посочената стойност. Равенство се достига, когато точките са върховете на правилен -ъгълник с център . Тогава съответният турнир е регулярният кръгов турнир и броят на насочените цикли е точно горната граница.Задача 6
Условие
Съществува ли неотрицателно цяло число , за което уравнениетоима повече от един милион различни решения в положителни цели числа?Решение
Отговорът е да. Ще докажем малко по-общо твърдение. **Твърдение.** Нека е функция, за която . Тогава за някое неотрицателно цяло число уравнениетоима повече от един милион решения в положителни цели числа. Доказателство на твърдението. За всяко избирамеТогава иПонеже , имамеЗатова можем да изберем достатъчно голямо, така чеТака от различни стойности на получаваме тройки , но възможните стойности на са по-малко от . По принципа на Дирихле някоя стойност на се среща повече от пъти. Това доказва твърдението. В нашата задача вземамеИмаме оценкататака че общото твърдение се прилага и дава търсеното число .2022
2 задачиЗадача 2
Условие
Да се намерят всички функции , такива че за всички са изпълнени следните две условия: 1. ; 2. поне две от числата , и са равни.Решение
Отговорът екъдето е произволно положително цяло число, а е фиксирано просто число. Лесно се проверява, че всяка такава функция работи. Наистина, ако , тогава . Ако пък , тогаватака че едно от числата и е равно на . Остава да докажем, че други решения няма. От първото условие имаме , а функцията е напълно мултипликативна. Ако има най-много едно просто число , за което , тогава от пълната мултипликативност веднага следва, че е от горния вид. Да допуснем за противоречие, че има поне две прости числа с образ по-голям от . Нека са двете най-малки такива прости числа. Понеже и , всички прости делители на имат образ , следователно . Прилагаме второто условие към числата и . Трите стойности саТъй като и , трябва да имамеСега ще изберем положителни цели числа и , за коитоиНекаТогава и . Поставямеи избирамеТогава , така че , а . Освен това , понеже е остатъкът при деление на с , и . Имаме още , откъдето . Накрая, от следва , така че ; понеже , получаваме , а от следва и . Поради минималността на и това даваНо вече знаем, че , а , така че трите числа , и са две по две различни. Това противоречи на второто условие и завършва доказателството.Задача 4
Условие
Дадено е положително цяло число . Да се определи най-голямото положително цяло число , за което съществуват реални числа , такива че 1. ; 2. за всяко .Решение
Отговорът е . ПоставямеТогава условието за се превръща вПонеже това е равносилно наако , получаваме рекурентната формулаОт началното условие имаме . Сега по индукция намирамеНаистина, ако и , тоСледователно . Затова не може да се продължи до : при равенството би дало , което е невъзможно. Значи . Остава да покажем, че се достига. Вземаме например и после определяме рекурентноТогава за всички , а току-що проверената рекурентна връзка между гарантира второто условие за всяко . Следователно най-голямата възможна стойност на е .2023
4 задачиЗадача 1
Условие
Дадени са положителни реални числа . За всяко полагамекъдето индексите се разглеждат по модул . Да се предположи, че за всички и от до е изпълненоДокажете, че .Решение
Първо ще докажем, че . Нека е индекс, за който . Понеже редът на числата и е един и същ, имаме и . Нозащото и . По същия начин, ако е индекс, за който , то , аСледователно всички числа са равни на . Значи за всяко имамеИзбираме индекс с . Тогава двете съседни числа на са най-много , а сборът им е точно , следователно и двете са равни на . Продължавайки по цикъла, получаваме, че всички са равни.Задача 3
Условие
Нека е фиксирано положително цяло число. Лекси има речник , състоящ се от някои низове с дължина , които съдържат само буквите и . Лекси иска да запише във всяка клетка на таблица една от буквите и така, че всеки стълб, прочетен отгоре надолу, да е низ от , и всеки ред, прочетен отляво надясно, също да е низ от . Кое е най-малкото цяло число със следното свойство: ако съдържа поне различни низа, тогава Лекси може да попълни таблицата по този начин, независимо кои точно низове са в ?Решение
Отговорът еПърво показваме, че низа не стигат. Нека се състои от всички низове, които започват с , с изключение на низа . Тогава . Ако съществуваше попълване, всеки стълб щеше да започва с , затова първият ред на таблицата щеше да бъде . Но този низ не е в , противоречие. Остава да докажем, че низа винаги стигат. Ако съдържа низа или низа , просто попълваме цялата таблица съответно само с или само с . Нека сега нито един от тези два константни низа не е в речника. Останалите възможни низа се разбиват на двойки противоположни низове: в една двойка поставяме два низа, които на всяка позиция имат различни букви, например и . Понеже , по принципа на Дирихле в има цяла такава двойка противоположни низове. Нека единият от тях е , а другият е противоположният му низ. Попълваме клетката в ред и стълб с буквата , ако , и с противоположната буква на , ако . Тогава всеки стълб е или , или противоположният низ, а всеки ред също е един от тези два низа. Следователно всички редове и стълбове принадлежат на , както се искаше.Задача 4
Условие
Охлювът Турбо стои в точка от окръжност с дължина . Дадена е безкрайна редица от положителни реални числа . Турбо последователно изминава разстояния по окръжността, като всеки път избира дали да пълзи по часовниковата стрелка или обратно на часовниковата стрелка. Да се определи най-голямата константа със следното свойство: за всяка редица от положителни реални числа с за всички , Турбо може, след като разгледа редицата, да гарантира, че има точка от окръжността, която никога няма да посети или да препълзи.Решение
Отговорът еПърво нека за всяко . Избираме произволна точка от окръжността, различна от началната точка на Турбо, и ще я пазим непосетена. Преди всеки ход Турбо не се намира в . Двете възможни дъги с дължина от текущото място, едната по часовниковата стрелка и другата обратно, не могат и двете да съдържат . Затова Турбо избира посоката, чиято дъга не съдържа . Така никога не се посещава и не се препълзява. Сега ще покажем, че всяко е невъзможно. Избираме така, че , и разглеждаме редицатаАко два последователни хода са в една и съща посока, техните дължини имат сбор , така че Турбо ще препълзи цялата окръжност. Следователно, за да избегне това, той е принуден да редува посоките на движение. При такова редуване след края на -тия ход Турбо се намира в край на вече препълзяна дъга с дължина . За достатъчно голямо тази дължина е поне , тоест цялата окръжност е препълзяна. Следователно за всяко съществува редица с , срещу която Турбо не може да запази непосетена точка.Задача 5
Условие
Дадено е положително цяло число . За всяко положително цяло число дефинираме неговото преобразуване така: записваме , където са неотрицателни цели числа и , и полагаме . За положително цяло число разглеждаме безкрайната редица , където и за всяко положително цяло число . Докажете, че тази редица съдържа тогава и само тогава, когато остатъкът на при деление на е или .Решение
Започваме с две прости наблюдения. Първо, ако , то се получава, като разгледаме като двуцифрено число в основа (с водеща нула, ако ) и разменим двете му цифри. В частност, повторната размяна връща числото обратно. Второ, ако , то . Наистина, при имаме , аСледователно описаната безкрайна редица в крайна сметка се редува между числата и за някакви . Тя съдържа точно когато , тоест когато накрая се редува между и . Остава да свържем това с остатъка по модул . Ще докажем, чеАко , това вече следва от размяната на двете цифри два пъти. В общия случай некакъдето са последните две цифри на в основа . Тогаваи след още едно преобразуване получавамеЗатовакоето доказва твърдението. Следователно членовете с една и съща четност в редицата имат един и същ остатък по модул . Когато редицата вече се редува между и , тези числа са между и . Затова редицата съдържа точно когато съответният краен двуцикъл е , което е еквивалентно на това първоначалното да дава остатък или по модул .2024
3 задачиЗадача 1
Условие
На дъската са написани две различни цели числа и . Извършваме последователност от ходове. На всеки ход можем да направим една от следните две операции: 1. Ако и са различни цели числа на дъската, можем да напишем , ако то още не е написано. 2. Ако са три различни цели числа на дъската и цяло число удовлетворява , можем да напишем , ако то още не е написано. Да се намерят всички начални двойки , от които всяко цяло число може в крайна сметка да бъде написано на дъската след краен брой ходове.Решение
Отговорът е: всички двойки различни цели числа , с изключение на случаите, в които някое от числата е , случаят и случаите, в които и двете числа са отрицателни. Първо виждаме защо тези изключения наистина са невъзможни. Ако едно от е , операцията със събиране не може да произведе ново число, а за квадратно уравнение са нужни три различни числа, така че не можем да започнем. Ако , операцията със събиране дава само , а след това нито една от двете операции не може да добави ново число. Накрая, ако и , тогава всички получени числа остават отрицателни: сборът на две отрицателни числа е отрицателен, а ако , то за имаме , така че положителен корен не може да се появи. Следователно в този случай не можем да получим всички цели числа. Ще докажем, че във всички останали случаи задачата е възможна. Най-напред можем да напишем . Наистина, можем да напишем , а числата , и са различни, понеже нито , нито е . Квадратното уравнениеима корен , затова може да бъде добавено. След това ще получим положително число . Понеже не сме в случая с две отрицателни числа и нито едно число не е , поне едно от е положително. Нека . Ако , сме готови. Ако , тогава другото число е отрицателно и, понеже случаят е изключен, то е най-много . Вече имаме , така че можем да напишем . После уравнениетоима корен , както искаме. Нека вече сме написали такова . Понеже имаме , можем последователно да напишем . Оттам можем да получим всички неотрицателни цели числа, като първо получим и после чрез събиране с получаваме , а с многократно добавяне на слизаме до всяко число в съответния интервал. Накрая, ако вече е написано, то е корен назатова можем да напишем и всички отрицателни цели числа. Това доказва достатъчността.Задача 3
Условие
Ще наричаме положително цяло число особено, ако за всеки положителен делител на числото дели . Докажете, че за всеки четири различни особени положителни цели числа е изпълненоРешение
Първо отбелязваме, че и всяко просто число са особени. Ще класифицираме съставните особени числа. Твърдение 1. Едно особено число има най-много два прости делителя, броени с кратност. Нека е най-малкият прост делител на и нека . Понеже е делител на , условието даваСледователноНо по модул имаме , откъдетоПонеже и дели това число, получаваме , тоестТъй като всички прости делители на са поне , числото не може да има три прости делителя с кратност. Твърдение 2. Квадрат на просто число никога не е особен. Ако , от делителя трябва да имаметоест . Това е невъзможно, защото . Твърдение 3. Ако е особено, където са прости числа, тогаваЧислото не е особено, така че можем да считаме . От условията за делителите и получавамеиВъв второто деление имаме , понеже , следователноПишем . От друга страна, от следвазатова и . Ако се дели на , тогава , тоест , и с горните граници получаваме . Ако пък не се дели на , тогава от и би следвало , което е невъзможно. Значи непременно , както твърдяхме. Сега фиксираме просто число . Особените числа, които се делят на , са най-много три: самото ; числотоако вторият множител е прост; и евентуално число , ако съществува просто , за коетоСледователно няма четири различни особени числа с общ прост делител. Това точно означава, че за всеки четири различни особени числа имаме .Задача 5
Условие
Да се намерят всички функции , такива че за всички са изпълнени: 1. и имат еднакъв брой положителни делители; 2. ако и , тоРешение
Отговорът екъдето е фиксирано просто число, а означава броя на положителните делители на . Първо проверяваме, че тези функции работят. Ясно е, че има точно положителни делители. Ако и , тогава в разлагането на поне един показател е строго по-малък от съответния показател в , а поне един е строго по-малък от съответния показател в . Следователнои оттукСега доказваме, че други решения няма. Имаме . Ако е просто число, тогава трябва да има точно два делителя, тоест също е просто число. Ако и са различни прости числа, то и , затоваЛявата страна е най-голям общ делител на две прости числа, следователно тези две прости числа трябва да са равни. Значи е едно и също просто число за всички прости ; означаваме го с . Твърдение 1. За всяко числото се дели на . Избираме просто число , което не дели и е различно от в случая, когато е просто. Тогава и , така чеЗначи . Твърдение 2. Ако са различни прости числа, а също са прости числа, тоДоказваме това с индукция по . При числото има делители. Тъй като е просто и се дели на , единствената възможност е . Нека и без ограничение . Вземаме ново просто число , различно от всички , и прилагаме условието къмиТези две числа не се делят едно друго, а техният НОД е . По индукционното предположениеСледователно е строго по-голям от това число, а понеже е степен на , заключаваме, че се дели на . Броят на делителите на е . Но никой собствен делител на произведението не е по-голям от , затова единствената възможност еОстава да преминем от прости стойности на показателите към произволни. Некакъдето всички основи са различни прости числа, числата са прости, а са произволни цели числа. ПишемЩе докажем с индукция по броя на непростите фактори , че . Случаят вече е доказан. Нека . Ако е просто, прехвърляме го към списъка с и сме готови. Иначе е съставно. По постулата на Бертран избираме просто число сНека е ново просто число и разгледамеТогава и , аПо индукционното предположениеиОт условието следва, че , следователноОт друга страна,Ако в това произведение се появи множител, по-голям от , то той трябва да е самото . Значи и няма други прости множители във . Получаваме , което завършва доказателството.2025
3 задачиЗадача 1
Условие
За положително цяло число некаса всички положителни цели числа, по-малки от и взаимнопрости с . Да се намерят всички , за коитоза всяко .Решение
Отговорът е: всички четни и всички степени на . Първо правим две прости наблюдения. Ако е четно, тогава всички числа са нечетни, така че всеки сбор е четен. Следователно . Ако е нечетно и не се дели на , тогава и , понеже и двете числа са взаимнопрости с . Но тогава е взаимнопросто с , което е забранено. Значи остава да разгледаме нечетните кратни на . Ако е степен на , тогава редицата е точно редицата на положителните числа, по-малки от и неделящи се на :Всеки две съседни числа в тази редица имат сбор, делящ се на , затова условието е изпълнено. Остава да докажем, че други нечетни кратни на не работят. Некакъдето , числото е нечетно и не се дели на . Тогава или . Ако , ще покажем, че и са съседни членове на редицата , а сборът им е взаимнопрост с . Наистина,така че числата и не са взаимнопрости с . От друга страна,иСледователно между и няма друг член на редицата . Освен товатака че сборът им е взаимнопрост с . Случаят е аналогичен: тогава и са съседни членове на редицата, а сборът им е взаимнопрост с . Така нечетно кратно на работи само когато , тоест когато е степен на .Задача 2
Условие
Безкрайна строго растяща редица от положителни цели числа се нарича централна, ако за всяко положително цяло число средното аритметично на първите члена на редицата е равно на . Докажете, че съществува безкрайна редица от положителни цели числа, такава че за всяка централна редица има безбройно много положителни цели числа , за които .Решение
Ще докажем, че може да се вземеФиксираме произволна централна редица . Ще казваме, че положително цяло число се появява, ако за някое . Тогава от дефиницията на централна редица следваЩе използваме свободно и факта, че се появяват произволно големи числа, понеже редицата е безкрайна и строго растяща. Разглеждаме пролукитеЩе разделим доказателството според това дали пролуката се среща безбройно много пъти. Първи случай: има безбройно много пролуки, равни на . Тогава има безбройно много числа , за които и , и се появяват. За всяко такова имамеиКато извадим, получавамеСледователно за безбройно много . Втори случай: има само краен брой пролуки, равни на . Нека този брой е . Твърдение. Има най-много пролуки, по-големи от . В частност съществуват цяло число и индекс , такива чеза всяко . Доказателство на твърдението. Нека е достатъчно голямо появяващо се число, така че всички пролуки, равни на , да са преди индекс . Избираме друго появяващо се число от вида , където . ТогаваПонеже след индекс няма пролуки , имамеСледователноДясната страна еСравнявайки с , получаваме . Ако преди индекс има повече от пролуки, по-големи от , тогава, като използваме , всички останали пролуки поне и най-много пролуки, равни на , получаваме . Това противоречи на току-що доказаното. Значи пролуките, по-големи от , са най-много . Тъй като и пролуките, равни на , са краен брой, от някой момент нататък всички пролуки са точно , което доказва твърдението. Остава да определим . Вземаме достатъчно голямо и поставяме . Тогава и се появяват, а индексите и са след . ЗатоваОт формулата за големи получавамеСледователно . Значи във втория случай също имамеза всички достатъчно големи , и в частност за безбройно много . Това завършва доказателството.Задача 5
Условие
Фиксирано е цяло число . В една конфигурация на дъска всяка от клетки съдържа стрелка, сочеща нагоре, надолу, наляво или надясно. При дадена начална конфигурация охлювът Турбо започва от една от клетките и се движи от клетка в клетка. На всеки ход Турбо се премества с една клетка в посоката, указана от стрелката в текущата клетка, като е възможно да излезе извън дъската. След всеки ход стрелките във всички клетки се завъртат на обратно на часовниковата стрелка. Наричаме една клетка добра, ако при старт от тази клетка Турбо посещава всяка клетка на дъската точно веднъж, не излиза извън дъската и в края се връща в началната си клетка. Да се определи, в зависимост от , максималният възможен брой добри клетки измежду всички начални конфигурации.Решение
Ако е нечетно и , няма как да се обходи цялата дъска в цикъл, който посещава всяка клетка точно веднъж: такъв цикъл би имал нечетна дължина, а решетъчната дъска е двуделен граф и всеки цикъл в нея има четна дължина. Следователно при нечетно добри клетки няма и отговорът е . Нека сега е четно. Ще докажем, че отговорът е . Всъщност ще покажем малко по-силно твърдение: ако съществува поне една добра клетка, тогава добрите клетки са точно . Да фиксираме валиден цикъл, започващ от добра клетка. Той има хода, а това число се дели на . Ако започнем от всяка четвърта клетка по същия цикъл, стрелките ще бъдат в същото състояние спрямо момента на пристигане, така че Турбо ще проследи същия цикъл. Това дава поне добри клетки. Остава да докажем, че повече не може. Достатъчно е да разгледаме северозападния ъгъл на дъската. Има само четири възможни начина Турбо да мине през този ъгъл; индексите показват реда на посещаване на съответните клетки една спрямо друга:Това се проверява директно от факта, че Турбо не може да излезе през горната или лявата страна на дъската, а след всяка стъпка всички стрелки се завъртат с едно и също количество. Ще казваме, че две конфигурации са ротации една на друга, ако едната се получава от другата чрез завъртане на всички стрелки с един и същ брой пъти по . В четирите локални начина по-горе никои две конфигурации не са ротации една на друга. Следователно за дадена начална конфигурация и даден хамилтонов цикъл моментът по модул , в който Турбо минава през северозападния ъгъл, е еднозначно определен. След като този момент е известен, целият насочен хамилтонов цикъл също е еднозначно определен: за всяка клетка знаем в кой момент по модул е посетена и към коя съседна клетка трябва да води стрелката в този момент. Затова различните добри начални клетки могат да бъдат само онези, които се намират през четири стъпки по един и същ цикъл. Следователно броят им е най-много . За четно такива цикли наистина съществуват, например чрез стандартно серпентинно обхождане на дъската, затворено по края. Значи максималният брой добри клетки е .2026
1 задачаЗадача 6