Evan Chen / USAMO Solution Notes

Задача 1

Пълен запис

Условие

Нека

p

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

s

е цяло число с

0\lt s\lt p

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

m

и

n

с

0\lt m\lt n\lt p

и

\left\{\frac{sm}{p}\right\}\lt\left\{\frac{sn}{p}\right\}\lt\frac{s}{p}

тогава и само тогава, когато

s

не дели

p-1

.

Решение

Условието е равносилно на това остатъците при деление на

p

да удовлетворяват

sm\bmod p\lt sn\bmod p\lt s

. Случаят

s=1

е ясен, затова нека

s\ge2

. За всяко

x\in\{1,2,\ldots,s-1\}

дефинираме

f(x)

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

\{1,2,\ldots,p-1\}

, за което

sf(x)\equiv x\pmod p.

Търсените

m,n

не съществуват точно когато тези прообрази се появяват в строго обратен ред, тоест

f(s-1)\lt f(s-2)\lt\cdots\lt f(1).

Избираме

t

така, че

t\equiv -s^{-1}\pmod p

и

0\lt t\lt p

. Тогава

f(x)\equiv 1+(s-x)t\pmod p,

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

1

и

p-1

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

(1+t)\bmod p\lt(1+2t)\bmod p\lt

\cdots\lt(1+(s-1)t)\bmod p.

Това просто означава, че числата

1+kt

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

p

, докато

k=1,2,\ldots,s-1

. Понеже

0\lt1+t\lt p

, получаваме

1+kt\lt p

за всички тези

k

. Освен това

1+st\equiv0\pmod p

, а от

1+(s-1)t\lt p

и

t\lt p

следва

0\lt1+st\lt2p

. Значи

1+st=p

. И така

m,n

не съществуват точно когато

1+st=p

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

s\mid p-1

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

m,n

съществуват точно когато

s

не дели

p-1

.

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

Задача 2

Пълен запис

Условие

Нека

k\gt0

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

N

като функция от

k

, за което съществува множество от

2k+1

различни положителни цели числа със сума, по-голяма от

N

, но всяко негово

k

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

N/2

.

Решение

Отговорът е

N=k(2k^2+3k+3).

Пример за равенство се дава от

S=\{k^2+1,k^2+2,\ldots,k^2+2k+1\}.

Сумата на всички елементи е

k(2k^2+3k+3)+1

, а сумата на най-големите

k

елемента е точно

N/2

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

N

е достижимо. Остава да докажем, че по-малко

N

е невъзможно. Нека даденото множество е

a_0\lt a_1\lt\cdots\lt a_{2k}.

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

N+1\le a_0+a_1+\cdots+a_{2k}

и

\frac N2\ge a_{k+1}+a_{k+2}+\cdots+a_{2k},

защото това са най-големите

k

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

a_0\ge 1+(a_{k+1}-a_1)+(a_{k+2}-a_2)+\cdots+(a_{2k}-a_k).

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

a_{k+j}-a_j\ge k

за

j=1,2,\ldots,k

. Затова

a_0\ge k^2+1

. Тогава

\frac N2\ge a_{k+1}+\cdots+a_{2k}\ge

(a_0+k+1)+(a_0+k+2)+\cdots+(a_0+2k).

Използвайки

a_0\ge k^2+1

, получаваме

\frac N2\ge k(k^2+1)+\frac{k(3k+1)}2,

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

N\ge k(2k^2+3k+3)

. Това доказва минималността.

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

Задача 3

Пълен запис

Условие

За цяло число

m

нека

p(m)

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

m

. По дефиниция поставяме

p(\pm1)=1

и

p(0)=\infty

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

f

с цели коефициенти, за които редицата

\{p(f(n^2))-2n\}_{n\ge0}

е ограничена отгоре. (В частност това изисква

f(n^2)\ne0

за всяко

n\ge0

.)

Решение

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

f(x)=C\prod_j(4x-a_j^2),

където

C

е ненулево цяло число, а всички

a_j

са нечетни цели числа. Празното произведение е позволено. Първо да проверим, че тези полиноми работят. За цяло

n\ge0

имаме

4n^2-a_j^2=(2n-a_j)(2n+a_j).

Понеже

a_j

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

n

. Всеки прост делител на него дели един от двата линейни множителя и следователно по абсолютна стойност е най-много

2n+|a_j|

. Простите делители на константата

C

са фиксирани. Значи има константа

B

, зависеща само от

f

, такава че

p(f(n^2))\le2n+B

за всички

n

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

f

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

g

. Достатъчно е да покажем, че ако

g

не е от вида

4x-a^2

, то стойностите

p(g(n^2))-2n

са неограничени отгоре. Нека

c

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

p\gt{}c

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

g(n^2)

. За такова

p

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

n

с

0\le n\le (p-1)/2

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

n^2

и

(-n)^2

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

p

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

p

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

n

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

c+1

възможни позиции, тоест да са от вида

(p-1)/2-k

с

0\le k\le c

. Наистина, тогава

0\equiv g\left(\left(\frac{p-1}{2}-k\right)^2\right)\equiv g\left(\left(k+\frac12\right)^2\right)\pmod p.

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

4

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

p

дели едно от крайно много фиксирани цели числа, освен ако някоя от стойностите

g((k+1/2)^2)

не е нула. В този изключителен случай линейният множител

4x-(2k+1)^2

дели

g(x)

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

g

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

g

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

c

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

p

и

n\le (p-1)/2-c

с

p\mid g(n^2)

. Тогава

p(g(n^2))-2n\ge p-2n\ge 2c+1,

което е неограничено, понеже

c

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

f

е от вида

4x-a^2

. Накрая, ако

a

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

4x-a^2

се занулява при

x=(a/2)^2

, което е забранено от условието. Затова всички

a

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

C

.

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

Задача 4

Пълен запис

Условие

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

n

, за които съществуват цяло число

k\ge2

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

a_1,\ldots,a_k

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

a_1+a_2+\cdots+a_k=a_1a_2\cdots a_k=n.

Решение

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

1,2,3,5

. Първо ще докажем, че сред числата

n\le5

работи само

n=4

. Числото

4

наистина работи, защото

2+2=2\cdot2=4

. Нека имаме решение с

n\le5

. Ако

k=2

, то от

a_1+a_2=a_1a_2=n

следва

(a_1-a_2)^2=(a_1+a_2)^2-4a_1a_2=

n^2-4n=(n-2)^2-4.

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

n\ge5

тя лежи строго между квадратите

(n-3)^2

и

(n-2)^2

, а при

n=1,2,3,4

пряката проверка оставя само

n=4

. Значи, за всяко друго решение с

n\le5

трябва да имаме

k\gt{}2

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

\frac{n}{k}=\frac{a_1+\cdots+a_k}{k}\ge (a_1\cdots a_k)^{1/k}=n^{1/k},

откъдето

n\ge k^{k/(k-1)}

. За

k=3

това е

3^{3/2}\gt{}5

, за

k=4

е

4^{4/3}\gt{}5

, а за

k\ge5

е още по-голямо от

5

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

n\le5

, така че малките изключения са точно

1,2,3,5

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

n

. Ако

n\ge6

е четно, вземаме

(a_1,\ldots,a_{n/2})=\left(\frac n2,2,1,\ldots,1\right),

където единиците са

n/2-2

на брой. Сумата и произведението са равни на

n

. Ако

n\ge9

е нечетно, вземаме

(a_1,\ldots,a_{(n-3)/2})=\left(\frac n2,\frac12,4,1,\ldots,1\right),

където единиците са

(n-9)/2

на брой; отново сумата и произведението са

n

. Остава специалният случай

n=7

, за който работи

\left(\frac43,\frac76,\frac92\right),

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

7

.

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

Задача 5

Пълен запис

Условие

Математическа жаба скача по числовата права. Тя започва от

1

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

n

, може да скочи или до

n+1

, или до

n+2^{m_n+1}

, където

2^{m_n}

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

2

, която дели

n

. Да се докаже, че ако

k\ge2

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

i

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

2^i k

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

2^i

.

Решение

Ще мислим за един път като за крайна редица от дължини на скокове

(s_1,s_2,\ldots,s_\ell)

. Ако позициите са

1=x_0,x_1,x_2,\ldots,x_\ell,

то

s_j=x_j-x_{j-1}

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

j

е изпълнено

s_j=1

или

s_j=2^{\nu_2(x_{j-1})+1}

, където

\nu_2(y)

е степента на

2

в разлагането на

y

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

e\gt{}0

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

2^e

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

2^e

. Ако останалият скок има дължина

1

, той винаги е позволен. Ако има дължина по-голяма от

1

, тя е степен на

2

и не се дели на

2^e

, следователно е по-малка от

2^e

. Затова старата стартова точка има

2

-адична валуация, по-малка от

e

, а добавянето или изваждането на кратно на

2^e

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

2^i k

. Ще го съкращаваме до път до

2^i

. Започваме от най-големите дължини на скокове и слизаме надолу: за всяко

e

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

2^e

, които завършват вдясно от

2^i

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

2^e

, текущият край на пътя е поне

2^i

и се дели на

2^{\min(i,e)}

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

e

. При изтриване на скок с дължина

2^e

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

2^i-2^e

; освен това по индукционната хипотеза той е кратен на

2^{\min(i,e)}

, защото го променяме само с кратни на

2^e

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

2^{\min(i,e)}

, което е по-голямо от

2^i-2^e

, е

2^i

. Следователно новият край пак е поне

2^i

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

2^i

, така че крайният пункт е най-много

2^i

. От твърдението той е поне

2^i

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

2^i

. Понеже началният път е завършвал в

2^i k\gt{}2^i

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

2^i k

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

2^i

. Следователно минималният брой скокове до

2^i k

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

2^i

.

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

Задача 6

Пълен запис

Условие

Нека

ABCD

е четириъгълник, а

E

и

F

са точки съответно върху страните

AD

и

BC

, такива че

\frac{AE}{ED}=\frac{BF}{FC}.

Лъчът

FE

пресича лъчите

BA

и

CD

съответно в

S

и

T

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

SAE

,

SBF

,

TCF

и

TDE

минават през една обща точка.

Решение

Нека

M

е точката на Микел на четириъгълника

ABCD

. Тогава

M

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

AD

в отсечката

BC

: в частност тя изпраща

A

в

B

и

D

в

C

. Понеже

E

и

F

делят съответните отсечки в едно и също отношение,

\frac{AE}{ED}=\frac{BF}{FC},

същата спирална подобност изпраща и точката

E

в точката

F

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

M

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

AE

в отсечката

BF

. Тъй като

S,A,B

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

S,E,F

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

M

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

SAE

и

SBF

. Аналогично, от същата спирална подобност имаме, че

D

се изпраща в

C

, а

E

- в

F

. Понеже

T,D,C

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

T,E,F

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

M

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

TDE

и

TCF

. Значи и четирите окръжности

(SAE)

,

(SBF)

,

(TCF)

и

(TDE)

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

M

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

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

2006

11-12

Условие

Условие

Условие

Условие

Условие

Условие