JMO

Evan Chen / JMO Solution Notes

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

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

По година По клас

Избран клас

11-12

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

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

2026 · 11-12: липсва задача 2, 4
2025 · 11-12: липсва задача 5
2023 · 11-12: липсва задача 2
2022 · 11-12: липсва задача 3, 4
2020 · 11-12: липсва задача 2, 3, 4
2019 · 11-12: липсва задача 3, 4
2018 · 11-12: липсва задача 3
2017 · 11-12: липсва задача 5
2016 · 11-12: липсва задача 5
2015 · 11-12: липсва задача 3
2014 · 11-12: липсва задача 2
2013 · 11-12: липсва задача 3, 5
2012 · 11-12: липсва задача 4
2011 · 11-12: липсва задача 3
2010 · 11-12: липсва задача 3

2010

5 задачи

Задача 1

Пълен запис

Условие

Нека

P(n)

е броят на пермутациите

(a_1,\ldots,a_n)

на числата

1,2,\ldots,n

, за които

ka_k

е точен квадрат за всяко

1\le k\le n

. Намерете с доказателство най-малкото

n

, за което

P(n)

се дели на

2010

Решение

Отговорът е

n=4489.

Първо ще опишем точно числото

P(n)

. Всяко положително цяло число се представя еднозначно във вида

c\cdot m^2,

където

c

е квадратносвободно положително цяло число, а

m

е положително цяло число. За всяко квадратносвободно

c

нека

S_c=\{c\cdot1^2,c\cdot2^2,c\cdot3^2,\ldots\}\cap\{1,2,\ldots,n\}.

Тогава множествата

S_c

разбиват числата от

1

до

n

, и

|S_c|=\left\lfloor\sqrt{\vphantom{x^2}\frac nc}\right\rfloor.

Условието

ka_k

да е точен квадрат означава точно, че

k

a_k

имат една и съща квадратносвободна част. Следователно допустимите пермутации са точно тези, които за всяко

c

разместват елементите на

S_c

само помежду им. Значи

P(n)=\prod_{c\text{ квадратносвободно}} |S_c|! =

\prod_{c\text{ квадратносвободно}} \left\lfloor\sqrt{\vphantom{x^2}\frac nc}\right\rfloor!.

Сега търсим най-малкото

n

, за което

2010

дели това произведение. Понеже

2010=2\cdot3\cdot5\cdot67,

необходимо е произведението да има множител

67

. Ако

n\lt{}67^2

, то за всяко

c

е изпълнено

\left\lfloor\sqrt{\vphantom{x^2}\frac nc}\right\rfloor\le66,

така че никой факториел в произведението не се дели на

67

. Следователно

2010\nmid P(n)

. От друга страна, при

n=67^2

членът за

c=1

67!

, който се дели на

2010

. Значи минималната стойност е

67^2=4489.

Отвори задачатаEvan Chen VONVON JMO 2010/1Условие — източник

Задача 2

Пълен запис

Условие

Нека

n\gt{}1

е цяло число. Да се намерят всички растящи редици от положителни цели числа

x_1,x_2,\ldots,x_{n-1}

, за които

x_i+x_{n-i}=2n

за всяко

i=1,2,\ldots,n-1

, и ако

x_i+x_j\lt{}2n

, то

x_i+x_j

също е член на редицата.

Решение

Ще докажем, че единствената възможност е

x_k=2k\qquad (k=1,2,\ldots,n-1).

Лесно се проверява, че тази редица наистина работи: тя е растяща, имаме

x_i+x_{n-i}=2i+2(n-i)=2n

, а ако

x_i+x_j=2(i+j)\lt{}2n

, то

i+j\lt{}n

и сумата е членът

x_{i+j}

. Остава да докажем единствеността. Понеже редицата е растяща, за всяко

m=1,2,\ldots,n-2

имаме

x_1+x_m \lt{} x_1+x_{n-1}=2n.

Следователно всяко число

x_1+x_m

е член на редицата. Тези

n-2

числа са строго растящи и всяко от тях е по-голямо от

x_1

. В редицата има точно

n-2

члена, които са по-големи от

x_1

, а именно

x_2,x_3,\ldots,x_{n-1}

. Значи задължително

x_1+x_m=x_{m+1}\qquad (m=1,2,\ldots,n-2).

Оттук по индукция получаваме

x_m=mx_1

за всички

m=1,2,\ldots,n-1

. Наистина, това е вярно за

m=1

, а ако

x_m=mx_1

, то

x_{m+1}=x_1+x_m=(m+1)x_1.

Накрая използваме условието

x_i+x_{n-i}=2n

. След заместване получаваме

ix_1+(n-i)x_1=nx_1=2n,

откъдето

x_1=2

. Следователно

x_m=2m

за всяко

m

, което доказва и единствеността.

Отвори задачатаEvan Chen VONVON JMO 2010/2Условие — източник

Задача 4

Пълен запис

Условие

Триъгълник се нарича параболичен, ако върховете му лежат върху параболата

y=x^2

. Докажете, че за всяко неотрицателно цяло число

n

съществуват нечетно число

m

и параболичен триъгълник с върхове в три различни точки с цели координати, чието лице е

(2^nm)^2

Решение

За

n=0

вземаме върховете

(1,1),\qquad (-1,1),\qquad (0,0).

Това са три различни точки с цели координати върху

y=x^2

, а лицето на триъгълника е

1=(2^0\cdot1)^2

. Нека вече

n\gt{}0

. Ще разгледаме триъгълника с върхове

(a,a^2),\qquad (-a,a^2),\qquad (b,b^2).

Основата между първите две точки има дължина

2a

, а височината до третата точка е

b^2-a^2

, ако изберем

b\gt{}a

. Следователно лицето е

\frac12\cdot2a\cdot(b^2-a^2)=a(b^2-a^2).

Избираме

a=2^{2n},\qquad m=2^{4n-2}-1,\qquad b=2^{4n-2}+1.

Тогава

m

е нечетно и

b^2-m^2=(b-m)(b+m)=2\cdot2^{4n-1}=2^{4n}=a^2.

Значи

b^2-a^2=m^2

, а лицето на построения триъгълник е

a(b^2-a^2)=2^{2n}m^2=(2^nm)^2.

Точките са различни и имат цели координати, така че построението доказва твърдението.

Отвори задачатаEvan Chen VONVON JMO 2010/4Условие — източник

Задача 5

Пълен запис

Условие

Две пермутации

a_1,a_2,\ldots,a_{2010}

b_1,b_2,\ldots,b_{2010}

на числата

1,2,\ldots,2010

се наричат пресичащи се, ако

a_k=b_k

за някое

k

1\le k\le2010

. Докажете, че съществуват

1006

пермутации на числата

1,2,\ldots,2010

, такива че всяка друга такава пермутация се пресича с поне една от тези

1006

пермутации.

Решение

Ще построим исканите

1006

пермутации. В първите

1006

позиции вземаме всички циклични размествания на числата

1,2,\ldots,1006

, а последните

1004

позиции оставяме фиксирани като

1007,1008,\ldots,2010.

Тоест пермутациите са от вида

\begin{align*} &(1,2,3,\ldots,1006,1007,\ldots,2010),\\ &(2,3,4,\ldots,1006,1,1007,\ldots,2010),\\ &(3,4,5,\ldots,1006,1,2,1007,\ldots,2010), \end{align*}

и така нататък, до всичките

1006

циклични размествания на първия блок. Ще докажем, че тази колекция работи. Нека

\pi

е произволна пермутация на числата

1,2,\ldots,2010

. Сред първите

1006

позиции на

\pi

трябва да има поне едно число от множеството

\{1,2,\ldots,1006\}

, защото числата

1007,1008,\ldots,2010

са само

1004

. Нека това число е

j

и нека стои на позиция

k

, където

1\le j,k\le1006

. В цикличните размествания на първия блок всяко от числата

1,2,\ldots,1006

се появява точно веднъж на всяка позиция от

1

до

1006

. Следователно една от построените

1006

пермутации също има числото

j

на позиция

k

. Тази построена пермутация се пресича с

\pi

, което доказва твърдението.

Отвори задачатаEvan Chen VONVON JMO 2010/5Условие — източник

Задача 6

Пълен запис

Условие

Нека

ABC

е триъгълник с

\angle A=90^\circ

. Точките

D

E

лежат съответно на страните

AC

AB

, като

\angle ABD=\angle DBC

\angle ACE=\angle ECB

. Отсечките

BD

CE

се пресичат в

I

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

AB

AC

BI

ID

CI

IE

всички да имат цели дължини.

Решение

Отговорът е: не. Всъщност ще докажем по-силно твърдение: не е възможно дори само

AB

AC

BI

CI

всички да са цели числа. Това е достатъчно, защото ако шестте отсечки от условието имаха цели дължини, в частност тези четири отсечки също биха имали цели дължини. По условие

BD

е ъглополовящата от върха

B

, а

CE

е ъглополовящата от върха

C

. Следователно тяхната пресечна точка

I

е пресечната точка на две вътрешни ъглополовящи, тоест е инцентърът на триъгълника

ABC

.Понеже

\angle A=90^\circ

, имаме

\angle B+\angle C=90^\circ

. Затова

\angle IBC+\angle ICB=\frac{\angle B}{2}+\frac{\angle C}{2}=\frac{90^\circ}{2}=45^\circ.

В триъгълника

BIC

получаваме

\angle BIC=180^\circ-45^\circ=135^\circ.

Да допуснем, че

AB

AC

BI

CI

са цели числа. От теоремата на Питагор в правоъгълния триъгълник

ABC

получаваме

BC^2=AB^2+AC^2,

така че

BC^2

е цяло число. От друга страна, по косинусовата теорема в триъгълника

BIC

BC^2=BI^2+CI^2-2\cdot BI\cdot CI\cos135^\circ=

BI^2+CI^2+BI\cdot CI\sqrt{\vphantom{x^2}2}.

Тук

BI

CI

са положителни, защото

I

е вътрешна точка на триъгълника. Ако те са цели числа, то

BI^2+CI^2

е цяло число, а

BI\cdot CI\sqrt{\vphantom{x^2}2}

е ненулево ирационално число. Следователно изразът за

BC^2

е ирационален, което противоречи на вече доказаното, че

BC^2

е цяло число. Следователно исканите шест отсечки не могат всички да имат цели дължини.

Отвори задачатаEvan Chen VONVON JMO 2010/6Условие — източник

2011

5 задачи

Задача 1

Пълен запис

Условие

Намерете всички положителни цели числа

n

, за които

2^n+12^n+2011^n

е точен квадрат.

Решение

Отговорът е само

n=1,

защото

2^1+12^1+2011^1=2025=45^2

. Ще докажем, че други стойности няма. Ако

n\ge2

е четно, то по модул

3

имаме

2^n+12^n+2011^n\equiv 1+0+1\equiv2\pmod3,

2

не е квадратичен остатък по модул

3

. Следователно в този случай сумата не е квадрат. Ако

n\ge3

е нечетно, то по модул

4

получаваме

2^n+12^n+2011^n\equiv0+0+3\equiv3\pmod4,

а квадрат не може да дава остатък

3

по модул

4

. Положителното цяло число

n

е или

1

, или четно поне

2

, или нечетно поне

3

, така че единственото решение е

n=1

Отвори задачатаEvan Chen VONVON JMO 2011/1Условие — източник

Задача 2

Пълен запис

Условие

Нека

a

b

c

са положителни реални числа, за които

a^2+b^2+c^2+(a+b+c)^2\le4.

Докажете, че

\frac{ab+1}{(a+b)^2}+\frac{bc+1}{(b+c)^2}+\frac{ca+1}{(c+a)^2}\ge3.

Решение

Условието е еквивалентно на

a^2+b^2+c^2+ab+bc+ca\le2.

Следователно, след умножаване на исканото неравенство по

2

, имаме

\begin{align*} \sum_{\mathrm{cyc}}\frac{2ab+2}{(a+b)^2} &\ge \sum_{\mathrm{cyc}}\frac{2ab+a^2+b^2+c^2+ab+bc+ca}{(a+b)^2}\\ &=\sum_{\mathrm{cyc}}\frac{(a+b)^2+(a+c)(b+c)}{(a+b)^2}\\ &=3+\sum_{\mathrm{cyc}}\frac{(a+c)(b+c)}{(a+b)^2}. \end{align*}

По неравенството между средното аритметично и средното геометрично,

\begin{align*} \sum_{\mathrm{cyc}}\frac{(a+c)(b+c)}{(a+b)^2} &\ge 3\sqrt[3]{\vphantom{x^2}\frac{(a+c)(b+c)}{(a+b)^2}\cdot\frac{(a+b)(a+c)}{(b+c)^2}\cdot\frac{(a+b)(b+c)}{(c+a)^2}}\\ &=3. \end{align*}

Значи

2\sum_{\mathrm{cyc}}\frac{ab+1}{(a+b)^2}\ge6,

което е точно исканото неравенство.

Отвори задачатаEvan Chen VONVON JMO 2011/2Условие — източник

Задача 4

Пълен запис

Условие

Дума наричаме всяка крайна поредица от букви. Дума е палиндром, ако се чете еднакво отляво надясно и отдясно наляво. Нека редицата от думи

W_0,W_1,W_2,\ldots

е дефинирана така:

W_0=a

W_1=b

, а за

n\ge2

думата

W_n

се получава, като първо се изпише

W_{n-2}

, а след това

W_{n-1}

. Докажете, че за всяко

n\ge1

думата, получена чрез последователно изписване на

W_1,W_2,W_3,\ldots,W_n

, е палиндром.

Решение

Първите няколко думи са

\begin{align*} W_0&=a,\\ W_1&=b,\\ W_2&=ab,\\ W_3&=bab,\\ W_4&=abbab,\\ W_5&=bababbab. \end{align*}

Ще докажем твърдението с индукция по

n

. Случаите

n=1,2,3,4

се проверяват директно. Нека

\overline{X}

означава думата

X

, записана в обратен ред. За индукционната стъпка разглеждаме

W_1W_2\cdots W_{n-3}W_{n-2}W_{n-1}W_n.

Понеже

W_n=W_{n-2}W_{n-1}

, от индукционното предположение за

n-1

получаваме

\begin{align*} W_1W_2\cdots W_n &=\overline{W_{n-1}}\,\overline{W_{n-2}}\,\overline{W_{n-3}}\cdots \overline{W_2}\,\overline{W_1}\,W_{n-2}W_{n-1}\\ &=\overline{W_{n-1}}\,\overline{W_{n-2}}\,(\overline{W_{n-3}}\cdots \overline{W_2}\,\overline{W_1})\,W_{n-2}W_{n-1}. \end{align*}

По индукционното предположение за

n-3

средната част

\overline{W_{n-3}}\cdots \overline{W_2}\,\overline{W_1}

е равна на

W_1W_2\cdots W_{n-3}

и е палиндром. Следователно целият израз е симетричен: отвън стоят съответно

\overline{W_{n-1}}

W_{n-1}

, после

\overline{W_{n-2}}

W_{n-2}

, а в средата е палиндром. Значи

W_1W_2\cdots W_n

също е палиндром.

Отвори задачатаEvan Chen VONVON JMO 2011/4Условие — източник

Задача 5

Пълен запис

Условие

Точките

A

B

C

D

E

лежат на окръжност

\omega

, а точка

P

лежи извън окръжността. Дадено е, че правите

PB

PD

са допирателни към

\omega

, точките

P

A

C

са колинеарни и

DE\parallel AC

. Докажете, че правата

BE

разполовява отсечката

AC

Решение

Нека

M=BE\cap AC.

Ще докажем, че

M

е средата на

AC

.Първо ще дадем кратко проективно доказателство. От стандартния факт за конфигурация с две допирателни и секуща следва, че ако допирателните от

P

допират окръжността в

B

D

, а секущата през

P

я пресича в

A

C

, то четворката

(A,C;B,D)

е хармонична, тоест нейното кръстно отношение е

-1

. Този факт може да се види и през полярната на

P

: хордата на допиране

BD

е полярната на

P

, а двойката

A,C

по секущата през

P

е спрегната с двойката допирни точки

B,D

в породената инволюция върху окръжността. Следователно получената четворка върху окръжността е хармонична. Проектираме тази четворка от точката

E

върху правата

AC

. Точките

A

C

остават съответно

A

C

. Точката

B

се проектира в

M

, защото

M=BE\cap AC

. Точката

D

се проектира в точката при безкрайност на правата

AC

, понеже

DE\parallel AC

. Кръстното отношение се запазва при проекция, следователно

(A,C;M,\infty)=-1.

Когато четвъртата точка е точката при безкрайност, последното равенство е равносилно на

\frac{AM}{MC}=1.

Значи

AM=MC

, т.е.

M

е средата на отсечката

AC

. Следователно правата

BE

разполовява

AC

. За пълнота ще запишем и комплексната проверка от източника. Нека

\omega

е единичната окръжност и нека малките букви са комплексните координати на съответните точки. Точките

b,d,e

са върху единичната окръжност. Допирателната към единичната окръжност в точка

u

има уравнение

z+u^2\overline z=2u,

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

b

d

p=\frac{2bd}{b+d}.

Също така, ако

u

v

лежат върху единичната окръжност, правата

uv

има уравнение

z+uv\overline z=u+v.

Оттук условието

DE\parallel AC

дава еднакви направления на хордите, което в тази нормировка записваме като

ac=de.

Понеже

p

a

c

са колинеарни, уравнението на хордата

AC

дава

a+c=p+ac\overline p.

От

|b|=|d|=1

получаваме

\overline p=\frac{2}{b+d}

, така че

\begin{align*} \frac{a+c}{2} &=\frac{bd}{b+d}+\frac{de}{b+d}\\ &=\frac{d(b+e)}{b+d}. \end{align*}

От друга страна

\overline{\frac{a+c}{2}}=\frac{a+c}{2ac}=\frac{b+e}{e(b+d)}.

Следователно, ако

m=\frac{a+c}{2}

, то

m+be\overline m=\frac{d(b+e)}{b+d}+\frac{b(b+e)}{b+d}=b+e.

Но това е точно уравнението на правата

BE

, приложено към точката

m

. Значи средата

m

на

AC

лежи на

BE

. Понеже правата през

B

E

минава през средата на

AC

, тя разполовява отсечката

AC

, което отново доказва твърдението.

Отвори задачатаEvan Chen VONVON JMO 2011/5Условие — източник

Задача 6

Пълен запис

Условие

Разгледайте твърдението, че за всяко положително цяло число

n\ge2

остатъкът при деление на

2^{2^n}

на

2^n-1

е степен на

4

. Или докажете твърдението, или намерете контрапример с доказателство.

Решение

Твърдението е невярно. Ще покажем, че

n=25

е контрапример. Понеже

2^{25}\equiv1\pmod{2^{25}-1}

, можем да намалим показателя

2^{25}

по модул

25

. От

2^{20}\equiv1\pmod{25}

2^5\equiv7\pmod{25}

следва

2^{25}\equiv7\pmod{25}.

Затова

2^{2^{25}}\equiv2^7\pmod{2^{25}-1}.

Освен това

0\lt{}2^7\lt{}2^{25}-1

, така че самият остатък е

2^7=128

. Но

128=2^7

не е степен на

4

, защото степените на

4

са точно числата

2^{2k}

с четен показател на двойката. Следователно

n=25

е търсеният контрапример.

Отвори задачатаEvan Chen VONVON JMO 2011/6Условие — източник

2012

3 задачи

Задача 2

Пълен запис

Условие

Намерете всички цели числа

n\ge3

, за които сред всеки

n

положителни реални числа

a_1,a_2,\ldots,a_n

, удовлетворяващи

\max(a_1,a_2,\ldots,a_n)\le n\cdot\min(a_1,a_2,\ldots,a_n),

съществуват три числа, които са дължини на страните на остроъгълен триъгълник.

Решение

Отговорът е: всички

n\ge13.

Нека

(F_m)

е редицата на Фибоначи, дефинирана чрез

F_1=F_2=1

F_{m+1}=F_m+F_{m-1}

. Първо ще ни трябва следното просто наблюдение:

F_m\le m^2\quad\Longleftrightarrow\quad m\le12.

Наистина, първите четиринадесет числа на Фибоначи са

1,1,2,3,5,8,13,21,34,55,89,144,233,377

. Оттук се вижда, че

F_m\le m^2

е вярно за

m=1,2,\ldots,12

, като

F_{12}=12^2=144

, но вече е невярно за

m=13

m=14

. За

m\ge15

това следва по индукция, защото

F_m=F_{m-1}+F_{m-2}\gt{}

(m-1)^2+(m-2)^2=m^2+(m-1)(m-5)\gt{}m^2.

Сега нека

n\ge13

и да допуснем противното: дадени са

n

числа, но никои три от тях не са страни на остроъгълен триъгълник. Подреждаме ги така, че

a_1\le a_2\le\cdots\le a_n.

За всяко

i\ge2

тройката

a_{i-1},a_i,a_{i+1}

не образува остроъгълен триъгълник. При подредени положителни числа това означава

a_{i+1}^2\ge a_i^2+a_{i-1}^2.

Следователно

\begin{align*} a_3^2&\ge a_2^2+a_1^2\ge2a_1^2,\\ a_4^2&\ge a_3^2+a_2^2\ge3a_1^2,\\ a_5^2&\ge a_4^2+a_3^2\ge5a_1^2, \end{align*}

и по индукция получаваме

a_i^2\ge F_i a_1^2

за всяко

i

. В частност

a_n^2\ge F_n a_1^2

. От условието на задачата обаче имаме

a_n\le n a_1

, така че

F_n\le n^2

. Това е невъзможно при

n\ge13

според наблюдението по-горе. Остава да покажем, че никое

n\le12

не върши работа. За такова

n

вземаме

a_i=\sqrt{\vphantom{x^2}F_i}\qquad (1\le i\le n).

Тогава

\min a_i=1

, а

\max a_i=\sqrt{\vphantom{x^2}F_n}\le n

, така че даденото условие е изпълнено. Но ако

i\lt{}j\lt{}k

, то

a_k^2=F_k=F_{k-1}+F_{k-2}\ge F_j+F_i=a_j^2+a_i^2,

следователно тези три числа не са страни на остроъгълен триъгълник. Така получаваме контрапример за всяко

n\le12

, което завършва доказателството.

Отвори задачатаEvan Chen VONVON JMO 2012/2Условие — източник

Задача 3

Пълен запис

Условие

Нека

a,b,c\gt{}0

. Докажете, че

\frac{a^3+3b^3}{5a+b}+\frac{b^3+3c^3}{5b+c}+\frac{c^3+3a^3}{5c+a}\ge

\frac23(a^2+b^2+c^2).

Решение

Ще използваме линеаризация. Основното твърдение е

\frac{a^3+3b^3}{5a+b}\ge\frac{25}{36}b^2-\frac{1}{36}a^2.

За да го докажем, полагаме

x=a/b\gt{}0

. След деление на

b^2

исканото неравенство става

\frac{x^3+3}{5x+1}\ge\frac{25-x^2}{36}.

Това е еквивалентно на

\begin{align*} 36(x^3+3)-(5x+1)(25-x^2) &=41x^3+x^2-125x+83\\ &=(x-1)^2(41x+83)\ge0, \end{align*}

което доказва твърдението. Сумираме това неравенство циклично за двойките

(a,b)

(b,c)

(c,a)

. Получаваме

\begin{align*} \sum_{\mathrm{cyc}}\frac{a^3+3b^3}{5a+b} &\ge \frac{25}{36}(a^2+b^2+c^2)-\frac{1}{36}(a^2+b^2+c^2)\\ &=\frac23(a^2+b^2+c^2), \end{align*}

както се искаше.

Отвори задачатаEvan Chen VONVON JMO 2012/3Условие — източник

Задача 5

Пълен запис

Условие

За различни положителни цели числа

a,b\lt{}2012

дефинираме

f(a,b)

като броя на целите числа

k

1\le k\lt{}2012

, за които остатъкът при деление на

ak

на

2012

е по-голям от остатъка при деление на

bk

на

2012

. Нека

S

е минималната стойност на

f(a,b)

, когато

a

b

пробягват всички двойки различни положителни цели числа, по-малки от

2012

. Определете

S

Решение

Отговорът е

S=502.

Първо ще докажем долна граница. Да фиксираме различни

a,b\lt{}2012

и да вземем

k

, за което

\gcd(k,2012)=1

. Тогава

ak

bk

са ненулеви по модул

2012

, а освен това

ak\not\equiv bk\pmod{2012}

, защото

k

е обратимо по модул

2012

a\not\equiv b\pmod{2012}

. Нека

r_a

r_b

са съответно остатъците на

ak

bk

при деление на

2012

. За числото

2012-k

съответните остатъци са

2012-r_a

2012-r_b

. Понеже

r_a\ne r_b

, точно едно от двете числа

k

2012-k

се брои във

f(a,b)

. Следователно всеки чифт взаимнопрости остатъци

\{k,2012-k\}

дава точно един принос към

f(a,b)

. Понеже

2012=4\cdot503\qquad\text{и}\qquad

\varphi(2012)=2012\left(1-\frac12\right)\left(1-\frac1{503}\right)=1004,

получаваме

f(a,b)\ge\frac{\varphi(2012)}2=502.

Сега ще покажем, че равенство е възможно. Вземаме

a=4,\qquad b=1010.

Ако

k

е четно, тогава

4k\equiv1010k\pmod{2012},

защото

1010k-4k=1006k

се дели на

2012

. Следователно никое четно

k

не се брои. Ако пък

503\mid k

, тогава

4k\equiv0\pmod{2012},

така че остатъкът на

4k

0

и не може да бъде по-голям от остатъка на

1010k

. Значи при тази двойка

(a,b)

всички

k

, които не са взаимнопрости с

2012

, не дават принос. А сред взаимнопростите

k

вече знаем, че във всеки чифт

\{k,2012-k\}

се брои точно едно число. Следователно

f(4,1010)=502,

и заедно с долната граница това дава

S=502

Отвори задачатаEvan Chen VONVON JMO 2012/5Условие — източник

2013

4 задачи

Задача 1

Пълен запис

Условие

Съществуват ли цели числа

a

b

, такива че

a^5b+3

ab^5+3

да са точни кубове на цели числа?

Решение

Не, такива цели числа

a

b

не съществуват. Ще разгледаме два случая. Първо да допуснем, че

3\mid ab

. Без ограничение нека

3\mid a

. Тогава

a^5b+3\equiv3\pmod 9,

което е невъзможно за точен куб, защото кубовете по модул

9

са само

0,1

8

. Остава случаят

3\nmid ab

. Тогава

a^5b+3

е куб, който не се дели на

3

, следователно е равен на

\pm1

по модул

9

. Получаваме

a^5b\in\{5,7\}\pmod 9.

Аналогично

ab^5\in\{5,7\}\pmod 9.

Но тези две сравнения не могат да са едновременно верни. Наистина, понеже

3\nmid ab

, от теоремата на Ойлер имаме

(ab)^6\equiv1\pmod 9.

От друга страна произведението на двете числа

a^5b

ab^5

трябва да е произведение на две числа от множеството

\{5,7\}

, а

5\cdot5\equiv7,\qquad 5\cdot7\equiv8,\qquad 7\cdot7\equiv4\pmod 9.

Нито един от тези остатъци не е

1

. Противоречието доказва, че търсените цели числа не съществуват.

Отвори задачатаEvan Chen VONVON JMO 2013/1Условие — източник

Задача 2

Пълен запис

Условие

Всяка клетка на дъска

m\times n

е запълнена с някакво неотрицателно цяло число. Две числа в запълването се наричат съседни, ако клетките им имат обща страна. Запълването се нарича градина, ако удовлетворява следните две условия: 1. Разликата между всеки две съседни числа е

0

или

1

. 2. Ако едно число е по-малко или равно на всички свои съседни числа, то е равно на

0

. Да се намери броят на различните градини в зависимост от

m

n

Решение

Отговорът е

2^{mn}-1

. Ще докажем нещо по-силно, като опишем всички градини. Нека

S

е произволно непразно множество от клетки на дъската. За всяка клетка

\theta

записваме минималното таксиметрово разстояние от

\theta

до някоя клетка от

S

; в частност в клетките от

S

записваме

0

. Тогава получаваме градина, и всяка градина се получава по този начин. Понеже има точно

2^{mn}-1

непразни множества

S

, това ще даде искания брой. Например, ако

S

има три клетки, може да се получи градина от вида

\begin{bmatrix} 2 & 1 & 2 & 1 & \mathbf{0} & 1 \\ 1 & \mathbf{0} & 1 & 2 & 1 & 2 \\ 1 & 1 & 2 & 3 & 2 & 3 \\ \mathbf{0} & 1 & 2 & 3 & 3 & 4 \end{bmatrix}.

Лесно се вижда, че описаната процедура винаги дава градина: при движение към съседна клетка таксиметровото разстояние до

S

се променя с най-много

1

, а всяка клетка извън

S

има съседна клетка, която е с една стъпка по-близо до

S

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

0

: вземаме клетка с минимално записано число; то е не по-голямо от числата във всички съседни клетки, следователно по условие е

0

. Нека

S

е множеството от всички клетки, в които е записана нула. Твърдим, че ако в клетка

\theta

е записано числото

d

, то минималното разстояние от

\theta

до клетка от

S

е точно

d

. Доказателството е с индукция по

d

. За

d=0

твърдението е вярно по дефиниция на

S

. Нека сега

d\ge1

и в клетката

\theta

е записано

d

. Всеки съсед на

\theta

има число поне

d-1

, така че при всяка стъпка по път към клетка с нула стойността може да намалява с най-много

1

; следователно всеки такъв път има дължина поне

d

. От друга страна, по второто условие не може всички съседи на

\theta

да имат числа поне

d

, защото тогава

d

би трябвало да е

0

. Значи има съседна клетка с число

d-1

. По индукционната хипотеза от тази съседна клетка има път с дължина

d-1

до

S

, а като добавим първата стъпка от

\theta

, получаваме път с дължина точно

d

. Следователно числото във всяка клетка е точно минималното таксиметрово разстояние до

S

, както искахме.

Отвори задачатаEvan Chen VONVON JMO 2013/2Условие — източник

Задача 4

Пълен запис

Условие

Нека

f(n)

е броят на начините да се представи

n

като сбор от степени на

2

, като редът на събираемите се отчита. Например

f(4)=6

, защото

4

може да се представи като

4

2+2

2+1+1

1+2+1

1+1+2

1+1+1+1

. Намерете най-малкото

n\gt{}2013

, за което

f(n)

е нечетно.

Решение

Отговорът е

2047

. За удобство полагаме

f(0)=1

. Ако разгледаме първото събираемо в представянето на

n

, получаваме рекурентната формула

f(n)=\sum_{k=0}^{\lfloor\log_2 n\rfloor} f(n-2^k).\tag{1}

Първите стойности са

\begin{aligned} f(0)&=1, & f(1)&=1, & f(2)&=2, & f(3)&=3,\\ f(4)&=6, & f(5)&=10, & f(6)&=18, & f(7)&=31. \end{aligned}

Те подсказват следното твърдение. Ще докажем, че

f(n)

е нечетно тогава и само тогава, когато

n+1

е степен на

2

. Еквивалентно,

f(n)

е нечетно точно за числата

n=0,1,3,7,15,\ldots

, тоест за нула и за числата, чийто двоичен запис се състои само от единици. Доказваме това с индукция по

n

. Да наречем такова число специално. По индукционната хипотеза в дясната страна на (1) нечетни са точно онези събираеми, за които

n-2^k

е специално. Това е еквивалентно на

n+1=2^k+2^r

за някое

r\ge0

. Ако

n+1

е степен на

2

, има точно един такъв избор: двете степени трябва да са равни, тоест

2^k=2^r=(n+1)/2

. Следователно в (1) има точно едно нечетно събираемо и

f(n)

е нечетно. Ако

n+1

е сбор на две различни степени на

2

, тогава има точно два избора за

k

, съответстващи на тези две степени, и броят на нечетните събираеми в (1) е четен. Ако пък двоичният запис на

n+1

има поне три единици, няма такъв избор изобщо. И в двата случая

f(n)

е четно. Така твърдението е доказано. Най-малката степен на

2

, по-голяма от

2014

, е

2048

, следователно най-малкото търсено

n

2048-1=2047.

Отвори задачатаEvan Chen VONVON JMO 2013/4Условие — източник

Задача 6

Пълен запис

Условие

Намерете всички реални числа

x,y,z\ge1

, за които

\min\left(\sqrt{\vphantom{x^2}x+xyz},\sqrt{\vphantom{x^2}y+xyz},\sqrt{\vphantom{x^2}z+xyz}\right)=

\sqrt{\vphantom{x^2}x-1}+\sqrt{\vphantom{x^2}y-1}+\sqrt{\vphantom{x^2}z-1}.

Решение

Поставяме

x=1+a,\qquad y=1+b,\qquad z=1+c,

където

a,b,c\ge0

. Без ограничение нека

a\le b\le c

. Тогава минималният член в лявата страна е

\sqrt{\vphantom{x^2}x+xyz}=\sqrt{\vphantom{x^2}(1+a)\left(1+(1+b)(1+c)\right)}.

Ще докажем, че тази величина винаги е поне

\sqrt a+\sqrt b+\sqrt c,

и после ще разгледаме случаите на равенство. Имаме

\begin{aligned} (1+a)\left(1+(1+b)(1+c)\right) &\ge (1+a)\left(1+(\sqrt b+\sqrt c)^2\right)\\ &\ge \left(\sqrt a+\sqrt b+\sqrt c\right)^2. \end{aligned}

Първото неравенство е еквивалентно на

(\sqrt{\vphantom{x^2}bc}-1)^2\ge0

, а второто - на

\left(\sqrt a(\sqrt b+\sqrt c)-1\right)^2\ge0.

Следователно даденото равенство е възможно точно когато едновременно

bc=1

a=\frac{1}{(\sqrt b+\sqrt c)^2}.

Нека

c=t^2

за

t\gt{}0

. Тогава

b=t^{-2}

a=\frac{1}{(t+t^{-1})^2}=\left(\frac{t}{t^2+1}\right)^2.

Значи всички решения са пермутациите на тройките

(x,y,z)=\left(1+\left(\frac{t}{t^2+1}\right)^2, 1+\frac{1}{t^2}, 1+t^2\right),\qquad t\gt{}0.

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

Отвори задачатаEvan Chen VONVON JMO 2013/6Условие — източник

2014

3 задачи

Задача 1

Пълен запис

Условие

Нека

a

b

c

са реални числа, по-големи или равни на

1

. Докажете, че

\min\left(\frac{10a^2-5a+1}{b^2-5b+10},\frac{10b^2-5b+1}{c^2-5c+10},\frac{10c^2-5c+1}{a^2-5a+10}\right)\le

abc.

Решение

Достатъчно е да забележим едно еднопроменливо неравенство. За всяко

a\ge1

имаме

\frac{10a^2-5a+1}{a^2-5a+10}\le a^3,

защото след пренасяне то е еквивалентно на

(a-1)^5\ge0.

Аналогично получаваме същото неравенство за

b

c

. Умножаваме трите циклични неравенства

\frac{10a^2-5a+1}{a^2-5a+10}\le a^3,

\qquad \frac{10b^2-5b+1}{b^2-5b+10}\le b^3,

\qquad \frac{10c^2-5c+1}{c^2-5c+10}\le c^3.

След пренареждане на знаменателите това дава

\frac{10a^2-5a+1}{b^2-5b+10}\cdot \frac{10b^2-5b+1}{c^2-5c+10}\cdot \frac{10c^2-5c+1}{a^2-5a+10}\le

(abc)^3.

Следователно най-малкото от трите числа в лявата страна на условието е най-много тяхното средно геометрично, а то е най-много

abc

. Това доказва исканото неравенство.

Отвори задачатаEvan Chen VONVON JMO 2014/1Условие — източник

Задача 3

Пълен запис

Условие

Намерете всички функции

f\colon\mathbb Z\to\mathbb Z

, за които

xf\left(2f(y)-x\right)+y^2f\left(2x-f(y)\right)=

\frac{f(x)^2}{x}+f\left(yf(y)\right)

за всички

x,y\in\mathbb Z

x\ne0

Решение

Отговорът е

f(x)\equiv0\qquad\text{и}\qquad f(x)\equiv x^2.

Директната проверка е непосредствена. Остава да докажем, че други решения няма. Поставяме

y=0

и получаваме

x f\left(2f(0)-x\right)=\frac{f(x)^2}{x}+f(0).\tag{1}

Първо ще покажем, че

f(0)=0

. Ако това не е вярно, избираме просто число

p

, което не дели

f(0)

, и поставяме

x=p

в (1). Тогава от дясната страна следва, че

p\mid f(p)^2

, значи

p\mid f(p)

, а оттук

p\mid f(p)^2/p

. Уравнението (1) тогава налага

p\mid f(0)

, противоречие. Следователно

f(0)=0.

Сега от (1) следва

x^2f(-x)=f(x)^2\tag{2}

за всяко цяло

x

. Замествайки

x

-x

, получаваме и

f(-x)^2=x^2f(x).\tag{3}

Ще докажем, че

f

е четна функция. Ако за някое

x

имаме

f(x)\ne f(-x)

, то

x\ne0

, и като извадим (2) и (3), след разлагане получаваме

f(x)+f(-x)=-x^2.

Замяната в (2) дава

\left(f(x)+\frac12x^2\right)^2=-\frac34x^4\lt{}0,

което е невъзможно. Значи

f(x)=f(-x)

за всяко

x

, и от (2) получаваме

f(x)^2=x^2f(x).

Следователно за всяко цяло число

x

е изпълнено

f(x)\in\{0,x^2\}.\tag{4}

Да допуснем, че съществува ненулево цяло число

t

f(t)=0

. Ще докажем, че тогава

f\equiv0

. Поставяме

y=t

в началното уравнение. Понеже

f(t)=0

, получаваме

t^2f(2x)=0

за всяко цяло

x\ne0

, тоест

f(2\mathbb Z)\equiv0

. Сега поставяме

x=2k\ne0

в началното уравнение. Понеже

f(2k)=0

, остава

y^2f(4k-f(y))=f(yf(y)).\tag{5}

Да допуснем за противоречие, че

f(m)=m^2

за някое нечетно

m\ne0

. От (5) при

y=m

следва

m^2 f(4k-m^2)=f(m^3).

Ако

f(m^3)\ne0

, то за всяко

k\ne0

числото

f(4k-m^2)

също е ненулево, и по (4) получаваме

m^2(4k-m^2)^2=m^6,

което не може да е вярно за произволно

k\ne0

. Следователно

f(4k-m^2)=f(m^2-4k)=f(m^3)=0

за всяко

k\ne0

. Понеже

m

е нечетно, имаме

m^2\equiv1\pmod4

. Така

f(n)=0

за всяко цяло

n

, с изключение евентуално на

\pm m^2

. Но от

f(m)=m^2

следва

m=\pm1

. Значи или

f\equiv0

, или единствената оставаща възможност е

f(x)=\begin{cases}1,&x=\pm1,\\0,&\text{иначе}. \end{cases}

Последната функция обаче не удовлетворява уравнението: при

x=5

y=1

лявата страна е

0

, а дясната е

1

. Следователно, ако някъде има ненулево

t

f(t)=0

, то непременно

f\equiv0

. Ако пък няма такова

t

, то от (4) следва

f(x)=x^2

за всяко ненулево

x

, а вече знаем

f(0)=0

. Това дава второто решение

f(x)=x^2

. Значи посочените две функции са точно всички решения.

Отвори задачатаEvan Chen VONVON JMO 2014/3Условие — източник

Задача 4

Пълен запис

Условие

Нека

b\ge2

е фиксирано цяло число, а

s_b(n)

означава сумата на цифрите на

n

в бройна система с основа

b

. Докажете, че съществуват безбройно много положителни цели числа, които не могат да се представят във вида

n+s_b(n)

, където

n

е положително цяло число.

Решение

За краткост полагаме

f(n)=n+s_b(n).

Ще докажем, че за всяко положително цяло число

M

функцията

f

пропуска поне

M

стойности в началния интервал от положителните цели числа. Първо, ако

x\ge b^{2M}

, то очевидно

f(x)\ge b^{2M}.

От друга страна, за

k=1,2,\dots,M

числото

b^{2M}-k

в бройна система с основа

b

започва с поне

M

цифри, равни на

b-1

. Наистина

k\le M\lt{}b^M

, така че

k

засяга само най-много последните

M

разряда, а най-старшите поне

M

разряда след заемането от

b^{2M}

стават равни на

b-1

. Следователно

s_b(b^{2M}-k)\ge M,

и затова

f(b^{2M}-k)=(b^{2M}-k)+s_b(b^{2M}-k)\ge

b^{2M}-k+M\ge b^{2M}.

Сега разглеждаме стойностите в интервала

[1,b^{2M}-1]

. Всяко

x\ge b^{2M}

дава стойност поне

b^{2M}

, а сред числата

1,2,\dots,b^{2M}-1

точно

M

от тях, а именно

b^{2M}-1,\ b^{2M}-2,\ \dots,\ b^{2M}-M,

също дават стойности поне

b^{2M}

. Значи стойностите в интервала

[1,b^{2M}-1]

могат да бъдат получени от най-много

b^{2M}-1-M

различни входа. Този интервал обаче съдържа

b^{2M}-1

цели числа, следователно поне

M

от тях не са от вида

n+s_b(n)

. Понеже

M

е произволно голямо, пропуснатите положителни цели числа са безбройно много.

Отвори задачатаEvan Chen VONVON JMO 2014/4Условие — източник

2015

3 задачи

Задача 1

Пълен запис

Условие

Дадена е редица от реални числа. Един ход се състои в това да изберем два члена на редицата и да заменим всеки от тях с тяхното средно аритметично. Докажете, че съществува редица от

2015

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

Решение

Един подходящ пример е редицата

0,1,2,\dots,2014.

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

1007

. Ще казваме, че две числа са противоположни, ако средното им аритметично е

1007

. Числото

1007

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

1007

. Да кажем, че са променени числата

a

b

, като и двете са заменени с

c=\frac{a+b}{2}.

Ако

a

b

са противоположни, достатъчно е да осредним всички останали двойки противоположни числа. Нека сега

a

b

не са противоположни. Нека

a'

b'

са съответно противоположните на

a

b

; тогава четирите числа

a,b,a',b'

са различни. Осредняваме

a'

b'

и получаваме два пъти числото

c'=2014-c.

След това работим само с тези четири числа:

\begin{array}{cccc} c & c & a' & b' \cr c & c & c' & c' \cr 1007 & c & 1007 & c' \cr 1007 & 1007 & 1007 & 1007. \end{array}

Накрая осредняваме всички останали двойки противоположни числа. Остава случаят, в който началният ход участва

1007

и някое число

a

. Избираме число

k

, различно от

a

и от противоположното му число, и нека

a'

k'

са противоположните на

a

k

. Работим само с тези пет числа:

\begin{array}{ccccc} \frac{a+1007}{2} & \frac{a+1007}{2} & a' & k & k' \cr \frac{a+1007}{2} & \frac{a+1007}{2} & a' & 1007 & 1007 \cr \frac{a+1007}{2} & \frac{a+1007}{2} & \frac{a'+1007}{2} & \frac{a'+1007}{2} & 1007 \cr 1007 & \frac{a+1007}{2} & 1007 & \frac{a'+1007}{2} & 1007 \cr 1007 & 1007 & 1007 & 1007 & 1007. \end{array}

След това отново осредняваме останалите двойки противоположни числа. Така във всички случаи стигаме до константната редица с членове

1007

Отвори задачатаEvan Chen VONVON JMO 2015/1Условие — източник

Задача 2

Пълен запис

Условие

Намерете всички двойки цели числа

(x,y)

, които удовлетворяват уравнението

x^2+xy+y^2=\left(\frac{x+y}{3}+1\right)^3.

Решение

Полагаме

a=x+y,\qquad b=x-y.

Тогава

a

b

са цели числа с еднаква четност, а

x=\frac{a+b}{2},\qquad y=\frac{a-b}{2}.

Уравнението се превръща в

\frac14\left((a+b)^2+(a+b)(a-b)+(a-b)^2\right)=

\left(\frac a3+1\right)^3,

тоест

3a^2+b^2=4\left(\frac a3+1\right)^3.\tag{1}

След умножение на (1) с

27

и разглеждане по модул

3

получаваме

3\mid a

. Нека

a=3c

. Тогава (1) се свежда до

b^2=(c-2)^2(4c+1).\tag{2}

Следователно

4c+1=m^2

за някое нечетно цяло число

m

; обратното също дава решения. Наистина от

4c+1=m^2

имаме

c=\frac{m^2-1}{4},\qquad b=\pm\frac{m(m^2-9)}4,

и затова

x=\frac18\left(3(m^2-1)\pm(m^3-9m)\right),

\qquad y=\frac18\left(3(m^2-1)\mp(m^3-9m)\right).

Понеже

m

е нечетно, тези изрази винаги са цели числа. Ако запишем

m=2n+1

, получаваме по-удобната параметризация

x=n^3+3n^2-1,\qquad y=-n^3+3n+1,

както и двойката с разменени координати, където

n

е произволно цяло число. Това са всички решения.

Отвори задачатаEvan Chen VONVON JMO 2015/2Условие — източник

Задача 4

Пълен запис

Условие

Намерете всички функции

f\colon\mathbb Q\to\mathbb Q

, за които

f(x)+f(t)=f(y)+f(z)

за всички рационални числа

x\lt{}y\lt{}z\lt{}t

, които образуват аритметична прогресия.

Решение

Отговорът е: всички функции от вида

f(q)=\alpha q+\beta,

където

\alpha,\beta\in\mathbb Q

. Директната проверка е ясна. Нека

a\in\mathbb Q

d\gt{}0

е рационално число. От условието имаме

f(a)+f(a+3d)=f(a+d)+f(a+2d)

f(a-d)+f(a+2d)=f(a)+f(a+d).

Като съберем тези две равенства и съкратим, получаваме

f(a-d)+f(a+3d)=2f(a+d).

Следователно за произволни рационални

x

y

е изпълнено

f(x)+f(y)=2f\left(\frac{x+y}{2}\right).\tag{1}

Това е уравнението на Йенсен върху

\mathbb Q

, откъдето следва, че

f

е афинна функция. За пълнота ще довършим без да се позоваваме на това име. Нека

d

е положително цяло число, а

n

е цяло число. Прилагаме условието към двете аритметични прогресии

\frac{2n-1}{2d},\frac{2n}{2d},\frac{2n+1}{2d},\frac{2n+2}{2d}

\frac{2n-2}{2d},\frac{2n-1}{2d},\frac{2n}{2d},\frac{2n+1}{2d}.

Получаваме

f\left(\frac{2n-1}{2d}\right)+f\left(\frac{2n+2}{2d}\right)=f\left(\frac{2n}{2d}\right)+f\left(\frac{2n+1}{2d}\right)

f\left(\frac{2n-2}{2d}\right)+f\left(\frac{2n+1}{2d}\right)=f\left(\frac{2n-1}{2d}\right)+f\left(\frac{2n}{2d}\right).

След събиране и опростяване следва

f\left(\frac{n-1}{d}\right)+f\left(\frac{n+1}{d}\right)=2f\left(\frac nd\right).

Значи върху рационалните числа със знаменател, делящ

d

, последователните разлики са равни. В частност

f\left(\frac nd\right)=f(0)+\frac nd\left(f(1)-f(0)\right).

Понеже всяко рационално число е от вида

n/d

, окончателно

f(q)=f(0)+q\left(f(1)-f(0)\right),

което е точно описаният по-горе вид.

Отвори задачатаEvan Chen VONVON JMO 2015/4Условие — източник

2016

4 задачи

Задача 2

Пълен запис

Условие

Да се докаже, че съществува положително цяло число

n\lt{}10^6

, за което десетичният запис на

5^n

съдържа шест последователни нули.

Решение

Ще построим такова

n

, като контролираме последните

20

цифри на

5^n

. Нека

n=20+2^{19}.

Тогава

n\lt{}10^6

. Ще покажем, че

5^n

има същите последни

20

цифри като

5^{20}

. По модул

5^{20}

и двете числа са

0

. По модул

2^{20}

, от теоремата на Ойлер имаме

5^{2^{19}}\equiv1\pmod{2^{20}}

, защото

\varphi(2^{20})=2^{19}

\gcd(5,2^{20})=1

. Следователно

5^n=5^{20}\cdot5^{2^{19}}\equiv5^{20}\pmod{2^{20}}.

С китайската теорема за остатъците получаваме

5^n\equiv5^{20}\pmod{10^{20}}.

Но

5^{20}=95367431640625

има

14

цифри. Значи последните

20

цифри на

5^n

са

00000095367431640625,

което съдържа шест последователни нули. Това доказва твърдението.

Отвори задачатаEvan Chen VONVON JMO 2016/2Условие — източник

Задача 3

Пълен запис

Условие

Нека

X_1

X_2

\ldots

X_{100}

са редица от две по две различни непразни подмножества на множество

S

. За всеки две съседни множества

X_i

X_{i+1}

е изпълнено, че те са несечащи се и обединението им не е цялото множество

S

, тоест

X_i\cap X_{i+1}=\varnothing\qquad\text{и}\qquad X_i\cup X_{i+1}\ne S

за всички

i=1,2,\ldots,99

. Да се намери най-малкият възможен брой елементи на

S

Решение

Отговорът е

8

. Първо ще докажем, че

|S|\ge8

е необходимо. Очевидно трябва да има поне

100

различни непразни подмножества, така че

|S|\ge7

. Ще покажем, че

|S|=7

все още не стига. Нека

S=\{1,2,\ldots,7\}

и да имаме редица с исканите свойства. Всяко подмножество с поне

4

елемента може да стои до множество с най-много

2

елемента: ако съседното множество има

3

или повече елемента и е несечащо се с него, тогава обединението би било цялото

S

. Подмножества с най-много

2

елемента има

\binom71+\binom72=28.

Следователно в редицата може да има най-много

29

множества с поне

4

елемента. Освен това множествата с точно

3

елемента са само

\binom73=35

. Значи общият брой членове на такава редица е най-много

29+28+35=92\lt{}100,

противоречие. Значи

|S|\ge8

. Остава да построим пример при

|S|=8

. Ще дадем по-обща индуктивна конструкция. За всяко

n\ge4

ще построим редица от

2^{n-1}+1

подмножества на

\{1,2,\ldots,n\}

със същите свойства. За

n=4

работи редицата

34,\ 1,\ 23,\ 4,\ 12,\ 3,\ 14,\ 2,\ 13,

където например

34

означава множеството

\{3,4\}

. Нека вече имаме такава редица за

\{1,2,\ldots,n\}

. Премахваме крайния й член, така че дължината да стане четна, правим две копия на останалата редица и ги слепваме с

\varnothing

между тях. После добавяме новия елемент

n+1

към множествата на редуващи се позиции, започвайки от първата позиция. Лесно се проверява, че съседните множества в новата редица пак са несечащи се и обединението им не е цялото множество: в старите съседства това следва от индукционното предположение, а при слепването празното множество не създава проблем; добавянето на

n+1

в редуващи се позиции запазва несечението на всяка съседна двойка и оставя във всяка двойка поне един липсващ елемент. Дължината става

2\cdot2^{n-1}+1=2^n+1.

При

n=8

получаваме редица с

2^7+1=129

различни непразни подмножества. Вземайки първите

100

от тях, получаваме търсената редица. Следователно най-малкият възможен размер на

S

8

Отвори задачатаEvan Chen VONVON JMO 2016/3Условие — източник

Задача 4

Пълен запис

Условие

Да се намери най-малкото положително цяло число

N

със следното свойство: ако от множеството

\{1,2,\ldots,N\}

премахнем произволни

2016

числа, тогава сред останалите числа винаги могат да се изберат

2016

различни числа със сбор

N

Решение

Отговорът е

N=2017+2018+\cdots+4032=

1008\cdot6049=6097392.

Първо ще докажем, че по-малко

N

не стига. Ако премахнем числата

1,2,\ldots,2016

, тогава най-малкият възможен сбор на

2016

различни останали числа е

2017+2018+\cdots+4032.

Следователно всяко работещо

N

трябва да е поне тази стойност. Остава да докажем, че това

N

наистина работи. Разглеждаме двойките

(1,6048),(2,6047),\ldots,(3024,3025).

Всяка от тях има сбор

6049

, а всички използвани числа са не по-големи от

6048\lt{}N

. Премахването на

2016

числа може да развали най-много

2016

от тези

3024

двойки, защото едно премахнато число принадлежи на най-много една двойка. Значи остават поне

3024-2016=1008

непокътнати двойки. Избираме числата от тези

1008

двойки. Получаваме точно

2016

различни останали числа, а сборът им е

1008\cdot6049=N.

Така посоченото

N

има исканото свойство и по долната граница е минимално.

Отвори задачатаEvan Chen VONVON JMO 2016/4Условие — източник

Задача 6

Пълен запис

Условие

Да се намерят всички функции

f:\mathbb R\to\mathbb R

такива, че за всички реални числа

x

y

е изпълнено

(f(x)+xy)f(x-3y)+(f(y)+xy)f(3x-y)=

f(x+y)^2.

Решение

Двете решения са

f(x)\equiv0\qquad\text{и}\qquad f(x)=x^2.

Лесна проверка показва, че и двете функции удовлетворяват уравнението. Ще докажем, че други няма. Поставяме

x=y=0

и получаваме

f(0)=0

. После при

x=0

имаме

f(y)f(-y)=f(y)^2.

След замяна на

y

-y

следва и

f(-y)f(y)=f(-y)^2

. От тези две равенства получаваме

f(y)=f(-y)

за всяко

y

, тоест

f

е четна. Сега поставяме

y=-x

. Тъй като

f

е четна и

f(0)=0

, получаваме

2(f(x)-x^2)f(4x)=0.

Следователно за всяко реално

x

е вярно, че

f(x)=x^2\quad\text{или}\quad f(4x)=0.\tag{1}

Ще използваме още едно свойство на нулите. Поставяме

(x,y)=(3t,t)

. Понеже

f(0)=0

, уравнението става

(f(t)+3t^2)f(8t)=f(4t)^2.\tag{2}

Оттук

f(4t)\ne0

влече

f(8t)\ne0

, тоест

f(z)\ne0

влече

f(2z)\ne0

. Еквивалентно, ако

f(2z)=0

, то

f(z)=0

. За обратната посока допускаме

f(8t)\ne0

. От (1), приложено за

2t

, следва

f(2t)=4t^2

; при

t\ne0

това е ненулево, а вече доказаната посока дава

f(4t)\ne0

. Следователно

f(4t)=0

влече

f(8t)=0

. Значи за всяко реално

z

f(z)=0\quad\Longleftrightarrow\quad f(2z)=0.\tag{3}

От (1) и (3) следва, че за всяко

x

имаме само две възможности:

f(x)=x^2\quad\text{или}\quad f(x)=0.

Ако няма ненулево

a

f(a)=0

, то веднага

f(x)=x^2

за всички

x\ne0

, а и

f(0)=0

; значи

f(x)=x^2

. Остава случаят, когато съществува

a\ne0

f(a)=0

. От (3) получаваме

f(2^n a)=0

за всяко

n\ge0

. Нека

b\gt{}0

е произволно. По четност можем да приемем

a\gt{}0

. Избираме

n

така, че

c=2^n a\gt{}b

, и поставяме

x=\frac{3c+b}{4},\qquad y=\frac{c-b}{4}.

Тогава

x,y\gt{}0

x-3y=b

x+y=c

3x-y=2c+b

. В уравнението дясната страна е

f(c)^2=0

. От предишния абзац всички стойности на

f

са неотрицателни, а

f(x)+xy\gt{}0

f(y)+xy\gt{}0

. Следователно

(f(x)+xy)f(b)+(f(y)+xy)f(2c+b)=0

е възможно само ако

f(b)=0

. Значи

f

занулява всяко положително

b

, а по четност и всяко реално

b

. Тогава

f\equiv0

. Получихме точно двете посочени функции.

Отвори задачатаEvan Chen VONVON JMO 2016/6Условие — източник

2017

5 задачи

Задача 1

Пълен запис

Условие

Да се докаже, че съществуват безкрайно много двойки взаимно прости положителни цели числа

a,b\gt{}1

, за които

a+b

дели

a^b+b^a

Решение

Ще построим безкрайно много примери. Нека

d\gt{}1

е произволно цяло число с

d\equiv1\pmod4

и поставяме

x=\frac{d^d+2^d}{d+2},\qquad a=\frac{x+d}{2},\qquad b=\frac{x-d}{2}.

Понеже

d\equiv-2\pmod{d+2}

d

е нечетно, имаме

d^d+2^d\equiv0\pmod{d+2}

, така че

x

е цяло число. Освен това

x

d

са нечетни, следователно

a

b

са цели числа. При достатъчно големи

d

те са по-големи от

1

. Ще проверим, че

a

b

са взаимно прости. Имаме

a-b=d

a+b=x

, а от формулата за

x

следва

\gcd(x,d)=1

: ако просто число

p

дели

d

, тогава по модул

p

получаваме

x\equiv2^{d-1}\not\equiv0

. Понеже

d

е нечетно, това дава

\gcd(a,b)=\gcd(b,d)=1

, следователно в частност

\gcd(a,b)=1

. Остава делимостта. Тъй като

a+b=x

a\equiv-b\pmod x

, а

b

е нечетно,

a^b+b^a\equiv

(-b)^b+b^a=b^b(b^{a-b}-1)=b^b(b^d-1)\pmod x.

От

x=d+2b

имаме

2b\equiv-d\pmod x

. Понеже

x

е нечетно, можем да повдигнем на степен и да получим

b^d\equiv-\frac{d^d}{2^d}\pmod x.

Но по построение

x\mid d^d+2^d

, следователно

b^d\equiv1\pmod x

. Значи

x=a+b

дели

a^b+b^a

. Различните допустими стойности на

d

дават безкрайно много двойки.

Отвори задачатаEvan Chen VONVON JMO 2017/1Условие — източник

Задача 2

Пълен запис

Условие

Докажете, че диофантовото уравнение

(3x^3+xy^2)(x^2y+3y^3)=(x-y)^7

има безбройно много решения в положителни цели числа, и опишете всички решения.

Решение

Понеже лявата страна е положителна, трябва да имаме

x\gt{}y

. Нека

x=da,\qquad y=db,

където

d

е положително цяло число,

\gcd(a,b)=1

a\gt{}b

. След съкращаване уравнението е еквивалентно на това числото

d=\frac{ab(a^2+3b^2)(3a^2+b^2)}{(a-b)^7}

да бъде цяло. Тоест трябва и е достатъчно да е изпълнено

(a-b)^7\mid ab(a^2+3b^2)(3a^2+b^2).\tag{1}

Ще докажем, че (1) е вярно тогава и само тогава, когато

a-b=1

. Ако

a-b=1

, това е очевидно. Обратно, нека (1) е изпълнено. Ако

a

b

са нечетни, тогава

a-b

е четно, а

a^2+3b^2\equiv4\pmod8,\qquad 3a^2+b^2\equiv4\pmod8.

Понеже

ab

е нечетно, произведението вдясно в (1) се дели точно на

2^4

. Но

(a-b)^7

се дели поне на

2^7

, противоречие. Следователно не е възможно

a

b

да са едновременно нечетни. Значи

a-b

е нечетно. Тогава

\gcd(a-b,a)=\gcd(a-b,b)=1,

а също

\gcd(a-b,a^2+3b^2)=\gcd(a-b,4b^2)=1

и по същия начин

\gcd(a-b,3a^2+b^2)=1

. Следователно

a-b

е взаимно просто с всеки от множителите вдясно в (1), така че единствената възможност е

a-b=1

. Значи всички решения се получават така: избираме произволно положително цяло число

b

, поставяме

a=b+1

d=ab(a^2+3b^2)(3a^2+b^2).

Тогава

(x,y)=(da,db)

е решение, а всяко решение има този вид. Това веднага дава безбройно много решения. Еквивалентно, ако

n\gt{}1

е нечетно, можем да запишем

a=\frac{n+1}{2},\qquad b=\frac{n-1}{2},\qquad d=\frac{n^6-1}{4},

и тогава

(x,y)=\left(\frac{(n+1)(n^6-1)}8,\frac{(n-1)(n^6-1)}8\right).

Отвори задачатаEvan Chen VONVON JMO 2017/2Условие — източник

Задача 3

Пълен запис

Условие

Нека

ABC

е равностранен триъгълник и

P

е точка върху описаната му окръжност. Правите

PA

BC

PB

CA

PC

AB

се пресичат съответно в

D

E

F

. Докажете, че лицето на триъгълника

DEF

е два пъти лицето на триъгълника

ABC

Решение

Ще използваме барицентрични координати спрямо

ABC

.Нека

P=(u:v:w)

. Понеже триъгълникът

ABC

е равностранен, уравнението на описаната му окръжност в тези координати е

uv+vw+wu=0.

От дефиницията на барицентричните координати пресечните точки с противоположните страни са

D=(0:v:w),\qquad E=(u:0:w),\qquad F=(u:v:0).

Наистина например правата

PA

съдържа всички точки от вида

(tu+s:tv:tw)

, а при пресичане с

BC

първата координата става нула, което дава

(0:v:w)

. За ориентирани лица получаваме стандартната детерминантна формула

\frac{[DEF]}{[ABC]} =\frac{1}{(u+v)(v+w)(w+u)} \det\begin{bmatrix} 0&v&w\\ u&0&w\\ u&v&0 \end{bmatrix} =\frac{2uvw}{(u+v)(v+w)(w+u)}.

Но

(u+v)(v+w)(w+u)=

(u+v+w)(uv+vw+wu)-uvw=-uvw,

защото

P

лежи на описаната окръжност. Следователно

\frac{[DEF]}{[ABC]}=\frac{2uvw}{-uvw}=-2.

Минусът показва само, че ориентацията на

DEF

е противоположна на тази на

ABC

. Следователно обикновеното лице на триъгълника

DEF

е точно

2[ABC]

, както трябваше да се докаже.

Отвори задачатаEvan Chen VONVON JMO 2017/3Условие — източник

Задача 4

Пълен запис

Условие

Съществуват ли тройки положителни цели числа

(a,b,c)

, за които числото

p=(a-2)(b-2)(c-2)+12

е просто и е собствен делител на положителното число

a^2+b^2+c^2+abc-2017?

Решение

Отговорът е не. Да допуснем, че такава тройка съществува, и поставяме

x=a-2,\qquad y=b-2,\qquad z=c-2,

като без ограничение

x\ge y\ge z\ge-1

. Тогава

p=xyz+12

и след пряко разкриване

a^2+b^2+c^2+abc-2017=(x+y+z+4)^2+p-45^2.

Понеже

p

дели това число, получаваме

p\mid

(x+y+z+4)^2-45^2=(x+y+z-41)(x+y+z+49).

Освен това деленето е собствено, така че числото е по-голямо от

p

; следователно

(x+y+z+4)^2\gt{}45^2

и в частност

x+y+z\gt{}41

. Оттук

x\ge14

. Първо ще покажем, че

x,y,z\ge1

. Ако

z=0

, тогава

p=12

, невъзможно. Ако

z=-1

y\ge1

, то

p=12-xy\lt{}0

. Ако

z=-1

y=0

, отново

p=12

. Остава възможността

z=y=-1

; тогава

p=x+12

, а от

x+y+z\gt{}41

имаме

p\gt{}55

. Делимостта по-горе става

x+12\mid x-43

или

x+12\mid x+47

, тоест

x+12

дели съответно

55

или

35

, невъзможно при

p=x+12\gt{}55

. Следователно наистина

z\ge1

. Ако

y=1

, тогава и

z=1

, така че

p=x+12

. Тогава делимостта по-горе дава

x+12\mid x-39

или

x+12\mid x+51

, тоест

x+12

дели съответно

51

или

63

, невъзможно за просто число поне

29

. Следователно

y\ge2

. По същия начин

p\ge14\cdot2\cdot1+12=40

, така че

p

е просто, по-голямо от

3

, и

\gcd(p,6)=1

. От

p=xyz+12

следва

\gcd(xyz,6)=1

, затова

x,y,z

са нечетни и не се делят на

3

. Тогава

x+y+z

е нечетно, следователно и двата множителя

x+y+z-41

x+y+z+49

са четни. Понеже простото число

p

дели един от тях, всъщност

2p

дели някой от тях, а оттук непременно

x+y+z+49\ge2p=2xyz+24.

Но вече имаме

y\ge2

z\ge1

, а от нечетността всъщност

y\ge3

z\ge1

. Така дясната страна расте твърде бързо: за

x\ge14

получаваме

2xyz+24-(x+y+z+49)\ge

6x+24-(x+3+1+49)=5x-29\gt{}0,

което противоречи на предишното неравенство. Следователно такава тройка не съществува.

Отвори задачатаEvan Chen VONVON JMO 2017/4Условие — източник

Задача 6

Пълен запис

Условие

Върху единичната окръжност са избрани

2017

червени и

2017

сини точки, като никоя от тях не е точката

(1,0)

. Нека

P_1,P_2,\ldots,P_{2017}

е някаква подредба на червените точки. За всяко

i

свързваме

P_i

с най-близката синя точка до

P_i

в посока обратно на часовниковата стрелка, която още не е била използвана. Получаваме

2017

дъги, всяка с един червен и един син край. Да се докаже, че броят на тези дъги, които съдържат точката

(1,0)

, не зависи от избраната подредба на червените точки.

Решение

Ще докажем по-силно твърдение. Започваме от точката

(1,0)

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

1

, когато минем през червена точка, и изваждаме

1

, когато минем през синя точка. Нека

m

е най-малката стойност, която този баланс приема. Твърдим, че независимо от реда на червените точки броят на избраните дъги, които минават през

(1,0)

, е точно

-m

. Това веднага дава независимостта от реда. Доказваме твърдението с индукция по броя на червените точки. Нека първата избрана червена точка е

R

, а синята точка, с която тя се свързва, е

B

. По избора на

B

отворената дъга от

R

до

B

обратно на часовниковата стрелка не съдържа сини точки. Ако тази дъга не съдържа

(1,0)

, тогава при обхождане от

(1,0)

точката

R

се среща преди

B

. След премахване на

R

B

балансът между тях намалява с

1

, а извън този интервал остава същият. Но в този интервал преди премахването балансът е поне колкото стойността точно преди

R

, защото там няма сини точки. Следователно минималната стойност

m

не се променя. Премахнатата дъга не се брои, а по индукция останалите дават

-m

дъги през

(1,0)

. Ако дъгата от

R

до

B

съдържа

(1,0)

, тогава при обхождане от

(1,0)

първо срещаме

B

, а по-късно

R

. След премахването на

R

B

балансът в интервала от

B

до

R

се увеличава с

1

, а извън него остава същият. Понеже по допълнителната дъга от

R

през

(1,0)

до

B

няма сини точки, минимумът се достига в интервала от

B

до

R

; следователно новият минимум е

m+1

. Премахнатата дъга се брои веднъж, а по индукция останалите дават

-(m+1)

дъги през

(1,0)

. Общият брой пак е

1-(m+1)=-m

. Така твърдението е доказано за всички стъпки, а числото

-m

зависи само от първоначалното разположение и оцветяване на точките, не и от реда на червените точки.

Отвори задачатаEvan Chen VONVON JMO 2017/6Условие — източник

2018

5 задачи

Задача 1

Пълен запис

Условие

За всяко положително цяло число

n

намерете броя на положителните цели числа с

n

цифри, в които няма две съседни еднакви цифри и последната цифра е проста.

Решение

Нека

a_n

означава търсения брой, а за удобство поставяме

a_0=0

. Ще преброим малко по-широк клас: низове от

n

цифри, при които първата цифра може да бъде

0

, няма две съседни еднакви цифри и последната цифра е една от простите цифри

2,3,5,7

. Ако строим такъв низ отдясно наляво, последната цифра се избира по

4

начина, а всяка предишна цифра има

9

избора, защото само трябва да е различна от следващата. Значи общият брой е

4\cdot9^{n-1}

. От тези низове тези, които започват с ненулева цифра, са точно числата, броени от

a_n

. Тези, които започват с

0

, след изтриване на началната нула дават точно допустимо число с

n-1

цифри, броено от

a_{n-1}

. Следователно

a_n+a_{n-1}=4\cdot9^{n-1}.

Тази рекурсия с

a_0=0

дава

a_n=4\left(9^{n-1}-9^{n-2}+9^{n-3}-\cdots+(-1)^{n-1}\right).

Сумирайки геометричната прогресия, получаваме

a_n=\frac{2}{5}\left(9^n-(-1)^n\right).

Това е търсеният брой.

Отвори задачатаEvan Chen VONVON JMO 2018/1Условие — източник

Задача 2

Пълен запис

Условие

Нека

a

b

c

са положителни реални числа, за които

a+b+c=4\sqrt[3]{\vphantom{x^2}abc}.

Докажете, че

2(ab+bc+ca)+4\min(a^2,b^2,c^2)\ge a^2+b^2+c^2.

Решение

Неравенството и условието са хомогенни, затова без ограничение можем да приемем, че

c=\min(a,b,c)=1.

Тогава условието става

a+b+1=4\sqrt[3]{\vphantom{x^2}ab}.

Исканото неравенство е еквивалентно на

4ab+2a+2b+3\ge(a+b)^2.

Нека

t=\sqrt[3]{\vphantom{x^2}ab}.

От условието имаме

a+b=4t-1

. Замествайки, остава да докажем

4t^3+2(4t-1)+3\ge(4t-1)^2.

Но това е точно

0\le4t^3-16t^2+16t=4t(t-2)^2,

което е очевидно, понеже

t\gt{}0

. Равенство се получава само при

t=2

, тоест

ab=8

a+b=7

след нормировката

c=1

. Тогава

\{a,b\}=\left\{\frac{7+\sqrt{\vphantom{x^2}17}}2,\frac{7-\sqrt{\vphantom{x^2}17}}2\right\},

а всички останали случаи на равенство се получават чрез общо умножаване на

a,b,c

с положителна константа.

Отвори задачатаEvan Chen VONVON JMO 2018/2Условие — източник

Задача 4

Пълен запис

Условие

Да се намерят всички реални числа

x

със следното свойство: съществува триъгълник с дължини на страните

a,b,c

, радиус на описаната окръжност

2

и поне един ъгъл, не по-малък от

90^\circ

, така че

x^4+ax^3+bx^2+cx+1=0.

Решение

Отговорът е

x=-\frac{\sqrt6+\sqrt2}{2}\qquad\text{или}\qquad x=-\frac{\sqrt6-\sqrt2}{2}.

Понеже всички коефициенти без свободния член са положителни, коренът трябва да е отрицателен. Нека страната

b

е срещу ъгъла, който е поне

90^\circ

. По теоремата на косинусите имаме

b^2\ge a^2+c^2.

От радиуса на описаната окръжност, равен на

2

, следва

b\le4

, тоест

b^2\le4b

. Следователно

a^2+c^2\le b^2\le4b.

Сега преобразуваме уравнението така:

0=x^4+ax^3+bx^2+cx+1

=x^2\left(\left(x+\frac a2\right)^2+\left(\frac1x+\frac c2\right)^2+b-\frac{a^2+c^2}{4}\right).

Последната скоба е сума от неотрицателни членове, затова всички те трябва да са нула. Получаваме

x=-\frac a2,\qquad \frac1x=-\frac c2,\qquad a^2+c^2=4b.

Първите две равенства дават

ac=4

. От веригата

a^2+c^2\le b^2\le4b

и равенството

a^2+c^2=4b

следва

b^2=4b

, следователно

b=4

a^2+c^2=16

. Така

(a+c)^2=a^2+c^2+2ac=24,

и числата

a

c

са

\sqrt6+\sqrt2

\sqrt6-\sqrt2

в някакъв ред. Затова възможните стойности на

x=-a/2

са точно посочените две. Обратно, тези стойности наистина се получават от правоъгълен триъгълник с хипотенуза

4

и катети

\sqrt6+\sqrt2

\sqrt6-\sqrt2

. Радиусът на описаната окръжност е

2

, а горните равенства показват, че съответният полином има избрания корен.

Отвори задачатаEvan Chen VONVON JMO 2018/4Условие — източник

Задача 5

Пълен запис

Условие

Нека

p

е просто число и нека

a_1

a_2

\ldots

a_p

са цели числа. Докажете, че съществува цяло число

k

, за което числата

a_1+k,\ a_2+2k,\ \ldots,\ a_p+pk

дават поне

\frac p2

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

p

Решение

Достатъчно е да разгледаме стойностите

k=0,1,\ldots,p-1

. За всяко такова

k

построяваме граф

G_k

с върхове

1,2,\ldots,p

, като свързваме

i

j

тогава и само тогава, когато

a_i+ik\equiv a_j+jk\pmod p.

За

i\ne j

това е еквивалентно на

k\equiv-\frac{a_i-a_j}{i-j}\pmod p,

което определя точно една стойност на

k

по модул

p

. Следователно всяка двойка върхове се появява като ребро в точно един от графите

G_0,G_1,\ldots,G_{p-1}

. Значи някой от тези графи има най-много

\frac1p\binom p2=\frac{p-1}{2}

ребра. В граф с

p

върха и

e

ребра броят на свързаните компоненти е поне

p-e

, защото добавянето на едно ребро може да намали броя на компонентите с най-много

1

. За избрания граф получаваме поне

p-\frac{p-1}{2}=\frac{p+1}{2}\ge\frac p2

свързани компоненти. Но компонентите на

G_k

са точно класовете от индекси, които дават един и същ остатък сред числата

a_i+ik

. Следователно за този

k

има поне

p/2

различни остатъка, както трябваше.

Отвори задачатаEvan Chen VONVON JMO 2018/5Условие — източник

Задача 6

Пълен запис

Условие

Карл има

n

карти, номерирани с числата

1,2,\ldots,n

. В началото картите са подредени в този ред. В първия ход Карл премества карта

1

така, че в новата подредба вдясно от нея има толкова карти, колкото е имало вляво от нея преди хода. След това прави същото с карта

2

, после с карта

3

и така нататък до карта

n

. Да се докаже, че крайната подредба има същия брой инверсии като началната, тоест нула.

Решение

Ще сравним дадения процес с леко променен процес. При променения процес, когато местим карта

i

, едновременно заменяме нейния надпис

i

n+i

. След всяка стъпка броят на инверсиите остава непроменен. Наистина, точно преди да бъде преместена карта

i

, всички карти

1,2,\ldots,i-1

вече са получили надписи

n+1,n+2,\ldots,n+i-1

, а картите

i+1,\ldots,n

още имат старите си надписи. Следователно надписът

i

е по-малък от всички останали надписи. Ако преди хода вляво от картата има

\ell

карти, тя участва в точно

\ell

инверсии. След промяната новият надпис

n+i

прави тази карта по-голяма от всички останали надписи. Понеже я поставяме така, че вдясно от нея да има точно

\ell

карти, тя отново участва в точно

\ell

инверсии. Относителният ред на всички други карти не се изменя, така че общият брой инверсии се запазва. В началото промененият процес има същата подредба като първоначалния процес, следователно има нула инверсии. В края на променения процес редът на картите е същият като в края на първоначалния процес; единствената разлика е, че всички надписи са увеличени с

n

. Увеличаването на всички надписи с една и съща константа не променя кои двойки са инверсии. Затова крайната подредба в първоначалния процес също има нула инверсии.

Отвори задачатаEvan Chen VONVON JMO 2018/6Условие — източник

2019

4 задачи

Задача 1

Пълен запис

Условие

В редица са подредени

a+b

купи, номерирани от

1

до

a+b

, където

a

b

са дадени положителни цели числа. Първоначално във всяка от първите

a

купи има по една ябълка, а във всяка от последните

b

купи има по една круша. Един допустим ход се състои в това да преместим ябълка от купа

i

в купа

i+1

и круша от купа

j

в купа

j-1

, при условие че

i-j

е четно. Позволено е в една и съща купа едновременно да има няколко плода. Целта е накрая във всяка от първите

b

купи да има по една круша, а във всяка от последните

a

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

ab

е четно.

Решение

Първо ще докажем, че ако

ab

е четно, целта е постижима. Доказваме това с индукция по

a+b

, като допускаме междинно и случаите с някой от параметрите равен на

0

. Ако

\min(a,b)=0

, няма какво да се доказва. Ако

\min(a,b)=1

, например

a=1

, тогава

b

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

\min(a,b)\ge2

. Ако

a+b

е нечетно, разменяме най-лявата ябълка с най-дясната круша, като пак използваме само тези два плода. Това свежда задачата до параметрите

(a-1,b-1)

, а поне един от тях е четен, така че прилагаме индукцията. Ако пък

a+b

е четно, то понеже

ab

е четно, числата

a

b

са четни. Тогава разменяме ябълката в купа

1

с крушата в купа

a+b-1

, а ябълката в купа

2

с крушата в купа

a+b

. След тези размени оставаме със задачата за

(a-2,b-2)

, която също е възможна по индукция. Остава да докажем невъзможността, когато

ab

е нечетно. Нека

X=\text{броят на ябълките в купи с нечетни номера},

Y=\text{броят на крушите в купи с нечетни номера}.

При всеки допустим ход двете преместени купи имат еднаква четност преди хода и еднаква четност след него, така че разликата

X-Y

не се променя. Ако

a

b

са нечетни, първоначално

X=\frac{a+1}{2},\qquad Y=\frac{b-1}{2},

а в желаната крайна конфигурация

X=\frac{a-1}{2},\qquad Y=\frac{b+1}{2}.

Следователно

X-Y

би се променило с

2

, което е невъзможно. Значи целта е постижима точно когато

ab

е четно.

Отвори задачатаEvan Chen VONVON JMO 2019/1Условие — източник

Задача 2

Пълен запис

Условие

За кои двойки цели числа

(a,b)

съществуват функции

f\colon\mathbb Z\to\mathbb Z

g\colon\mathbb Z\to\mathbb Z

, за които

f(g(x))=x+a\qquad\text{и}\qquad g(f(x))=x+b

за всяко цяло число

x

Решение

Отговорът е: точно когато

a=b

или

a=-b

. Ако

a=b

, можем да вземем

f(x)=x+a

g(x)=x

. Ако

a=-b

, можем да вземем

f(x)=-x+a

g(x)=-x

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

f

g

са биекции. Сюрективността следва веднага от равенствата

f(g(x))=x+a

g(f(x))=x+b

. За инективността, ако

f(u)=f(v)

, тогава

u+b=g(f(u))=g(f(v))=v+b,

тоест

u=v

; аналогично

g

е инективна. Освен това за всяко цяло

x

имаме

f(x+b)=f(g(f(x)))=f(x)+a

g(x+a)=g(f(g(x)))=g(x)+b.\tag{1}

Ако

a=0

или

b=0

, от (1) и инективността веднага следва, че и другото число е

0

, и сме в случая

a=b

. Нека вече

ab\ne0

. Ще покажем, че

|a|=|b|

. Ако

|b|\gt{}|a|

, разглеждаме числата

f(0),f(1),\dots,f(|b|-1)

по модул

|a|

. По принципа на Дирихле две от тях, да кажем

f(r)

f(s)

0\le r\lt{}s\lt{}|b|

, са сравними по модул

|a|

. Значи

f(s)=f(r)+ta

за някое цяло

t

. От първото равенство в (1), приложено многократно и в двете посоки, получаваме

f(r+tb)=f(r)+ta=f(s).

Понеже

f

е инективна, следва

s=r+tb

, което е невъзможно при

0\lt{}s-r\lt{}|b|

, освен ако

t=0

, но тогава пак получаваме

s=r

. Противоречие. Същият аргумент с разменени роли на

f,g

a,b

изключва случая

|a|\gt{}|b|

. Следователно

|a|=|b|

, тоест

a=b

или

a=-b

, както трябваше.

Отвори задачатаEvan Chen VONVON JMO 2019/2Условие — източник

Задача 5

Пълен запис

Условие

Нека

n

е неотрицателно цяло число. Да се намери броят на начините да се изберат множества

S_{ij}\subseteq\{1,2,\ldots,2n\}

за всички

0\le i\le n

0\le j\le n

(не непременно различни), така че -

|S_{ij}|=i+j

; -

S_{ij}\subseteq S_{kl}

винаги когато

0\le i\le k\le n

0\le j\le l\le n

Решение

Отговорът е

(2n)!\cdot2^{n^2}.

Първо отбелязваме, че

\varnothing=S_{00}\subsetneq S_{01}\subsetneq\cdots\subsetneq S_{0n}\subsetneq S_{1n}\subsetneq\cdots\subsetneq S_{nn}=

\{1,2,\ldots,2n\}.

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

(2n)!

. След преименуване на елементите можем да приемем, че

S_{0i}=\{1,2,\ldots,i\}\qquad\text{и}\qquad S_{in}=\{1,2,\ldots,n+i\}.

Остава да преброим начините за запълване на останалата решетка. Ще докажем по-силно твърдение. Нека

T

е избор от клетки, които искаме да запълним, със свойството, че ако една клетка е в

T

, то всички клетки над нея и вляво от нея също са в

T

; с други думи,

T

е диаграма на Юнг. Тогава броят на допустимите запълвания на клетките в

T

е точно

2^{|T|}

. Доказателството е с индукция по

|T|

. При

|T|=0

няма какво да се доказва. Нека добавяме нова ъглова клетка и нека локалната картина е

\begin{bmatrix} B & C \\ A & S \end{bmatrix},

където

A

B

C

вече са фиксирани, а

S

трябва да се избере. Понеже размерите на множествата се увеличават с по

1

при всяка стъпка нагоре или надясно, можем да запишем

B=A\cup\{x\},\qquad C=A\cup\{x,y\}

за някои

x,y\notin A

. Тогава за

S

има точно две възможности:

A\cup\{x\}\qquad\text{и}\qquad A\cup\{y\},

и двете удовлетворяват всички нужни включвания и имат правилната големина. Следователно всяка добавена клетка дава независим фактор

2

. За пълния квадрат има

n^2

такива клетки, така че след фиксираната граница получаваме

2^{n^2}

запълвания. Общият брой е

(2n)!\cdot2^{n^2}.

Отвори задачатаEvan Chen VONVON JMO 2019/5Условие — източник

Задача 6

Пълен запис

Условие

Нека

m

n

са взаимно прости положителни цели числа. На дъската са написани числата

\frac mn

\frac nm

. Във всеки момент Евън може да избере две от написаните числа

x

y

и да запише или тяхното средно аритметично

\frac{x+y}{2}

, или тяхното хармонично средно

\frac{2xy}{x+y}

. За кои двойки

(m,n)

Евън може да запише числото

1

след краен брой стъпки?

Решение

Това е възможно тогава и само тогава, когато

m+n

е степен на

2

. Нека

q=m/n

, така че началните числа на дъската са

q

q^{-1}

. Първо ще докажем невъзможността. Нека

p

е нечетен прост делител на

m+n

. Тогава

p\nmid mn

, понеже

m

n

са взаимно прости, и

q\equiv q^{-1}\equiv -1\pmod p.

Ако

a\equiv b\equiv -1\pmod p

, то

2\not\equiv0\pmod p

a+b\equiv -2\not\equiv0\pmod p

, така че и двете средни са определени по модул

p

\frac{a+b}{2}\equiv -1\pmod p, \qquad \frac{2ab}{a+b}\equiv -1\pmod p.

Следователно всички числа, които някога се появят на дъската, остават сравними с

-1

по модул

p

. Числото

1

не може да се появи. Значи

m+n

не може да има нечетен прост делител. Обратно, нека

m+n=2^r

. Всъщност ще използваме само средноаритметични операции. Чрез последователно вземане на средни аритметични можем да получим всяка двоична изпъкнала комбинация

\frac{a q+b q^{-1}}{2^r}

a+b=2^r

: това е просто построяване чрез повтарящо се делене наполовина. Избираме

a=n

b=m

. Тогава

\frac{nq+mq^{-1}}{m+n}=\frac{n\cdot m/n+m\cdot n/m}{m+n}=1.

Понеже

m+n=2^r

, това число може да бъде построено с крайно много средноаритметични операции. Следователно търсените двойки са точно тези, за които

m+n

е степен на

2

Отвори задачатаEvan Chen VONVON JMO 2019/6Условие — източник

2020

3 задачи

Задача 1

Пълен запис

Условие

Нека

n\ge2

е цяло число. Карл има

n

книги, подредени на лавица. Всяка книга има височина и ширина. Няма две книги с еднаква височина и няма две книги с еднаква ширина. Първоначално книгите са подредени отляво надясно по нарастваща височина. Един ход се състои в това Карл да избере две съседни книги, при които лявата книга е по-широка и по-ниска от дясната, и да разменя местата им. Карл повтаря това, докато повече не може да направи ход. Докажете, че независимо как Карл избира ходовете си, процесът спира след краен брой ходове и тогава книгите са подредени отляво надясно по нарастваща ширина.

Решение

Ще казваме, че двойка книги

(A,B)

е инвертирана по височина, ако

A

е вляво от

B

A

е по-висока от

B

. Аналогично дефинираме двойки, инвертирани по ширина. Всеки ход намалява броя на двойките, инвертирани по ширина: при размяна на две съседни книги се променя само техният взаимен ред, а избраната двойка вече не е инвертирана по ширина. Следователно процесът завършва, понеже първоначално има най-много

\binom n2

такива двойки. Сега разглеждаме момент, в който повече ходове не са възможни. Да допуснем противното: има две съседни книги

(A,B)

, които все още са инвертирани по ширина, тоест

A

е вляво от

B

и е по-широка от нея. Понеже ход вече не е възможен, тази двойка трябва да е инвертирана и по височина, тоест

A

е по-висока от

B

. Първоначално обаче книгите са били подредени по нарастваща височина, така че

B

е била вляво от

A

. За да се окажат в реда

A,B

, двете книги някога трябва да са били разменени една с друга. Но когато са били в реда

B,A

, лявата книга

B

е била по-ниска и по-тясна от

A

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

Отвори задачатаEvan Chen VONVON JMO 2020/1Условие — източник

Задача 5

Пълен запис

Условие

Нека

(a_1,b_1),(a_2,b_2),\dots,(a_{100},b_{100})

са различни наредени двойки от неотрицателни цели числа. Нека

N

е броят на двойките цели числа

(i,j)

, за които

1\le i\lt{}j\le100

\left\lvert a_ib_j-a_jb_i\right\rvert=1.

Да се намери най-голямата възможна стойност на

N

при всички избори на тези

100

наредени двойки.

Решение

Отговорът е

197

. По-общо, ако числото

100

се замени с произволно

n\ge2

, отговорът е

2n-3

. Нека

P_i=(a_i,b_i)

е точка в координатната равнина, а

O=(0,0)

. Условието

|a_ib_j-a_jb_i|=1

означава, че триъгълникът

OP_iP_j

има лице

\frac12

. Ще наричаме такъв триъгълник добър. Първо даваме конструкция за

197

добри триъгълника. Вземаме точките

(1,0),(1,1),(2,1),(3,1),\dots,(99,1).

Има

98

добри триъгълника с върхове

(0,0)

(k,1)

(k+1,1)

за

k=1,2,\dots,98

, както и

99

добри триъгълника с върхове

(0,0)

(1,0)

(k,1)

за

k=1,2,\dots,99

. Общо получаваме

98+99=197

. Остава да докажем, че повече не може. Ще докажем по индукция по

n

, че за

n

точки броят на добрите триъгълници е най-много

2n-3

. Базата

n=2

е очевидна. Нека

P=P_n=(a,b)

е точка, която е най-далеч от

O

измежду всички избрани точки. Твърдим, че

P

участва в най-много два добри триъгълника. Ако

\gcd(a,b)\gt{}1

, тогава

P

не участва в нито един добър триъгълник, защото всеки общ делител на

a

b

дели и детерминантата

ay-bx

за всяка целочислена точка

Q=(x,y)

. Нека сега

\gcd(a,b)=1

. Множеството от точките

Q=(x,y)

, за които

[OPQ]=\frac12

, е обединението на двете прави

ay-bx=1\qquad\text{и}\qquad ay-bx=-1.

Те са успоредни на

OP

. Върху всяка от тези прави целочислените точки се получават една от друга чрез прибавяне или изваждане на вектора

(a,b)

.Понеже всички избрани точки са в първи квадрант и

P

е най-далеч от

O

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

(a,b)

, то по-далечната е строго по-далеч от

O

от самата точка

P=(a,b)

, което противоречи на избора на

P

. Следователно

P

участва в най-много два добри триъгълника. Изтриваме точката

P

. По индукционната хипотеза останалите

n-1

точки дават най-много

2(n-1)-3

добри триъгълника, а изтритата точка е участвала в най-много още два. Затова общият брой е най-много

2(n-1)-3+2=2n-3.

За

n=100

това дава горна граница

197

, а конструкцията по-горе я достига.

Отвори задачатаEvan Chen VONVON JMO 2020/5Условие — източник

Задача 6

Пълен запис

Условие

Нека

n\ge2

е цяло число. Нека

P(x_1,x_2,\ldots,x_n)

е неконстантен полином на

n

променливи с реални коефициенти. Да се предположи, че

P

се занулява винаги когато две от променливите му са равни. Докажете, че

P

има поне

n!

едночлена.

Решение

Ще докажем твърдението с индукция по

n

. Първо отбелязваме следния факт. Твърдение. За никои

1\le i\lt{}j\le n

полиномът

P

няма едночлен, в който не участват едновременно и

x_i

, и

x_j

. Наистина, ако положим

x_i=x_j=0

, полиномът трябва да стане тъждествено нула като полином в останалите

n-2

променливи, защото се занулява за всички реални стойности на тези променливи. Следователно след събирането на подобните членове не може да остане едночлен, който не съдържа нито

x_i

, нито

x_j

. Базата

n=2

е ясна: неконстантен полином, който се занулява при

x_1=x_2

, има поне два едночлена. Нека

n\ge3

и твърдението вече е доказано за

n-1

променливи. Можем да приемем, че

P

не се дели на никоя от променливите

x_1,x_2,\ldots,x_n

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

x_i=x_j

. Сега за всяко

r=1,2,\ldots,n

разглеждаме полинома, получен от

P

след полагане

x_r=0

. Той не е тъждествено нула, защото

x_r

не дели

P

, и пак се занулява винаги когато две от останалите му променливи са равни. По индукционното предположение той има поне

(n-1)!

едночлена. Остава да забележим, че едночлените, които се виждат при различни избори на

r

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

P

оцеляваше едновременно при

x_i=0

и при

x_j=0

, той нямаше да съдържа нито

x_i

, нито

x_j

, което противоречи на твърдението. Следователно

P

има поне

n\cdot(n-1)\neq{}n!

едночлена. Границата е точна, например за полинома на Вандермонд

\prod_{1\le i\lt{}j\le n}(x_i-x_j),

който има точно

n!

едночлена.

Отвори задачатаEvan Chen VONVON JMO 2020/6Условие — източник

2022

4 задачи

Задача 1

Пълен запис

Условие

Да се намерят всички положителни цели числа

m

, за които съществува безкрайна редица в

\mathbb Z/m\mathbb Z

, която едновременно е аритметична прогресия и геометрична прогресия, но не е константна.

Решение

Отговорът е: точно числата

m

, които не са безквадратни. Нека първо

m

е безквадратно и да разгледаме три последователни члена

s-d, s, s+d

на аритметична прогресия по модул

m

. За да бъдат те и три последователни члена на геометрична прогресия, е необходимо

s^2\equiv(s-d)(s+d)\pmod m,

тоест

d^2\equiv0\pmod m.

Понеже

m

е безквадратно, от това следва

d\equiv0\pmod m

. Следователно всяка такава редица е константна. Обратно, нека

p^2\mid m

за някое просто число

p

. Поставяме

d=m/p

, което не е

0

по модул

m

, но

d^2

се дели на

m

. Тогава всяка аритметична прогресия

s,s+d,s+2d,\ldots

по модул

m

удовлетворява условието

d^2\equiv0\pmod m

, а значи всеки три последователни нейни члена изпълняват съотношението за геометрична прогресия. Тя не е константна, понеже

d\not\equiv0\pmod m

. Това дава търсената редица.

Отвори задачатаEvan Chen VONVON JMO 2022/1Условие — източник

Задача 2

Пълен запис

Условие

Нека

a

b

са неотрицателни цели числа. Всяка клетка на квадратна таблица

(a+b+1)\times(a+b+1)

е оцветена или в кехлибарено, или в бронзово. Да се докаже, че ако има поне

a^2+ab-b

кехлибарени клетки и поне

b^2+ab-a

бронзови клетки, то могат да се изберат

a

кехлибарени и

b

бронзови клетки така, че никои две от избраните клетки да не са в един и същи ред или в един и същи стълб.

Решение

Нека

N=a+b+1

. Ще наричаме трансверсал избор на

N

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

N

. От условието получаваме

\mathbb E(\#\text{ кехлибарени})\ge

\frac{a^2+ab-b}{a+b+1}=a-1+\frac1N.

Значи съществува трансверсал

T_A

, който съдържа поне

a

кехлибарени клетки. По същия начин съществува трансверсал

T_B

, който съдържа поне

b

бронзови клетки, а следователно съдържа най-много

a+1

кехлибарени клетки. Сега ще преминем от

T_A

към

T_B

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

T_A

до

T_B

. При една размяна броят на кехлибарените клетки се изменя с най-много

2

. В началото той е поне

a

, а в края е най-много

a+1

; следователно в някой момент по веригата той е точно

a

или точно

a+1

. Ако е точно

a

, избираме всички кехлибарени клетки от този трансверсал и допълваме с произволни

b

бронзови клетки от него. Ако е точно

a+1

, тогава в трансверсала има точно

b

бронзови клетки и избираме тях, заедно с произволни

a

от кехлибарените клетки. В двата случая избраните клетки остават в различни редове и стълбове.

Отвори задачатаEvan Chen VONVON JMO 2022/2Условие — източник

Задача 5

Пълен запис

Условие

Да се намерят всички наредени двойки прости числа

(p,q)

, за които и

p-q

, и

pq-q

са точни квадрати.

Решение

Единствената двойка е

(p,q)=(3,2)

, която наистина работи, защото

3-2=1

3\cdot2-2=4

. Нека сега

(p,q)

е произволно решение. Понеже

p-q

е квадрат, имаме

p\ge q

. Случаят

p=q

е невъзможен, защото тогава

pq-q=q(p-1)

съдържа простия множител

q

на нечетна степен. Следователно можем да запишем

p-q=a^2,\qquad q(p-1)=b^2

за цели числа

0\lt{}a\lt{}b\lt{}p

. Изваждаме двете равенства и получаваме

(b-a)(b+a)=b^2-a^2=p(q-1).

Понеже

0\lt{}b-a\lt{}p

0\lt{}b+a\lt{}2p

, простото число

p

трябва да дели множителя

b+a

; значи

b+a=p

b-a=q-1

. Следователно

p

q-1

имат една и съща четност. Ако

p

е нечетно, то

q-1

е нечетно, откъдето

q=2

. Ако

p=2

, то

q=2

, което вече беше изключено. Значи

q=2

. Тогава

p-2=a^2,\qquad 2p-2=b^2.

Ако

p\not=3

, разглеждаме по модул

3

. При

p\equiv1\pmod3

числото

p-2

е конгруентно на

2

по модул

3

, невъзможно за квадрат. При

p\equiv2\pmod3

числото

2p-2

е конгруентно на

2

по модул

3

, отново невъзможно за квадрат. Остава

p=3

, и получаваме единственото решение

(3,2)

Отвори задачатаEvan Chen VONVON JMO 2022/5Условие — източник

Задача 6

Пълен запис

Условие

Нека

a_0

b_0

c_0

са комплексни числа и за всяко неотрицателно цяло число

n

са дефинирани

\begin{align*} a_{n+1}&=a_n^2+2b_nc_n,\\ b_{n+1}&=b_n^2+2c_na_n,\\ c_{n+1}&=c_n^2+2a_nb_n. \end{align*}

Да се предположи, че

\max\{|a_n|,|b_n|,|c_n|\}\le2022

за всяко

n\ge0

. Докажете, че

|a_0|^2+|b_0|^2+|c_0|^2\le1.

Решение

За краткост полагаме

s_n=|a_n|^2+|b_n|^2+|c_n|^2.

Тези числа са реални. Ще използваме следното ключово тъждество:

s_{n+1}-s_n^2=2|a_n\overline{b_n}+b_n\overline{c_n}+c_n\overline{a_n}|^2.

Да го докажем чрез директна сметка. Първо,

\begin{align*} s_{n+1}&=\left|a_n^2+2b_nc_n\right|^2+\left|b_n^2+2c_na_n\right|^2+\left|c_n^2+2a_nb_n\right|^2\\ &=\sum_{\mathrm{cyc}}\left|a_n^2+2b_nc_n\right|^2\\ &=\sum_{\mathrm{cyc}}(a_n^2+2b_nc_n)(\overline{a_n}^2+2\overline{b_n}\overline{c_n})\\ &=\sum_{\mathrm{cyc}}\left(|a_n|^4+2\overline{a_n}^2b_nc_n+2a_n^2\overline{b_n}\overline{c_n}+4|b_n|^2|c_n|^2\right)\\ &=s_n^2+2\sum_{\mathrm{cyc}}\left(\overline{a_n}^2b_nc_n+a_n^2\overline{b_n}\overline{c_n}+|b_n|^2|c_n|^2\right). \end{align*}

От друга страна,

\begin{align*} &|a_n\overline{b_n}+b_n\overline{c_n}+c_n\overline{a_n}|^2\\ &\quad=(a_n\overline{b_n}+b_n\overline{c_n}+c_n\overline{a_n})(\overline{a_n}b_n+\overline{b_n}c_n+\overline{c_n}a_n)\\ &\quad=|a_n|^2|b_n|^2+a_n\overline{b_n}^2c_n+a_n^2\overline{b_n}\overline{c_n} +\overline{a_n}b_n^2\overline{c_n}+|b_n|^2|c_n|^2+a_nb_n\overline{c_n}^2\\ &\qquad+\overline{a_n}^2b_nc_n+\overline{a_n}\overline{b_n}c_n^2+|a_n|^2|c_n|^2. \end{align*}

Това съвпада с горната циклична сума член по член, което доказва тъждеството. В частност

s_{n+1}\ge s_n^2

. Повтаряйки, получаваме

s_n\ge s_0^{2^n}.

Ако

s_0\gt{}1

, то редицата

(s_n)

е неограничена. Това противоречи на условието

\max\{|a_n|,|b_n|,|c_n|\}\le2022

за всички

n

. Следователно

s_0\le1

, както се искаше.

Отвори задачатаEvan Chen VONVON JMO 2022/6Условие — източник

2023

4 задачи

Задача 1

Пълен запис

Условие

Да се намерят всички тройки положителни цели числа

(x,y,z)

, за които е изпълнено

2(x+y+z+2xyz)^2=(2xy+2yz+2zx+1)^2+2023

Решение

Отговорът е всички пермутации на

(2,3,3)

. Основната стъпка е следното тъждество, което се проверява с директно разкриване на скоби:

2(x+y+z+2xyz)^2-(2xy+2yz+2zx+1)^2=

(2x^2-1)(2y^2-1)(2z^2-1).

То може да се види и като умножение на норми в

\mathbb Q(\sqrt2)

, но тук самото тъждество е достатъчно. От даденото уравнение получаваме

(2x^2-1)(2y^2-1)(2z^2-1)=2023=7\cdot17^2.

Всеки от трите множителя е положителен нечетен делител на

2023

. Делителите са

1,7,17,119,289,2023

. Ако

2t^2-1

е един от тях, то

(d+1)/2

трябва да е квадрат. Това става само за

d=1,7,17

, като съответните стойности на

t

са

1,2,3

. В произведението обаче не може да участва множителят

1

, защото тогава останалите два множителя трябва да дадат

2023

, а това би изисквало множител

119

или

2023

, които не са от вида

2t^2-1

. Следователно трите множителя са точно

7,17,17

в някакъв ред. Значи съответно

x,y,z

са

2,3,3

в някакъв ред. Обратно, при всяка пермутация на

(2,3,3)

трите множителя са

7,17,17

, така че тъждеството връща точно даденото уравнение.

Отвори задачатаEvan Chen VONVON JMO 2023/1Условие — източник

Задача 3

Пълен запис

Условие

Нека

n

е нечетно положително цяло число. Разглеждаме дъска

n\times n

, съставена от единични квадратчета. Да наречем една конфигурация максимална, ако тя се състои от

(n^2-1)/2

домина, подравнени по решетката, които покриват всички квадратчета освен едно. От такава конфигурация е позволено да плъзнем едно домино, без да го въртим, така че то да покрие непокритото квадратче; тогава се получава нова максимална конфигурация с друго непокрито квадратче. За максимална конфигурация

C

нека

k(C)

е броят на различните максимални конфигурации, които могат да се достигнат от

C

чрез поредица от такива плъзгания. Да се намери най-голямата възможна стойност на

k(C)

Решение

Отговорът е

\left(\frac{n+1}{2}\right)^2.

Номерираме квадратчетата с координати

(x,y)

, където

1\le x,y\le n

. За дадена конфигурация наричаме специални непокритото квадратче и всички квадратчета, чиито две координати имат същите четности като координатите на непокритото квадратче. Броят на специалните квадратчета е най-много

((n+1)/2)^2

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

S

, то покрива и съседно неспециално квадратче; ако в същата посока на още една стъпка има специално квадратче

T

, поставяме ребро

S\to T

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

G

е слабосвързаната компонента, която съдържа непокритото квадратче. В нея няма ненасочен цикъл: ако имаше такъв, условието за най-много едно изходящо ребро от връх би принудило целия цикъл да е насочен, а тогава той не може да лежи в компонента на връх без изходящо ребро. Следователно подлежащият граф на

G

е дърво, а всички ребра в него са ориентирани към непокритото квадратче. Едно плъзгане по ребро на това дърво просто обръща ориентацията на това ребро и премества единствения връх без изходящо ребро в съседен връх. Така достижимите конфигурации са най-много колкото върховете на

G

, а значи най-много

((n+1)/2)^2

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

((n+1)/2)^2

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

((n+1)/2)^2

Отвори задачатаEvan Chen VONVON JMO 2023/3Условие — източник

Задача 4

Пълен запис

Условие

Блейк и Руби играят игра върху безкрайна дъска от единични квадратчета. Първоначално всички квадратчета са бели. Двамата се редуват, като Блейк започва. На всеки ход Блейк оцветява в синьо едно бяло квадратче, а Руби оцветява в червено две бели квадратчета. Блейк може да приключи играта, когато пожелае; тогава резултатът е броят на единичните квадратчета в най-голямата проста многоъгълна област, съставена само от сини квадратчета. Да се намери най-големият резултат, който Блейк може да гарантира, независимо как играе Руби.

Решение

Отговорът е

4

. Първо Блейк може винаги да постигне синя област от поне

4

квадратчета. Той започва от произволно квадратче и след това винаги избира бяло квадратче, което има обща страна с вече построената синя област. Трябва само да проверим, че докато синята област има

m\le3

квадратчета, Руби не може да блокира всички възможни продължения. Всяка свързана фигура от

m\le3

единични квадратчета има повече от

2m

свободи, тоест несини квадратчета с обща страна със синята фигура. След

m

хода на Блейк Руби е оцветила само

2m

червени квадратчета, затова поне една свобода остава бяла и Блейк може да продължи. Така той достига четири свързани сини квадратчета. Сега описваме стратегия на Руби, която не допуска по-голяма синя област. Разделяме дъската на неприпокриващи се блокове

2\times2

. Когато Блейк оцвети квадратче

c

, Руби оцветява в червено всички бели квадратчета от същия блок, които имат обща страна с

c

; ако така са по-малко от две, тя използва останалите си ходове произволно. Следователно в един блок никога няма две сини квадратчета с обща страна: първото от тях би накарало Руби веднага да оцвети второто в червено. За горната оценка вземаме произволно синьо квадратче

w

. След завъртане на картината можем да смятаме, че

w

е югоизточното квадратче в своя блок

2\times2

. Нека

x

y

z

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

w

. Синя свързана област, която съдържа

w

, не може да напусне четворката

\{w,x,y,z\}

: когато някое от тези четири квадратчета стане синьо, стратегията на Руби оцветява неговите съседни квадратчета в съответния блок, а точно те са изходите от четворката навън. Значи всяка проста синя многоъгълна област има най-много

4

единични квадратчета. Комбинирайки двете стратегии, при оптимална игра най-голямата такава област има точно

4

квадратчета.

Отвори задачатаEvan Chen VONVON JMO 2023/4Условие — източник

Задача 5

Пълен запис

Условие

Фиксирани са положителни цели числа

a

N

, а на дъската са записани

N

положителни цели числа. Алиса и Боб играят следната игра. На ход на Алиса тя трябва да замени някое число

n

на дъската с

n+a

, а на ход на Боб той трябва да замени някое четно число

n

на дъската с

n/2

. Алиса започва и двамата се редуват. Ако на ход на Боб няма възможен ход, играта приключва. След като анализира

N

-те числа на дъската, Боб разбира, че независимо какви ходове прави Алиса, той може да принуди играта в крайна сметка да приключи. Докажете, че всъщност за тези стойности на

a

и за тези

N

числа на дъската играта задължително приключва независимо от ходовете и на Алиса, и на Боб.

Решение

При

N=1

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

N\ge2

. Нека

S

е множеството от числата на дъската. Твърдение. Ако

N\ge2

\nu_2(x)\lt{}\nu_2(a)

за всяко

x\in S

, тогава играта задължително приключва независимо как играе всеки от двамата. Доказателство. При ход на Алиса стойността на

\nu_2

на избраното число не се променя, понеже добавяме число с по-голяма

2

-адична оценка. При ход на Боб стойността на

\nu_2

на избраното число намалява с

1

. Играта приключва, когато всички тези оценки станат

0

. Следователно Боб може да направи само краен брой ходове, независимо от избора на двамата играчи. Твърдение. Ако

N\ge2

и на дъската има число

x

\nu_2(x)\ge\nu_2(a)

, тогава Алиса може да направи така, че играта да продължи безкрайно. Доказателство. Нека

x

е първото число на дъската, като стойността му се променя с времето. Стратегията на Алиса е следната: ако

\nu_2(x)=\nu_2(a)

, тя играе върху първото число, така че новата стойност има

\nu_2(x+a)\gt{}\nu_2(a)

; в противен случай тя играе върху някое друго число. Двойна индукция показва, че точно преди всеки ход на Боб винаги е изпълнено

\nu_2(x)\gt{}\nu_2(a)

, а след всеки ход на Боб винаги е изпълнено

\nu_2(x)\ge\nu_2(a)

. В частност Боб никога няма да остане без възможен ход, защото деленето на

x

на

2

винаги е разрешено. Сега завършваме задачата. Ако имаше число

x

на дъската с

\nu_2(x)\ge\nu_2(a)

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

x

на дъската имаме

\nu_2(x)\lt{}\nu_2(a)

, а по първото твърдение играта приключва независимо от ходовете на двамата.

Отвори задачатаEvan Chen VONVON JMO 2023/5Условие — източник

2024

5 задачи

Задача 1

Пълен запис

Условие

Нека

ABCD

е вписан четириъгълник с

AB=7

CD=8

. Точките

P

Q

са избрани върху отсечката

AB

така, че

AP=BQ=3

. Точките

R

S

са избрани върху отсечката

CD

така, че

CR=DS=2

. Да се докаже, че

PQRS

е вписан четириъгълник.

Решение

Ето три възможни подхода. **Решение в един ред.** Четирите точки

P

Q

R

S

имат една и съща степен

-12

спрямо

(ABCD)

. Следователно всъщност те лежат върху окръжност, концентрична с

(ABCD)

. **Решение чрез степен на външна точка.** Разглеждаме два случая. **Случай, в който

AB

CD

не са успоредни.** Нека правите

AB

CD

се пресичат в

T

. Без ограничение на общността

A

лежи между

B

T

, а

D

лежи между

C

T

. Нека

x=TA

y=TD

, както е показано по-долу.От степен на точка имаме

\begin{align*} \text{$ABCD$ е вписан} &\iff x(x+7)=y(y+8), \\ \text{$PQRS$ е вписан} &\iff (x+3)(x+4)=(y+2)(y+6). \end{align*}

Второто равенство обаче се получава от първото, като към двете страни се прибави

12

. (Тоест

(x+3)(x+4)=x(x+7)+12

, докато

(y+2)(y+6)=y(y+8)+12

.) Следователно заключението е непосредствено. **Случай, в който

AB

CD

са успоредни.** Тогава

ABCD

е равнобедрен трапец. Цялата конфигурация е симетрична спрямо общата средна перпендикулярна към правите

AB

CD

. Сега

PQRS

също е равнобедрен трапец, следователно и той е вписан.**Решение с Питагоровата теорема.** Нека

\rho

O

са съответно радиусът и центърът на описаната около

ABCD

окръжност. Ще покажем, че всъщност

P

Q

R

S

лежат върху окръжност с център

O

, тоест че дължините

PO

QO

RO

SO

са равни.В доказателството многократно ще използваме Питагоровата теорема. Нека

M

е средата на

\overline{PQ}

, която е и средата на

\overline{AB}

, понеже

AM=MB=3.5

PM=QM=0.5

. Ако

M

е различна от

O

, то

\overline{OM}

е средната перпендикулярна към

\overline{AB}

и от Питагоровата теорема получаваме

\begin{align*} PO^2 &= PM^2+MO^2=PM^2+(AO^2-AM^2)=0.5^2+\rho^2-3.5^2, \\ QO^2 &= QM^2+MO^2=QM^2+(BO^2-BM^2)=0.5^2+\rho^2-3.5^2. \end{align*}

И в случая

O=M

същите равенства също са верни. Аналогично, нека

N

е средата на

\overline{RS}

, която е и средата на

\overline{CD}

, понеже

CN=DN=4

RN=SN=2

. Повтарянето на същото пресмятане дава

\begin{align*} RO^2 &= RN^2+NO^2=RN^2+(CO^2-CN^2)=2^2+\rho^2-4^2, \\ SO^2 &= SN^2+NO^2=SN^2+(DO^2-DN^2)=2^2+\rho^2-4^2. \end{align*}

Оттук следва, че

PO^2=QO^2=RO^2=SO^2=\rho^2-12.

С това задачата е решена.

Отвори задачатаEvan Chen VONVON JMO 2024/1Условие — източник

Задача 2

Пълен запис

Условие

Нека

m

n

са положителни цели числа. Нека

S

е множеството от решетъчните точки

(x,y)

, за които

1\le x\le 2m

1\le y\le 2n

. Конфигурация от

mn

правоъгълника със страни, успоредни на координатните оси, се нарича щастлива, ако всяка точка от

S

е връх на точно един правоъгълник. Да се докаже, че броят на щастливите конфигурации е нечетен.

Решение

Нека

f(2m,2n)

означава броя на щастливите конфигурации върху решетка от

2m\times2n

точки. Разстоянията между редовете и стълбовете нямат значение; важен е само редът им. Първо, при

m=1

решетката има два стълба и

2n

реда. Всеки правоъгълник тогава се определя единствено от двойка редове, затова броим съвършените сдвоявания на

2n

реда:

f(2,2n)=(2n-1)!\neq{}(2n-1)(2n-3)\cdots3\cdot1.

Следователно

f(2,2n)

е нечетно. Сега ще покажем, че

f(2m,2n)\equiv f(2m-2,2n)\pmod 2.

Разглеждаме операцията

\tau

, която разменя последните два стълба. Тя е инволюция върху щастливите конфигурации. Всички конфигурации, които не са фиксирани от

\tau

, се разбиват на двойки и не влияят на паритета. Фиксираните конфигурации са точно тези, при които последните два стълба са самостоятелни: всеки правоъгълник с връх в тях лежи изцяло в тези два стълба. Такива конфигурации се избират по

f(2m-2,2n)\cdot f(2,2n)

начина. Понеже

f(2,2n)

е нечетно, това дава исканото сравнение по модул

2

. Повтаряйки намаляването на броя стълбове, получаваме

f(2m,2n)\equiv f(2,2n)\equiv1\pmod2.

Следователно броят на щастливите конфигурации винаги е нечетен.

Отвори задачатаEvan Chen VONVON JMO 2024/2Условие — източник

Задача 3

Пълен запис

Условие

Последователността

a_1,a_2,\ldots

от положителни цели числа е дефинирана рекурсивно с

a_1=2

a_{n+1}=a_n^{n+1}-1

за

n\ge1

. Да се докаже, че за всяко нечетно просто число

p

и всяко цяло число

k

някой член на последователността се дели на

p^k

Решение

При

k\le0

твърдението е тривиално, така че нека

k\ge1

. Ще използваме три кратки наблюдения. Първо, ако

n

се дели на

p-1

, то или

a_{n-1}\equiv0\pmod p

, или

a_n\equiv0\pmod p

. Наистина, ако

a_{n-1}\not\equiv0\pmod p

, от малката теорема на Ферма следва

a_n=a_{n-1}^n-1=\left(a_{n-1}^{n/(p-1)}\right)^{p-1}-1\equiv0\pmod p.

Второ, ако

n\ge2

е четно, тогава

a_n^{n+1}\mid a_{n+2}.

Това е така, защото

a_{n+2}=a_{n+1}^{n+2}-1

, а понеже

n+2

е четно, изразът се дели на

a_{n+1}+1=a_n^{n+1}

. Ако за някое кратно

n

на

p-1

n\gt{}k

имаме

p\mid a_n

, второто наблюдение веднага дава член, делящ се на

p^k

. Остава случаят, в който за избраното кратно на

p-1

първото наблюдение ни дава

p\mid a_{n-1}

. Избираме

n

така, че

n\equiv0\pmod{p-1},\qquad n\equiv1\pmod{p^{k-1}},

което е възможно по китайската теорема за остатъците; освен това

n

е четно, понеже

p-1

е четно. Ако

p\mid a_{n-1}

, то от

a_{n-1}=a_{n-2}^{n-1}-1

следва, че

a_{n-2}\not\equiv0\pmod p

a_{n-2}^{n-1}\equiv1\pmod p.

Понеже

n\equiv0\pmod{p-1}

, получаваме

a_{n-2}^n\equiv1\pmod p

, а след деление на предишното сравнение -

a_{n-2}\equiv1\pmod p

. Сега лемата за повдигане на показателя дава

\nu_p(a_{n-1})=\nu_p(a_{n-2}^{n-1}-1)=

\nu_p(a_{n-2}-1)+\nu_p(n-1)\ge

1+(k-1)=k.

Значи и в този случай

p^k\mid a_{n-1}

. Двете възможности покриват всички случаи, така че търсеният член съществува.

Отвори задачатаEvan Chen VONVON JMO 2024/3Условие — източник

Задача 4

Пълен запис

Условие

Нека

n\ge3

е цяло число. Роуан и Колин играят върху таблица

n\times n

от квадратчета, като всяко квадратче е оцветено в червено или синьо. Роуан може да размества редовете, а Колин може да размества стълбовете. Оцветяване се нарича подредено, ако са изпълнени двете условия: независимо как Роуан размести редовете, Колин може след това да размести стълбовете така, че да възстанови първоначалното оцветяване; и независимо как Колин размести стълбовете, Роуан може след това да размести редовете така, че да възстанови първоначалното оцветяване. В зависимост от

n

колко са подредените оцветявания?

Решение

Отговорът е

2n!+2

. Първо описваме всички такива оцветявания. Работят изцяло синьото оцветяване и изцяло червеното оцветяване. Работи и всяко оцветяване, в което във всеки ред и във всеки стълб има точно едно червено квадратче; те са

n!

на брой. Също така работят допълненията им, при които във всеки ред и във всеки стълб има точно едно синьо квадратче; те също са

n!

. Остава да докажем, че други няма. Нека

A

е подредено оцветяване и разгледаме произволен стълб

C

в него. Нека

m

е броят на червените квадратчета в

C

. Когато Роуан прилага произволна пермутация

\sigma

на редовете, стълбът

C

се превръща в стълб с произволен избор на

m

червени позиции. По условие всеки такъв стълб трябва вече да се среща някъде в първоначалната таблица, защото Колин може само да пренарежда стълбове. Следователно таблицата трябва да съдържа всички

\binom nm

възможни стълбове с

m

червени квадратчета. Ако

2\le m\le n-2

, тогава

\binom nm\gt{}n

, което е невъзможно, понеже таблицата има само

n

стълба. Значи всеки стълб има

0

1

n-1

или

n

червени квадратчета. Ако за някой стълб

m=1

, всички

n

възможни стълба с едно червено квадратче трябва да присъстват; това дава точно оцветяване с по едно червено квадратче във всеки ред и стълб. Случаят

m=n-1

е неговото допълнение. Остава случаят, в който всеки стълб е едноцветен. Тогава второто условие принуждава всички стълбове да са с един и същ цвят: ако имаше и червен, и син стълб, Колин би могъл да ги размени, а разместване на редовете не променя едноцветните стълбове и не може да върне таблицата. Следователно получаваме само изцяло червената или изцяло синята таблица. Така общият брой е

2n!+2

Отвори задачатаEvan Chen VONVON JMO 2024/4Условие — източник

Задача 5

Пълен запис

Условие

Да се реши над

\mathbb R

функционалното уравнение

f(x^2-y)+2yf(x)=f(f(x))+f(y)

Решение

Отговорът е

f(x)\equiv x^2,\qquad f(x)\equiv0,\qquad f(x)\equiv -x^2.

Лесно се проверява, че и трите функции работят. Нека

P(x,y)

означава даденото твърдение. От

P(1,1/2)

получаваме

f(1)=f(f(1))

, а от

P(1,0)

получаваме

f(1)=f(f(1))+f(0)

, следователно

f(0)=0

. После

P(0,y)

дава

f(-y)=f(y)

, тоест

f

е четна. Сега сравняваме

P(x,x^2/2)

P(x,0)

. Те дават основната връзка

x^2f(x)=f(x^2)=f(f(x)).

Ще докажем, че за всяко

x

имаме

f(x)\in\{-x^2,0,x^2\}

. Ако общата стойност

f(f(x))=f(x^2)

е нула, тогава

x^2f(x)=0

, откъдето

f(x)=0

за

x\ne0

, а при

x=0

вече знаем същото. Ако тази обща стойност не е нула, прилагаме следното следствие на основната връзка: от

f(a)=f(b)\ne0

следва

a^2=b^2

, защото

a^2f(a)=f(f(a))=f(f(b))=b^2f(b)

. Слагайки

a=f(x)

b=x^2

, получаваме

f(x)^2=x^4

, тоест

f(x)=\pm x^2

. Така твърдението е доказано. Остава да различим трите възможности глобално. Понеже

f

е четна, ако

f

е решение, то и

-f

е решение; затова случаят

f(1)=-1

е аналогичен на случая

f(1)=1

. Нека първо

f(1)=1

. От

P(1,y)

следва

f(1-y)+(2y-1)=f(y).

За всяко

y

двете стойности

f(1-y)

f(y)

са съответно измежду

\pm(1-y)^2,0

\pm y^2,0

. От деветте възможни полиномиални равенства само

(1-y)^2+(2y-1)=y^2

е тъждество. Следователно за всички достатъчно големи

y

задължително

f(y)=y^2

. За произволно

z\gt{}0

избираме

x,y

достатъчно големи така, че

x^2-y=z

. Тогава в

P(x,y)

вече знаем

f(x)=x^2

f(y)=y^2

f(f(x))=f(x^2)=x^4

, откъдето

f(z)+2yx^2=x^4+y^2,

тоест

f(z)=z^2

. Понеже

f

е четна и

f(0)=0

, получаваме

f(x)=x^2

за всички реални

x

. Случаят

f(1)=-1

дава аналогично

f(x)=-x^2

. Ако

f(1)=0

, тогава от

P(1,y)

следва

f(1-y)=f(y)

. При

|1-y|\ne |y|

това е възможно само ако

f(y)=0

, защото ненулева обща стойност би принудила

(1-y)^2=y^2

. Остава само

y=1/2

; от

P(2,7/2)

получаваме

f(1/2)=0

. Следователно в този случай

f\equiv0

. Това завършва решението.

Отвори задачатаEvan Chen VONVON JMO 2024/5Условие — източник

2025

5 задачи

Задача 1

Пълен запис

Условие

Да се докаже, че ако

f:\mathbb Z\to\mathbb Z

е произволна функция, то има безкрайно много цели числа

c

, за които функцията

g(x)=f(x)+cx

не е биекция.

Решение

Да допуснем противното. Тогава съществува крайно множество

S

от лоши стойности на

c

, такова че

f(x)+cx

е биекция за всяко

c\notin S

. Първото наблюдение е, че всяка последователна разлика на стойности на

f

трябва да е лоша. Наистина, ако вземем

c=f(t)-f(t+1),

то функцията

x\mapsto f(x)+cx

приема една и съща стойност при

x=t

и при

x=t+1

, защото

f(t)+ct=f(t+1)+c(t+1).

Следователно тя не може да бъде инективна, а значи този

c

принадлежи на

S

. Значи всички числа

f(0)-f(1),\ f(1)-f(2),\ f(2)-f(3),\ldots

са в крайното множество

S

. Избираме цяло число

M

така, че

M\gt{}|s|

за всяко

s\in S

. Тогава

M+100\notin S

, така че по допускане функцията

h(x)=f(x)+(M+100)x

трябва да е биекция. Но за всяко цяло

x

имаме

h(x+1)-h(x)=f(x+1)-f(x)+M+100.

Понеже

f(x)-f(x+1)\in S

, получаваме

f(x+1)-f(x)\gt{}-M

, а значи

h(x+1)-h(x)\gt{}100

. Следователно

h

е строго растяща и прескача цели интервали от цели числа между съседните си стойности; в частност не е сюрективна върху

\mathbb Z

. Това противоречи на предположението, че

h

е биекция. Следователно лошите стойности на

c

са безкрайно много.

Отвори задачатаEvan Chen VONVON JMO 2025/1Условие — източник

Задача 2

Пълен запис

Условие

Нека

k

d

са фиксирани положителни цели числа. Да се докаже, че за всяко достатъчно голямо нечетно положително цяло число

n

всички цифри в записа на

n^k

в бройна система с основа

2n

са по-големи от

d

Решение

Нека

1\le\ell\le k

. Ще разгледаме най-десните

\ell

цифри на

n^k

в основа

2n

, тоест остатъка

r_\ell

на

n^k

при деление на

(2n)^\ell

. Твърдим, че съществува нечетно цяло число

c_\ell

1\le c_\ell\le 2^\ell-1

такова, че

r_\ell=c_\ell n^\ell.

Действително остатъкът

r_\ell

е кратен на

n^\ell

, а след деление на

n^\ell

трябва да изберем клас по модул

2^\ell

. Понеже

n

е нечетно, китайската теорема за остатъците дава точно класа

c_\ell\equiv n^{k-\ell}\pmod{2^\ell},

който е нечетен. Сега ще покажем, че прагът

n\ge(d+1)2^{k-1}

е достатъчен. При такова

n

числото

n^k

има точно

k

цифри в основа

2n

, защото

(2n)^{k-1}\le n^k\lt{}(2n)^k.

За всяко

\ell=1,2,\ldots,k

имаме

r_\ell=c_\ell n^\ell\ge n^\ell\ge

(d+1)2^{\ell-1}n^{\ell-1}=(d+1)(2n)^{\ell-1}.

Но

\ell

-тата цифра отдясно е цялата част на

r_\ell/(2n)^{\ell-1}

, следователно тя е поне

d+1

. Това важи за всички

k

цифри на

n^k

, така че всяка от тях е по-голяма от

d

Отвори задачатаEvan Chen VONVON JMO 2025/2Условие — източник

Задача 3

Пълен запис

Условие

Нека

m

n

са положителни цели числа, а

R

е правоъгълна дъска

2m\times2n

от единични квадратчета. Домино е правоъгълник

1\times2

или

2\times1

. Стълбичен път е път от долния ляв ъгъл на

R

до горния десен ъгъл на

R

, съставен от точно

2m+2n

страни на квадратчета и движещ се само нагоре и надясно. В зависимост от

m

n

да се намери броят на стълбичните пътища, които разделят

R

на две подмножества от квадратчета, всяко от които може да бъде покрито с домина.

Решение

Отговорът е

\binom{m+n}{m}^2.

Оцветяваме дъската шахматно. За област от квадратчета, която може да се покрие с домина, е необходимо броят на черните и белите квадратчета в нея да е еднакъв. За стълбичните области, които се получават под такъв път, това условие е и достатъчно. Доказателството е индукция по броя квадратчета. Ако стълбицата не е празна и е балансирана, то поне една от следните локални операции е възможна: последните две колони имат еднаква височина и се покриват заедно; две съседни колони се различават по височина с поне две и се премахва горна лента от двойки квадратчета над по-ниската част; първите две редици имат еднаква дължина и се покриват заедно; или аналогична хоризонтална лента се премахва при две съседни редици с разлика поне две. Всяка операция покрива домино-покриваема част и оставя отново балансирана стълбица. Ако никоя операция не е възможна, височините трябва да са

1,2,\ldots,t

, а такава стълбица не е балансирана, освен при

t=0

. Това доказва критерия. Следователно търсим точно пътищата, за които областта под пътя има равен брой черни и бели квадратчета; понеже цялата дъска

2m\times2n

е балансирана, тогава и другата област е балансирана. Нека височините на колоните под пътя са

0\le h_1\le h_2\le\cdots\le h_{2n}\le2m.

Ако долното ляво квадратче е черно, тогава колона

i

допринася излишък от един черен квадрат точно когато

h_i

е нечетно и

i

е нечетно, и излишък от един бял квадрат точно когато

h_i

е нечетно и

i

е четно. Значи стълбицата е балансирана точно когато сред индексите

i

с нечетно

h_i

има еднакво много четни и нечетни. Поставяме

t_i=h_i+i.

Тогава

1\le t_1\lt{}t_2\lt{}\cdots\lt{}t_{2n}\le2m+2n,

и условието за баланс става: множеството

\{t_1,t_2,\ldots,t_{2n}\}

има еднакво много четни и нечетни елементи. В интервала от

1

до

2m+2n

има

m+n

четни и

m+n

нечетни числа. Трябва да изберем

n

от четните и

n

от нечетните, затова броят е

\binom{m+n}{n}^2=\binom{m+n}{m}^2.

Отвори задачатаEvan Chen VONVON JMO 2025/3Условие — източник

Задача 4

Пълен запис

Условие

Нека

n

е положително цяло число и нека

a_0\ge a_1\ge\cdots\ge a_n\ge0

са цели числа. Да се докаже, че

\sum_{i=0}^n i\binom{a_i}{2}\le\frac12\binom{a_0+a_1+\cdots+a_n}{2}.

Решение

Ще докажем твърдението с индукция по

n

, като случаят

n=0

е празен. Нека

A=a_0+a_1+\cdots+a_{n-1}.

По индукционното предположение за първите

n

члена имаме

\sum_{i=0}^{n-1}i\binom{a_i}{2}\le\frac12\binom{A}{2}.

Следователно е достатъчно да докажем, че добавянето на последния член не увеличава лявата страна с повече от позволеното увеличение на дясната страна, тоест

n\binom{a_n}{2}\le\frac12\left(\binom{A+a_n}{2}-\binom A2\right).

Умножаваме по

2

и разкриваме скобите; това е равносилно на

2n(a_n^2-a_n)\le a_n^2+a_n(2A-1).

След прехвърляне на всички членове вдясно получаваме

0\le2a_n(A-na_n)+a_n(a_n+2n-1).

Последното е очевидно, защото

a_0,a_1,\ldots,a_{n-1}\ge a_n

, следователно

A\ge na_n

, а освен това

a_n\ge0

a_n+2n-1\ge0

. Индукцията е завършена.

Отвори задачатаEvan Chen VONVON JMO 2025/4Условие — източник

Задача 6

Пълен запис

Условие

Нека

S

е множество от цели числа със следните свойства:

\{1,2,\ldots,2025\}\subseteq S

; ако

a,b\in S

\gcd(a,b)=1

, то

ab\in S

; ако

s+1

е съставно за някое

s\in S

, тогава всички положителни делители на

s+1

са в

S

. Да се докаже, че

S

съдържа всички положителни цели числа.

Решение

Ще докажем с индукция по

N

, че

\{1,2,\ldots,N\}\subseteq S

. Началото

N\le2025

е дадено. Нека вече всички положителни цели числа до

N

са в

S

и искаме да докажем, че

N+1\in S

. Ако

N+1

е съставно, тогава

N\in S

и третото условие, приложено към

s=N

, директно дава

N+1\in S

. Остава случаят

N+1=p

, където

p\gt{}2025

е просто число. Ще наричаме едно число добро, ако всяка проста степен в каноничното му разлагане е по-малка от

p

. По индукционното предположение всички тези прости степени са в

S

, а понеже са две по две взаимно прости, второто условие показва, че всяко добро число е в

S

. Разглеждаме три случая. Първо, нека нито

p-1

, нито

p+1

е степен на

2

. Тогава

s=p^2-1=(p-1)(p+1)

е добро: всяка нечетна проста степен в разлагането му дели точно едно от

p-1

p+1

, а най-голямата степен на

2

, която го дели, също е по-малка от

p

, защото единият от двата съседни четни множителя има само един множител

2

, а другият не е чиста степен на

2

. Следователно

s\in S

, а понеже

s+1=p^2

е съставно, третото условие дава

p\in S

. Второ, нека

p+1

е степен на

2

, тоест

p=2^q-1

. За

p\gt{}2025

можем да приемем, че

q\ge11

е нечетно. Числото

s_0=2^{q+1}-1=\left(2^{(q+1)/2}-1\right)\left(2^{(q+1)/2}+1\right)

е добро, защото двата му множителя са взаимно прости и по-малки от

p

. Значи

s_0\in S

, а от

s_0+1=2^{q+1}

получаваме

2^{q+1}\in S

. Сега в

p^2-1=(p-1)(p+1)

най-голямата степен на

2

е точно

2^{q+1}

, а всички останали прости степени са по-малки от

p

; чрез второто условие заключаваме, че

p^2-1\in S

. Отново

(p^2-1)+1=p^2

е съставно, следователно

p\in S

. Трето, нека

p-1

е степен на

2

. Тогава

p

е просто число на Ферма, така че

p\equiv2\pmod3

. Поставяме

s=2p-1.

Имаме

s\equiv0\pmod3

. Освен това

s

не е степен на

3

: иначе от

p=2^{2^e}+1

бихме получили

2^{2^e+1}+1=3^r,

което за

p\gt{}2025

е изключено от теоремата на Михайлеску, известна и като теоремата на Каталан. Понеже

s\lt{}2p

, всяка проста степен в разлагането на

s

е по-малка от

p

, освен ако самото

s

не е проста степен; последното току-що изключихме. Значи

s

е добро и

s\in S

. Но

s+1=2p

е съставно, така че третото условие дава

p\in S

. Във всички случаи

N+1=p

принадлежи на

S

, което завършва индукцията и доказва, че

S

съдържа всички положителни цели числа.

Отвори задачатаEvan Chen VONVON JMO 2025/6Условие — източник

2026

4 задачи

Задача 1

Пълен запис

Условие

Нека

a,b,c

са различни положителни цели числа, за които

ab+c=c^2

. Да се докаже, че

(a-b)^2\ge4c.

Решение

Ще използваме еквивалентната форма на исканото неравенство. Понеже

ab=c^2-c=c(c-1)

, имаме

(a-b)^2\ge4c\quad\Longleftrightarrow\quad (a+b)^2\ge4ab+4c=4c^2.

Тъй като

a+b

е положително, това е равносилно на

a+b\ge2c.

Остава да докажем последното. Без ограничение можем да приемем

a\gt{}b

. От

ab=c(c-1)

следва, че не може

b\ge c

, защото тогава

ab\gt{}c(c-1)

, а не може и

a\le c-1

, защото тогава

ab\lt{}c(c-1)

. Понеже

a,b,c

са различни, получаваме всъщност

a\gt{}c\gt{}c-1\gt{}b.

Разглеждаме функцията

f(x)=x+\frac{c(c-1)}{x}

за

x\gt{}\sqrt{\vphantom{x^2}c(c-1)}

. Тя е строго растяща, защото

f'(x)=1-\frac{c(c-1)}{x^2}\gt{}0

в този интервал. Понеже

a\gt{}c\gt{}\sqrt{\vphantom{x^2}c(c-1)}

b=c(c-1)/a

, имаме

a+b=f(a)\gt{}f(c)=c+(c-1)=2c-1.

Лявата страна е цяло число, следователно

a+b\ge2c

. Това доказва исканото неравенство.

Отвори задачатаEvan Chen VONVON JMO 2026/1Условие — източник

Задача 3

Пълен запис

Условие

Нека

ABC

е остроъгълен разностранен триъгълник, нито един от ъглите на който не е равен на

60^\circ

. Нека

\omega

е описаната около

ABC

окръжност. Нека

\Delta_B

е равностранният триъгълник с три върха върху

\omega

, единият от които е

B

. Нека

\ell_B

е правата през другите два върха на

\Delta_B

. Аналогично се дефинират

\Delta_C

\ell_C

. Нека

Y

е пресечната точка на

AC

\ell_B

, а

Z

е пресечната точка на

AB

\ell_C

. Да допуснем, че описаната около

AYZ

окръжност пресича

\omega

P\ne A

, правата

BC

пресича

YZ

D

, а правата

PA

пресича

YZ

E

. Да се докаже, че

PE=PD

Решение

Понеже

P

е Микеловата точка на конфигурацията

BZYC

, четириъгълникът

DBZP

е вписан. Следователно

\begin{align*} \angle PDE&=\angle PDZ=\angle PBZ=\angle PBA,\\ \angle DEP&=\angle(YZ,AP). \end{align*}

Затова задачата е решена, ако докажем

\angle PBA=\angle(YZ,AP).\qquad(\star)

Ще докажем

(\star)

с комплексни числа. Нека

\omega=e^{2\pi i/3}

. Понеже

Y

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

a,c

и през

\omega b,\omega^2b

, имаме

\begin{align*} y&=\frac{b^2(a+c)-ac(\omega b+\omega^2b)}{b^2-ac}=\frac{b(ab+bc+ca)}{b^2-ac},\\ z&=\frac{c(ab+bc+ca)}{c^2-ab}. \end{align*}

Сега пресмятаме точката

P

. **Твърдение.** Имаме

p=\frac{ab+bc+ca}{a+b+c}.

**Доказателство.** Забелязваме, че

\frac{p-z}{p-y}=\frac{p-b}{p-c}\iff p=\frac{by-cz}{b+y-c-z}.

Числителят и знаменателят в дясната страна са съответно

\begin{align*} by-cz&=(ab+bc+ca)\left(\frac{b^2}{b^2-ac}-\frac{c^2}{c^2-ab}\right)\\ &=(ab+bc+ca)\frac{a(c^3-b^3)}{(b^2-ac)(c^2-ab)}\\ &=-(ab+bc+ca)\frac{a(b-c)(b^2+bc+c^2)}{(b^2-ac)(c^2-ab)},\\ b+y-c-z&=\frac{(b-c)[(b^2-ac)(c^2-ab)-(ab+bc+ca)^2]}{(b^2-ac)(c^2-ab)}\\ &=\frac{(b-c)[-ab^3-ac^3+a^2bc-a^2b^2-c^2a^2-2abc(a+b+c)]}{(b^2-ac)(c^2-ab)}\\ &=\frac{-a(b-c)[a(b^2+bc+c^2)+b^3+c^3+2bc(b+c)]}{(b^2-ac)(c^2-ab)}\\ &=\frac{-a(b-c)(a+b+c)(b^2+bc+c^2)}{(b^2-ac)(c^2-ab)}. \end{align*}

След деление получаваме твърдението.

\square

Желаното равенство

(\star)

се записва като

\mathbb R\ni\frac{p}{p+a}\div\frac{y-z}{p-a}=\frac{p-a}{p+a}\cdot\frac{p}{y-z}\iff\frac{p}{y-z}\in

i\mathbb R,

тъй като

\frac{p-a}{p+a}

очевидно е чисто имагинерно число при

|a|=|p|=1

. Пресмятаме

\begin{align*} y-z&=(ab+bc+ca)\frac{b(c^2-ab)-c(b^2-ac)}{(b^2-ac)(c^2-ab)}\\ &=(ab+bc+ca)\frac{-(b-c)(bc+ab+ac)}{(b^2-ac)(c^2-ab)}\\ &=-(ab+bc+ca)^2\frac{b-c}{(b^2-ac)(c^2-ab)}. \end{align*}

Следователно

\frac{p}{y-z}=

\frac{(b^2-ac)(c^2-ab)}{(b-c)(a+b+c)(ab+bc+ca)}.

Комплексно спрегнатото число е

\overline{\left(\frac{p}{y-z}\right)}=

\frac{\left(\frac1{b^2}-\frac1{ac}\right)\left(\frac1{c^2}-\frac1{ab}\right)}{\left(\frac1b-\frac1c\right)\cdot\frac{ab+bc+ca}{abc}\cdot\frac{a+b+c}{abc}}=

-\frac{p}{y-z},

както искахме да докажем.

Отвори задачатаEvan Chen VONVON JMO 2026/3Условие — източник

Задача 5

Пълен запис

Условие

Положително цяло число

n

се нарича самотно, ако за всички неотрицателни цели числа

a

b

a+b=n

поне едно от числата

a

b

съдържа цифрата

1

. Да се намери, с доказателство, броят на самотните числа, по-малки от

10^{2026}

Решение

Ще докажем, че едно число е самотно точно когато десетичният му запис има следния вид: цифрата

1

се среща точно веднъж, всички цифри вляво от нея са

0

или

2

, а всички цифри вдясно от нея са

9

. Например

202201999999

е от този вид. Първо нека

n

има този вид. Ако последната цифра е

9

, тогава при всяко представяне

n=a+b

последните цифри на

a

b

се събират до

9

, без пренос към тази позиция. Затова можем да изтрием последната цифра и да приложим същия аргумент към по-късия запис. Повтаряйки, стигаме до случая, в който единствената цифра

1

е последна. Ако вляво има водеща цифра

2

, то или някое от

a

b

вече има цифра

1

в тази позиция, или едното има цифра

2

и можем да изтрием тази еднаква водеща част и да продължим индуктивно. Ако не се появи цифра

1

по-рано, последната позиция задължително дава цифра

1

в едно от двете числа. Следователно всяко число от описания вид е самотно. Сега нека

n

е самотно. Първо, като вземем

b=0

, виждаме, че самото

n

съдържа поне една цифра

1

. Ако

n

съдържа четен брой единици, можем да ги сдвоим отляво надясно и във всяка двойка да построим събиране без цифри

1

чрез блокове от вида

9993+\cdots8

, като всички останали позиции се допълват с нули. Ако броят на единиците е нечетен и поне три, правим същото, но оставяме първата единица да бъде получена като

1+0

, а останалите единици отново се елиминират по двойки чрез заеми и блокове от деветки. И в двата случая получаваме представяне

n=a+b

, в което нито

a

, нито

b

съдържа цифра

1

, противоречие. Значи в

n

има точно една цифра

1

. Остава да ограничим останалите цифри. Ако вдясно от единствената единица има цифра

d\ne9

, тогава можем да използваме заем от тази единица: в междинните позиции поставяме в едното събираемо деветки, а в позицията с

d

избираме цифра

d+1

; при

d=0

вместо това използваме

9998

и цифрата

2

. Така пак получаваме разлагане без цифра

1

, невъзможно за самотно число. Следователно всички цифри вдясно са

9

. Ако вляво от единицата има цифра

e\ne0,2

, вземаме заем през следващите позиции, като използваме блок от деветки, и заменяме

e

e-1

, а единицата с

2

в другото събираемо. Отново получаваме две числа без цифра

1

, противоречие. Значи всяка цифра вляво е

0

или

2

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

2026

цифри. Ако единствената цифра

1

е на

i

-та позиция отляво, то преди нея има

i-1

свободни позиции, всяка с избор

0

или

2

, а след нея всички цифри са

9

. Това дава

2^{i-1}

числа. Следователно общият брой е

\sum_{i=1}^{2026}2^{i-1}=2^{2026}-1.

Отвори задачатаEvan Chen VONVON JMO 2026/5Условие — източник

Задача 6

Пълен запис

Условие

Емили има червен лист хартия. Тя начертава

2026

окръжности върху листа, не задължително с равни радиуси. Избира една от окръжностите и оцветява вътрешността й в черно, след което разрязва листа по обиколките на всички

2026

окръжности. Така тя отделя поне

2

черни парчета и някакъв брой червени парчета. Възможно ли е всички черни парчета да са конгруентни?

Решение

Отговорът е не. Нека

\Gamma

е черната окръжност. За всяка точка във вътрешността на

\Gamma

броим в колко от начертаните

2026

кръга се намира тя. Избираме точка

X

, за която този брой е максимален, и нека

\mathcal P

е черното парче, което съдържа

X

. Ще използваме следното наблюдение: всяка дъга от границата на

\mathcal P

е обърната навън спрямо

\mathcal P

. Наистина, ако някоя гранична дъга беше обърната навътре, тогава веднага от другата й страна щеше да има точка

Y

, която лежи във всички кръгове, съдържащи

X

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

X

. Сега разглеждаме друго черно парче. В графа на съседство между черните парчета има път от

\mathcal P

до него, защото всички те са части на един и същ черен кръг, разрязан от окръжности. Още първата стъпка по такъв път пресича дъга, която е външна за

\mathcal P

, но същата дъга е вътрешна за съседното парче. Следователно това съседно парче има поне една гранична дъга, обърната навътре. Свойството всички гранични дъги да са обърнати навън се запазва при конгруентност на парчета с техните гранични дъги. Но

\mathcal P

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

Отвори задачатаEvan Chen VONVON JMO 2026/6Условие — източник