maths.bgmaths.bg
Всички колекции
JMO

Evan Chen / JMO Solution Notes

66 задачи от базата, подредени за бързо решаване по година или клас. Показаните източници са тези, записани към самите задачи.

16 години1 класаИма видими липси
По годинаПо клас

Избрана година

2023

Назад към папките

Открити липси за попълване от източника

  • 2023 · 11-12: липсва задача 2

11-12

4 задачи

Задача 1

Пълен запис
Условие
Да се намерят всички тройки положителни цели числа (x,y,z)(x,y,z), за които е изпълнено 2(x+y+z+2xyz)2=(2xy+2yz+2zx+1)2+20232(x+y+z+2xyz)^2=(2xy+2yz+2zx+1)^2+2023.
РешениеОтговорът е всички пермутации на (2,3,3)(2,3,3). Основната стъпка е следното тъждество, което се проверява с директно разкриване на скоби: 2(x+y+z+2xyz)2−(2xy+2yz+2zx+1)2=2(x+y+z+2xyz)^2-(2xy+2yz+2zx+1)^2=(2x2−1)(2y2−1)(2z2−1).(2x^2-1)(2y^2-1)(2z^2-1). То може да се види и като умножение на норми в Q(2)\mathbb Q(\sqrt2), но тук самото тъждество е достатъчно. От даденото уравнение получаваме (2x2−1)(2y2−1)(2z2−1)=2023=7⋅172.(2x^2-1)(2y^2-1)(2z^2-1)=2023=7\cdot17^2. Всеки от трите множителя е положителен нечетен делител на 20232023. Делителите са 1,7,17,119,289,20231,7,17,119,289,2023. Ако 2t2−12t^2-1 е един от тях, то (d+1)/2(d+1)/2 трябва да е квадрат. Това става само за d=1,7,17d=1,7,17, като съответните стойности на tt са 1,2,31,2,3. В произведението обаче не може да участва множителят 11, защото тогава останалите два множителя трябва да дадат 20232023, а това би изисквало множител 119119 или 20232023, които не са от вида 2t2−12t^2-1. Следователно трите множителя са точно 7,17,177,17,17 в някакъв ред. Значи съответно x,y,zx,y,z са 2,3,32,3,3 в някакъв ред. Обратно, при всяка пермутация на (2,3,3)(2,3,3) трите множителя са 7,17,177,17,17, така че тъждеството връща точно даденото уравнение.
Отвори задачатаEvan Chen VONVON JMO 2023/1Условие — източник

Задача 3

Пълен запис
Условие
Нека nn е нечетно положително цяло число. Разглеждаме дъска n×nn\times n, съставена от единични квадратчета. Да наречем една конфигурация максимална, ако тя се състои от (n2−1)/2(n^2-1)/2 домина, подравнени по решетката, които покриват всички квадратчета освен едно. От такава конфигурация е позволено да плъзнем едно домино, без да го въртим, така че то да покрие непокритото квадратче; тогава се получава нова максимална конфигурация с друго непокрито квадратче. За максимална конфигурация CC нека k(C)k(C) е броят на различните максимални конфигурации, които могат да се достигнат от CC чрез поредица от такива плъзгания. Да се намери най-голямата възможна стойност на k(C)k(C).
РешениеОтговорът е (n+12)2.\left(\frac{n+1}{2}\right)^2. Номерираме квадратчетата с координати (x,y)(x,y), където 1≤x,y≤n1\le x,y\le n. За дадена конфигурация наричаме специални непокритото квадратче и всички квадратчета, чиито две координати имат същите четности като координатите на непокритото квадратче. Броят на специалните квадратчета е най-много ((n+1)/2)2((n+1)/2)^2. Ще покажем, че при плъзганията непокритото квадратче може да се движи само в една дървовидна компонента от специални квадратчета. Построяваме насочен граф върху специалните квадратчета. Ако домино покрива специално квадратче SS, то покрива и съседно неспециално квадратче; ако в същата посока на още една стъпка има специално квадратче TT, поставяме ребро S→TS\to T. Непокритото квадратче няма изходящо ребро. Всяко друго специално квадратче има най-много едно изходящо ребро. Нека GG е слабосвързаната компонента, която съдържа непокритото квадратче. В нея няма ненасочен цикъл: ако имаше такъв, условието за най-много едно изходящо ребро от връх би принудило целия цикъл да е насочен, а тогава той не може да лежи в компонента на връх без изходящо ребро. Следователно подлежащият граф на GG е дърво, а всички ребра в него са ориентирани към непокритото квадратче. Едно плъзгане по ребро на това дърво просто обръща ориентацията на това ребро и премества единствения връх без изходящо ребро в съседен връх. Така достижимите конфигурации са най-много колкото върховете на GG, а значи най-много ((n+1)/2)2((n+1)/2)^2. Остава да видим, че тази граница се достига. Избираме за специални всички квадратчета с нечетни координати и ги подреждаме в змиевиден път: първо минаваме през нечетните позиции в първия ред, после през нечетните позиции в третия ред в обратна посока, и така нататък. За всяко специално квадратче освен последното поставяме домино, което сочи към следващото специално квадратче по този път; последното остава непокрито. Останалите квадратчета се покриват с домина в неизползваните ленти между тези ходове. Получаваме дърво, което съдържа всички ((n+1)/2)2((n+1)/2)^2 специални квадратчета, и непокритото квадратче може чрез последователни плъзгания да бъде преместено във всеки негов връх. Следователно максималната стойност е точно ((n+1)/2)2((n+1)/2)^2.
Отвори задачатаEvan Chen VONVON JMO 2023/3Условие — източник

Задача 4

Пълен запис
Условие
Блейк и Руби играят игра върху безкрайна дъска от единични квадратчета. Първоначално всички квадратчета са бели. Двамата се редуват, като Блейк започва. На всеки ход Блейк оцветява в синьо едно бяло квадратче, а Руби оцветява в червено две бели квадратчета. Блейк може да приключи играта, когато пожелае; тогава резултатът е броят на единичните квадратчета в най-голямата проста многоъгълна област, съставена само от сини квадратчета. Да се намери най-големият резултат, който Блейк може да гарантира, независимо как играе Руби.
РешениеОтговорът е 44. Първо Блейк може винаги да постигне синя област от поне 44 квадратчета. Той започва от произволно квадратче и след това винаги избира бяло квадратче, което има обща страна с вече построената синя област. Трябва само да проверим, че докато синята област има m≤3m\le3 квадратчета, Руби не може да блокира всички възможни продължения. Всяка свързана фигура от m≤3m\le3 единични квадратчета има повече от 2m2m свободи, тоест несини квадратчета с обща страна със синята фигура. След mm хода на Блейк Руби е оцветила само 2m2m червени квадратчета, затова поне една свобода остава бяла и Блейк може да продължи. Така той достига четири свързани сини квадратчета. Сега описваме стратегия на Руби, която не допуска по-голяма синя област. Разделяме дъската на неприпокриващи се блокове 2×22\times2. Когато Блейк оцвети квадратче cc, Руби оцветява в червено всички бели квадратчета от същия блок, които имат обща страна с cc; ако така са по-малко от две, тя използва останалите си ходове произволно. Следователно в един блок никога няма две сини квадратчета с обща страна: първото от тях би накарало Руби веднага да оцвети второто в червено. За горната оценка вземаме произволно синьо квадратче ww. След завъртане на картината можем да смятаме, че ww е югоизточното квадратче в своя блок 2×22\times2. Нека xx, yy и zz са съответно квадратчетата непосредствено вдясно, непосредствено отдолу и диагонално вдясно-отдолу спрямо ww. Синя свързана област, която съдържа ww, не може да напусне четворката {w,x,y,z}\{w,x,y,z\}: когато някое от тези четири квадратчета стане синьо, стратегията на Руби оцветява неговите съседни квадратчета в съответния блок, а точно те са изходите от четворката навън. Значи всяка проста синя многоъгълна област има най-много 44 единични квадратчета. Комбинирайки двете стратегии, при оптимална игра най-голямата такава област има точно 44 квадратчета.
Отвори задачатаEvan Chen VONVON JMO 2023/4Условие — източник

Задача 5

Пълен запис
Условие
Фиксирани са положителни цели числа aa и NN, а на дъската са записани NN положителни цели числа. Алиса и Боб играят следната игра. На ход на Алиса тя трябва да замени някое число nn на дъската с n+an+a, а на ход на Боб той трябва да замени някое четно число nn на дъската с n/2n/2. Алиса започва и двамата се редуват. Ако на ход на Боб няма възможен ход, играта приключва. След като анализира NN-те числа на дъската, Боб разбира, че независимо какви ходове прави Алиса, той може да принуди играта в крайна сметка да приключи. Докажете, че всъщност за тези стойности на aa и за тези NN числа на дъската играта задължително приключва независимо от ходовете и на Алиса, и на Боб.
РешениеПри N=1N=1 няма какво да доказваме, защото на всеки ход играчът има най-много една възможност. Затова по-нататък разглеждаме само N≥2N\ge2. Нека SS е множеството от числата на дъската. Твърдение. Ако N≥2N\ge2 и ν2(x)<ν2(a)\nu_2(x)\lt{}\nu_2(a) за всяко x∈Sx\in S, тогава играта задължително приключва независимо как играе всеки от двамата. Доказателство. При ход на Алиса стойността на ν2\nu_2 на избраното число не се променя, понеже добавяме число с по-голяма 22-адична оценка. При ход на Боб стойността на ν2\nu_2 на избраното число намалява с 11. Играта приключва, когато всички тези оценки станат 00. Следователно Боб може да направи само краен брой ходове, независимо от избора на двамата играчи. Твърдение. Ако N≥2N\ge2 и на дъската има число xx с ν2(x)≥ν2(a)\nu_2(x)\ge\nu_2(a), тогава Алиса може да направи така, че играта да продължи безкрайно. Доказателство. Нека xx е първото число на дъската, като стойността му се променя с времето. Стратегията на Алиса е следната: ако ν2(x)=ν2(a)\nu_2(x)=\nu_2(a), тя играе върху първото число, така че новата стойност има ν2(x+a)>ν2(a)\nu_2(x+a)\gt{}\nu_2(a); в противен случай тя играе върху някое друго число. Двойна индукция показва, че точно преди всеки ход на Боб винаги е изпълнено ν2(x)>ν2(a)\nu_2(x)\gt{}\nu_2(a), а след всеки ход на Боб винаги е изпълнено ν2(x)≥ν2(a)\nu_2(x)\ge\nu_2(a). В частност Боб никога няма да остане без възможен ход, защото деленето на xx на 22 винаги е разрешено. Сега завършваме задачата. Ако имаше число xx на дъската с ν2(x)≥ν2(a)\nu_2(x)\ge\nu_2(a), второто твърдение би дало стратегия на Алиса за безкрайна игра, което противоречи на предположението, че Боб може да принуди край. Значи за всяко число xx на дъската имаме ν2(x)<ν2(a)\nu_2(x)\lt{}\nu_2(a), а по първото твърдение играта приключва независимо от ходовете на двамата.
Отвори задачатаEvan Chen VONVON JMO 2023/5Условие — източник