TSTST

Evan Chen / USA TSTST Solutions

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

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

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

Избран клас

11-12

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

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

2022 · 11-12: липсва задача 2, 6, 7
2021 · 11-12: липсва задача 6, 7, 8
2020 · 11-12: липсва задача 5, 6
2019 · 11-12: липсва задача 2, 5
2018 · 11-12: липсва задача 3, 5
2017 · 11-12: липсва задача 5
2016 · 11-12: липсва задача 2
2015 · 11-12: липсва задача 2
2014 · 11-12: липсва задача 2
2013 · 11-12: липсва задача 3, 4
2012 · 11-12: липсва задача 2, 4, 7, 8
2011 · 11-12: липсва задача 2, 3, 4

2011

6 задачи

Задача 1

Пълен запис

Условие

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

f

, дефинирани върху наредени двойки реални числа и приемащи реални стойности, със следното свойство: за всички реални числа

a,b,c

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

f(a,b)

f(b,c)

f(c,a)

е равна на медианата на

a,b,c

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

Решение

Отговорът е

f(x,y)=x\quad\text{за всички }x,y

f(x,y)=y\quad\text{за всички }x,y.

Лесно се проверява, че и двете функции работят. Първо ще докажем основното твърдение от решението на Evan Chen и Andrew He. Нека

a\lt{}b\lt{}c

са произволни. Върху множеството

\{a,b,c\}^2

функцията

f

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

\begin{array}{c|ccc} f & a & b & c \cr \hline a & a & b & \ge c \cr b & \le a & b & \ge c \cr c & \le a & b & c \end{array} \qquad\text{или}\qquad \begin{array}{c|ccc} f & a & b & c \cr \hline a & a & \le a & \le a \cr b & b & b & b \cr c & \ge c & \ge c & c \end{array}.

Наистина, от тройката

(x,x,x)

следва

f(x,x)=x

за всяко

x

. От тройките

(a,a,c)

(a,c,c)

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

f(a,c)

f(c,a)

е поне

c

, а другото е най-много

a

. После от тройката

(a,b,c)

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

f(a,b)

f(b,c)

е равно на

b

; аналогично едно от

f(b,a)

f(c,b)

е равно на

b

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

f(b,a)=b

. Ще получим първата таблица. От тройката

(a,a,b)

следва

f(a,b)\le a

, следователно от предишния абзац

f(b,c)=b

, а после

f(c,b)\ge c

. Накрая, като разгледаме тройката

(c,b,a)

заедно с вече установеното за

f(a,c)

f(c,a)

, получаваме

f(a,c)\le a

f(c,a)\ge c

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

f(a,b)=b

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

x\lt{}y

ще казваме, че двойката има тип I, ако

f(y,x)=y

f(x,y)\le x

, и тип II, ако

f(x,y)=y

f(y,x)\le x

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

f(x,y)=y

f(x,y)\le x

. Ако

x\lt{}y\lt{}z

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

(x,y)

(y,z)

са от тип I, а втората - че и двете са от тип II. Следователно всички двойки реални числа имат един и същ тип. Ако този общ тип е I, то за

x\lt{}y

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

u\lt{}x

и прилагаме първата таблица към

u\lt{}x\lt{}y

; получаваме

f(x,y)=x

, а вече имаме и

f(y,x)=y

. Значи

f(x,y)=x

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

x,y

, а също и за

x=y

. Ако общият тип е II, аналогично получаваме

f(x,y)=y

за всички

x,y

. Така намерихме точно двете функции, посочени в началото.

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

Задача 5

Пълен запис

Условие

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

Решение

Ще използваме езика на графите. Върховете са сираците, а ребрата свързват двойките приятели. Разглеждаме всички максимални клики в този граф. Първо твърдим, че всеки връх участва в най-много две максимални клики. Наистина, нека

v

е приятел с

w_1

w_2

, но

w_1

w_2

не са приятели. Ако

u

е друг приятел на

v

, тогава в тройката

w_1,w_2,u

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

u

е приятел с точно един от

w_1

w_2

. Освен това, ако

u

u'

са приятели на

v

и и двамата са приятели с

w_1

, тогава в тройката

w_1,u,u'

първите две двойки са приятелски, така че и

u,u'

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

w_2

. Значи всички приятели на

v

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

v

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

v

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

v

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

x

y

са върхове от двете клики, съдържащи общото ребро, условието за тройката приятели на единия край на това ребро принуждава

x

y

също да са приятели. Значи всяка двойка приятели има точно един общ родител. Остава любовният триъгълник. Ако деца

a,b,c

са такива, че

a

b

имат един общ родител, а

a

c

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

a

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

b

c

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

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

Задача 6

Пълен запис

Условие

Нека

a,b,c

са реални числа в интервала

[0,1]

, за които

a+b,b+c,c+a\ge1

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

1\le

(1-a)^2+(1-b)^2+(1-c)^2

+\frac{2\sqrt2abc}{\sqrt{\vphantom{x^2}a^2+b^2+c^2}}.

Решение

Ще използваме подхода на Ashwin Sah. От условията следва, че

a,b,c

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

a+b\ge1\ge c

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

k

и за всички

a,b,c

, които са страни на евентуално изроден триъгълник, е вярно

k^2\le

(k-a)^2+(k-b)^2+(k-c)^2

+\frac{2\sqrt2abc}{\sqrt{\vphantom{x^2}a^2+b^2+c^2}}.

Първоначалната задача е случаят

k=1

. Фиксираме

a,b,c

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

k

от вида

2k^2-2(a+b+c)k+C,

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

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

Поставяме

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

Тогава

x,y,z\ge0

a=y+z

b=z+x

c=x+y

. След заместване неравенството се свежда до

(x+y+z)^2\le

x^2+y^2+z^2

+\frac{2(x+y)(y+z)(z+x)}{\sqrt{\vphantom{x^2}x^2+y^2+z^2+xy+yz+zx}}.

След прехвърляне това е еквивалентно на

x^2+y^2+z^2+xy+yz+zx\le

\left(\frac{(x+y)(y+z)(z+x)}{xy+yz+zx}\right)^2.

Нека

t=xy+yz+zx

. Понеже

(x+y)(x+z)=x^2+t

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

t^2(x^2+y^2+z^2+t)\le (x^2+t)(y^2+t)(z^2+t).

То е очевидно след разкриване на скобите: дясната страна съдържа всички членове от лявата и още неотрицателни членове. Това доказва хомогенизираната форма, а с

k=1

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

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

Задача 7

Пълен запис

Условие

Нека

ABC

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

BC

CA

AB

в точките

D,E,F

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

ABC

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

DEF

Решение

Нека

a=BC

b=CA

c=AB

, нека

s=(a+b+c)/2

е полупериметърът, а

R

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

ABC

. Трябва да докажем

EF+FD+DE\ge s.

Ще оценим всяка страна на

DEF

чрез ортогонална проекция. За страната

EF

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

BC

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

AE=AF=s-a.

Затова ориентираната дължина на проекцията на

EF

върху

BC

a-(s-a)(\cos B+\cos C).

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

EF\ge a-(s-a)(\cos B+\cos C).

Прилагаме това циклично и събираме:

\begin{align*} -s+\sum_{\rm cyc} EF &\ge -s+\sum_{\rm cyc}\left(a-(s-a)(\cos B+\cos C)\right)\\ &=s-\sum_{\rm cyc}a\cos A\\ &=\sum_{\rm cyc}a\left(\frac12-\cos A\right)\\ &=R\sum_{\rm cyc}\sin A(1-2\cos A)\\ &=R\sum_{\rm cyc}(\sin A-\sin2A). \end{align*}

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

\frac{\sin2B+\sin2C}{2}=\sin(B+C)\cos(B-C)=\sin A\cos(B-C)\le

\sin A.

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

\sum_{\rm cyc}\sin2A\le\sum_{\rm cyc}\sin A.

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

-s+EF+FD+DE\ge0

, тоест

EF+FD+DE\ge s

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

ABC

2s

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

Задача 8

Пълен запис

Условие

Нека

x_0,x_1,\ldots,x_{n_0-1}

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

d_1,d_2,\ldots,d_k

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

n_0=d_1\gt{}d_2\gt{}\dotsb\gt{}d_k\quad\text{и}\quad \gcd(d_1,d_2,\ldots,d_k)=1.

За всяко цяло число

n\ge n_0

дефинираме

x_n=\left\lfloor\frac{x_{n-d_1}+x_{n-d_2}+\dots+x_{n-d_k}}{k}\right\rfloor.

Да се докаже, че редицата

(x_n)

е константна от някой член нататък.

Решение

Нека началните членове лежат в интервала

[A,B]

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

[A,B]

. Понеже членовете са цели числа, има само краен брой възможни блокове от

n_0

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

T

. Ще разглеждаме индексите по модул

T

. Нека

M

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

x_n=M

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

\frac{x_{n-d_1}+x_{n-d_2}+\dots+x_{n-d_k}}{k}

всички събираеми са най-много

M

. За да може цялата част да бъде

M

, самото средно трябва да е поне

M

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

x_{n-d_i}=M\quad\text{за всички }i=1,2,\ldots,k.

Значи множеството от остатъци

n\pmod T

, за които

x_n=M

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

d_i

. От

\gcd(d_1,d_2,\ldots,d_k)=1

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

d_1,d_2,\ldots,d_k

пораждат цялата група

\mathbb Z/T\mathbb Z

; еквивалентно, чрез теоремата на Безу можем да получим всяка разлика от тях по модул

T

. Понеже поне един остатък има стойност

M

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

d_i

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

T

да имат стойност

M

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

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

Задача 9

Пълен запис

Условие

Нека

n

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

2^n+1

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

2^n

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

Решение

Нека всички обекти, които се срещат в някое от дадените множества, са общо

\ell

на брой. Представяме всяко множество чрез неговия характеристичен вектор в

\mathbb F_2^\ell

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

2^n+1

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

2^\ell\ge2^n+1

, тоест

\ell\ge n+1

. Идентифицираме адитивната група

\mathbb F_2^\ell

с крайното поле

F

2^\ell

елемента. Нека

R\subseteq F

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

B\subseteq F

- множеството от сините. Трябва да докажем, че

|B+R|\ge2^n.

Да допуснем противното. Тогава можем да изберем множество

X\subseteq F

|X|=2^n-1

, което съдържа всички суми

b+r

b\in B

r\in R

. Разглеждаме полинома

P(b,r)=\prod_{x\in X}(b+r-x)\in F[b,r].

За всяко

b\in B

r\in R

имаме

b+r\in X

, така че

P(b,r)=0

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

P

2^n-1

, а

|B|-1+|R|-1=|B|+|R|-2=2^n-1.

Коефициентът пред

b^{|B|-1}r^{|R|-1}

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

(b+r)^{2^n-1}

и е

\binom{2^n-1}{|B|-1}.

По теоремата на Лукас това число е нечетно, следователно е ненулево в поле с характеристика

2

. Сега комбинаторната Nullstellensatz, приложена към множествата

B

R

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

b\in B

r\in R

, за които

P(b,r)\ne0

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

|B+R|\ge2^n

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

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

2012

5 задачи

Задача 1

Пълен запис

Условие

Да се определят всички безкрайни низове от букви със следните свойства: (a) всяка буква е

T

или

S

; (b) ако на позиции

i

j

стои буквата

T

, то на позиция

i+j

стои буквата

S

; (c) има безбройно много цели числа

k

, за които на позиция

2k-1

стои

k

-тата буква

T

Решение

Единственият възможен низ е

T,S,T,S,T,S,\ldots,

тоест буквата

T

стои точно на нечетните позиции. Нека позициите, на които стои

T

, са

a_1\lt{}a_2\lt{}a_3\lt{}\dotsb.

Тогава условието (b) казва, че не съществуват положителни цели числа

i,j,k

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

a_i+a_j=a_k.

А условието (c) казва, че за безбройно много

k

имаме

a_k=2k-1.

Фиксираме такова

k\gt{}1

и поставяме

A_k=\{a_1,a_2,\ldots,a_k\}

. Всички елементи на

A_k

са между

1

2k-1

. Разглеждаме положителните разлики между два елемента на

A_k

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

A_k

: ако

a_i-a_j=a_t\gt{}0

, то

a_j+a_t=a_i

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

a_i+a_j=a_k

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

k

елемента на

A_k

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

2k-1

. Броят на положителните разлики е

(|A_k-A_k|-1)/2

, затова

2k-1\ge |A_k|+\frac{|A_k-A_k|-1}{2}\ge

k+\frac{(2k-1)-1}{2}=2k-1,

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

|A_k-A_k|\ge2|A_k|-1

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

|A_k-A_k|\ge2|A_k|-1

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

A_k

е аритметична прогресия. Понеже

A_k

съдържа

k

положителни цели числа и най-големият му елемент е

2k-1

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

A_k=\{1,3,5,\ldots,2k-1\}.

Такива стойности на

k

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

m

можем да изберем

k\ge m

от тях и да получим

a_m=2m-1

. Значи всички позиции с буква

T

са точно нечетните. Този низ очевидно удовлетворява условията: сборът на две нечетни позиции е четна позиция, а

k

-тата буква

T

е на позиция

2k-1

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

Задача 3

Пълен запис

Условие

Нека

\mathbb N

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

f:\mathbb N\to\mathbb N

е функция, която удовлетворява следните две условия: (a)

f(m)

f(n)

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

m

n

са взаимно прости; (b)

n\le f(n)\le n+2012

за всяко

n

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

n

и всяко просто число

p

, ако

p

дели

f(n)

, то

p

дели

n

Решение

Нека

p_0,p_1,p_2,\ldots

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

i

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

q_i

на

f(p_i)

. Това е възможно, защото

f(p_i)\ge p_i\gt{}1

. От условието следва, че числата

f(p_i)

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

q_i

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

q_i=p_i

за всяко

i

. Да допуснем противното и след преномериране да имаме

q_0\ne p_0

, като изберем

p_1,p_2,\ldots,p_{2012}

по-големи от

2012

. По китайската теорема за остатъците можем да намерим цяло число

m

, такова че за

0\le i\le2012

m+i\equiv0\pmod{q_i},\qquad m\not\equiv0\pmod{p_i}.

Втората система условия е съвместима с първата: ако за някое

i\gt{}0

се случи

q_i=p_i

, тогава първото условие дава

m\equiv-i\not\equiv0\pmod{p_i}

, понеже

p_i\gt{}2012

. Сега

m

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

p_0,p_1,\ldots,p_{2012}

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

f(m)

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

f(p_i)

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

q_0,q_1,\ldots,q_{2012}

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

m\le f(m)\le m+2012

, така че

f(m)=m+i

за някое

i

между

0

2012

. Но тогава

q_i

дели

m+i=f(m)

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

q_i

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

p_i

. Тъй като изборът на прост делител на

f(p_i)

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

f(p_i)

са равни на

p_i

, тоест

f(p_i)

е степен на

p_i

. Накрая нека

p

е просто и

p\nmid n

. Тогава

p

n

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

f(p)

f(n)

са взаимно прости. Но

p

дели

f(p)

, понеже

f(p)

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

p

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

p

не дели

f(n)

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

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

Задача 5

Пълен запис

Условие

Дадено е рационално число

x

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

x_0,x_1,x_2,\ldots

със следните свойства: (a)

x_0=x

; (b) за всяко

n\ge1

имаме или

x_n=2x_{n-1}

, или

x_n=2x_{n-1}+\frac1n

; (c) някой член

x_n

е цяло число.

Решение

Ще записваме избора на всеки ход чрез число

\varepsilon_n\in\{0,1\}

, така че

x_n=2x_{n-1}+\frac{\varepsilon_n}{n}.

Ако сме стигнали до момент

t

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

N\gt{}t

, то

x_N=2^{N-t}x_t+\sum_{j=t+1}^N \varepsilon_j\frac{2^{N-j}}{j}.

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

2

, вземаме само ходове от вида

x_n=2x_{n-1}

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

t

знаменателят на

x_t

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

q=p^e

в своята

p

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

r,m,N

така, че

t\lt{}2^{r+1}q\lt{}2^{r+2}q\lt{}\cdots\lt{}2^{r+m}q\lt{}N.

Зануляваме всички нови

\varepsilon_j

освен евентуално тези при

j_i=2^{r+i}q

1\le i\le m

. Тогава приносът на такъв момент към

x_N

\varepsilon_{j_i}\frac{2^{N-j_i}}{j_i}=\frac{c_i\varepsilon_{j_i}}{q},

където

c_i

е степен на

2

. В частност

c_i\not\equiv0\pmod p

. Привеждаме дробите към общ знаменател, чиято

p

-част е

q

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

p

, само заменя всеки

c_i

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

p

. Следователно можем да избираме добавка от вида

\frac{c_1\varepsilon_{j_1}+\cdots+c_m\varepsilon_{j_m}}{q}.

Когато

m

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

c_i

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

p

. Например това следва от Коши-Давенпорт: сумата на множествата

\{0,c_i\}

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

1

, докато не стане цялото поле

\mathbb Z/p\mathbb Z

. Затова можем да изберем

\varepsilon_{j_i}

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

q

да стане делим на

p

. Така

p

-степента в знаменателя намалява с

1

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

2

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

2

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

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

Задача 6

Пълен запис

Условие

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

x,y,z

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

xyz+xy+yz+zx=x+y+z+1.

Докажете, че

\frac13\left(\sqrt{\vphantom{x^2}\frac{1+x^2}{1+x}}+\sqrt{\vphantom{x^2}\frac{1+y^2}{1+y}}+\sqrt{\vphantom{x^2}\frac{1+z^2}{1+z}}\right)\le

\left(\frac{x+y+z}{3}\right)^{5/8}.

Решение

Нека

s=x+y+z

. Ключовото тъждество е

\frac{x^2+1}{x+1}=\frac{(x+y)(x+z)}{1+x+y+z},

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

(x+1)(y+1)(z+1)

и използване на

xyz+xy+yz+zx=x+y+z+1

се получава

(x^2+1)(y+1)(z+1)=2(x+y)(x+z),

което е точно горната формула. Следователно

\sum_{\mathrm{cyc}}\sqrt{\vphantom{x^2}\frac{1+x^2}{1+x}}=

\sum_{\mathrm{cyc}}\frac{\sqrt{\vphantom{x^2}(x+y)(x+z)}}{\sqrt{\vphantom{x^2}1+s}}.

По неравенството на Коши-Шварц,

\begin{align*} \left(\sum_{\mathrm{cyc}}\frac{\sqrt{\vphantom{x^2}(x+y)(x+z)}}{\sqrt{\vphantom{x^2}1+s}}\right)^2 &\le \frac{\left(\sum_{\mathrm{cyc}}(x+y)\right)\left(\sum_{\mathrm{cyc}}(x+z)\right)}{1+s}\\ &=\frac{4s^2}{1+s}. \end{align*}

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

\frac{4s^2}{1+s}\le 9\left(\frac{s}{3}\right)^{5/4}.

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

1+s

. Получаваме точно

9^4\left(\frac{s}{3}\right)^5(1+s)^4-(4s^2)^4=

s^5(s-3)^2(27s^2+14s+3)\ge

0.

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

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

Задача 9

Пълен запис

Условие

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

S

от

n

променливи. Двоична операция

\times

върху

S

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

(x\times y)\times z=x\times(y\times z)

за всички

x,y,z\in S

и ако

x\times y\in\{x,y\}

за всички

x,y\in S

. При дадена проста операция

\times

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

S

може да се редуцира до един елемент, например

xyz

може да се пресметне като

x\times(y\times z)

. Низ от променливи от

S

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

S

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

\times

. Например

xxx

xx

x

са еквивалентни, но са пълни само когато

n=1

. Нека

T

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

T

. Да се намери броят на елементите на

T

Решение

Отговорът е

(n!)^2.

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

x\times y

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

xx=x,\qquad xyxzx=xyzx.

Първото е непосредствено. Второто се проверява с асоциативността и условието, че всяко произведение избира един от двата си аргумента; еквивалентно, може да се провери по описаната по-горе класификация. Да наречем двоен разноцветен низ конкатенация на два пълни низа с дължина

n

, т.е. конкатенация на две пермутации на елементите на

S

. Такива низове има точно

(n!)^2

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

s

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

s

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

ss

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

s

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

u

, а

uu=u

. След това тъждеството

xyxzx=xyzx

позволява последователно да премахваме излишните повторения, докато във всяка от двете половини остане по едно срещане на всяка променлива. Така стигаме до конкатенация на две пермутации. Остава да видим, че два различни двойни разноцветни низа не са еквивалентни. Нека

R_1

R_2

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

a

b

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

R_1

R_2

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

a

b

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

abab,\qquad abba,\qquad baab,\qquad baba,

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

S

, дефинираме проста операция, при която

a

b

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

a,b

R_1

R_2

показва, че

R_1

R_2

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

(n!)^2

, което е търсеният отговор.

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

2013

5 задачи

Задача 2

Пълен запис

Условие

Крайна редица от цели числа

a_1,a_2,\ldots,a_n

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

x

, такова че

\lfloor kx\rfloor=a_k\qquad\text{за }1\le k\le n.

За дадена регулярна редица

a_1,a_2,\ldots,a_n

казваме, че членът

a_k

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

a_1,a_2,\ldots,a_{k-1},b

е регулярна тогава и само тогава, когато

b=a_k

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

1000

члена.

Решение

Отговорът е

985

. Можем да изместим

x

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

a_1=0

, тоест

0\le x\lt{}1

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

k-1

члена, възможните стойности на

x

образуват полуотворен интервал

A\le x\lt{}B,

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

a_k

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

m/k

, защото тогава стойността на

\lfloor kx\rfloor

може да се смени при преминаване през тази точка. Сега използваме стандартното свойство на редиците на Фарей. Ако в даден момент краищата са съседни дроби

\frac ab\le x\lt{}\frac cd,

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

\frac{a+c}{b+d},

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

k=b+d

. В този момент членът не е принуден; след като изберем от коя страна на медиантата да останем, единият край на интервала се заменя с медиантата. Така броят на непринудените членове е броят на знаменателите, които се появяват в процеса. Започваме със знаменателите

1

1

. Ако текущите знаменатели са

b\le d

, следващият непринуден момент е

b+d

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

b+d

, защото тогава следващата сума е

b+2d

, а не

2b+d

. Следователно оптималната стратегия дава последователни знаменатели

1,2,3,5,8,13,\ldots,

тоест числата на Фибоначи, започвайки от

1,2

. Под

1000

са точно

1,2,3,5,8,13,21,34,55,

89,144,233,377,610,987,

общо

15

числа. Значи във всяка редица има поне

15

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

1000-15=985.

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

Задача 5

Пълен запис

Условие

Нека

p

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

1000p

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

p

Решение

Работим по модул

p

. Избираме произволно

p-1

несвързани триъгълника; това е възможно, понеже графът има много повече от

3(p-1)

върха. Ако някой от тези триъгълници има сума на ребрата

0\pmod p

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

u_i,x_i,v_i

така, че

\ell(u_ix_i)+\ell(x_iv_i)\not\equiv \ell(u_iv_i)\pmod p,

където

\ell(ab)

е означението на реброто

ab

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

0\pmod p

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

A_i=

\{\ell(u_ix_i)+\ell(x_iv_i),\ell(u_iv_i)\}\subseteq\mathbb Z/p\mathbb Z.

Това е множество с два елемента. От Коши-Давенпорт и индукция получаваме

|A_1+A_2+\cdots+A_t|\ge \min\{p,t+1\}

за

1\le t\le p-1

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

A_1+A_2+\cdots+A_{p-1}=\mathbb Z/p\mathbb Z.

Остава само да свържем триъгълниците. Добавяме фиксираните ребра

v_1u_2, v_2u_3, \ldots, v_{p-2}u_{p-1}, v_{p-1}u_1

и нека сумата на техните означения е

K

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

u_i x_i v_i

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

u_iv_i

. Понеже сумите от множествата

A_i

дават всички остатъци, можем да направим избора така, че вътрешната сума да бъде

-K\pmod p

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

0\pmod p

. Това е търсеният цикъл.

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

Задача 6

Пълен запис

Условие

Нека

\mathbb N

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

f:\mathbb N\to\mathbb N

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

f^{abc-a}(abc)+f^{abc-b}(abc)+f^{abc-c}(abc)=

a+b+c

за всички

a,b,c\ge2

. Тук

f^k

означава

k

-кратно прилагане на функцията

f

Решение

Отговорът е

f(n)=n-1\quad\text{за всяко } n\ge3,

като

f(1)

f(2)

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

abc

и спираме в

a,b,c\ge2

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

1

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

f^{t^2-t}(t^2)=t\qquad\text{за всяко }t\ge2.

Нека наречем число

1\le k\le8

добро, ако

f^{t^9-t^k}(t^9)=t^k

за всяко

t\ge2

. От уравнението при

(a,b,c)=(t^3,t^3,t^3)

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

k=3

е добро, а от

(a,b,c)=(t,t,t)

имаме

f^{t^3-t}(t^3)=t

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

k=1

е добро. Сега при

(a,b,c)=(t,t^4,t^4)

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

f^{t^9-t}(t^9)+2f^{t^9-t^4}(t^9)=t+2t^4.

Понеже

k=1

е добро, следва, че

k=4

е добро. При

(a,b,c)=(t^2,t^3,t^4)

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

k=2

е добро. Тогава

f^{t^9-t^2}(t^9)=t^2\quad\text{и}\quad f^{t^9-t}(t^9)=t,

а разликата в броя на итерациите е

t^2-t

. Значи

f^{t^2-t}(t^2)=t

, както твърдяхме. Фиксираме

t

и за

n\lt{}t

поставяме

g_t(n)=f^{t-n}(t)-n.

Ако

a,b\ge2

ab\mid t

ab\lt{}t

, тогава ще покажем, че

g_t(a)+g_t(b)=g_t(ab).

Нека

t=abc

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

f^{t-a}(t)+f^{t-b}(t)+f^{t-c}(t)=a+b+c.

После го прилагаме към тройката

(ab,t,c)

, чието произведение е

t^2

. Получаваме

f^{t^2-ab}(t^2)+f^{t^2-t}(t^2)+f^{t^2-c}(t^2)=ab+t+c.

По лемата средният член е

t

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

f^{t-ab}(t)

f^{t-c}(t)

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

g_t

. Нека сега

a,b\ge2

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

p\gt{}q\gt{}\max\{a,b\}

и поставяме

s=a^p b^q

t=s^2

. Повтаряйки току-що доказаната адитивност, получаваме

p g_t(a)+q g_t(b)=g_t(a^p b^q)=

g_t(s)=f^{s^2-s}(s^2)-s=0,

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

q\mid g_t(a)

p\mid g_t(b)

. Освен това

g_t(a)\gt{}-a

g_t(b)\gt{}-b

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

f

са положителни. Понеже

p,q

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

a,b

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

p g_t(a)+q g_t(b)=0

принуждава

g_t(a)=g_t(b)=0

. В частност за произволно

n\ge2

прилагаме това с

a=n

b=n+1

. Получаваме едновременно

f^{t-n}(t)=n,\qquad f^{t-(n+1)}(t)=n+1

за подходящо

t

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

f

изпраща

n+1

n

, тоест

f(n+1)=n

за всяко

n\ge2

. Това е точно

f(m)=m-1

за всяко

m\ge3

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

Задача 7

Пълен запис

Условие

В една държава има

n

града, означени с

1,2,3,\ldots,n

. Тя иска да построи точно

n-1

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

1

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

1

n

. Нека

T_n

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

n

числото

T_n

се дели на

n

. (b) Докажете, че за всяко четно

n

числото

T_n

се дели на

n/2

Решение

Разполагаме градовете

1,2,\ldots,n

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

\mathbb Z/n\mathbb Z

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

T

. Нека ротацията

g^e

фиксира

T

, и нека

k=\gcd(e,n)

. Тогава ротацията

g^k

също фиксира

T

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

k

, така че

\frac{n}{k}\mid \sum_v \deg(v)=2n-2.

Ако

n

е нечетно, то

\gcd(n,2n-2)=1

. Понеже

n/k

дели и

n

, и

2n-2

, получаваме

n/k=1

, тоест

k=n

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

n

, откъдето

n\mid T_n

. Ако

n

е четно, то

\gcd(n,2n-2)=2

. Същият аргумент дава

n/k\le2

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

2

, а орбитата му има размер поне и всъщност кратен на

n/2

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

n/2

, и

n/2\mid T_n

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

Задача 8

Пълен запис

Условие

Дефинираме функция

f:\mathbb N\to\mathbb N

чрез

f(1)=1

f(n+1)=f(n)+2^{f(n)}

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

n

. Докажете, че числата

f(1),f(2),\ldots,f(3^{2013})

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

3^{2013}

Решение

Ще докажем по индукция по

k\ge1

следното по-силно твърдение: всеки

3^k

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

f

дават различни остатъци по модул

3^k

. За

k=1

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

f

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

3

имаме

2^{f(n)}\equiv -1

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

1,0,2,1,0,2,\ldots

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

k

. Понеже всички

f(n)

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

3^k

последователни стойности, която е пълна по модул

3^k

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

2\cdot3^k

. А степените

2^r

по модул

3^{k+1}

зависят от

r

с период

2\cdot3^k

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

n

имаме

\begin{align*} f(n+3^k)-f(n) &=\sum_{i=0}^{3^k-1}2^{f(n+i)}\\ &\equiv 2^1+2^3+\cdots+2^{2\cdot3^k-1}\pmod{3^{k+1}}\\ &=2\cdot\frac{4^{3^k}-1}{3}. \end{align*}

Нека

C=2\cdot\frac{4^{3^k}-1}{3}.

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

3

-адична валуация,

\nu_3(C)=k.

Значи

C

се дели на

3^k

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

3^{k+1}

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

3^{k+1}

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

3^k

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

3^k

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

C

по модул

3^{k+1}

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

0,C,2C

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

3^k

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

3^{k+1}

. Индукцията е завършена, а при

k=2013

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

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

2014

5 задачи

Задача 1

Пълен запис

Условие

Нека

\leftarrow

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

\texttt{ab}\leftarrow\texttt{cd}\leftarrow\leftarrow\texttt{e}\leftarrow\leftarrow\texttt{f},

получаваме текста

\texttt{faecdb}

. Казваме, че низът

B

е достижим от низ

A

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

\leftarrow

A

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

B

. Така примерът показва, че

\texttt{faecdb}

е достижим от

\texttt{abcdef}

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

A

B

низът

A

е достижим от

B

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

B

е достижим от

A

Решение

Очевидно

A

B

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

A=123\ldots n

, а

B=\sigma(1)\sigma(2)\ldots\sigma(n)

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

A

. Тогава

B

е достижим от

A

точно когато пермутацията

\sigma

избягва шаблона

213

, тоест няма индекси

i\lt{}j\lt{}k

такива, че

\sigma(j)\lt{}\sigma(i)\lt{}\sigma(k).

Необходимостта е ясна: ако първо е изписан символът

i

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

B

индуктивно. След като сме поставили

1,2,\ldots,k

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

k+1

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

k

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

213

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

213

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

213

. Наистина, ако

i\lt{}j\lt{}k

\sigma(j)\lt{}\sigma(i)\lt{}\sigma(k)

, поставяме

i'=\sigma(j),\qquad j'=\sigma(i),\qquad k'=\sigma(k).

Тогава

i'\lt{}j'\lt{}k'

\sigma^{-1}(j')\lt{}\sigma^{-1}(i')\lt{}\sigma^{-1}(k'),

което е същият забранен шаблон за

\sigma^{-1}

. Обратната посока е симетрична. Сега задачата следва веднага. Ако

B

е достижим от

A

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

213

-избягваща пермутация

\sigma

, която казва на коя позиция в

B

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

A

. Ако символите се повтарят, такава пермутация може да не е единствена, но съществува. Понеже

\sigma^{-1}

също избягва

213

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

A

от

B

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

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

Задача 3

Пълен запис

Условие

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

P(x)

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

P(x\sqrt2)=P\left(x+\sqrt{\vphantom{x^2}1-x^2}\right)

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

x

|x|\le1

Решение

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

P(x)=g\left(U\left(\frac{x}{\sqrt2}\right)\right),

където

g\in\mathbb R[x]

, а

U

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

U(\cos\theta)=\cos(8\theta).

Това е полиномът на Чебишев

T_8

. Поставяме

Q(x)=P(x\sqrt2)

. Условието става

Q(\cos\theta)=Q\left(\frac{\cos\theta+\sin\theta}{\sqrt2}\right)=Q(\cos(\theta-45^\circ))

за всяко

0\le\theta\le180^\circ

. Ще наричаме такъв полином

Q

добър. Полиномът

U

е добър, защото смяната

\theta\mapsto\theta-45^\circ

променя

8\theta

360^\circ

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

g(U(x))

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

\deg Q

. Случаят на константен

Q

е очевиден. За неконстантен добър

Q

имаме веригата

\begin{align*} Q(\cos136^\circ)&=Q(\cos91^\circ)=Q(\cos46^\circ)=Q(\cos1^\circ)\\ &=Q(\cos(-44^\circ))=Q(\cos44^\circ)=Q(\cos89^\circ)=Q(\cos134^\circ)=Q(\cos179^\circ). \end{align*}

Тук има осем различни стойности на

x

; двете стойности

\cos(-44^\circ)

\cos44^\circ

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

U(x)-U(\cos1^\circ),

който е от степен

8

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

\widetilde Q(x)=\frac{Q(x)-Q(\cos1^\circ)}{U(x)-U(\cos1^\circ)}

е полином. Освен това

\widetilde Q

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

x=\cos\theta

\cos(\theta-45^\circ)

. Ако

Q

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

8

, и имаме

Q(x)=\bigl(U(x)-U(\cos1^\circ)\bigr)\widetilde Q(x)+Q(\cos1^\circ).

По индукционната хипотеза

\widetilde Q

е полином от

U(x)

, значи и

Q

е полином от

U(x)

. Връщайки

Q(x)=P(x\sqrt2)

, получаваме точно описаните по-горе решения.

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

Задача 4

Пълен запис

Условие

Нека

P(x)

Q(x)

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

P\ne0

, и нека

d=\deg P

. Докажете, че съществуват полиноми

A(x)

B(x)

, не и двата нулеви, такива че

\max\{\deg A,\deg B\}\le \frac d2

P(x)\mid A(x)+Q(x)B(x).

Решение

Нека

V

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

\lfloor d/2\rfloor

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

\begin{align*} V\oplus V&\longrightarrow \mathbb R[x]/(P(x)),\\ (A,B)&\longmapsto A+QB \pmod{P}. \end{align*}

Областта има размерност

2\left(\left\lfloor\frac d2\right\rfloor+1\right),

а пространството

\mathbb R[x]/(P(x))

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

d

, защото всеки остатък по модул

P

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

d

. За всяко цяло

d\ge0

имаме

2\left(\left\lfloor\frac d2\right\rfloor+1\right)\gt{}d.

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

(A,B)

от това ядро. Тогава

A

B

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

\lfloor d/2\rfloor\le d/2

, и

A+QB\equiv0\pmod P,

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

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

Задача 5

Пълен запис

Условие

Да се намери най-голямото число

E

със следното свойство: съществува граф с

60

върха и

E

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

3

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

5

Решение

Отговорът е

E=30^2+2\cdot15^2=6\cdot15^2=1350.

Първо ще докажем горната граница. Твърдим, че графът не може да съдържа

K_5

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

K_5

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

2

-регулярен граф върху

5

върха, тоест цикъл

C_5

. Така в

K_5

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

5

, противоречие. Значи целият граф е

K_5

-свободен. По теоремата на Туран броят на ребрата му е най-много броя на ребрата в пълния

4

-делен граф с равни части по

15

върха, тоест

E\le \binom42\cdot15^2=1350.

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

30

върха и оцветяваме всички ребра между двете групи в червено; това е червен

K_{30,30}

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

15

върха и оцветяваме всички ребра между тези две подгрупи в синьо; така получаваме два сини

K_{15,15}

. Полученият граф има

30\cdot30+2\cdot15\cdot15=1350

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

3

или

5

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

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

Задача 6

Пълен запис

Условие

Нека

a,b,c,d

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

p

е нечетно просто число, което не дели никое от тях. Нека

M

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

ca-db,\quad ca^2-db^2,

\quad ca^3-db^3,\quad ca^4-db^4,\quad\ldots.

За всеки неин член гледаме показателя

\nu_p

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

p

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

M

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

T

, зависещо евентуално от

a,b,c,d,p,M

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

p

дели член на редицата, неговата

p

-адична валуация е точно

T

Решение

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

p

. Условието

p\mid ca^n-db^n

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

\left(\frac ab\right)^n\equiv\frac dc\pmod p,

защото

p

не дели

a,b,c,d

. Следователно, ако има поне едно решение

n=\kappa

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

\kappa,\quad \kappa+\lambda,\quad \kappa+2\lambda,\quad\ldots,

където

\lambda

е редът на

a/b

по модул

p

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

p

-адична валуация

0

\nu_p\left(ca^{\kappa+n\lambda}-db^{\kappa+n\lambda}\right)=

\nu_p\left(\left(\frac{a^\lambda}{b^\lambda}\right)^n-\frac{db^\kappa}{ca^\kappa}\right).

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

p

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

x,y\in\mathbb Q_{\gt{}0}

са такива, че

x\equiv y\equiv1\pmod p

. Ако редицата

\nu_p(x^n-y)

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

m,n

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

d=\nu_p(x^n-y)\lt{}\nu_p(x^m-y)=e.

Тогава

\nu_p(x^m-x^n)=\nu_p\big((x^m-y)-(x^n-y)\big)=d.

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

x\equiv1\pmod p

, следва, че можем да намерим

k

\nu_p(x^k-1)=e;

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

k=p^{e-d}|m-n|

. Записваме

x^k=1+p^e u,\qquad x^m=y+p^e v,

където

u,v\in\mathbb Q

не се делят на

p

в смисъл на

p

-адична валуация. За всяко цяло

r

1\le r\le p-1

разглеждаме

\begin{align*} x^{kr+m}-y&=(1+p^e u)^r(y+p^e v)-y\\ &=p^e(v+yur)+p^{2e}(\cdots). \end{align*}

Понеже

y\equiv1\pmod p

, можем да изберем

r

така, че

v+yur\equiv0\pmod p

. Тогава

\nu_p(x^{kr+m}-y)\ge e+1.

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

M

. Следователно върху индексите, за които

p

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

T

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

2015

5 задачи

Задача 1

Пълен запис

Условие

Нека

a_1,a_2,\ldots,a_n

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

m\lt{}n

е фиксирано положително цяло число. Ще наричаме индекс

k

1\le k\le n

добър, ако съществува

\ell

1\le\ell\le m

, такова че

a_k+a_{k+1}+\dotsb+a_{k+\ell-1}\ge0,

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

n

. Нека

T

е множеството на всички добри индекси. Докажете, че

\sum_{k\in T}a_k\ge0.

Решение

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

n

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

k

\ell

-добър, ако

\ell

е най-малкото число, за което

a_k+a_{k+1}+\cdots+a_{k+\ell-1}\ge0,

и освен това

\ell\le m

. Ако

k

\ell

-добър, тогава индексите

k+1,k+2,\ldots,k+\ell-1

също са добри: за всеки от тях можем да вземем съответната опашка на същия блок, а минималността на

\ell

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

\ell

-добър, и групираме блока

a_k,a_{k+1},\ldots,a_{k+\ell-1}.

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

N

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

N

копия на дадената циклична редица. Прилагаме току-що доказания нецикличен резултат към тази дълга редица. Всички вътрешни копия дават точно същите добри индекси като в цикличната задача; разлика може да се появи само в краищата, където блоковете могат да бъдат отрязани. Затова получаваме неравенство от вида

N\sum_{k\in T}a_k+c_N\ge0,

където грешката

c_N

идва само от краищата. Тя е ограничена независимо от

N

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

a_1,\ldots,a_n

m

. Делим на

N

и пускаме

N

да расте. Получаваме

\sum_{k\in T}a_k\ge0,

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

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

Задача 3

Пълен запис

Условие

Нека

P

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

M

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

P

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

\{p_1,p_2,\ldots,p_k\}

на

M

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

p_1p_2\cdots p_k+1

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

M

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

M=P

Решение

Първо

M

е безкрайно: ако умножим всички известни елементи на

M

и прибавим

1

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

M

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

p\notin M

. Ще наричаме простото число

q\in M

рядко, ако има само краен брой елементи на

M

, които са сравними с

q

по модул

p

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

p

. Нека

C

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

C=1

. Понеже

p\notin M

, имаме

p\nmid C

. Започваме с

a_0=1

. За

k\ge0

разглеждаме простото разлагане на

Ca_k+1.

Всеки негов прост делител принадлежи на

M

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

a_k

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

C

. Освен това никой от тези прости делители не е рядък, защото редките прости вече делят

C

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

Ca_k+1

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

Ca_k+1

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

M

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

p

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

a_{k+1}

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

a_{k+1}

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

M

a_{k+1}\equiv Ca_k+1\pmod p.

Следователно по индукция

a_k\equiv C^k+C^{k-1}+\cdots+1\pmod p.

Понеже

C\not\equiv0\pmod p

, можем да изберем

k

, за което дясната страна е

0

по модул

p

: ако

C\equiv1\pmod p

, вземаме

k=p-1

, а иначе вземаме

k=p-2

, тъй като тогава

1+C+\cdots+C^{p-2}=\frac{C^{p-1}-1}{C-1}\equiv0\pmod p.

Получаваме

p\mid a_k

. Това е невъзможно, защото

a_k

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

M

, а

p\notin M

. Противоречието доказва, че

M=P

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

Задача 4

Пълен запис

Условие

Нека

x,y,z

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

x^4+y^4+z^4+xyz=4.

Докажете, че

x\le2

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

Решение

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

x\le2

. Имаме

\begin{align*} 5&=x^4+y^4+(z^4+1)+xyz\\ &=\frac{3x^4}{4}+\left(\frac{x^4}{4}+y^4\right)+(z^4+1)+xyz\\ &\ge \frac{3x^4}{4}+x^2y^2+2z^2+xyz. \end{align*}

Последните три члена са неотрицателни, защото

x^2y^2+xyz+2z^2

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

xy

z

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

x^4\le20/3\lt{}16

, откъдето

x\lt{}2

, и в частност

x\le2

. Остава да докажем второто неравенство. Ако

(y+z)/2\le0

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

2-x\ge\left(\frac{y+z}{2}\right)^2.

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

2-x\lt{}\left(\frac{y+z}{2}\right)^2,

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

4x+y^2+2yz+z^2\gt{}8.

От неравенствата

x^4+3\ge4x,\qquad \frac{y^4+1}{2}\ge y^2,\qquad \frac{z^4+1}{2}\ge z^2

получаваме

x^4+\frac{y^4+z^4}{2}+2yz+4\gt{}8.

Заместваме

x^4=4-y^4-z^4-xyz

и намираме

-\frac{y^4+z^4}{2}+(2-x)yz\gt{}0.

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

yz\gt{}0

\frac{y^4+z^4}{2yz}\lt{}2-x\lt{}\left(\frac{y+z}{2}\right)^2.

Умножавайки по

4yz\gt{}0

, получаваме

2y^4+2z^4\lt{}yz(y+z)^2=y^3z+2y^2z^2+yz^3.

Това е невъзможно, защото при

yz\gt{}0

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

2y^4-y^3z-2y^2z^2-yz^3+2z^4=

(y-z)^2(2y^2+3yz+2z^2)\ge

0.

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

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

Задача 5

Пълен запис

Условие

Нека

\varphi(n)

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

n

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

n

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

m

, за което уравнението

\varphi(n)=m

има поне

2015

решения за

n

Решение

Ще дадем конструкция с най-малките прости числа. Нека

2=p_1\lt{}p_2\lt{}\cdots\lt{}p_{2015}

са най-малките

2015

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

2015

числа:

\begin{align*} n_1&=(p_1-1)p_2p_3\cdots p_{2015},\\ n_2&=p_1(p_2-1)p_3\cdots p_{2015},\\ &\vdots\\ n_{2015}&=p_1p_2\cdots p_{2014}(p_{2015}-1). \end{align*}

Ще покажем, че всички те имат една и съща стойност на функцията на Ойлер. Фиксираме

i

. Числото

p_i-1

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

p_i

, защото е по-малко от

p_i

. Тези прости делители са сред

p_1,p_2,\ldots,p_{i-1}

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

n_i

са точно сред

p_1,p_2,\ldots,p_{2015}

, като

p_i

не се появява. Използваме мултипликативната формула

\varphi(N)=N\prod_{q\mid N}\left(1-\frac1q\right).

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

p_i-1

вече са сред по-малките

p_j

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

\varphi(n_i)=(p_i-1)\prod_{j\ne i}(p_j-1)=

\prod_{j=1}^{2015}(p_j-1).

Така всички числа

n_1,n_2,\ldots,n_{2015}

са решения на едно и също уравнение

\varphi(n)=m

, където

m=\prod_{j=1}^{2015}(p_j-1).

Остава само да отбележим, че числата

n_i

са различни. Ако

i\lt{}j

, то

p_j

дели

n_i

, но не дели

n_j

: наистина

p_j

не дели

p_j-1

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

n_j

са по-малки от

p_j

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

2015

различни решения, както се искаше.

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

Задача 6

Пълен запис

Условие

Ним-подобна игра се задава по следния начин. Избират се две положителни цели числа

k

n

, както и крайно множество

S

от

k

-орки цели числа (не непременно положителни). В началото на играта на дъската е записана

k

-орката

(n,0,0,\ldots,0)

. Разрешен ход се състои в това да се изтрие записаната

k

-орка

(a_1,a_2,\ldots,a_k)

и да се замени с

(a_1+b_1,a_2+b_2,\ldots,a_k+b_k)

, където

(b_1,b_2,\ldots,b_k)\in S

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

k

S

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

n

е степен на

2

, а иначе вторият играч има печеливша стратегия.

Решение

Ще дадем конструкция с

14

регистъра и

22

хода. Регистрите са

X,Y,\operatorname{Go},S_X^0,S_X,S_X',S_Y^0,

S_Y,S_Y',\operatorname{Cl},A,B,\operatorname{Die},\operatorname{Die}'.

В началото

X=n

, а всички останали регистри са нули. За компактност в таблицата пишем

G=\operatorname{Go}

X_0=S_X^0

X_1=S_X

X_2=S_X'

Y_0=S_Y^0

Y_1=S_Y

Y_2=S_Y'

C=\operatorname{Cl}

D=\operatorname{Die}

D'=\operatorname{Die}'

. Нека

k=14

, а

S

е множеството от следните

22

хода, записани като 14-орки в реда

X,Y,G,X_0,X_1,X_2,Y_0,Y_1,Y_2,C,A,B,D,D'

: Init = (-1,0,1,0,0,0,0,0,0,0,0,1,1,1) Begin = (1,0,-1,1,0,0,0,0,0,0,-1,1,0,0) Sleep = (0,0,0,0,0,0,0,0,0,0,1,-1,0,0) StartX = (0,0,0,-1,1,0,0,0,0,0,-1,1,0,0) WorkX = (-1,0,0,0,-1,1,0,0,0,0,-1,1,0,0) WorkX' = (-1,1,0,0,1,-1,0,0,0,0,-1,1,0,0) DoneX = (0,0,0,0,-1,0,1,0,0,0,-1,1,0,0) WrongX = (-1,0,0,0,0,0,-1,0,0,0,0,-1,0,0) StartY = (0,0,0,0,0,0,-1,1,0,0,-1,1,0,0) WorkY = (0,-1,0,0,0,0,0,-1,1,0,-1,1,0,0) WorkY' = (1,-1,0,0,0,0,0,1,-1,0,-1,1,0,0) DoneY = (0,0,0,1,0,0,0,-1,0,0,-1,1,0,0) WrongY = (0,-1,0,-1,0,0,0,0,0,0,0,-1,0,0) ClaimX = (-1,0,0,-1,0,0,0,0,0,1,-1,1,0,0) ClaimY = (0,-1,0,0,0,0,-1,0,0,1,-1,1,0,0) FakeX = (-1,0,0,0,0,0,0,0,0,-1,0,-1,0,0) FakeY = (0,-1,0,0,0,0,0,0,0,-1,0,-1,0,0) Win = (0,0,0,0,0,0,0,0,0,-1,-1,0,0,0) PunA = (0,0,0,0,0,0,0,0,0,0,0,-2,0,0) PunB = (0,0,0,0,0,0,0,0,0,0,-1,-1,0,0) Kill = (0,0,0,0,0,0,0,0,0,0,0,-1,-2,1) Kill' = (0,0,0,0,0,0,0,0,0,0,0,-1,1,-2) Първият играч ще наричаме Алиса, а втория - Боб. Механиката се управлява от броячите

A

B

. След първия ход Алиса играе Init. По-нататък казваме, че играта е в главната част, ако

A+B=1

и никой не е играл Init втори път; във всички други случаи тя е в смъртната част. В главната част на ход на Алиса винаги е

(A,B)=(1,0)

, а на ход на Боб е

(A,B)=(0,1)

. Първо, играч, който играе Init за втори път, губи. В частност губи и играч, който трябва да мести при

A=B=0

. Ако нарушителят е при

A=B=0

, той е принуден да играе Init; другият играч отговаря с Kill, после нарушителят пак е принуден към Init, а другият отговаря с Kill'. Това се повтаря, докато

X

стане отрицателно. Ако Алиса играе Init при

(A,B)=(1,0)

, Боб я наказва с PunB и стига до същия сценарий; ако Боб играе Init при

(A,B)=(0,1)

, Алиса го наказва с PunA. Следователно рационалната игра избягва смъртната част. Вторият ход е Sleep на Боб, после Алиса играе Begin (което възстановява стойността

n

X

), а Боб пак играе Sleep. В главната част състоянието е един от регистрите

S_X^0,S_X,S_X',S_Y^0,S_Y,S_Y'

или

\operatorname{Cl}

да е равен на

1

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

X

-фази и

Y

-фази. Да разгледаме

X

-фаза, започваща при

(X,Y)=(x,0)

x\gt{}1

. Алиса може да я завърши без загуба тогава и само тогава, когато

x

е четно; в този случай започва

Y

-фаза с

(X,Y)=(0,x/2)

. Наистина, при

x\gt{}1

ходът ClaimX е лош, защото Боб отговаря с FakeX и печели. Чрез редуване на WorkX и WorkX' Алиса намалява

X

2

и увеличава

Y

1

; Боб през това време има само Sleep. Накрая тя трябва да спре с DoneX. Ако тогава

X\ne0

, Боб печели с WrongX; ако

X=0

, той може само да играе Sleep. Аналогично твърдение важи за

Y

-фазите. Така всеки успешен цикъл дели текущото положително число на

2

и го прехвърля между

X

Y

. Ако

n

не е степен на

2

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

1

и Алиса губи. Ако

n=2^m

, Алиса последователно стига до

(X,Y)=(0,2^{m-1}),(2^{m-2},0),\ldots

и накрая до

(1,0)

или

(0,1)

. Тогава тя играе съответно ClaimX или ClaimY и влиза в състояние

\operatorname{Cl}

. Боб вече не може да играе FakeX или FakeY, затова играе Sleep, а Алиса печели с Win. Това доказва, че първият играч печели точно когато

n

е степен на

2

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

2016

4 задачи

Задача 1

Пълен запис

Условие

Нека

A=A(x,y)

B=B(x,y)

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

A(x,y)/B(x,y)

е полином по

x

за безбройно много стойности на

y

и е полином по

y

за безбройно много стойности на

x

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

B

дели

A

, т.е. съществува полином

C

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

A=B\cdot C.

Решение

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

A/B

може да се запише като полином по

x

, чиито коефициенти са рационални функции по

y

. Работим в пръстена

(\mathbb R(y))[x]

, тоест разглеждаме полиноми по

x

с коефициенти от полето

\mathbb R(y)

. По алгоритъма за деление имаме

A=QB+R,\qquad Q,R\in(\mathbb R(y))[x],

където

\deg_x R\lt{}\deg_x B

. Твърдим, че

R\equiv0

. По условие за безбройно много стойности

y_0

полиномът

B(x,y_0)

дели

A(x,y_0)

\mathbb R[x]

. За всички такива

y_0

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

Q,R

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

\deg_x R(x,y_0)\lt{}\deg_x B(x,y_0)

се запазва. Но от

A=QB+R

следва, че

B(x,y_0)

дели

R(x,y_0)

. Това е възможно при горното степенно неравенство само ако

R(x,y_0)\equiv0

. Така получаваме безбройно много стойности

y_0

, за които всеки коефициент на

R

се занулява. Следователно всички тези рационални функции са нулеви, т.е.

R\equiv0

. Значи

\frac AB=Q(x,y)

като полином по

x

с рационални функции по

y

. След умножение с общ знаменател можем да запишем

\frac AB=\frac{F(x,y)}{M(y)},

където

F\in\mathbb R[x,y]

M\in\mathbb R[y]

. Повтаряйки същия аргумент, но с разменени роли на

x

y

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

\frac AB=\frac{G(x,y)}{N(x)},

където

G\in\mathbb R[x,y]

N\in\mathbb R[x]

. Съкращаваме дробите така, че

\gcd(F,M)=1

\gcd(G,N)=1

\mathbb R[x,y]

. Освен това

\gcd(M,N)=1

, защото единият полином зависи само от

y

, а другият само от

x

. От равенството

F(x,y)N(x)=G(x,y)M(y)

следва, че

M

дели

F\cdot N

. Понеже

M

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

F

и с

N

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

M

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

A/B

всъщност е полином от

\mathbb R[x,y]

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

B

дели

A

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

Задача 3

Пълен запис

Условие

Съществува ли неконстантен полином

Q(x)

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

n\gt{}2

числата

Q(0),Q(1),Q(2),\ldots,Q(n-1)

да дават най-много

0.499n

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

n

Решение

Да, такъв полином съществува. Ще покажем, че

Q(x)=420(x^2-1)^2

работи. Достатъчно е да проверим случая

n=4

и случая, когато

n=p

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

d

на

n

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

d

идва от най-много

n/d

остатъка по модул

n

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

n

е най-много

0.499n

. Всяко

n\gt{}2

има делител

4

или нечетен прост делител. При

n=4

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

420\equiv0\pmod4

. Нека сега

p

е нечетно просто число. Ако

p

дели

420

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

p

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

p\ge11

и разглеждаме

F(x)=(x^2-1)^2,

защото умножаването по ненулевата константа

420

не променя броя на стойностите по модул

p

. Първо ще използваме следния факт: за поне

\frac12(p-3)

стойности на

a

числото

1-a^2

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

p

. Действително, ако

k\ne0

k^2\ne-1

, тогава

a=\frac{1-k^2}{1+k^2}

дава

1-a^2=\frac{4k^2}{(1+k^2)^2},

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

k^2

дават различни

a

, а те са поне

\frac12(p-3)

. Стойностите на

F

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

\frac12(p+1)

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

t

полезен, ако нито

1-t

, нито

1+t

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

p

. Ако

t

е полезен, тогава

t^2

не е стойност на

F

, защото равенството

(x^2-1)^2=t^2

би дало

x^2=1+t

или

x^2=1-t

. Нека

\chi(u)=\left(\frac{u}{p}\right)

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

N

е броят на полезните остатъци

t

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

t

по модул

p

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

\begin{align*} N&\ge \frac14\sum_t\left(1-\chi(1-t)\right)\left(1-\chi(1+t)\right)-1\\ &=\frac14\left(p+\sum_t\chi(1-t^2)\right)-1. \end{align*}

В последната сума има поне

\frac12(p-3)

члена, равни на

+1

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

t=\pm1

са

0

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

-1

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

N\ge\frac14(p-5).

Понеже полезните остатъци

t

-t

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

t^2

, от образа на

F

липсват поне

N/2

квадратични остатъка. Значи броят на стойностите на

F

по модул

p

е най-много

\frac12(p+1)-\frac12N\le\frac38(p+3).

За

p\ge11

имаме

\frac38(p+3)\lt{}0.499p

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

Q(x)=420(x^2-1)^2

удовлетворява условието за всяко

n\gt{}2

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

Задача 4

Пълен запис

Условие

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

n

k

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

\varphi^k(n)=1

, то

n\le3^k

. Тук

\varphi^k

означава

k

последователни приложения на функцията на Ойлер.

Решение

Основната идея е да следим колко степени на

2

неизбежно ще се появят при многократно прилагане на

\varphi

. Дефинираме адитивна тежест

w

върху положителните цели числа чрез

w(ab)=w(a)+w(b),\qquad w(2)=1,

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

p

полагаме

w(p)=w(p-1).

Тази дефиниция е коректна, защото при

p\gt{}2

числото

p-1

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

p

, така че можем да дефинираме

w

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

n=\prod p^{e_p}

. От формулата

\varphi(n)=\prod_{p\mid n}p^{e_p-1}(p-1)

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

n

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

w(\varphi(n))=w(n)-1

, а ако

n

е нечетно и

n\gt{}1

, тогава

w(\varphi(n))=w(n)

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

\varphi

намалява

w

с най-много

1

. Понеже

w(1)=0

\varphi^k(n)=1

, непременно

k\ge w(n).

Остава да свържем

w(n)

с размера на

n

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

w(q)\ge\log_3 q

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

q

. За

q=2

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

w(2)=1\gt{}\log_3 2

. Нека

q\gt{}2

и да използваме силна индукция. Тогава

w(q)=w(q-1)=w(2)+w\left(\frac{q-1}{2}\right)\ge1+\log_3\left(\frac{q-1}{2}\right).

А понеже

q\ge3

, имаме

1+\log_3\left(\frac{q-1}{2}\right)=\log_3\left(\frac{3(q-1)}{2}\right)\ge\log_3 q.

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

n

w(n)\ge\log_3 n.

Комбинирайки това с

k\ge w(n)

, получаваме

k\ge\log_3 n

, т.е.

n\le3^k

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

Задача 5

Пълен запис

Условие

В координатната равнина са дадени краен брой стени, които са непресичащи се отсечки, никоя от които не е успоредна на някоя от координатните оси. Булдозер започва от произволна точка и се движи в посока на положителната

x

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

Решение

Ще казваме, че стена

v

е над стена

w

, ако някоя точка от

v

се намира точно над някоя точка от

w

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

n\ge3

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

P_i,Q_i

за

i=1,2,\ldots,n

(индексите се вземат по модул

n

), така че

Q_i

да е точно над

P_{i+1}

за всяко

i

, отсечката

Q_iP_{i+1}

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

P_iQ_i

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

2n

върха, която няма самопресичания. Нека

Q_iP_{i+1}

е най-лявата вертикална отсечка от тази начупена линия, а

Q_jP_{j+1}

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

P_{i+1}

до

Q_j

, както и път от

P_{j+1}

до

Q_i

. Понеже тези два пътя трябва да преминат от лявата вертикална отсечка към дясната и обратно, те неизбежно се пресичат. Това противоречи на липсата на самопресичания и доказва съществуването на най-ниска стена. По същия начин съществува и най-висока стена. Ако след някакъв момент булдозерът се движи нагоре безкрайно, той никога не може да удари долната страна на най-ниската стена. Ако след някакъв момент се движи надолу безкрайно, той никога не може да удари горната страна на най-високата стена. Остава само да отбележим, че хоризонтален последен лъч се покрива със същия аргумент след размяна на ролите на координатните оси: тогава съществуват най-лява и най-дясна стена, и булдозерът пропуска съответната им странична страна. Ако пък движението приключи с последен удар преди да бъдат ударени всички страни, твърдението е вече ясно. Следователно в никой случай не може да бъдат ударени и двете страни на всяка стена.

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

2017

4 задачи

Задача 2

Пълен запис

Условие

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

k

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

k

подниза, равни на думата на Ана. Тук подниз се получава чрез изтриване на някои букви, без да се променя редът на останалите. Ана печели, ако може да даде такава дума; иначе губи. Например, ако Ана избере думата

\text{TST}

, а Банана избере

k=4

, Ана може да даде думата

\text{TSTST}

, която има

4

подниза, равни на

\text{TST}

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

k

, избрана от Банана?

Решение

Разбиваме думата на Ана на блокове: блок е максимален непрекъснат участък от еднакви букви. Например думата

\text{AABBBCAAA}

има четири блока:

\text{AA},\quad \text{BBB},\quad \text{C},\quad \text{AAA}.

Нека избраната от Ана дума е

A=A_1A_2\cdots A_m=\underbrace{a_1\cdots a_1}_{x_1}\underbrace{a_2\cdots a_2}_{x_2}\cdots\underbrace{a_m\cdots a_m}_{x_m},

където съседните букви

a_i

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

A

, копие на

A

. Задачата е да разберем кога Ана може да построи дума с точно

k

такива копия за всяко

k\ge0

. Първо, ако някой блок има дължина

1

, Ана винаги печели. Нека

x_i=1

. За дадено

k\ge1

тя взема думата, получена от

A

, като замени единичната буква

a_i

с блок от

k

копия на

a_i

W=A_1\cdots A_{i-1}\underbrace{a_i\cdots a_i}_{k}A_{i+1}\cdots A_m.

Има поне

k

копия: избираме коя от

k

-те букви в новия блок да бъде използвана за единичния блок

A_i

, а всички останали букви са принудени. Това са и всички копия. Наистина, в произволен подниз, равен на

A

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

A_i

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

A_1\cdots A_{i-1}

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

A_{i+1}\cdots A_m

, защото тогава няма да остане място за предходните или следващите блокове в правилния ред. Следователно тя трябва да се избере от новия

i

-ти блок, а всички останали копия на

a_i

в този блок трябва да бъдат изтрити. Получаваме точно

k

копия. За

k=0

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

A

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

2

, Банана може да избере

k=2

и Ана ще загуби. Ще покажем по-силно: ако някоя дума

W

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

A

, тогава има поне три копия. Нека

W=w_1w_2\cdots w_n

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

A_p

с дължина

\ell\ge2

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

i_1\lt{}i_2\lt{}\cdots\lt{}i_\ell

за този блок, а второто използва позиции

j_1\lt{}j_2\lt{}\cdots\lt{}j_\ell.

В интервала от

\min(i_1,j_1)

до

\max(i_\ell,j_\ell)

има поне

\ell+1

срещания на буквата

a_p

; иначе двете

\ell

-орки позиции биха съвпадали. Освен това всеки избор на

\ell

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

A

, като използваме същите избори за блоковете преди и след

A_p

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

\binom{\ell+1}{\ell}=\ell+1\ge3.

Значи дума с точно две копия не съществува, когато всички

x_i\ge2

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

1

: тогава тя повтаря тази изолирана буква

k

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

2

, Банана избира

k=2

, а такава дума не може да бъде построена.

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

Задача 3

Пълен запис

Условие

Разглеждаме представянията на

x^2-cx+1=\frac{f(x)}{g(x)},

където

f

g

са ненулеви полиноми с неотрицателни реални коефициенти. За всяко

c\gt{}0

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

f

или докажете, че такива

f

g

не съществуват.

Решение

Ако

c\ge2

, такива полиноми не съществуват: при

x=1

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

2-c\le0

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

f

g

са ненулеви полиноми с неотрицателни коефициенти. Нека занапред

0\lt{}c\lt{}2

и пишем

c=2\cos\theta

, където

0\lt{}\theta\lt{}\pi

. Отговорът е

n=\left\lceil\frac{\pi}{\arccos(c/2)}\right\rceil,

тоест най-малкото цяло

n

, за което

\sin(n\theta)\le0

. Първо доказваме, че степента на

f

не може да бъде по-малка. Нека

f=(x^2-2\cos\theta\,x+1)g

и нека

\deg f=n

. Тогава

\deg g=n-2

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

g(x)=a_0+a_1x+\cdots+a_{n-2}x^{n-2},

\qquad a_i\ge0,\quad a_{n-2}\gt{}0.

Неотрицателността на коефициентите на

f

дава веригата

\begin{align*} a_1&\ge2\cos\theta\, a_0,\\ a_0+a_2&\ge2\cos\theta\, a_1,\\ a_1+a_3&\ge2\cos\theta\, a_2,\\ &\vdots\\ a_{n-4}+a_{n-2}&\ge2\cos\theta\, a_{n-3},\\ a_{n-3}&\ge2\cos\theta\, a_{n-2}. \end{align*}

Ако

\sin(k\theta)\gt{}0

за

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

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

\sin\theta,\sin2\theta,\ldots,\sin((n-1)\theta)

и ги събираме. Тъждеството

\sin(k\theta)+\sin((k+2)\theta)=2\sin((k+1)\theta)\cos\theta

съкращава всички вътрешни членове и остава

\sin((n-2)\theta)a_{n-2}\ge2\cos\theta\sin((n-1)\theta)a_{n-2}.

След делене на

a_{n-2}\gt{}0

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

\sin(n\theta)\le0

. Значи за степен

n

е необходимо

\sin(n\theta)\le0

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

n

е най-малкото цяло число със

\sin(n\theta)\le0

и поставяме

g(x)=\sum_{k=0}^{n-2}\sin((k+1)\theta)x^k.

По минималността на

n

всички коефициенти на

g

са неотрицателни, всъщност положителни. При умножаване с

x^2-2\cos\theta\,x+1

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

x^{n-1}

-\sin(n\theta)\ge0

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

f(x)=(x^2-cx+1)g(x)

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

n

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

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

Задача 4

Пълен запис

Условие

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

a,b,c,n

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

2^a+3^b+5^c=n!,

където

n!

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

n

Решение

За

n\le4

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

2^2+3^0+5^0=3!,

2^1+3^1+5^0=3!,

2^4+3^1+5^1=4!.

Тоест получаваме

(a,b,c,n)=(2,0,0,3),

\quad(1,1,0,3),\quad(4,1,1,4).

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

n\ge5

няма решения. Тогава

120\mid n!

, така че лявата страна трябва да е

0

по модул

120

. Един бърз начин е да се отбележи, че

2^a\pmod{120}\in\{1,2,4,8,16,32,64\},

3^b\pmod{120}\in\{1,3,9,27,81\},

5^c\pmod{120}\in\{1,5,25\},

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

120

. За пълнота даваме и стандартната проверка с по-малки модули. Първо нека

a\lt{}3

. Ако

a=0

, лявата страна е нечетна, което е невъзможно. Ако

a=1

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

8

следва

3^b+5^c\equiv6\pmod8,

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

b

е четно, а

c

е нечетно. В частност

c\gt{}0

, и по модул

5

получаваме

3^b\equiv3\pmod5

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

b

. Ако

a=2

, от

3^b+5^c\equiv4\pmod8

следва, че

b

е нечетно, а

c

е четно. По модул

5

имаме

3^b+5^c\equiv1\pmod5

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

c=0

, така и при

c\gt{}0

. Остава

a\ge3

. По модул

8

получаваме

3^b+5^c\equiv0\pmod8

, което принуждава

b

c

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

3

равенството

2^a+5^c\equiv0\pmod3

налага

a

да е четно, защото

c

е нечетно. От друга страна, по модул

5

равенството

2^a+3^b\equiv0\pmod5

при нечетно

b

налага

a

да е нечетно. Получаваме противоречие. Следователно други решения няма.

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

Задача 6

Пълен запис

Условие

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

(a_n)_{n\ge1}

от тип Фибоначи, ако тя удовлетворява рекурентната връзка

a_{n+2}=a_{n+1}+a_n

за всяко

n\ge1

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

Решение

Да, възможно е. Ще използваме числата на Фибоначи

F_1=F_2=1,\qquad F_3=2,\qquad F_4=3,\qquad F_5=5,\ldots.

Ще ни трябва теоремата на Цекендорф: всяко положително цяло число се представя единствено като сума от несъседни числа на Фибоначи, ако използваме числата

F_2,F_3,F_4,\ldots

. Нека припомним доказателството. Ако

F_k

е най-голямото число на Фибоначи, което не надминава

n

, тогава

n-F_k\lt{}F_{k+1}-F_k=F_{k-1}.

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

F_k

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

F_k\gt{}F_{k-1}+F_{k-3}+F_{k-5}+\cdots.

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

n-F_k

. Записваме представянето на Цекендорф като двоичен низ

\overline{a_k\cdots a_2a_1}_{\mathrm{Fib}},

където

a_i=1

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

F_{i+1}

. Сега за всеки такъв низ, който завършва на

a_1=1

, разглеждаме редицата

\overline{a_k\cdots a_2a_1}_{\mathrm{Fib}},\quad \overline{a_k\cdots a_2a_10}_{\mathrm{Fib}},

\quad \overline{a_k\cdots a_2a_100}_{\mathrm{Fib}},\quad\ldots.

Това е редица от тип Фибоначи: добавянето на една нула в края просто измества всички използвани числа на Фибоначи с един индекс нагоре, а самите числа на Фибоначи удовлетворяват същата рекурентна връзка. Остава да видим, че тези редици наистина дават разбиване. Всяко положително цяло число има единствено представяне на Цекендорф. Ако неговият низ завършва с няколко нули, премахваме точно тези крайни нули; получаваме единствен низ, който завършва на

1

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

1

и без съседни единици, например

1

101

1001

10001

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

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

2018

7 задачи

Задача 1

Пълен запис

Условие

Нека

\mathbb Z[x]

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

x

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

\theta:\mathbb Z[x]\to\mathbb Z,

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

p,q\in\mathbb Z[x]

са изпълнени: (a)

\theta(p+1)=\theta(p)+1

; (b) ако

\theta(p)\ne0

, то

\theta(p)

дели

\theta(pq)

Решение

Отговорът е

\theta(p)=p(c)\qquad\text{за фиксирано }c\in\mathbb Z.

Ясно е, че всяка такава функция работи: добавянето на

1

към полинома добавя

1

към стойността му при

c

, а ако

p(c)\ne0

, то

p(c)

дели

p(c)q(c)

. Остава да докажем, че други функции няма. Нека

x\in\mathbb Z[x]

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

c=\theta(x).

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

P

и всяко цяло число

r

имаме

\theta(P+r)=\theta(P)+r.

В частност

\theta(x-n)=c-n

за всяко цяло

n

. Фиксираме произволен полином

P(x)\in\mathbb Z[x]

и цяло число

n\ne c

. Понеже

x-n\mid P(x)-P(n)

\mathbb Z[x]

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

\theta(x-n)\mid\theta(P(x)-P(n)).

Тук

\theta(x-n)=c-n\ne0

, а по първото условие

\theta(P(x)-P(n))=\theta(P(x))-P(n).

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

c-n\mid\theta(P(x))-P(n).

От друга страна, обикновената делимост на стойностите на полиномите дава

c-n\mid P(c)-P(n).

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

c-n\mid\theta(P(x))-P(c).

Числото

\theta(P(x))-P(c)

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

n

може да бъде произволно голямо по абсолютна стойност. Единствената възможност е

\theta(P(x))-P(c)=0.

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

\theta(P)=P(c)

за всеки

P\in\mathbb Z[x]

, както трябваше да се докаже.

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

Задача 2

Пълен запис

Условие

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

2

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

1

, т.е. е от вида

2^r

за някое цяло

r\ge1

Решение

Да преведем задачата на езика на графите. Имаме прост ориентиран граф

G

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

2

. Търсим броя на подграфите, в които всяка входяща и всяка изходяща степен е равна на

1

. Построяваме неориентиран двуделен граф

\Gamma

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

G

: едното наричаме

V_{\mathrm{out}}

, а другото

V_{\mathrm{in}}

. За

v\in V_{\mathrm{out}}

w\in V_{\mathrm{in}}

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

vw

\Gamma

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

G

има ориентирано ребро

v\to w

. Изборът на пътищата, които остават отворени, е точно перфектно съчетание в

\Gamma

. Наистина, от всяко

v\in V_{\mathrm{out}}

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

v

; и към всяко

w\in V_{\mathrm{in}}

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

w

. Но

\Gamma

2

-регулярен двуделен граф: всеки връх от лявото копие има степен

2

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

2

заради двата входящи пътя. Всеки краен

2

-регулярен граф е обединение на неприпокриващи се цикли; тук циклите са с четна дължина, понеже графът е двуделен. Във всеки такъв четен цикъл има точно две перфектни съчетания: вземаме редуващите се ребра по единия или по другия начин. Ако компонентите-цикли на

\Gamma

са

r

на брой, изборите върху тях са независими, така че общият брой перфектни съчетания е

2^r.

Понеже графът има поне една компонента,

r\ge1

, и този брой е степен на

2

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

1

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

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

Задача 4

Пълен запис

Условие

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

n

означаваме с

\mathcal F(n)

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

m

, за които полиномът

p(x)=x^2+mx+n

има цял корен. (a) Нека

S

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

n

, за които

\mathcal F(n)

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

S

е безкрайно, но

\sum_{n\in S}\frac1n\le1.

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

n

, за които

\mathcal F(n)

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

Решение

Ще докажем първо точно описание на множеството от част (a):

S=\{x(x+1)y(y+1)\mid x,y\gt{}0\}.

Наистина,

m,m+1\in\mathcal F(n)

тогава и само тогава, когато съществуват цели числа

q\gt{}p\ge0

, за които

\begin{align*} m^2-4n&=p^2,\\ (m+1)^2-4n&=q^2. \end{align*}

След изваждане получаваме

2m+1=q^2-p^2

, така че

p

q

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

q-p=2x+1,\qquad q+p=2y+1,

където

y\ge x\ge0

са цели числа. Тогава

\begin{align*} 4n&=m^2-p^2\\ &=\left(\frac{q^2-p^2-1}{2}\right)^2-p^2\\ &=\left(\frac{q^2-p^2-1}{2}-p\right)\left(\frac{q^2-p^2-1}{2}+p\right)\\ &=\frac14(q-p-1)(q-p+1)(q+p-1)(q+p+1), \end{align*}

откъдето

n=x(x+1)y(y+1).

Понеже

n\gt{}0

, имаме

x,y\gt{}0

. Обратно, ако

n=x(x+1)y(y+1)

за положителни

x,y

, вземаме

m=2xy+x+y.

Тогава

m^2-4n=(x-y)^2

(m+1)^2-4n=(x+y+1)^2,

така че и

m

, и

m+1

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

\mathcal F(n)

. Описанието на

S

е доказано. Оттук част (a) следва веднага:

\sum_{n\in S}\frac1n\le

\left(\sum_{x\ge1}\frac1{x(x+1)}\right)\left(\sum_{y\ge1}\frac1{y(y+1)}\right)=

1\cdot1=1.

Освен това

S

е безкрайно, например при фиксирано

x=1

и произволно

y\ge1

получаваме безкрайно много стойности. За част (b) запазваме означенията от доказателството. Нужно е още

m+2\in\mathcal F(n)

, тоест

(m+2)^2-4n=r^2

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

r

. В параметрите

p,q

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

\begin{align*} r^2&=(m+2)^2-4n=m^2-4n+4m+4\\ &=p^2+2+2(2m+1)=2q^2-p^2+2, \end{align*}

или

2q^2+2=p^2+r^2.\tag{1}

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

8

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

p\lt{}q\lt{}r

. За всяко

q

уравнението има каноничното решение

(p,r)=(q-1,q+1)

, но то дава

n=0

, което не ни върши работа. Избираме безкрайно много цели числа

q

, за които

q^2+1

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

1

по модул

4

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

\ell

съществува решение на

q^2\equiv-1\pmod\ell

. Всяко просто число

\ell\equiv1\pmod4

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

2q^2+2=2(q^2+1)

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

(q-1)^2+(q+1)^2

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

p^2+r^2

p\lt{}q\lt{}r

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

n=\frac1{16}(q-p-1)(q-p+1)(q+p-1)(q+p+1),

за което

m,m+1,m+2

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

\mathcal F(n)

. Такива

q

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

n

има безбройно много.

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

Задача 6

Пълен запис

Условие

Нека

S=\{1,\ldots,100\}

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

n

дефинираме

T_n=\{(a_1,\ldots,a_n)\in S^n: a_1+\cdots+a_n\equiv0\pmod{100}\}.

Да се определи за кои

n

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

75

елемента на

S

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

n

-орките в

T_n

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

Решение

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

n

. Нека

R(x)=\sum_{s\text{ червено}}x^s,\qquad B(x)=\sum_{s\text{ синьо}}x^s,

където синьо означава просто „нечервено“. Чрез филтър с корени на единството броят на

n

-орките в

T_n

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

k

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

\binom nk\frac1{100}\sum_\omega R(\omega)^kB(\omega)^{n-k},

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

X

е броят на

n

-орките в

T_n

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

Y

- броят на тези с нечетен брой. Тогава

\begin{align*} X-Y&=\frac1{100}\sum_\omega\sum_k(-1)^k\binom nk R(\omega)^kB(\omega)^{n-k}\\ &=\frac1{100}\sum_\omega (B(\omega)-R(\omega))^n. \end{align*}

За

\omega\ne1

имаме

B(\omega)+R(\omega)=1+\omega+\cdots+\omega^{99}=0

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

B(\omega)-R(\omega)=2B(\omega)

. Понеже

R(1)=75

B(1)=25

, получаваме

\begin{align*} X-Y&=\frac1{100}\left[(-50)^n+\sum_{\omega\ne1}(2B(\omega))^n\right]\\ &=\frac1{100}\left[(-50)^n-50^n\right]+2^nZ, \end{align*}

където

Z=\frac1{100}\sum_\omega B(\omega)^n

е броят на

n

-орките в

T_n

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

Z\ge0

. Ако

n

е четно, първата скоба е нула, така че

X-Y=2^nZ\ge0

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

T_n

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

n

не работи. Оцветяваме

s

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

s\not\equiv2\pmod4

. Точно

75

числа са червени, а сините са числата, сравними с

2

по модул

4

. Ако

n

е нечетно, сума от

n

сини числа е сравнима с

2\pmod4

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

100

. Значи

Z=0

, а тогава

X-Y=-\frac2{100}\cdot50^n\lt{}0.

Така по-малко от половината от

n

-орките са с четен брой червени координати, което завършва доказателството.

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

Задача 7

Пълен запис

Условие

Нека

n

е положително цяло число. Жаба започва върху числовата права в точка

0

. Тя прави крайна последователност от скокове при следните две условия: (i) жабата посещава само точки от множеството

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

, всяка най-много по веднъж; (ii) дължината на всеки скок е измежду

\{2^0,2^1,2^2,\ldots\}

. Скоковете могат да бъдат както наляво, така и надясно. Нека

S

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

S

Решение

Отговорът е

\frac{4^n-1}{3}.

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

2^0,2^1,\ldots,2^{n-1}

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

0

до

2^n-1

. Нека

a_i

е броят на скоковете с дължина

2^i

, където

0\le i\le n-1

. Твърдим, че за всяко

k=1,2,\ldots,n

е изпълнено

a_{n-1}+a_{n-2}+\cdots+a_{n-k}\le2^n-2^{n-k}.\tag{1}

Нека

m=n-k

и разгледаме точките по модул

2^m

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

2^{m-1}

, и голям, ако дължината му е поне

2^m

. Малкият скок сменя класа по модул

2^m

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

2^m

има

2^n/2^m

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

\{0,1,\ldots,2^n-1\}

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

2^n/2^m-1

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

2^m

класа получаваме точно (1). Сега

S=a_0+2a_1+4a_2+\cdots+2^{n-1}a_{n-1}.

Пренаписваме това като сумиране по части:

\begin{align*} S={}&(a_0+a_1+\cdots+a_{n-1})+(a_1+\cdots+a_{n-1})\\ &+2(a_2+\cdots+a_{n-1})+4(a_3+\cdots+a_{n-1})+\cdots+2^{n-2}a_{n-1}. \end{align*}

Прилагайки (1) към всяка от скобите, получаваме

\begin{align*} S&\le(2^n-2^0)+(2^n-2^1)+2(2^n-2^2)+\cdots+2^{n-2}(2^n-2^{n-1})\\ &=\frac{4^n-1}{3}. \end{align*}

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

0

, посещават всяка точка от

\{0,1,\ldots,2^n-1\}

точно веднъж, имат точно

2^i

скока с дължина

2^i

за всяко

0\le i\le n-1

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

1

2^n-1

. При

n=1

това е ясно. Да построим път за

n+1

, който завършва в

2^{n+1}-1

. Първо вземаме мащабирано копие на пътя за

n

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

0,2,4,\ldots,2^{n+1}-2

и започва от

0

, завършвайки в

2

. После вземаме мащабирано и преместено копие върху нечетните точки

1,3,5,\ldots,2^{n+1}-1,

което започва от

1

и завършва в

2^{n+1}-1

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

2\to1

. За път, който завършва в

1

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

0

до

2^{n+1}-2

, после скачаме до

2^{n+1}-1

, а след това следваме обратно подходящ път по нечетните точки до

1

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

2^i

е точно

2^i

за всяко

i

. Затова

S=1\cdot1+2\cdot2+4\cdot4+\cdots+2^{n-1}\cdot2^{n-1}=

1+4+4^2+\cdots+4^{n-1}=\frac{4^n-1}{3}.

Това доказва както горната граница, така и достижимостта й.

Отвори задачатаEvan Chen VONVON TSTST 2018/7Условие — източник

Задача 8

Пълен запис

Условие

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

b\gt{}2

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

n

, такива че

n^2

дели

b^n+1

Решение

Отговорът е: точно тези

b

, за които

b+1

не е степен на

2

. Първо да разгледаме случая, когато

b+1

е степен на

2

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

n=1

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

n\gt{}1

работи, и нека

p

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

n

. Не може

p=2

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

b^n+1\equiv2\pmod4,

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

4

. Значи

p

е нечетно. От

p\mid n

n^2\mid b^n+1

следва

b^n\equiv-1\pmod p

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

b^{2n}\equiv1\pmod p

. Редът на

b

по модул

p

дели

2n

и също дели

p-1

. Понеже

p

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

n

, имаме

\gcd(n,p-1)=1

, откъдето редът дели

2

. Така

p\mid b^2-1=(b-1)(b+1)

. Но

b+1

е степен на

2

, а

p

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

p\mid b-1

. Тогава

b^n+1\equiv2\pmod p

, противоречие. Сега нека

b+1

не е степен на

2

. Ще построим безкрайна редица от различни нечетни прости числа

p_0,p_1,p_2,\ldots

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

k\ge0

, ако

n_k=p_0p_1\cdots p_k,

то

n_k^2\mid b^{n_k}+1

. Избираме

p_0

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

b+1

. Тогава

p_0\mid b+1

, а по лемата за повдигане на степента

p_0^2\mid b^{p_0}+1,

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

p_0,\ldots,p_k

n_k^2\mid b^{n_k}+1

. По теоремата на Цигмонди съществува нечетен прост делител

q\mid b^{n_k}+1,

който не е сред

p_0,\ldots,p_k

. Тук използваме, че изключителният случай

b=2

не се появява, понеже в задачата

b\gt{}2

. Поставяме

p_{k+1}=q

n_{k+1}=n_kq

. Понеже

q\mid b^{n_k}+1

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

q^2\mid (b^{n_k})^q+1=b^{n_{k+1}}+1.

За старите прости делители

p_i

делимостите

p_i^2\mid b^{n_k}+1

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

b^{n_kq}+1

, пак по същата лема, защото

q

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

p_i

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

n_{k+1}^2=p_0^2p_1^2\cdots p_k^2q^2\mid b^{n_{k+1}}+1.

Индукцията дава безбройно много подходящи стойности на

n

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

Отвори задачатаEvan Chen VONVON TSTST 2018/8Условие — източник

Задача 9

Пълен запис

Условие

Да се докаже, че съществува абсолютна константа

c\lt{}1

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

\mathcal P

е многоъгълник с лице

1

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

\frac1{100}

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

\mathcal Q

, за който сечението на вътрешностите на

\mathcal P

\mathcal Q

има общо лице най-много

c

Решение

Ще докажем твърдението в малко по-общ вид за произволно измеримо множество

\mathcal P

с лице

1

. За вектор

v

означаваме с

\mathcal P+v

транслацията на

\mathcal P

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

\varepsilon\gt{}0

всяка транслация

\mathcal P+v

|v|=\frac1{100}

има сечение с

\mathcal P

с лице поне

1-\varepsilon

. Ще получим долна граница за

\varepsilon

. Първо фиксираме вектори

v_1,v_2,\ldots,v_N

, всеки с дължина

\frac1{100}

. Нека скакалец започва от случайна точка

x\in\mathcal P

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

x+v_1+v_2+\cdots+v_N.

Тогава вероятността през цялото време да остане в

\mathcal P

е поне

1-N\varepsilon

. Наистина, за да напусне

\mathcal P

на

i

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

\mathcal P\setminus(\mathcal P-v_i).

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

\varepsilon

. След сумиране по

i

вероятността скакалецът някога да напусне

\mathcal P

е най-много

N\varepsilon

. Сега нека

w

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

8

. Той може да се представи като сума на

800

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

\frac1{100}

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

\mathcal P

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

w

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

\mathcal P

е поне

1-800\varepsilon.\tag{1}

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

x\in\mathcal P

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

w

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

8

. Нека

q

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

x+w

да лежи в

\mathcal P

. От (1), ако първо фиксираме

w

, имаме

q\ge1-800\varepsilon.

От друга страна, ако първо фиксираме

x

, възможните точки

x+w

са равномерно разпределени в диск с лице

64\pi

, затова вероятността да попаднем в множеството

\mathcal P

с лице

1

е най-много

\frac1{64\pi}.

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

1-800\varepsilon\le q\le\frac1{64\pi},

тоест

\varepsilon\ge\frac{1-\frac1{64\pi}}{800}\gt{}0.001.

Така не може за всички посоки с дължина

\frac1{100}

лицето на сечението да е по-голямо от

0.999

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

c=0.999

, което е строго по-малко от

1

. За многоъгълници преминаването от множествата към вътрешностите не променя лицето, защото границата има лице

0

Отвори задачатаEvan Chen VONVON TSTST 2018/9Условие — източник

2019

6 задачи

Задача 1

Пълен запис

Условие

Намерете всички двуместни операции

\diamondsuit\colon \mathbb R_{\gt{}0}\times \mathbb R_{\gt{}0}\to \mathbb R_{\gt{}0}

, за които

a\diamondsuit (b\diamondsuit c)=(a\diamondsuit b)c

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

a,b,c

, и освен това

a\diamondsuit a\ge 1

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

a\ge 1

Решение

Отговорът е

a\diamondsuit b=ab\qquad\text{или}\qquad a\diamondsuit b=\frac ab.

Нека

f(x)=1\diamondsuit x

. От даденото равенство следва, че за всяко фиксирано

a

функцията

x\mapsto a\diamondsuit x

е инективна: ако

a\diamondsuit u=a\diamondsuit v

, то от

1\diamondsuit(a\diamondsuit u)=(1\diamondsuit a)u

1\diamondsuit(a\diamondsuit v)=(1\diamondsuit a)v

получаваме

u=v

. С подходящи замествания в основното тъждество получаваме

a\diamondsuit 1=a,\qquad 1\diamondsuit(1\diamondsuit x)=x,\qquad a\diamondsuit b=a(1\diamondsuit b).

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

a\diamondsuit b=af(b)

f(f(x))=x

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

f(bf(c))=f(b)c

, а понеже

f

е инволюция, това е равносилно на

f(xy)=f(x)f(y)

за всички

x,y\gt{}0

. Значи

f

е мултипликативна и инволютивна. Второто условие става

x f(x)\ge 1\quad\text{за всяко }x\ge 1.

Ще докажем, че за всяко

x\gt{}0

стойността

f(x)

е или

x

, или

1/x

. Достатъчно е да разгледаме

b\gt{}1

и да положим

f(b)=a

; тогава

a\ge 1/b

f(a)=b

. Ако

ab=1

, сме готови. Нека

ab\gt{}1

. За произволни цели

m,n

a^n b^m\ge 1

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

a^n b^m

, дава

a^m b^n=f(a^n b^m)\ge \frac{1}{a^n b^m}.

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

(ab)^{m+n}\ge 1

, а понеже

ab\gt{}1

, получаваме

m+n\ge 0

. С други думи,

m+n\lt{}0\quad\Longrightarrow\quad n\log_b a+m\lt{}0

за всички цели

m,n

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

\log_b a=1

, тоест

a=b

. Така

f(b)

е или

b

, или

1/b

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

g(t)=\log f(e^t)

. От вече доказаното следва

g(t)\in\{t,-t\}

, а мултипликативността дава

|g(t)-g(s)|=|g(t-s)|=|t-s|.

Значи

g

е непрекъсната. Ако

f(2)=2

, то за всяко рационално

q

имаме

f(2^q)=2^q

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

f(2)=1/2

, аналогично

f(x)=1/x

за всяко

x\gt{}0

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

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

Задача 3

Пълен запис

Условие

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

Решение

Нека

S

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

S

на хоризонтални ивици с височина

1

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

S

: след като това е възможно за всеки достатъчно голям правоъгълник, можем последователно да избираме все по-големи правоъгълници и така да получим безкрайна допустима последователност от ходове, в която всяка конкретна кола се мести безкрайно много пъти.Ще опишем пететапен план за колите. 1. Всички вертикални коли, които се намират в зелена клетка, се преместват с една клетка напред в червена клетка (или излизат от

S

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

S

, защото в зелените клетки вече няма вертикални коли. Освен това две хоризонтални коли в един и същ ред не си пречат: условието, че няма две коли, насочени една към друга, означава, че колите, движещи се наляво и надясно, могат да се извеждат към съответните страни без да се сблъскат. 3. Всички вертикални коли, които се намират в червена клетка, се преместват с една клетка напред в зелена клетка (или излизат от

S

), понеже всички зелени клетки вече са празни. 4. Всички хоризонтални коли в червени клетки могат да напуснат

S

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

S

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

S

, а оттук следва и исканата безкрайна последователност от ходове.

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

Задача 4

Пълен запис

Условие

Разглеждаме монети с положителни реални номинали, ненадминаващи

1

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

C\gt{}0

със следното свойство: ако са дадени произволни

100

такива монети с обща стойност

50

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

50

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

C

Решение

Отговорът е

C=\frac{50}{51}

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

51

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

1/51

49

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

1

. Ако в едната купчина попаднат

x

от големите монети, то в другата попадат

49-x

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

\left|x+\frac{50-x}{51}-(49-x)-\frac{x+1}{51}\right|=\frac{50}{51}|2x-49|\ge

\frac{50}{51}.

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

C\ge 50/51

. Сега доказваме, че

C=50/51

винаги е достатъчно. Нека стойностите на монетите са

0\lt{}a_1\le a_2\le \cdots\le a_{100}\le 1,\qquad \sum_{i=1}^{100}a_i=50.

Тогава

a_{50}\le 50/51

, защото монетите

a_{50},a_{51},\ldots,a_{100}

са

51

на брой и общата им стойност е най-много

50

. Също така

a_{51}\ge 1/51

, защото ако

a_{51}\lt{}1/51

, първите

51

монети биха имали обща стойност под

1

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

49

монети имат обща стойност най-много

49

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

a_1,a_3,\ldots,a_{49},\qquad a_{52},a_{54},\ldots,a_{100},

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

50

монети. Нека

D

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

D=

(a_1-a_2)+\cdots+(a_{49}-a_{50})-a_{51}

+(a_{52}-a_{53})+\cdots+(a_{98}-a_{99})+a_{100}.

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

D\le -a_{51}+a_{100}\le -\frac{1}{51}+1=\frac{50}{51}.

От друга страна можем да запишем същия

D

като

D=

a_1+(a_3-a_2)+\cdots+(a_{49}-a_{48})-a_{50}

+(a_{52}-a_{51})+\cdots+(a_{100}-a_{99}).

Всички разлики тук са неотрицателни, а

a_1\gt{}0

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

D\ge -a_{50}\ge -\frac{50}{51}.

Получихме

|D|\le 50/51

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

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

Задача 6

Пълен запис

Условие

Нека

P

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

n

сумата на десетичните цифри на

|P(n)|

не е число на Фибоначи. Вярно ли е, че

P

трябва да е константен?

Решение

Отговорът е да:

P

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

S(n)

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

|n|

. Ще използваме две твърдения. Твърдение 1. Ако

P(x)\in\mathbb Z[x]

е неконстантен полином с положителен старши коефициент, то съществува полином

F(x)\in\mathbb Z[x]

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

P(F(x))

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

F

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

T_0(x)=x^3+x+1.

T_0(x)^{\deg P}

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

T_1(x)=x^3-\frac1D x^2+x+1.

По непрекъснатост, ако

D

е достатъчно голямо спрямо

\deg P

, то

T_1(x)^{\deg P}

е добър; единственият отрицателен коефициент идва от члена

-\frac3D x^{3\deg P-1}

. Накрая вземаме

F(x)=C T_1(x),

където

C

е достатъчно голямо кратно на

D

, така че

F

да има цели коефициенти и водещият член на

P

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

9

има безбройно много числа на Фибоначи. Доказателство. Редицата на Фибоначи е периодична по модул

9

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

\begin{align*} F_0&=0\equiv0\pmod9,\\ F_1&=1\equiv1\pmod9,\\ F_3&=2\equiv2\pmod9,\\ F_4&=3\equiv3\pmod9,\\ F_7&=13\equiv4\pmod9,\\ F_5&=5\equiv5\pmod9,\\ F_{-4}&=-3\equiv6\pmod9,\\ F_9&=34\equiv7\pmod9,\\ F_6&=8\equiv8\pmod9. \end{align*}

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

P

е неконстантен, заменяме при нужда

P

-P

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

|P(n)|

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

F

, така че

P(F(x))=c_Nx^N-c_{N-1}x^{N-1}+c_{N-2}x^{N-2}+\cdots+c_0,

където всички

c_i

са положителни. Сега поставяме

x=10^e

, като

e

е достатъчно голямо, например

10^e\gt{}10\max_i c_i

. Тогава десетичният запис на

P(F(10^e))

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

c_N-1,\quad 10^e-c_{N-1},\quad c_{N-2},\quad c_{N-3},\ldots,c_0,

като между по-ниските блокове има нужните водещи нули. Например, ако

P(F(x))=15x^3-7x^2+4x+19,

то

P(F(1000))=14\,993\,004\,019.

Следователно сумата на цифрите е от вида

S(P(F(10^e)))=9e+k,

където

k

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

P

F

, но не и от

e

. По Твърдение 2 има произволно големи числа на Фибоначи, които са сравними с

k

по модул

9

. Някое от тях е равно на

9e+k

за достатъчно голямо

e

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

P

не може да е неконстантен.

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

Задача 7

Пълен запис

Условие

Нека

f\colon\mathbb Z\to\{1,2,\ldots,10^{100}\}

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

\gcd(f(x),f(y))=\gcd(f(x),x-y)

за всички цели числа

x

y

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

m

n

, такива че

f(x)=\gcd(m+x,n)

за всяко цяло число

x

Решение

Нека

\mathcal P

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

10^{100}

. За всяко

p\in\mathcal P

поставяме

e_p=\max_x \nu_p(f(x)),

и избираме

c_p

, за което максимумът се достига, т.е.

\nu_p(f(c_p))=e_p

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

f

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

p\in\mathcal P

имаме

\nu_p(f(x))=\min(\nu_p(x-c_p),e_p).

Наистина, от условието при

y=c_p

получаваме

\gcd(f(c_p),f(x))=\gcd(f(c_p),x-c_p).

Вземаме

\nu_p

от двете страни. Понеже

\nu_p(f(x))\le\nu_p(f(c_p))=e_p

, получаваме точно желаната формула. Сега избираме

n

m

така:

n=\prod_{p\in\mathcal P}p^{e_p},

m

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

m\equiv -c_p\pmod{p^{e_p}}\quad\text{за всяко }p\in\mathcal P.

Такава стойност на

m

съществува по Китайската теорема за остатъците, като простите степени в модулите са две по две взаимнопрости; модулите с

e_p=0

просто се пропускат. Тогава за всяко

x\in\mathbb Z

имаме

\begin{align*} f(x)&=\prod_{p\in\mathcal P}p^{\nu_p(f(x))} =\prod_{p\mid n}p^{\min(\nu_p(x-c_p),e_p)}\\ &=\prod_{p\mid n}p^{\min(\nu_p(x+m),\nu_p(n))} =\gcd\left(x+m,n\right). \end{align*}

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

Отвори задачатаEvan Chen VONVON TSTST 2019/7Условие — източник

Задача 8

Пълен запис

Условие

Дадени са

16

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

8

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

Решение

Отговорът е

1430

. Ще докажем по-общо твърдение: за всеки набор от

2n

точки в общо положение броят на непересичащите се съвършени сдвоявания е поне

C_n=\frac{1}{n+1}\binom{2n}{n},

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

2n

-ъгълник. За изпъкъл многоъгълник това е стандартното броене на Каталановите числа чрез избора на партньора на един фиксиран връх. Доказваме долната граница със силна индукция по

n

. Избираме точка

P

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

A_1,A_2,\ldots,A_{2n-1}

по ъгъл около

P

. За всяко

k=0,1,\ldots,n-1

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

P

е свързана с

A_{2k+1}

.Отсечката

PA_{2k+1}

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

2k

2(n-k-1)

точки. Понеже

P

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

C_k

C_{n-k-1}

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

P

е свързана с

A_{2k+1}

, са поне

C_k C_{n-k-1}

. Сумираме по всички възможни

k

и получаваме

\sum_{k=0}^{n-1} C_k C_{n-k-1}=C_n,

което е рекурентната формула за Каталановите числа. При

n=8

това дава

C_8=1430

Отвори задачатаEvan Chen VONVON TSTST 2019/8Условие — източник

2020

5 задачи

Задача 3

Пълен запис

Условие

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

\theta_1

\theta_2

\theta_3

особен, ако съществуват цели числа

r_1

r_2

r_3

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

r_1\theta_1+r_2\theta_2+r_3\theta_3=0.

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

n\ge3

, за които триъгълник със страни

n-1

n

n+1

е особен.

Решение

Отговорът е

n=3,4,5,7

. Ще използваме следната стандартна разновидност на полиномите на Чебишов. За всяко

k\ge0

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

P_k(X)\in\mathbb Z[X]

, който за

k\ge1

е моничен от степен

k

, и за който

P_k(X+X^{-1})=X^k+X^{-k}.

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

P_0(X)=2

P_1(X)=X

P_2(X)=X^2-2

P_3(X)=X^3-3X

. Това следва веднага по индукция от рекурсията

P_{k+1}(T)=T P_k(T)-P_{k-1}(T).

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

\alpha\lt{}\beta\lt{}\gamma

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

n-1,n,n+1

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

2\cos\alpha=\frac{n+4}{n+1},\qquad 2\cos\gamma=\frac{n-4}{n-1}.

Триъгълникът е особен тогава и само тогава, когато съществуват цели неотрицателни

r,s

, не и двете нули, такива че

\cos(r\alpha)=\pm\cos(s\gamma),

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

P_r\left(\frac{n+4}{n+1}\right)=\pm P_s\left(\frac{n-4}{n-1}\right).

Наистина, ако

x\alpha+y\beta+z\gamma=0

, то от

\alpha+\beta+\gamma=\pi

следва

(x-y)\alpha=(y-z)\gamma-y\pi.

Затова можем да вземем

r=|x-y|

s=|y-z|

; случаят

r=s=0

би дал

x=y=z

, а тогава

x\pi=0

, тоест трите коефициента са нули. Обратно, ако

\cos(r\alpha)=\pm\cos(s\gamma)

, то

r\alpha\pm s\gamma=k\pi=k(\alpha+\beta+\gamma)

за някое цяло

k

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

r=0

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

P_s(X)\pm2

, следва, че

\frac{n-4}{n-1}

трябва да е цяло число. При

n\ge3

това става само за

n=4

. По същия начин се обработва случаят

s=0

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

n\ne4

r,s\gt{}0

. Нужен ни е следният прост извод. Ако

A/B

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

P(X)\in\mathbb Z[X]

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

P(A/B)

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

B

. Действително, след умножаване по подходяща степен на

B

, водещият член дава числител, сравним с

A^d

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

B

, и затова никой такъв прост делител не се съкращава напълно. Следователно, ако

n\ne4

работи, то знаменателите на дробите

\frac{n+4}{n+1}

\frac{n-4}{n-1}

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

\gcd(n+1,n-1)\mid2,

а числата

\gcd(n+4,n+1)

\gcd(n-4,n-1)

делят

3

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

3

, са невъзможни. Получават се само следните три случая: 1.

n+1=2^u

n-1=2^v

. Това дава само

n=3

. Тогава

2\cos\alpha=\frac74

2\cos\gamma=-\frac12

, а

P_2(-1/2)=-\frac74

. 2.

n+1=3\cdot2^u

n-1=2^v

. Това дава само

n=5

. Тогава

2\cos\alpha=\frac32

2\cos\gamma=\frac14

, а

P_2(3/2)=\frac14

. 3.

n+1=2^u

n-1=3\cdot2^v

. Това дава само

n=7

. Тогава

2\cos\alpha=\frac{11}{8}

2\cos\gamma=\frac12

, а

P_3(1/2)=-\frac{11}{8}

. Накрая

n=4

също работи, защото триъгълникът със страни

3,4,5

е правоъгълен и за ъглите му е изпълнено

\alpha+\beta-\gamma=0

. Така точно

n=3,4,5,7

са решения.

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

Задача 4

Пълен запис

Условие

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

(a,b)

, които удовлетворяват следните условия: 1.

a

дели

b^4+1

; 2.

b

дели

a^4+1

; 3.

\lfloor\sqrt a\rfloor=\lfloor\sqrt b\rfloor

Решение

Единствените решения са

(1,1)

(1,2)

(2,1)

; те очевидно работят. Ще докажем, че други няма. Първо, ясно е, че

\gcd(a,b)=1

. От условията следва, че и

a

, и

b

делят

(a-b)^4+1

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

ab\mid(a-b)^4+1.

Поставяме

k=\frac{(b-a)^4+1}{ab}.

Оценка. Имаме

k\le16

. Наистина, нека

n=\lfloor\sqrt a\rfloor=\lfloor\sqrt b\rfloor.

Тогава

a,b\in[n^2,n^2+2n]

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

ab\ge n^2(n^2+1)\ge n^4+1

(b-a)^4+1\le(2n)^4+1=16n^4+1,

откъдето

k\le16

. Ще докажем, че всъщност

k=1

. Първо,

k

не може да е четно. Ако беше четно, тогава

a

b

щяха да са с различна четност, но тогава

(b-a)^4+1\equiv2\pmod4

, докато

kab

се дели на

4

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

k

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

x^4+1

е сравним с

1

по модул

8

: ако

q\mid x^4+1

, то

x^8\equiv1\pmod q

, но

x^4\not\equiv1\pmod q

, така че редът на

x

по модул

q

8

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

8\mid q-1

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

17

. Понеже

k\le16

, получаваме

k=1

. Остава да решим

ab=(b-a)^4+1.

Пишем

b=a+d

и без ограничение приемаме

d\ge0

. Тогава

a(a+d)=d^4+1,

или

a^2+ad-(d^4+1)=0.

Дискриминантата

d^2+4(d^4+1)=4d^4+d^2+4

трябва да е точен квадрат. При

d=0

получаваме

(1,1)

, а при

d=1

получаваме

(1,2)

. Ако

d\ge2

, то

(2d^2)^2\lt{}4d^4+d^2+4\lt{}4d^4+4d^2+1=(2d^2+1)^2,

така че дискриминантата не може да е точен квадрат. Това дава само

(1,1)

(1,2)

при

b\ge a

; по симетрия получаваме и

(2,1)

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

Задача 7

Пълен запис

Условие

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

P(z)

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

P(z)

P(z)-1

имат модул

1

Решение

Отговорът е: полиномите

P(z)=\lambda z^n-\mu,

където

n\ge1

|\lambda|=|\mu|

\operatorname{Re}\mu=-\frac12

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

P

имат модул

1

, когато

|\mu|=|\lambda|

, а корените на

P-1

имат модул

1

, когато

|\mu+1|=|\lambda|

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

\begin{align*} P(z)&=c_nz^n+c_{n-1}z^{n-1}+\cdots+c_1z+c_0\\ &=c_n(z+\alpha_1)(z+\alpha_2)\cdots(z+\alpha_n),\\ P(z)-1&=c_n(z+\beta_1)(z+\beta_2)\cdots(z+\beta_n). \end{align*}

По условие

|\alpha_i|=|\beta_i|=1

за всички

i

. Понеже при комплексно спрегнатите числа имаме

\overline{\alpha_i}=1/\alpha_i

\overline{\beta_i}=1/\beta_i

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

(z+\alpha_1)\cdots(z+\alpha_n)=(z+\beta_1)\cdots(z+\beta_n)+c_n^{-1}

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

\left(z+\frac1{\alpha_1}\right)\cdots\left(z+\frac1{\alpha_n}\right)=

\left(z+\frac1{\beta_1}\right)\cdots\left(z+\frac1{\beta_n}\right)+\overline{c_n}^{\,-1}.

Сравняваме коефициентите пред

z^k

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

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

това дава

\frac{c_{n-k}}{\alpha_1\alpha_2\cdots\alpha_n}=\frac{c_{n-k}}{\beta_1\beta_2\cdots\beta_n}.

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

P

P-1

имаме

\alpha_1\alpha_2\cdots\alpha_n-\beta_1\beta_2\cdots\beta_n=\frac1{c_n}\ne0.

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

c_{n-k}=0

за всяко

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

. Значи всички междинни коефициенти на

P

са нули и

P(z)=\lambda z^n-\mu.

Както вече отбелязахме, условията за корените са точно

|\lambda|=|\mu|=|\mu+1|

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

|\lambda|=|\mu|

\operatorname{Re}\mu=-\frac12

Отвори задачатаEvan Chen VONVON TSTST 2020/7Условие — източник

Задача 8

Пълен запис

Условие

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

N

нека

\sigma(N)

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

N

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

m\ge n\ge2

, за които

\frac{\sigma(m)-1}{m-1}=\frac{\sigma(n)-1}{n-1}=\frac{\sigma(mn)-1}{mn-1}.

Решение

Отговорът е:

m

n

трябва да са степени на едно и също просто число. Първо проверяваме, че всички такива двойки работят. Ако

m=p^a

n=p^b

, то за всяко

e\ge1

имаме

\frac{\sigma(p^e)-1}{p^e-1}=\frac{(1+p+\cdots+p^e)-1}{p^e-1}=

\frac{p(1+p+\cdots+p^{e-1})}{p^e-1}=\frac{p}{p-1}.

Същото важи и за

mn=p^{a+b}

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

\lambda

е общата стойност на трите дроби. Делителите на

mn

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

m

, както и числата

m d

, където

d

пробягва делителите на

n

; числото

m

е преброено два пъти, затова го изваждаме веднъж. Следователно

\begin{align*} \sigma(mn)&\ge\sigma(m)+m\sigma(n)-m\\ &=(\lambda m-\lambda+1)+m(\lambda n-\lambda+1)-m\\ &=\lambda mn-\lambda+1. \end{align*}

Но от дефиницията на

\lambda

имаме точно

\sigma(mn)=\lambda mn-\lambda+1

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

mn

е или делител на

m

, или е от вида

m d

за някой делител

d

на

n

. Прилагайки същия аргумент със сменени роли на

m

n

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

mn

е или делител на

n

, или е от вида

n d

за някой делител

d

на

m

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

m

n

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

p\mid n

, но

p\nmid m

, тогава

p

е делител на

mn

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

m

и не може да е от вида

md

понеже

m\ge2

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

m

дели

n

, така че

m

n

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

p

q

. Нека

\nu_p(m)=\alpha,\qquad \nu_p(n)=\beta.

Тогава

p^{\alpha+eta}

е делител на

mn

. Той не е делител на

m

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

p

е твърде голяма. Не може да е и от вида

m d

d\mid n

, защото

q

дели

m

, а числото

p^{\alpha+eta}

няма делител

q

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

m

n

, т.е.

m

n

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

Отвори задачатаEvan Chen VONVON TSTST 2020/8Условие — източник

Задача 9

Пълен запис

Условие

Десет милиона светулки светят в

\mathbb R^3

в полунощ. Някои от светулките са приятелки, като приятелството винаги е взаимно. Всяка секунда една светулка се премества на ново място така, че разстоянието й до всяка от приятелките й е същото, каквото е било преди преместването. Това е единственият начин, по който светулките някога променят положенията си. Никои две светулки никога не могат да заемат една и съща точка. Първоначално никои две светулки, независимо дали са приятелки, или не, не са на разстояние повече от един метър. След краен брой секунди всички светулки се оказват на разстояние поне десет милиона метра от първоначалните си положения. При тези условия намерете най-големия възможен брой приятелства между светулките.

Решение

Отговорът е

\left\lfloor\frac{10^{14}}3\right\rfloor=33333333333333.

По-общо ще докажем, че за

n\ge70

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

f(n)=\left\lfloor\frac{n^2}3\right\rfloor.

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

\ell_A,\ell_B,\ell_C

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

1

и никои две светулки да не съвпадат. Обявяваме две светулки за приятелки точно когато лежат върху различни от трите прави. Така получаваме пълен триделен граф с възможно най-равни дялове, следователно броят на приятелствата е

f(n)

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

\ell_A

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

\ell_B

\ell_C

, после всички светулки върху

\ell_B

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

\ell_C

\ell_A

, после всички светулки върху

\ell_C

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

\ell_A

\ell_B

, и повтаряме. Всяко такова отражение може да се извърши светулка по светулка, защото приятелките на движещата се светулка лежат в равнината на отражение, а отражението запазва разстоянията до всички точки от тази равнина. В перпендикулярно сечение това е разгъване по триъгълната решетка, затова след достатъчно много повторения трите прави, а значи и всички светулки, са на произволно голямо разстояние от началните си положения. Това дава долната граница. Сега доказваме горната граница. Разглеждаме произволна допустима конфигурация с

n

светулки. Ако графът на приятелствата няма

4

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

f(n)

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

a,b,c,d

. Нека

g(n)

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

4

-клика. Ще използваме прост факт: за да може една светулка да се премести на друго място, всичките й приятелки в този момент трябва да са в една равнина, понеже те лежат в срединната равнина на отсечката между старото и новото й положение. Първо не може четири копланарни светулки да са две по две приятелки. Ако това се случи, никоя от тях не може да се премести нетривиално, запазвайки разстоянията до другите три; в изродения случай с три колинеарни точки ограничението е още по-силно. Това противоречи на факта, че накрая всяка светулка се е отдалечила много от началното си положение. Ключово твърдение. Има най-много

12

светулки

e

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

a,b,c,d

. Нека

A,B,C,D

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

a,b,c,d

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

ABCD

винаги има една и съща форма, защото шестте му ръба са разстояния между приятелки. Ще използваме този тетраедър като подвижна отправна система. Без ограничение нека

e

е приятелка с

a,b,c

. Тогава спрямо триъгълника

ABC

светулката

e

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

E_1

E_2

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

ABC

, така че

E_1ABC

E_2ABC

са тетраедри с фиксирана форма. Точките

D,E_1,E_2

са различни; ако например

D

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

4

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

a

. Тогава приятелките й

b,c,d,e

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

E_1,E_2

лежи в равнината

BCD

. По същия начин, когато се движат

b

c

, една от точките

E_1,E_2

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

ACD

ABD

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

E_1

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

BCD

ACD

. Значи

E_1

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

CD

, а

E_2

лежи в равнината

ABD

. Това определя еднозначно двойката

\{E_1,E_2\}

спрямо тетраедъра

ABCD

: точката

E_1

е пресечната точка на правата

CD

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

ABD

спрямо равнината

ABC

, а

E_2

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

ABD

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

CD

спрямо равнината

ABC

. Като отчетем избора на трите приятелки измежду

a,b,c,d

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

12

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

e

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

a,b,c,d

, защото приятелките й не биха били копланарни. Следователно всяка от тези най-много

12

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

3

ребра към четворката. Затова ребрата, които имат точно един край измежду

a,b,c,d

, са най-много

(n-16)\cdot2+12\cdot3=2n+4.

След премахване на четирите светулки

a,b,c,d

получаваме

g(n)\le6+(2n+4)+\max\{f(n-4),g(n-4)\}.

За

n\ge24

имаме

(2n+10)+f(n-4)\le f(n),

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

g(n)\le\max\{f(n),(2n+10)+g(n-4)\}.

Итерираме това неравенство. Нека

r

е такова, че

n-4r-4\lt{}24\le n-4r.

Тогава

\begin{align*} g(n)\le\max\Big\{f(n),\ &(2n+10)+(2(n-4)+10)+\cdots\\ &+(2(n-4r)+10)+g(n-4r-4)\Big\}. \end{align*}

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

\begin{align*} &(r+1)(2n-4r+10)+\binom{24}{2}\\ &\le\left(\frac n4-5\right)(n+37)+\binom{24}{2}, \end{align*}

а за

n\ge70

това е по-малко от

f(n)

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

4

-клика имаме най-много

f(n)

приятелства. За

n=10^7

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

\left\lfloor10^{14}/3\right\rfloor=33333333333333

Отвори задачатаEvan Chen VONVON TSTST 2020/9Условие — източник

2021

5 задачи

Задача 2

Пълен запис

Условие

Нека

a_1\lt{}a_2\lt{}a_3\lt{}a_4\lt{}\dotsb

е безкрайна редица от реални числа в интервала

(0,1)

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

\frac{a_1}{1},\;\frac{a_2}{2},\;\frac{a_3}{3},\;\frac{a_4}{4},\;\dots.

Решение

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

\lambda

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

S_\lambda=\{k: a_k/k=\lambda\}

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

S_\lambda

е крайно, защото от

a_k=k\lambda\lt{}1

следва

k\lt{}1/\lambda

. Нека

m_\lambda

M_\lambda

са съответно най-малкият и най-големият елемент на

S_\lambda

, и нека

T_\lambda=\{m_\lambda,m_\lambda+1,\ldots,M_\lambda\}.

Така всяко

T_\lambda

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

T_\lambda

покриват

\mathbb N

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

m_\lambda

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

T_\lambda

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

\mathbb N

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

\mathbb N

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

\Lambda

е множеството от стойностите на

\lambda

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

\bigcup_{\lambda\in\Lambda}T_\lambda=\mathbb N,

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

T_\lambda

. Затова

\sum_{\lambda\in\Lambda}\sum_{k\in T_\lambda}(a_{k+1}-a_k)\le

2\sum_{k\ge1}(a_{k+1}-a_k)\le2,

тъй като всички

a_k

лежат между

0

1

. От друга страна, за фиксирано

\lambda\in\Lambda

имаме

a_{m_\lambda}=\lambda m_\lambda

a_{M_\lambda}=\lambda M_\lambda

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

\begin{align*} 2\sum_{k\in T_\lambda}(a_{k+1}-a_k)&\ge 2\sum_{m_\lambda\le k\lt{}M_\lambda}(a_{k+1}-a_k)\\ &=2(a_{M_\lambda}-a_{m_\lambda})=2(M_\lambda-m_\lambda)\lambda\\ &=2(M_\lambda-m_\lambda)\frac{a_{m_\lambda}}{m_\lambda}\\ &\ge (M_\lambda-m_\lambda+1)\frac{a_1}{m_\lambda}\\ &\ge a_1\sum_{k\in T_\lambda}\frac1k. \end{align*}

Сумирайки по всички

\lambda\in\Lambda

, получаваме

4\ge 2\sum_{\lambda\in\Lambda}\sum_{k\in T_\lambda}(a_{k+1}-a_k)\ge

a_1\sum_{\lambda\in\Lambda}\sum_{k\in T_\lambda}\frac1k\ge a_1\sum_{k\ge1}\frac1k.

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

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

Задача 3

Пълен запис

Условие

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

k\gt{}1

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

n

, такова че

\binom nk

се дели на

n

, а

\binom nm

не се дели на

n

за всяко

2\le m\lt{}k

Решение

Такова число

n

съществува за всяко

k\gt{}1

. Първо нека

k

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

n=(k-1)!.

За

m\lt{}k

от

m!\mid n

следва

\begin{align*} (n-1)(n-2)\cdots(n-m+1)&\equiv(-1)(-2)\cdots(-m+1)\\ &\equiv(-1)^{m-1}(m-1)!\not\equiv0\pmod{m!}. \end{align*}

Затова

m!

не дели

(n-1)(n-2)\cdots(n-m+1)

\binom nm

не е кратно на

n

. За

m=k

имаме

\binom nk=\frac nk\binom{n-1}{k-1}.

Понеже

k\nmid n

, а

k

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

k\mid\binom{n-1}{k-1}

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

n\mid\binom nk

. Сега нека

k

е съставно. Ще изберем

n

, удовлетворяващо няколко сравнения. За всяко просто

p\le k

полагаме

t_p=\nu_p(\operatorname{lcm}(1,2,\dots,k-1))=

\max(\nu_p(1),\nu_p(2),\dots,\nu_p(k-1))

и избираме

k_p\in\{1,2,\dots,k-1\}

възможно най-голямо, така че

\nu_p(k_p)=t_p

. Искаме

n

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

\begin{align} n&\equiv0\pmod{p^{t_p+1}} &&\text{ако } p\nmid k, \label{eq:tstst2021-3-cong1}\\ \nu_p(n-k_p)&=t_p+\nu_p(k) &&\text{ако } p\mid k. \label{eq:tstst2021-3-cong2} \end{align}

за всички прости

p\le k

. По Китайската теорема за остатъците такова

n

съществува. Например за \eqref{eq:tstst2021-3-cong2} е достатъчно да наложим

n\equiv k_p+p^{t_p+\nu_p(k)}\pmod{p^{t_p+\nu_p(k)+1}}.

Ще покажем, че това

n

върши работа. Първо пресмятаме

\nu_p(n-i)

за прости

p\lt{}k

1\le i\lt{}k

. Ако

p\nmid k

, то

\nu_p(i),\nu_p(n-i)\le t_p

\nu_p(n)\gt{}t_p

, откъдето

\nu_p(n-i)=\nu_p(i)

. Ако

p\mid k

i\ne k_p

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

\nu_p(i),\nu_p(n-i)\le t_p

\nu_p(n)\ge t_p

, така че

\nu_p(n-i)=\nu_p(i)

. Ако

p\mid k

i=k_p

, тогава по конструкция

\nu_p(n-i)=\nu_p(i)+\nu_p(k).

Следователно винаги имаме

\nu_p(n-i)=\nu_p(i)

, освен при

i=k_p

, където се добавя

\nu_p(k)

; тази формула е безвредна и когато

p\nmid k

, понеже тогава

\nu_p(k)=0

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

\binom nk

се дели на

n

. Това е равносилно на това

k!

да дели

(n-1)(n-2)\cdots(n-k+1).

За всяко просто

p\le k

имаме

\begin{align*} \nu_p((n-1)(n-2)\cdots(n-k+1)) &=\nu_p(n-k_p)+\sum_{\substack{i\lt{}k\\ i\ne k_p}}\nu_p(n-i)\\ &=\nu_p(k_p)+\nu_p(k)+\sum_{\substack{i\lt{}k\\ i\ne k_p}}\nu_p(i)\\ &=\sum_{i=1}^k\nu_p(i)=\nu_p(k!). \end{align*}

Значи

k!

дели произведението и

n\mid\binom nk

. Накрая нека

1\lt{}m\lt{}k

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

n

не дели

\binom nm

, т.е. че

m!

не дели

(n-1)(n-2)\cdots(n-m+1)

. Ако

m

има прост делител

q

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

k

, тогава

\begin{align*} \nu_q((n-1)(n-2)\cdots(n-m+1)) &=\sum_{i=1}^{m-1}\nu_q(n-i)\\ &=\sum_{i=1}^{m-1}\nu_q(i)=\nu_q((m-1)!)\lt{}\nu_q(m!), \end{align*}

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

m

делят

k

. Ако има такъв прост делител

p

, за който

\nu_p(m)\gt{}\nu_p(k)

, тогава

\begin{align*} \nu_p((n-1)(n-2)\cdots(n-m+1)) &=\nu_p(k)+\sum_{i=1}^{m-1}\nu_p(i)\\ &\lt{}\nu_p(m)+\sum_{i=1}^{m-1}\nu_p(i)=\nu_p(m!), \end{align*}

и пак сме готови. Ако пък

\nu_p(m)\le\nu_p(k)

за всяко

p\mid k

, то

m\mid k

и понеже

m\lt{}k

, имаме

m\le k/2

. Нека

p

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

m

. От избора на

k_p

следва

k_p\ge k/2

: иначе вместо

k_p

бихме могли да използваме

2k_p

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

m\le k/2\le k_p

, и

\begin{align*} \nu_p((n-1)(n-2)\cdots(n-m+1)) &=\sum_{i=1}^{m-1}\nu_p(n-i)\\ &=\sum_{i=1}^{m-1}\nu_p(i)=\nu_p((m-1)!)\lt{}\nu_p(m!). \end{align*}

Така и в последния случай

m!

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

\binom nm

не се дели на

n

за всяко

m\lt{}k

, а избраното

n

има исканото свойство.

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

Задача 4

Пълен запис

Условие

Нека

a

b

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

(m,n)

, за които и

m^2+an+b

, и

n^2+am+b

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

a

дели

2b

Решение

Разглеждаме

a

b

като фиксирани. По условие има безбройно много четворки

(m,n,r,s)

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

\begin{gather*} m^2+an+b=(m+r)^2,\\ n^2+am+b=(n+s)^2. \end{gather*}

Ще наричаме двойката

(r,s)

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

(m,n)

, удовлетворяващи тази система. Твърдение. Ако

(r,s)

е изключителна двойка, то е изпълнено поне едно от следните:

0\lt{}r\lt{}\frac a2 \text{ и } 0\lt{}s\le\frac{a^2}{4},

0\lt{}s\lt{}\frac a2 \text{ и } 0\lt{}r\le\frac{a^2}{4},

или

r^2+s^2\le2b.

В частност има само краен брой изключителни двойки

(r,s)

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

r^2+s^2-2b=(a-2r)m+(a-2s)n. \qquad(\dagger)

Ако

0\lt{}r\lt{}a/2

, използваме от първото уравнение оценката

an+b\ge2m+1

, откъдето

m\le\frac{an+b-1}{2}.

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

(n+s)^2=n^2+am+b\le n^2+a\cdot\frac{an+b-1}{2}+b.

За да е възможно това за безбройно много цели числа

n

, при сравнение на коефициентите пред

n

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

2s\le a^2/2

, т.е.

s\le a^2/4

. Аналогично се разглежда случаят

0\lt{}s\lt{}a/2

. Ако

\min(r,s)\gt{}a/2

, тогава от

(\dagger)

следва

r^2+s^2\le2b

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

(r,s)

, за която системата има безбройно много решения

(m,n)

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

\begin{gather*} an=2rm+r^2-b,\\ 2sn=am+b-s^2. \end{gather*}

Това е линейна система по

m,n

. За да има безбройно много решения, двете уравнения трябва да са зависими. Следователно

\frac a{2s}=\frac{2r}{a}=\frac{r^2-b}{b-s^2}.

Оттук

a=2\sqrt{\vphantom{x^2}rs}

b=\frac{s^2\sqrt r+r^2\sqrt s}{\sqrt r+\sqrt s}.

Понеже

rs

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

r=kx^2,\qquad s=ky^2,\qquad \gcd(x,y)=1.

Тогава получаваме

a=2kxy

b=k^2xy(x^2-xy+y^2).

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

2b=a\cdot k(x^2-xy+y^2),

така че

a\mid2b

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

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

Задача 5

Пълен запис

Условие

Нека

T

е дърво с

n

върха и точно

k

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

\frac{n+k-1}{2}

върха на

T

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

T

съдържа четен брой ребра.

Решение

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

T

всички листа са в един и същи цвят; тогава всеки път между две листа има четен брой ребра. Първо решение. Ще използваме следната лема. Лема. Ако

S

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

T

, то

\sum_{v\in S}\deg(v)\le n-1.

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

S

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

T

е инцидентно с най-много един връх от

S

, понеже

S

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

S

, към които са инцидентни. За равенство всяко ребро трябва да е инцидентно с точно един връх от

S

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

S

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

\frac{n+k-1}{2}

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

k

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

1

, а останалите избрани върхове имат степен поне

2

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

k+2\cdot\frac{n-k-1}{2}=n-1.

От лемата тя е и най-много

n-1

, така че навсякъде имаме равенство. Следователно независимото множество съдържа всички листа и е един от двата цветови класа. Значи всички листа са в един и същи цвят, както искахме. Второ решение. Ще използваме друга лема. Лема. Върховете на

T

могат да се разбият на

k-1

пътя, така че ребрата на

T

, които не са част от тези пътища, са инцидентни с краен връх на някой от пътищата. Доказателство. Повтаряме следната операция: вземаме листо и премахваме най-дългия път, който го съдържа и след чието премахване останалият граф все още е дърво. Така всеки път използва две листа от текущото дърво, с изключение на последната тривиална стъпка, и се получават

k-1

пътя с исканото свойство. Нека един от тези пътища има

a

върха. В независимо множество могат да попаднат най-много

\frac{a+1}{2}

от тях. Ако дължините на пътищата са

a_1,\dots,a_{k-1}

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

T

е най-много

\sum_i\frac{a_i+1}{2}=\frac{n+k-1}{2}.

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

\frac{n+k-1}{2}

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

T

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

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

Задача 9

Пълен запис

Условие

Нека

q=p^r

, където

p

е просто число, а

r

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

\zeta=e^{2\pi i/q}

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

n

, за което

\begin{aligned}\sum_{\substack{1\le k\le q\\ \gcd(k,p)=1}}\frac{1}{(1-\zeta^k)^n}\end{aligned}

не е цяло число. Сумата е по всички

1\le k\le q

, за които

p\nmid k

Решение

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

n=((p-1)r-1)p^{r-1}+1.

Нека

S_q

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

q

-ти корени на единицата и нека

d=\phi(q)=(p-1)p^{r-1}.

Разглеждаме числата

\frac1{1-\omega}

за

\omega\in S_q

като корени на полинома

P(x)=x^d-c_1x^{d-1}+c_2x^{d-2}-\dotsb\pm c_d,

така че

c_j

j

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

S_n=\sum_{\omega\in S_q}\frac1{(1-\omega)^n}.

По Нютоновите тъждества имаме например

S_1=c_1,\qquad S_2=c_1S_1-2c_2,

\qquad S_3=c_1S_2-c_2S_1+3c_3,

а общо за

n\le d

S_n=

\left[\sum_{j=1}^{n-1}(-1)^{j+1}c_jS_{n-j}\right]+(-1)^{n+1}nc_n.\tag{1}

За

n\gt{}d

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

S_n=\sum_{j=1}^d(-1)^{j+1}c_jS_{n-j}.\tag{2}

Първо ще опишем знаменателите на коефициентите

c_i

. Лема 1. Всички

c_i

са цели числа, освен

c_d

. Всъщност

c_d=1/p

. Доказателство.

q

-тият циклотомен полином е

\Phi_q(x)=1+x^{p^{r-1}}+x^{2p^{r-1}}+\dotsb+x^{(p-1)p^{r-1}}.

Полиномът

Q(x)=

1+(1+x)^{p^{r-1}}+(1+x)^{2p^{r-1}}

+\dotsb+(1+x)^{(p-1)p^{r-1}}

има корени

\omega-1

за

\omega\in S_q

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

Q(x)=p(-x)^dP(-1/x).

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

c_n

1/p

по коефициента пред

x^n

Q(x)

. В частност водещият коефициент на

Q

1

, така че

c_d=1/p

точно. Работим по модул

p

. Понеже

(x+y)^p\equiv x^p+y^p\pmod p

, имаме

\begin{align*} Q(x)&\equiv 1+(1+x^{p^{r-1}})+(1+x^{p^{r-1}})^2+\dotsb+(1+x^{p^{r-1}})^{p-1}\\ &\equiv \frac{(1+x^{p^{r-1}})^p-1}{x^{p^{r-1}}}\pmod p. \end{align*}

Последният полином е сравним с

x^d

по модул

p

. Значи всички коефициенти на

Q(x)

, освен водещия, се делят на

p

. Оттук

c_n

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

n\lt{}d

, а

c_d=1/p

. Лемата е доказана. От (1) веднага следва, че

S_n

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

n\lt{}d

. Ако

r=1

, тогава

d=p-1

dc_d=(p-1)/p

не е цяло число; следователно от (1) получаваме, че

S_d

не е цяло число. В този случай отговорът е

p-1

, което съвпада с формулата. По-нататък нека

r\ge2

. Тогава

dc_d

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

S_d

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

1/p

. Ще използваме

p

-адичната валуация

\nu_p

. Лема 2. За

1\le n\le d

е изпълнено

\nu_p(nc_n)\ge r-2

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

n

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

n=d-p^{r-1}+1.

Доказателство. Числото

nc_n

1/p

по коефициента пред

x^{n-1}

в производната

Q'(x)

. Имаме

Q'(x)=

p^{r-1}(1+x)^{p^{r-1}-1}\left[\sum_{k=1}^{p-1}k(1+x)^{(k-1)p^{r-1}}\right].

Достатъчно е да видим, че всички коефициенти на полинома в квадратните скоби се делят на

p

, освен водещия. Отново по модул

p

, ако запишем

w=x^{p^{r-1}}

, този полином става

1+2(1+w)+3(1+w)^2+\dotsb+(p-1)(1+w)^{p-2}.

Това е производната по

w

на

1+(1+w)+(1+w)^2+\dotsb+(1+w)^{p-1}=\frac{(1+w)^p-1}{w}.

Понеже междинните биномни коефициенти

\binom pj

се делят на

p

, всички коефициенти на тази производна, освен водещия, са кратни на

p

. Умножението с

(1+x)^{p^{r-1}-1}

не може да създаде по-ранен некратен на

p

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

(p-2)p^{r-1}

по

x

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

d-p^{r-1}=(p-2)p^{r-1}.

Затова първото равенство

\nu_p(nc_n)=r-2

е при

n=d-p^{r-1}+1

. Лемата е доказана. Полагаме

m=d-p^{r-1}=(p-2)p^{r-1}.

Ще докажем следното твърдение. Твърдение. За всички цели

k\ge0

1\le j\le d

е вярно

\begin{align*} \nu_p(S_{kd+m+1})&=r-2-k,\\ \nu_p(S_{kd+m+j})&\ge r-2-k. \end{align*}

Доказателство. Първо разглеждаме

1\le n\le d

. От Нютоновите тъждества и лема 2 следва, че

S_1,S_2,\dots,S_m

се делят на

p^{r-1}

. При

n=m+1

членът

(m+1)c_{m+1}

има валуация точно

r-2

, а всички предишни членове в (1) имат валуация поне

r-1

, затова

\nu_p(S_{m+1})=r-2.

По същия начин за

m+1\le n\le d

получаваме

\nu_p(S_n)\ge r-2

. Сега използваме рекурсията (2). По лема 1 коефициентите

c_1,\dots,c_{d-1}

са цели, а

c_d=1/p

. Затова единственият член, който може да намали

p

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

d

стойности към

S_n

, е последният член с

S_{n-d}

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

n\gt{}d

са валидни две прости последици: - ако

\nu_p(S_{n-j})\ge \ell

за всички

1\le j\le d

\nu_p(S_{n-d})\ge \ell+1

, то

\nu_p(S_n)\ge \ell

; - ако

\nu_p(S_{n-j})\ge \ell

за всички

1\le j\le d

\nu_p(S_{n-d})=\ell

, то

\nu_p(S_n)=\ell-1

. Във втория случай няма скрито съкращаване: членът

c_dS_{n-d}=S_{n-d}/p

има валуация

\ell-1

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

\ell

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

d

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

r-2

при индекса

m+1

и поне

r-2

до края на блока. Всеки следващ блок измества тази точна валуация с

d

напред и я намалява с

1

, докато останалите стойности в блока остават поне толкова големи. Това доказва твърдението. От твърдението най-малкото

n

, за което

\nu_p(S_n)\lt{}0

, е

n=(r-1)d+m+1.

Тъй като всички

S_n

се получават от рекурсиите с рационални коефициенти с единствен възможен знаменател степен на

p

, отрицателната

p

-адична валуация е точно условието

S_n

да не бъде цяло число. Накрая

\begin{align*} (r-1)d+m+1&=(r-1)(p-1)p^{r-1}+(p-2)p^{r-1}+1\\ &=((p-1)r-1)p^{r-1}+1. \end{align*}

Това е търсеният най-малък положителен индекс.

Отвори задачатаEvan Chen VONVON TSTST 2021/9Условие — източник

2022

6 задачи

Задача 1

Пълен запис

Условие

Нека

n

е положително цяло число. Намерете най-малкото положително цяло число

k

, такова че за всяко множество

S

от

n

точки във вътрешността на единичния квадрат съществува множество от

k

правоъгълника със следните свойства: 1. страните на всеки правоъгълник са успоредни на страните на единичния квадрат; 2. никоя точка от

S

не лежи във вътрешността на нито един от правоъгълниците; 3. всяка точка от вътрешността на единичния квадрат, която не е от

S

, лежи във вътрешността на поне един от тези

k

правоъгълника. Вътрешността на многоъгълник не съдържа границата му.

Решение

Отговорът е

\boxed{2n+2}.

Ще мислим за задачата така: за всяко множество

S\subset(0,1)^2

n

точки трябва да покрием

(0,1)^2\setminus S

с възможно най-малко отворени правоъгълници, успоредни на страните на квадрата. Първо доказваме долната граница. Избираме

S=\{(s_1,s_1),(s_2,s_2),\dots,(s_n,s_n)\},

където

0\lt{}s_1\lt{}s_2\lt{}\dots\lt{}s_n\lt{}1,

и вземаме достатъчно малко

\varepsilon\gt{}0

. Нека

S'

е множеството от

4n

точки, получени от всяка точка на

S

чрез преместване с

\varepsilon

наляво, надясно, нагоре или надолу:

S'=

S+\{(\varepsilon,0),(0,\varepsilon),(-\varepsilon,0),(0,-\varepsilon)\}\subset(0,1)^2.

Всички точки на

S'

трябва да бъдат покрити.Четирите правоъгълника, които покриват съответно точките

(s_1-\varepsilon,s_1),\quad (s_1,s_1-\varepsilon),

\quad (s_n+\varepsilon,s_n),\quad (s_n,s_n+\varepsilon),

не могат да покрият други точки от

S'

, без да съдържат точка от

S

във вътрешността си. Всеки друг правоъгълник, който избягва точките на

S

, може да покрие най-много две точки от

S'

. Следователно броят на правоъгълниците е поне

4+\frac{\lvert S'\rvert-4}{2}=4+\frac{4n-4}{2}=2n+2.

Остава да построим покритие с

2n+2

правоъгълника. По симетрия можем да предположим, че броят на различните

y

-координати на точките от

S

е поне броя на различните

x

-координати. Нека тези различни

x

-координати са

0=x_0\lt{}x_1\lt{}\dots\lt{}x_m\lt{}x_{m+1}=1,

Y_i

да е множеството от

y

-координатите на точките от

S

, които имат

x

-координата

x_i

. За всяко

1\le i\le m

вземаме

\lvert Y_i\rvert+1

правоъгълника, които заедно са

(x_{i-1},x_{i+1})\times((0,1)\setminus Y_i).

Добавяме още двата странични правоъгълника

(0,x_1)\times(0,1)\qquad\text{и}\qquad (x_m,1)\times(0,1).

Дотук използвахме

m+n+2

правоъгълника.Какво може да остане непокрито? Само точки, които лежат между две точки от

S

с една и съща

y

-координата и със съседни

x

-координати. Ако хоризонтално ниво съдържа

r

точки от

S

, то дава

r-1

такива съседни двойки. Като сумираме по всички различни

y

-координати, получаваме най-много

n-q\le n-m

двойки, където

q

е броят на различните

y

-координати, а по избора ни

q\ge m

. За всяка такава съседна двойка с координати

(x_i,y)

(x_{i+1},y)

добавяме много тънък правоъгълник

(x_i,x_{i+1})\times(y-\varepsilon,y+\varepsilon),

като

\varepsilon\gt{}0

се избира достатъчно малко, за да не се включват други точки от

S

. Това покрива всички останали точки и използва най-много

n-m

допълнителни правоъгълника. Общият брой е най-много

(m+n+2)+(n-m)=2n+2.

Така долната граница се достига, следователно търсеното най-малко

k

2n+2

Отвори задачатаEvan Chen VONVON TSTST 2022/1Условие — източник

Задача 3

Пълен запис

Условие

Да се определят всички положителни цели числа

N

, за които съществува строго растяща редица от положителни цели числа

s_0\lt{}s_1\lt{}s_2\lt{}\dots

със следните свойства: 1. редицата

s_1-s_0,s_2-s_1,s_3-s_2,\dots

е периодична; 2.

s_{s_n}-s_{s_{n-1}}\le N\lt{}s_{1+s_n}-s_{s_{n-1}}

за всяко положително цяло число

n

Решение

Отговорът е: всички

N

, за които

t^2\le N\lt{}t^2+t

за някое положително цяло число

t

. Първо, ако

t^2\le N\lt{}t^2+t

, редицата

s_n=tn+1

удовлетворява двете условия. Остава да докажем, че други стойности на

N

не са възможни. Нека

a_n=s_n-s_{n-1}

и нека

p

е минималният период на редицата

(a_n)

. За всяко

k\ge0

дефинираме

f(k)

като цялото число, за което

s_{f(k)}-s_k\le N\lt{}s_{f(k)+1}-s_k.

От условието следва, че

f(s_{n-1})=s_n

за всяко

n\ge1

. Ще докажем, че

s_i\not\equiv s_j\pmod p

за всички

i\lt{}j\lt{}i+p

. Да допуснем противното, т.е.

s_i\equiv s_j\pmod p

за някои такива

i,j

. Тогава, понеже

(a_n)

е периодична с период

p

, имаме

a_{s_i+k}=a_{s_j+k}\quad\text{за всяко }k\ge0,

и следователно

s_{s_i+k}-s_{s_i}=s_{s_j+k}-s_{s_j}\quad\text{за всяко }k\ge0.

Оттук получаваме

a_{i+1}=f(s_i)-s_i=f(s_j)-s_j=a_{j+1}

и също

s_{i+1}=f(s_i)\equiv f(s_j)=s_{j+1}\pmod p

. Повтаряйки същия аргумент индуктивно, получаваме

a_{i+k}=a_{j+k}

за всяко

k\ge0

, което дава период

j-i\lt{}p

на

(a_n)

- противоречие. Следователно за всяко

i

числата

s_i,s_{i+1},\ldots,s_{i+p-1}

образуват пълна система от остатъци по модул

p

. В частност

s_{i+p}\equiv s_i\pmod p

за всяко

i

. Нека

T=s_p-s_0=a_1+a_2+\cdots+a_p.

Понеже

(a_n)

е периодична с период

p

, за всички

i,k

имаме

s_{i+kp}-s_i=kT.

От

s_p\equiv s_0\pmod p

следва

p\mid T

. Тогава, прилагайки последната формула с

i=s_0

k=T/p

, получаваме

s_{s_p}-s_{s_0}=\frac Tp\cdot T=\frac{T^2}{p}.

Сумираме неравенствата

s_{s_n}-s_{s_{n-1}}\le N\lt{}

s_{s_n+1}-s_{s_{n-1}}=s_{s_n}-s_{s_{n-1}}+a_{s_n+1}

за

n=1,2,\ldots,p

. Лявата страна телескопира и дава

\frac{T^2}{p}=s_{s_p}-s_{s_0}\le Np.

От друга страна, понеже

s_1+1,s_2+1,\ldots,s_p+1

също образуват пълна система от остатъци по модул

p

, имаме

a_{s_1+1}+a_{s_2+1}+\cdots+a_{s_p+1}=T.

Затова

Np\lt{}\frac{T^2}{p}+T.

Делим на

p

и поставяме

t=T/p\in\mathbb Z^+

. Получаваме точно

t^2\le N\lt{}t^2+t,

както трябваше.

Отвори задачатаEvan Chen VONVON TSTST 2022/3Условие — източник

Задача 4

Пълен запис

Условие

Функция

f \colon \mathbb N \to \mathbb N

има следното свойство: за всички положителни цели числа

m

n

точно едно от числата

f(m+1), f(m+2), \dots, f(m+f(n))

се дели на

n

. Докажете, че

f(n)=n

за безбройно много положителни цели числа

n

Решение

Започваме със следното твърдение. Твърдение. Ако

a\mid b

, то

f(a)\mid f(b)

. Доказателство. От условието, приложено за

n=a

, следва, че множеството

S_a=\{t\ge2: a\mid f(t)\}

е аритметична прогресия с разлика

f(a)

. По същия начин

S_b=\{t\ge2: b\mid f(t)\}

е аритметична прогресия с разлика

f(b)

. От

a\mid b

следва

S_b\subseteq S_a

. Аритметична прогресия с разлика

x

може да се съдържа в аритметична прогресия с разлика

y

само ако

y\mid x

. Следователно

f(a)\mid f(b)

. Нека сега

a\ge2

е произволно положително цяло число. Понеже и

f(a)

, и

f(2a)

се делят на

f(a)

, сред

a+1

последователни стойности на

f

има поне две, делящи се на

f(a)

. От условието за

n=f(a)

следва, че

f(f(a))\le a

. От друга страна, точно едно от числата

f(2), f(3), \dots, f(1+f(a))

се дели на

a

; нека това е

f(t)

. Тогава

S_a=\{t,t+f(a),t+2f(a),\dots\}.

Понеже

t\mid2t

, от доказаното твърдение получаваме

f(t)\mid f(2t)

. А тъй като

a\mid f(t)

, следва

a\mid f(2t)

, така че

2t\in S_a

. Следователно

t

е кратно на

f(a)

. От

2\le t\le1+f(a)

f(a)\ge2

получаваме

t=f(a)

. Значи

f(f(a))

се дели на

a

. Заедно с

f(f(a))\le a

това дава

f(f(a))=a.

За

a=1

също имаме

f(f(1))=1

, защото условието при

n=1

веднага дава

f(1)=1

. Следователно

f(f(a))=a

за всяко

a

, т.е.

f

е биекция. Освен това вече знаем, че

f(a)\mid f(b)

влече

f(f(a))\mid f(f(b))

, тоест

a\mid b

. Значи

a\mid b \quad\Longleftrightarrow\quad f(a)\mid f(b).

Заедно с биективността това показва, че

f(n)

има същия брой положителни делители като

n

. Нека

p

е просто число. Тогава

f(p)=q

също е просто число. Ако

q\ne p

, то от

f(p)\mid f(pq)

f(q)\mid f(pq)

следва

pq\mid f(pq)

. Понеже

pq

f(pq)

имат еднакъв брой положителни делители, получаваме

f(pq)=pq

. Следователно за всяко просто число

p

е вярно поне едно от двете: или

f(p)=p

, или

f(pf(p))=pf(p)

. Така за всяко просто число получаваме положително цяло число, което е неподвижна точка на

f

. Тези числа са безбройно много: ако

f(p)=p

, получаваме самото просто число

p

, а иначе получаваме произведението

pf(p)

, което има

p

като делител и не може да съвпада за безбройно много различни прости числа. Значи

f(n)=n

за безбройно много

n

Отвори задачатаEvan Chen VONVON TSTST 2022/4Условие — източник

Задача 5

Пълен запис

Условие

Нека

A_1,\ldots,A_{2022}

са върховете на правилен

2022

-ъгълник в равнината. Алис и Боб играят игра. Алис тайно избира права и оцветява всички точки от едната страна на правата в синьо, а всички точки от другата страна - в червено. Точките върху самата права се оцветяват в синьо, така че всяка точка от равнината е или червена, или синя. Боб не вижда цветовете на точките. На всеки ход Боб избира точка в равнината, не непременно измежду

A_1,\ldots,A_{2022}

, а Алис му казва вярно цвета на тази точка. Кое е най-малкото число

Q

, за което Боб има стратегия винаги да определи цветовете на точките

A_1,\ldots,A_{2022}

за

Q

хода?

Решение

Отговорът е

22

. За долната граница отбелязваме, че има

2022\cdot2021+2\gt{}2^{21}

възможни оцветявания на върховете. Ако Боб зададе по-малко от

22

въпроса, той получава най-много

2^{21}

различни последователности от отговори, така че не може да различи всички възможни оцветявания. Следователно

Q\ge22

. Ще покажем стратегия с

22

въпроса. Основното наблюдение е, че множеството от червените точки е изпъкнало, както и множеството от сините точки. Затова, ако няколко точки са в един и същи цвят, цялата им изпъкнала обвивка е в този цвят. Лема 1. Нека

B_0,B_1,\ldots,B_{k+1}

са равноотдалечени точки върху една окръжна дъга, като цветовете на

B_0

B_{k+1}

са известни и различни. Тогава цветовете на

B_1,\ldots,B_k

могат да се определят с

\lceil\log_2 k\rceil

въпроса. Доказателство. Съществува индекс

0\le i\le k

, такъв че

B_0,\ldots,B_i

са в цвета на

B_0

, а

B_{i+1},\ldots,B_{k+1}

са в цвета на

B_{k+1}

. Иначе две едноцветни отсечки от различни цветове биха се пресекли, което е невъзможно по изпъкналост. Следователно можем да намерим мястото на прехода чрез двоично търсене. Лема 2. Нека

B_0,B_1,\ldots,B_{k+1}

са равноотдалечени точки върху една окръжна дъга и нека цветовете на

B_0

B_{\lceil k/2\rceil}

B_{k+1}

са известни и червени. Тогава е вярно поне едно от следните две твърдения: всички точки

B_1,\ldots,B_{\lceil k/2\rceil}

са червени или всички точки

B_{\lceil k/2\rceil},\ldots,B_k

са червени. Освен това с един въпрос можем да разберем кой от двата случая е изпълнен. Доказателство. Съществуването следва от същата изпъкналост като в първата лема. За да различим случаите, избираме точка

P

, така че всички

B_0,\ldots,B_{k+1}

да лежат между лъчите

PB_0

PB_{\lceil k/2\rceil}

, точките от първата половина да лежат вътре в триъгълника

PB_0B_{\lceil k/2\rceil}

, а точките от втората половина - извън него. Такава точка се намира, като гледаме близо до пресечната точка на правите

B_0B_1

B_{\lceil k/2\rceil-1}B_{\lceil k/2\rceil}

. Ако

P

е червена, всички вътрешни точки са червени, защото лежат в изпъкналата обвивка на червените точки

P

B_0

B_{\lceil k/2\rceil}

. Ако

P

е синя и някоя точка

B_i

i\gt{}\lceil k/2\rceil

е синя, отсечката

PB_i

е синя, а тя пресича червената отсечка

B_0B_{\lceil k/2\rceil}

- противоречие. Следователно във втория случай всички външни точки са червени. Сега стратегията е следната. Боб първо пита за цвета на

A_1

; без ограничение можем да го наречем червен. Ще докажем по индукция, че ако Боб не знае цветовете на най-много

2^k-1

последователни върха

A_i,\ldots,A_j

, а всички останали върхове са известни като червени, тогава той може да довърши за

2k-1

въпроса. При

k=1

има само една неизвестна точка и твърдението е ясно. Нека

k\gt{}1

. Боб пита за средната точка

A_{i+\lceil (j-i+1)/2\rceil}.

Ако тя е синя, двете неизвестни части от дъгата вече имат известни краища с различни цветове, така че по Лема 1 Боб довършва с най-много

2\log_2\left\lceil\frac{j-i+1}{2}\right\rceil\le2(k-1)

допълнителни въпроса, общо не повече от

2k-1

. Ако средната точка е червена, Боб задава още един въпрос от Лема 2 и научава, че поне едната половина от неизвестната дъга е изцяло червена. Остават най-много

2^{k-1}-1

последователни неизвестни точки, а вече са използвани два въпроса; по индукционната хипотеза са достатъчни още

2(k-1)-1

въпроса. Общо това са

2k-1

. След първия въпрос за

A_1

остават

2021\le2^{11}-1

неизвестни върха. Прилагаме доказаното с

k=11

и получаваме още

21

въпроса, т.е. общо

22

Отвори задачатаEvan Chen VONVON TSTST 2022/5Условие — източник

Задача 8

Пълен запис

Условие

Намерете всички функции

f \colon \mathbb N \to \mathbb Z

, такива че

\left\lfloor \frac{f(mn)}{n}\right\rfloor=f(m)

за всички положителни цели числа

m

n

Решение

Отговорът е следният. Работят двете семейства

f(n)=\lfloor \alpha n\rfloor \quad (\alpha\in\mathbb R)

f(n)=\lceil \alpha n\rceil-1 \quad (\alpha\in\mathbb R).

При ирационално

\alpha

двете формули съвпадат. Проверката е непосредствена и се свежда до тъждеството

\left\lfloor \frac{\lfloor xn\rfloor}{n}\right\rfloor=\lfloor x\rfloor,

валидно за всяко положително цяло число

n

и всяко реално число

x

; аналогичната проверка за горната цяла част е същата. Ще докажем, че други решения няма. Нека

f

е решение и дефинираме редицата

a_n=\frac{f(n!)}{n!} \qquad (n=1,2,\dots).

Прилагайки даденото условие към двойката

(n!,n+1)

, получаваме

a_{n+1}\in\left[a_n,a_n+\frac1{n!}\right).

Следователно редицата

a_1,a_2,\dots

е не намаляваща и е ограничена отгоре, например от

a_1+e

. Значи тя има граница; да я означим с

\alpha

. Ако съществува

k

, за което

a_k=\alpha

, то

a_\ell=\alpha

за всяко

\ell\gt{}k

. За всяко положително цяло число

m

избираме

\ell\gt{}k

, така че

m\mid \ell!

. Прилагаме условието с

mn=\ell!

и получаваме

f(m)=\left\lfloor \frac{f(\ell!)}{\ell!/m}\right\rfloor=\lfloor \alpha m\rfloor.

Това е първото семейство. Остава случаят, когато няма

k

a_k=\alpha

. Тогава

a_k\lt{}\alpha

за всяко

k

. Фиксираме положително цяло число

m

и избираме

\ell

, за което

m\mid\ell!

a_\ell=\alpha-x

с произволно малко положително

x

. Отново от условието при

mn=\ell!

имаме

f(m)=\left\lfloor \frac{f(\ell!)}{\ell!/m}\right\rfloor=\left\lfloor \alpha m-mx\right\rfloor.

Ако

\alpha m

е цяло число, избираме

\ell

така, че

mx\lt{}1

, и получаваме

f(m)=\alpha m-1=\lceil \alpha m\rceil-1.

Ако

\alpha m

не е цяло число, избираме

\ell

така, че

mx\lt{}\{\alpha m\}

, и пак получаваме

f(m)=\lfloor \alpha m\rfloor=\lceil \alpha m\rceil-1.

Следователно във втория случай

f

е от второто семейство. Това завършва класификацията.

Отвори задачатаEvan Chen VONVON TSTST 2022/8Условие — източник

Задача 9

Пълен запис

Условие

Нека

k\gt{}1

е фиксирано положително цяло число. Докажете, че ако

n

е достатъчно голямо положително цяло число, съществува редица от цели числа със следните свойства: 1. всеки член на редицата е между

1

n

включително; 2. за всеки два различни последователни отрязъка от редицата с дължина между

2

k

включително, мултимножествата от стойностите в тези два отрязъка са различни; 3. редицата има дължина поне

0.499n^2

Решение

Ще наричаме една редица

(n,k)

-добра, ако е крайна редица от цели числа между

1

n

включително и удовлетворява второто условие от задачата. Трябва да докажем, че за всяко фиксирано

k

и всяко достатъчно голямо

n

има

(n,k)

-добра редица с дължина поне

0.499n^2

. Първо работим по модул

n

, където

n=p^m

е степен на просто число и

p\gt{}k+1

. Нека

0\lt{}g\lt{}\frac nk-1

\gcd(g,n)=1

, и нека

a

е най-малкото положително цяло число, за което

g^a\equiv\pm1\pmod n.

Ще докажем, че при тези условия съществува

(n,k)

-добра редица от остатъци по модул

n

с дължина

a(n+2)+2

. Накрая остатъкът

r

ще се замени с числото

r+1

. Ще използваме следната лема. Нека

S

е множеството от остатъците на аритметична прогресия с дължина

i\le k

и разлика, взаимнопроста с

n

. Тогава съществуват единствени

0\lt{}d\le\frac n2

0\le b\lt{}n

, за които

S=\{b,b+d,\ldots,b+(i-1)d\}\pmod n.

Наистина, ако

i=2j+1

, средният член

u

се намира като средно аритметично на остатъците в

S

, защото

i

е обратимо по модул

n

. Ако

X

е сумата от квадратите на остатъците, то

X\equiv(2j+1)u^2+d^2\frac{j(j+1)(2j+1)}3\pmod n,

откъдето се намира

d^2

. Ако

i=2j

, отново намираме средното

u

и записваме прогресията около него като

u-(2j-1)h,u-(2j-3)h,\ldots,u+(2j-1)h,

където действителната разлика е

2h

. Тогава

X\equiv2ju^2+h^2\frac{(2j-1)2j(2j+1)}3\pmod n,

така че намираме

h^2

, а оттам и разликата

2h

до знак. Понеже

n=p^m

с нечетно

p

и разглежданата разлика е взаимнопроста с

n

, от квадрат по модул

n

тя се възстановява еднозначно до знак. Това доказва лемата. За

0\le \ell\lt{}a

дефинираме редицата

C_\ell: 0,g^\ell,g^\ell,2g^\ell,3g^\ell,

\ldots,(n-1)g^\ell,(n-1)g^\ell\pmod n.

Сега построяваме редицата

S_n

, като започваме с

0

, след това поставяме последователно

C_0,C_1,\ldots,C_{a-1}

, и накрая добавяме още един

0

. Ясно е, че дължината е

a(n+2)+2

. Важното наблюдение е следното: ако последователен отрязък от

S_n

с дължина най-много

k

съдържа два равни остатъка, тези два остатъка са съседни в отрязъка. Ако отрязъкът лежи изцяло в някое

C_\ell

, това е очевидно от конструкцията. Иначе той пресича границата между

C_{\ell-1}

C_\ell

и има части от вида

(n-r)g^{\ell-1},\ldots,(n-1)g^{\ell-1},(n-1)g^{\ell-1}

0,g^\ell,g^\ell,2g^\ell,\ldots,sg^\ell,

където

r+s\le k-3

. Ако има несъседно съвпадение между двете части, то за някои

0\lt{}u\le r

0\lt{}v\le s

ще имаме

(n-u)g^{\ell-1}\equiv vg^\ell\pmod n,

тоест

u+gv\equiv0\pmod n

. Но

0\lt{}u+gv\lt{}k+kg\lt{}n

, невъзможно. Остава да покажем, че от мултимножеството на всеки отрязък с дължина

2\le i\le k

можем да възстановим самия отрязък. Нека

M

е такова мултимножество от остатъци. Ако в

M

има повторен остатък, предишното наблюдение оставя само няколко случая. Ако

0

се среща повече от веднъж, отрязъкът е началото на

S_n

. Ако има два различни повтарящи се остатъка, те трябва да са крайните повторения около граница между две съседни редици

C_{\ell-1}

C_\ell

, т.е. копия на

-g^{\ell-1}

и на

g^\ell

; индексът

\ell

се определя еднозначно. След деление на

g^{\ell-1}

остатъците се разделят като

-r,-(r-1),\ldots,-1,-1

0,g,g,2g,\ldots,sg,

а неравенствата

sg\le kg\lt{}n-k

-r\equiv n-r\ge n-k

определят еднозначно

r

s

. Ако има повторен само остатък

g^\ell

, отрязъкът е в началото на

C_\ell

, евентуално с последни членове от

C_{\ell-1}

; след същото деление получаваме лесно различими възможности

g,g,2g,\ldots,tg

, евентуално заедно с

0

или

0,-1

. Случаят с единствен повторен остатък

-g^\ell

е аналогичен за края на

C_\ell

, като използваме, че

-t\equiv n-t\ge\frac n2

, докато

g\lt{}\frac n2

. Ако в

M

няма повторен остатък, то отрязъкът не съдържа и двете копия на някое от специално повторените числа. Затова той или лежи изцяло в някое

C_\ell

, където е част от аритметична прогресия и се възстановява от предишната лема, или пресича границата между

C_\ell

C_{\ell+1}

и тогава е отрязък от тричленната редица

(-g^\ell,0,g^{\ell+1})

, което също се разпознава еднозначно. Следователно

S_n

няма две различни отрязъка с еднакво мултимножество от стойности и е

(n,k)

-добра. Сега фиксираме

k

и вземаме просто число

p\gt{}k+1

. При

n=p^2

нека

g

е най-малкият примитивен корен по модул

p^2

. Тогава

a=\frac{p(p-1)}2

. Ще покажем, че

g\lt{}p

, откъдето за достатъчно голямо

p

имаме

g\lt{}\frac{p^2}{k}-1

и можем да приложим построението. Нека

g_0

е примитивен корен по модул

p

. Всеки от остатъците

g_0+tp

0\le t\lt{}p

, има ред, кратен на

p-1

по модул

p^2

, и е примитивен корен по модул

p^2

, освен ако

(g_0+tp)^{p-1}\equiv1\pmod{p^2}.

Но

(g_0+tp)^{p-1}\equiv g_0^{p-1}+g_0^{p-2}tp\pmod{p^2},

така че точно една стойност на

t

дава ред

p-1

, а останалите дават примитивни корени по модул

p^2

. Следователно или има примитивен корен между

0

p

, или всички остатъци с ред

p-1

по модул

p^2

лежат между

0

p

. Второто е невъзможно: ако

x

има ред

p-1

, то и

x^{-1}

има ред

p-1

, но два остатъка между

0

p

не могат да са взаимнообратни по модул

p^2

, освен тривиалния остатък

1

, който няма ред

p-1

. Значи

g\lt{}p

. Получаваме

(p^2,k)

-добра редица с дължина

\frac{p(p-1)(p^2+2)}2.

Накрая нека

N

е достатъчно голямо. По теоремата за простите числа можем да изберем просто

p\lt{}\sqrt N

\frac p{\sqrt N}

произволно близко до

1

. Построената редица използва само остатъци по модул

p^2

, които заменяме с числата

1,2,\ldots,p^2

; понеже

p^2\le N

, това е редица от числа между

1

N

. Дължината й е асимптотично

\frac12p^4

, а понеже

p^2

може да е произволно близко до

N

, за всички достатъчно големи

N

тя е поне

0.499N^2

. Това доказва задачата.

Отвори задачатаEvan Chen VONVON TSTST 2022/9Условие — източник

2023

9 задачи

Задача 1

Пълен запис

Условие

Нека

ABC

е триъгълник с медицентър

G

. Точките

R

S

са избрани съответно върху лъчите

GB

GC

така, че

\angle ABS=\angle ACR=180^\circ-\angle BGC

. Да се докаже, че

\angle RAS+\angle BAC=\angle BGC

Решение

Нека

M

N

са средите съответно на

AC

AB

. Понеже

G

е медицентър, точките

B,G,M

са колинеарни, както и точките

C,G,N

. От условието получаваме

\angle ACR=180^\circ-\angle BGC=\angle CGM

. Тъй като

A,M,C

са колинеарни и

R,G,M

са колинеарни, триъгълниците

MCR

MGC

са подобни. Следователно

MC^2=MG\cdot MR

. Но

M

е среда на

AC

, така че

MA=MC

и получаваме

MA^2=MG\cdot MR

. По теоремата за допирателната и хордата това дава

\angle RAC=\angle MGA

. Напълно аналогично, като използваме средата

N

и условието

\angle ABS=180^\circ-\angle BGC=\angle BGN

, получаваме

NA^2=NG\cdot NS

и оттук

\angle BAS=\angle AGN

. Сега събираме двете равенства:

\angle RAS+\angle BAC=\angle RAC+\angle BAS=\angle MGA+\angle AGN=\angle MGN

. А понеже

M,G,B

N,G,C

лежат на едни и същи прави, ъгълът

\angle MGN

е равен на

\angle BGC

. Следователно

\angle RAS+\angle BAC=\angle BGC

, както се искаше.

Отвори задачатаEvan Chen VONVON TSTST 2023/1Условие — източник

Задача 2

Пълен запис

Условие

Нека

n\ge m\ge1

са цели числа. Да се докаже, че

\sum_{k=m}^n\left(\frac1{k^2}+\frac1{k^3}\right)\ge m\left(\sum_{k=m}^n\frac1{k^2}\right)^2.

Решение

Ще използваме неравенството на Коши-Шварц в дробна форма. Понеже

\frac1{k^2}+\frac1{k^3}=\frac{k+1}{k^3},

имаме

\begin{align*} \sum_{k=m}^n\left(\frac1{k^2}+\frac1{k^3}\right) &=\sum_{k=m}^n\frac{(1/k^2)^2}{1/(k(k+1))}\\ &\ge\frac{\left(\sum_{k=m}^n\frac1{k^2}\right)^2}{\sum_{k=m}^n\frac1{k(k+1)}}. \end{align*}

А знаменателят се телескопира:

\sum_{k=m}^n\frac1{k(k+1)}=

\sum_{k=m}^n\left(\frac1k-\frac1{k+1}\right)=\frac1m-\frac1{n+1}\lt{}

\frac1m.

Следователно

\sum_{k=m}^n\left(\frac1{k^2}+\frac1{k^3}\right)\gt{}

\frac{\left(\sum_{k=m}^n\frac1{k^2}\right)^2}{1/m} =m\left(\sum_{k=m}^n\frac1{k^2}\right)^2,

което е дори малко по-силно от исканото.

Отвори задачатаEvan Chen VONVON TSTST 2023/2Условие — източник

Задача 3

Пълен запис

Условие

Да се намерят всички положителни цели числа

n

, за които е възможно някои клетки на безкрайна решетка от единични квадрати да се оцветят в червено така, че всеки правоъгълник, съставен от точно

n

клетки и със страни по линиите на решетката, да съдържа нечетен брой червени клетки.

Решение

Ще докажем, че това е възможно за всяко положително цяло число

n

. Да наречем едно положително цяло число добро, ако за него съществува такова оцветяване. Ще използваме две твърдения: (1) ако

n

е добро и

p

е нечетно просто число, то

pn

е добро; (2) за всяко

k\ge0

числото

2^k

е добро. Те дават резултата, защото всяко положително цяло число е произведение на степен на

2

и нечетни прости множители. Да докажем (1). Ако всеки правоъгълник от

n

клетки съдържа нечетен брой червени клетки, то всеки правоъгълник от

pn

клетки също съдържа нечетен брой червени клетки. Наистина, ако размерите му са

a\times b

ab=pn

, то поне една от страните се дели на

p

, така че правоъгълникът се разбива на

p

правоъгълника от по

n

клетки. Всеки от тях има нечетен брой червени клетки, а сумата на нечетен брой нечетни числа е нечетна. Остава да докажем (2). Нека

n=2^k

. Правоъгълниците от

n

клетки имат точно

k+1

възможни форми:

2^m\times2^{k-m}

за

0\le m\le k

. За всяка такава форма ще построим помощно оцветяване. Номерираме клетките с двойки

(x,y)\in\mathbb Z^2

според координатите на долния им ляв ъгъл и оцветяваме клетката

(x,y)

в червено точно когато

x

има остатък

0

по модул

2^m

y

има остатък

0

по модул

2^{k-m}

. Всеки правоъгълник с форма

2^m\times2^{k-m}

съдържа точно по един представител на всеки остатък за

x

по модул

2^m

и на всеки остатък за

y

по модул

2^{k-m}

, следователно съдържа точно една червена клетка. Сега да разгледаме правоъгълник с друга форма

2^\ell\times2^{k-\ell}

. Ако

\ell\gt{}m

, броят на допустимите координати

x

2^{\ell-m}

, което е четно, а броят на допустимите координати

y

0

или

1

. Значи общият брой червени клетки е четен. Случаят

\ell\lt{}m

е аналогичен, като ролите на

x

y

се разменят. Накрая вземаме сумата по модул

2

на тези

k+1

помощни оцветявания: една клетка е червена в окончателното оцветяване точно когато е червена в нечетен брой от помощните оцветявания. За правоъгълник с форма

2^m\times2^{k-m}

съответното помощно оцветяване дава нечетен брой червени клетки, а всички останали помощни оцветявания дават четен брой. Следователно окончателното оцветяване дава нечетен брой червени клетки за всяка възможна форма. Така

2^k

е добро за всяко

k\ge0

, а заедно с (1) това доказва, че всички положителни цели числа

n

работят.

Отвори задачатаEvan Chen VONVON TSTST 2023/3Условие — източник

Задача 4

Пълен запис

Условие

Нека

n\ge3

е цяло число и нека

K_n

е пълният граф с

n

върха. Всяко ребро на

K_n

е оцветено в червено, зелено или синьо. Нека

A

е броят на триъгълниците, чиито три ребра са в един и същ цвят, а

B

е броят на триъгълниците, чиито три ребра са в три различни цвята. Да се докаже, че

B\le2A+\frac{n(n-1)}3.

Решение

Разглеждаме всички ненаредени двойки различни ребра, които имат общ връх. Ще ги наричаме ъгли. Даваме на всеки такъв ъгъл заряд

+2

, ако двете му ребра са с един и същ цвят, и заряд

-1

иначе. Ще пресметнем общия заряд по два начина. Първо сумираме по триъгълници. Всеки ъгъл принадлежи на точно един триъгълник. Ако триъгълникът е едноцветен, трите му ъгъла дават заряд

3\cdot2=6

. Ако използва точно два цвята, зарядът е

2-1-1=0

. Ако трите му ребра са в различни цветове, зарядът е

-3

. Следователно общият заряд е

6A-3B.

Сега сумираме по върхове. Нека от даден връх излизат

a

червени,

b

зелени и

c

сини ребра. Зарядът на ъглите с център този връх е

\begin{align*} 2\left(\binom a2+\binom b2+\binom c2\right)-(ab+ac+bc) &=a^2+b^2+c^2-ab-ac-bc-(a+b+c)\\ &=a^2+b^2+c^2-ab-ac-bc-(n-1)\\ &\ge -(n-1), \end{align*}

защото

a^2+b^2+c^2-ab-ac-bc\ge0

. Сумирайки по всички

n

върха, получаваме, че общият заряд е поне

-n(n-1)

. Затова

6A-3B\ge -n(n-1),

което е еквивалентно на

B\le2A+\frac{n(n-1)}3.

Това доказва твърдението.

Отвори задачатаEvan Chen VONVON TSTST 2023/4Условие — източник

Задача 5

Пълен запис

Условие

Нека

a

b

c

са комплексни числа с произведение

1

. Да се предположи, че никое от тях не е реално и никое няма модул

1

. Дефинираме

p=(a+b+c)+\left(\frac1a+\frac1b+\frac1c\right),

\qquad q=\frac{a}{b}+\frac{b}{c}+\frac{c}{a}.

Ако

p

q

са реални числа, да се намерят всички възможни стойности на наредената двойка

(p,q)

Решение

Ще докажем, че единствената възможност е

(p,q)=(-3,3)

. Записваме

a=\frac yx,\qquad b=\frac zy,\qquad c=\frac xz

за ненулеви комплексни числа

x,y,z

. Тогава

abc=1

автоматично. Пряко пресмятане дава

p+3=3+\sum_{\mathrm{cyc}}\left(\frac xy+\frac yx\right)=

\frac{(x+y+z)(xy+yz+zx)}{xyz}

q-3=-3+\sum_{\mathrm{cyc}}\frac{y^2}{zx}=\frac{x^3+y^3+z^3-3xyz}{xyz}=

\frac{(x+y+z)(x^2+y^2+z^2-xy-yz-zx)}{xyz}.

Ако

x+y+z=0

, веднага получаваме

p=-3

q=3

. Остава да покажем, че друг случай е невъзможен. Да допуснем, че

x+y+z\ne0

. Умножаваме едновременно

x,y,z

по подходящо ненулево комплексно число, така че

x+y+z

да стане реално. Тъй като

3(p+3)+(q-3)=\frac{(x+y+z)^3}{xyz}

е реално, следва, че

xyz

е реално. Понеже и

p+3

е реално, от първата формула получаваме, че

xy+yz+zx

също е реално. Следователно

x,y,z

са корени на кубичен полином с реални коефициенти. Значи или трите числа са реални, или две от тях са комплексно спрегнати. В първия случай

a,b,c

са реални, което е забранено. Във втория случай отношението на спрегнатата двойка има модул

1

, така че едно от

a,b,c

има модул

1

, което също е забранено. Следователно непременно

x+y+z=0

, а тогава

(p,q)=(-3,3)

. Остава да видим, че тази двойка се постига. Например вземаме

x=3

y=4i

z=-(3+4i)

и дефинираме

a=y/x

b=z/y

c=x/z

. Тогава

abc=1

, никое от

a,b,c

не е реално или с модул

1

, а понеже

x+y+z=0

, получаваме точно

(p,q)=(-3,3)

Отвори задачатаEvan Chen VONVON TSTST 2023/5Условие — източник

Задача 6

Пълен запис

Условие

Нека

ABC

е разностранен триъгълник и нека

P

Q

са две различни точки във вътрешността му. Да се предположи, че ъглополовящите на

\angle PAQ

\angle PBQ

\angle PCQ

са съответно височините на триъгълника

ABC

. Да се докаже, че средата на

PQ

лежи на правата на Ойлер на

ABC

Решение

Нека

H

е ортоцентърът на

ABC

. Първо ще използваме следния стандартен факт: съществува точка

P'

такава, че

\angle APH+\angle AP'H=\angle BPH+\angle BP'H=

\angle CPH+\angle CP'H=0

като насочени ъгли. След инверсия с център

H

това е точно твърдението, че образът на

P

има изогонално спрегната точка спрямо образа на триъгълника

ABC

. Нека

X

Y

Z

са отраженията на

P

съответно спрямо правите

AH

BH

CH

. Нека

Q'

е образът на

Q

при инверсията спрямо окръжността

(PXYZ)

. Ще покажем, че четириъгълниците

ABCP'

XYZQ'

са подобни в противоположна ориентация. Наистина,

\angle YXZ=\angle YPZ=\angle(BH,CH)=-\angle BAC,

и аналогичните равенства важат циклично. Освен това

\angle HQ'X=-\angle HXQ=-\angle HXA=\angle HPA=-\angle HP'A,

и отново циклично; събирането по двойки дава

\angle YQ'Z=-\angle BP'C

и аналогичните две равенства. Следователно

ABCP'

XYZQ'

са подобни. Нека

O

е центърът на описаната окръжност на

ABC

. От полученото подобие следва

ABCOP'\sim XYZHQ'

. Понеже

\angle HP'A=\angle OP'A

, точката

P'

лежи на

OH

. Подобно пренасяне показва, че

Q'

лежи на правата на Ойлер на триъгълника

XYZ

. Остава да преведем това обратно към средата на

PQ

. Нека

G_1

G_2

са медицентровете съответно на

ABC

XYZ

. Работим със знакови лица. Понеже

Q'

G_2

H

са колинеарни, имаме

[G_1HP]+[G_1HQ]

=\frac{[AHP]+[BHP]+[CHP]}3+\frac{[AHQ]+[BHQ]+[CHQ]}3

=\frac{[AHQ]-[AHX]+[BHQ]-[BHY]+[CHQ]-[CHZ]}3

=\frac{[HQX]+[HQY]+[HQZ]}3=[QG_2H]=0.

Следователно точките

P

Q

имат противоположни знакови отстояния спрямо правата

G_1H

. Значи

G_1H

минава през средата на

PQ

. Но

G_1H

е правата на Ойлер на

ABC

, което доказва твърдението.

Отвори задачатаEvan Chen VONVON TSTST 2023/6Условие — източник

Задача 7

Пълен запис

Условие

В редица от

2023

монети най-лявата монета е тура, а след това монетите се редуват тура, ези, тура, ези и така нататък. С всяка операция избираме една монета и я обръщаме, но след първата операция всяка следваща избрана монета трябва да е съседна на монетата, избрана в предишната операция. Да се намери най-малкият възможен брой операции, след който всички монети могат да бъдат ези.

Решение

Ще докажем по-общо твърдение за

4n+3

монети. Отговорът тогава е

8n+4

, а при

4n+3=2023

имаме

n=505

, така че търсеният брой е

4044

. За долната оценка номерираме монетите отляво надясно. Монетите на нечетни позиции започват тура и трябва да бъдат обърнати нечетен брой пъти; монетите на четни позиции започват ези и трябва да бъдат обърнати четен брой пъти. Първата и последната монета са на нечетни позиции и трябва да се обърнат поне веднъж. Понеже последователните операции са върху съседни монети, за да се стигне от единия край до другия, трябва да се посетят всички позиции. Значи всяка четна позиция се обръща поне два пъти, общо поне

4n+2

обръщания върху четни позиции. Броят обръщания върху нечетни позиции се различава от него с най-много

1

, а освен това е четен, защото има

2n+2

нечетни позиции и всяка от тях се обръща нечетен брой пъти. Следователно и върху нечетни позиции има поне

4n+2

обръщания. Общо са нужни поне

8n+4

операции. Конструкцията постига тази граница: за всяко

k=0,1,\ldots,n-1

извършваме последователно операциите върху позициите

4k+1,4k+2,4k+3,4k+2,

4k+3,4k+4,4k+3,4k+4,

а накрая върху

4n+1,4n+2,4n+3,4n+2.

Лесна проверка по четност показва, че всяка нечетна позиция е обърната нечетен брой пъти, всяка четна позиция - четен брой пъти, и всички избрани позиции са съседни на предишната. Затова

8n+4

операции са достатъчни и необходими.

Отвори задачатаEvan Chen VONVON TSTST 2023/7Условие — източник

Задача 8

Пълен запис

Условие

Нека

ABC

е равностранен триъгълник със страна

1

. Точките

A_1

A_2

са избрани върху страната

BC

, точките

B_1

B_2

са избрани върху страната

CA

, а точките

C_1

C_2

са избрани върху страната

AB

така, че

BA_1\lt{}BA_2

CB_1\lt{}CB_2

AC_1\lt{}AC_2

. Да се предположи, че отсечките

B_1C_2

C_1A_2

A_1B_2

се пресичат в една точка, а периметрите на триъгълниците

AB_2C_1

BC_2A_1

CA_2B_1

са равни. Да се намерят всички възможни стойности на този общ периметър.

Решение

Ще докажем, че единствената възможна стойност на общия периметър е

1

. Първо записваме една стандартна лема. Ако шестте точки са избрани така, че триъгълниците

AB_2C_1

BC_2A_1

CA_2B_1

имат периметър

1

, тогава правите

B_1C_2

C_1A_2

A_1B_2

се пресичат в една точка. Наистина, в равностранен триъгълник със страна

1

условието

AB_2+B_2C_1+C_1A=1

е точно условието правата

B_2C_1

да е допирателна към вписаната окръжност на

ABC

. Аналогично

C_2A_1

A_2B_1

също са допирателни към същата окръжност. Следователно шестоъгълникът с върхове

A_1,A_2,B_1,B_2,C_1,C_2

е описан около тази окръжност, а по теоремата на Брианшон неговите главни диагонали

A_1B_2

A_2C_1

B_1C_2

се пресичат в една точка. Това доказва лемата. Нека сега общият периметър е

p

. Ясно е, че

p\gt{}0

. Ако

p=1

, лемата показва, че такава конфигурация наистина съществува; например може да се вземат трите малки триъгълника равностранни със страна

1/3

. Остава да покажем, че

p\ne1

е невъзможно. Прилагаме хомотетия към отсечката

B_2C_1

с център

A

и коефициент

1/p

и получаваме отсечката

B_2'C_1'

. По същия начин, циклично, получаваме

C_2'A_1'

A_2'B_1'

. Новите три малки триъгълника имат периметър

1

, затова по лемата правите

B_1'C_2'

C_1'A_2'

A_1'B_2'

се пресичат в една точка. Ако

p\lt{}1

, тогава новите точки са по-далече от съответните върхове от първоначалните точки. Правите

B_1C_2

C_1A_2

A_1B_2

трябва да лежат съответно във вътрешностите на трите четириъгълника

BCB_1'C_2'

CAC_1'A_2'

ABA_1'B_2'

. Тези три четириъгълника нямат обща вътрешна точка, което противоречи на това, че дадените три прави се пресичат в една точка. Следователно

p\ge1

. Същият аргумент, приложен с разменени роли на първоначалната и новата конфигурация, дава

p\le1

. Значи непременно

p=1

, както се искаше.

Отвори задачатаEvan Chen VONVON TSTST 2023/8Условие — източник

Задача 9

Пълен запис

Условие

Нека

p

е фиксирано просто число, а

a\ge2

e\ge1

са фиксирани цели числа. За функция

f:\mathbb Z/a\mathbb Z\to\mathbb Z/p^e\mathbb Z

и цяло число

k\ge0

дефинираме

k

-тата крайна разлика

\Delta^k f:\mathbb Z/a\mathbb Z\to\mathbb Z/p^e\mathbb Z

рекурсивно чрез

\Delta^0f(n)=f(n),

\qquad \Delta^k f(n)=\Delta^{k-1}f(n+1)-\Delta^{k-1}f(n)

за

k=1,2,\ldots

. Да се определи броят на функциите

f

, за които съществува

k\ge1

\Delta^k f=f

Решение

Отговорът е

p^{e(a-p^{\nu_p(a)})}.

Поставяме

d=\nu_p(a)

a=p^d b

, така че

p\nmid b

. Ще наричаме функцията

f

съществена, ако

f=\Delta^k f

за някое

k\ge1

. Основното твърдение е следното:

f

е съществена тогава и само тогава, когато за всяко

x\in\mathbb Z/a\mathbb Z

f(x)+f(x+p^d)+\cdots+f(x+(b-1)p^d)=0.

Първо доказваме необходимостта. Нека

h=\Delta^{p^d}g

. От биномната формула за крайни разлики

h(x)=\sum_{j=0}^{p^d}(-1)^j\binom{p^d}{j}g(x+p^d-j).

Всички вътрешни биномни коефициенти

\binom{p^d}{j}

1\le j\le p^d-1

, се делят на

p

, следователно

h(x)\equiv g(x+p^d)+(-1)^{p^d}g(x)\pmod p.

Сумирайки това по

x,x+p^d,\ldots,x+(b-1)p^d

, получаваме сума, която е

0

по модул

p

: за

p

нечетно членовете се телескопират, а за

p=2

множителят

2

също я занулява по модул

2

. Повтаряйки същия аргумент

e

пъти, следва, че ако

h=\Delta^{e p^d}g

, то

h(x)+h(x+p^d)+\cdots+h(x+(b-1)p^d)=0

\mathbb Z/p^e\mathbb Z

. Ако

f

е съществена, тогава

f

лежи в образа на всяка достатъчно голяма степен на

\Delta

, понеже от

f=\Delta^k f

следва

f=\Delta^{mk}f

за всички

m

. В частност

f

лежи в образа на

\Delta^{e p^d}

, и необходимото равенство е доказано. Обратно, нека

S

е множеството от всички функции, които удовлетворяват това равенство. Ясно е, че

\Delta

изпраща

S

в себе си. Достатъчно е да покажем, че

\Delta

е инективно върху

S

; понеже

S

е крайно, тогава

\Delta

е пермутация на

S

, а всяка функция в

S

е периодична под итерациите на

\Delta

, тоест съществена. Ако

f,g\in S

\Delta f=\Delta g

, тогава

g-f

е константа; да пишем

g=f+\lambda

. Прилагайки равенството за

f

и за

g

в един и същ клас

x,x+p^d,\ldots,x+(b-1)p^d

, получаваме

b\lambda=0

\mathbb Z/p^e\mathbb Z

. Понеже

p\nmid b

, числото

b

е обратимо по модул

p^e

, следователно

\lambda=0

f=g

. Значи

\Delta

е инективно върху

S

. Остава броенето. Условието казва, че във всеки от

p^d

-те класа

x,\ x+p^d,\ \ldots,\ x+(b-1)p^d

последната стойност се определя еднозначно от предишните

b-1

стойности. Затова произволно можем да изберем точно

a-p^d

стойности на функцията, всяка по

p^e

начина, а останалите

p^d

стойности са принудени. Следователно броят на функциите е

(p^e)^{a-p^d}=p^{e(a-p^{\nu_p(a)})},

както се искаше.

Отвори задачатаEvan Chen VONVON TSTST 2023/9Условие — източник

2024

9 задачи

Задача 1

Пълен запис

Условие

За всяка наредена двойка цели числа

(i,j)

, не непременно положителни, искаме да изберем точка

P_{i,j}

в декартовата равнина, чиито координати лежат във вътрешността на единичния квадрат

i\lt{}x\lt{}i+1,\qquad j\lt{}y\lt{}j+1.

Да се намерят всички реални числа

c\gt{}0

, за които е възможно точките да се изберат така, че за всички цели

i

j

периметърът на четириъгълника

P_{i,j}P_{i+1,j}P_{i+1,j+1}P_{i,j+1}

да е строго по-малък от

c

Решение

Отговорът е

c\ge4

. Първо ще докажем, че

c\lt{}4

е невъзможно. Нека

n

е произволно положително цяло число и разгледаме

n\times n

подтаблица от единични квадрати. Да оценим средната дължина на горната страна на всички четириъгълници в тази подтаблица. Тя е

\frac1{(n-1)^2}\sum_{i=1}^{n-1}\sum_{j=1}^{n-1}P_{i,j}P_{i+1,j}\ge

\frac1{(n-1)^2}\sum_{j=1}^{n-1}P_{1,j}P_{n,j}\gt{}\frac{n-2}{n-1}.

Същата оценка важи за всяка от четирите страни. Затова средният периметър е по-голям от

\frac{4(n-2)}{n-1}=4-\frac4{n-1}.

Следователно за достатъчно голямо

n

някой четириъгълник има периметър поне

c

, противоречие. Остава да покажем, че

c=4

е постижимо. Ще поставим

P_{i,j}=(f(i),f(j))

за функция

f:\mathbb Z\to\mathbb R

, която удовлетворява

n\lt{}f(n)\lt{}n+1

|f(n+1)-f(n)|\lt{}1

за всяко цяло

n

. Тогава съответният периметър е

2\bigl(|f(i+1)-f(i)|+|f(j+1)-f(j)|\bigr)\lt{}4.

Един пример е

f(n)=n+\frac12+\begin{cases} -\sum_{r=1}^{n}10^{-r},& n\ge0,\\ \sum_{r=1}^{-n}10^{-r},& n\lt{}0. \end{cases}

Сумата по абсолютна стойност е по-малка от

1/9

, така че

n\lt{}f(n)\lt{}n+1

. Освен това разликата между две съседни стойности е винаги строго по-малка от

1

. Следователно

c=4

работи, а оттам и всяко

c\ge4

Отвори задачатаEvan Chen VONVON TSTST 2024/1Условие — източник

Задача 2

Пълен запис

Условие

Нека

p

е нечетно просто число. Нека

P

Q

са полиноми с цели коефициенти, за които

P(0)=Q(0)=1

, няма неконстантен полином, който да дели едновременно

P

Q

, и

1+\cfrac{x}{1+\cfrac{2x}{1+\cfrac{\ddots}{1+(p-1)x}}}=\frac{P(x)}{Q(x)}.

Да се докаже, че всички коефициенти на

P

освен свободния член се делят на

p

, а нито един коефициент на

Q

не се дели на

p

Решение

Ще използваме стандартна рекурсия за крайни верижни дроби. Нека

a_1,a_2,\ldots

са ненулеви цели числа и дефинираме

R_1(x)=1,\qquad R_2(x)=1+a_1x,

\qquad R_{k+1}(x)=R_k(x)+a_kxR_{k-1}(x).

С индукция се проверява, че

1+\cfrac{a_kx}{1+\cfrac{a_{k-1}x}{1+\cfrac{\ddots}{1+a_1x}}}=

\frac{R_{k+1}(x)}{R_k(x)},

както и че

R_k(0)=1

\gcd(R_{k+1},R_k)=1

. За дадената дроб можем да вземем

a_1=p-1,\quad a_2=p-2,\quad\ldots,\quad a_{p-1}=1.

Ако от всяко

a_i

извадим

p

, коефициентите на получените числител и знаменател се променят само с кратни на

p

. След това умножаването на всички

a_i

по

-1

е същото като замяната

x\mapsto -x

, което само сменя знаци на някои коефициенти. Затова е достатъчно да разгледаме рекурсията при

a_i=i\qquad (i=1,2,\ldots,p-1).

При тази нормализация числителят е

R_p

, а знаменателят е

R_{p-1}

. Ще докажем формулата

R_n(x)=\sum_{k\ge0}\frac{n!}{2^k k!(n-2k)!}x^k,

като сумата спира при

k=\lfloor n/2\rfloor

. Базовите случаи са непосредствени. Ако формулата е вярна за

n

n-1

, то

\begin{align*} R_{n+1}&=R_n+nxR_{n-1}\\ &=\sum_{k\ge0}\frac{1}{2^k k!}\frac{n!}{(n-2k)!}x^k+\sum_{k\ge0}\frac{1}{2^k k!}\frac{n!}{(n-2k-1)!}x^{k+1}\\ &=\sum_{k\ge0}\frac{(n+1)!}{2^k k!(n+1-2k)!}x^k, \end{align*}

което завършва индукцията. Следователно

P(x)=R_p(x)=\sum_{k\ge0}\frac{p!}{2^k k!(p-2k)!}x^k.

За

k=0

коефициентът е

1

. За всяко

k\ge1

знаменателят не се дели на

p

, а числителят съдържа множител

p

, така че съответният коефициент се дели на

p

. От друга страна

Q(x)=R_{p-1}(x)=

\sum_{k\ge0}\frac{(p-1)!}{2^k k!(p-1-2k)!}x^k.

Тук нито числителят, нито знаменателят съдържа множител

p

, затова нито един коефициент на

Q

не се дели на

p

. Това доказва твърдението.

Отвори задачатаEvan Chen VONVON TSTST 2024/2Условие — източник

Задача 3

Пълен запис

Условие

Нека

A=\{a_1,\ldots,a_{2024}\}

е множество от

2024

различни по двойки реални числа. Нека съществуват положителни цели числа

b_1,b_2,\ldots,b_{2024}

, за които

a_1b_1+a_2b_2+\cdots+a_{2024}b_{2024}=0.

Да се докаже, че могат да се изберат

a_{2025},a_{2026},a_{2027},\ldots

така, че

a_k\in A

за всяко

k\ge2025

и за всяко положително цяло число

d

да има безбройно много положителни цели числа

n

, за които

\sum_{k=1}^n a_kk^d=0.

Решение

За удобство ще номерираме от

0

. Нека първоначалните елементи са

a_0,a_1,\ldots,a_{2023}

. Поставяме

m=b_0+b_1+\cdots+b_{2023}.

Като добавим още

b_i-1

копия на

a_i

за всяко

i

, получаваме първи блок

a_0,a_1,\ldots,a_{m-1}

със сума

0

. Нека

s_m(t)

означава сумата от цифрите на

t

в бройна система с основа

m

, взета по модул

m

. За всички следващи членове дефинираме

a_t=a_{s_m(t)}.

Това не променя вече зададения първи блок, защото за

0\le t\lt{}m

имаме

s_m(t)=t

. Ще докажем, че за фиксирано

d

сумата

\sum_{t=0}^{n-1}a_t(t+1)^d

е нула за всяко

n=cm^{d+1}

, където

c

е положително цяло число. Такива

n

са безбройно много. Достатъчно е да разгледаме един блок от

m^{d+1}

последователни члена:

S=\sum_{t=cm^{d+1}}^{(c+1)m^{d+1}-1}a_{s_m(t)}(t+1)^d.

Всеки индекс в този блок се записва единствено като

t=cm^{d+1}+e_0+e_1m+\cdots+e_dm^d,

където

0\le e_0,e_1,\ldots,e_d\lt{}m

. Тогава

s_m(t)\equiv s_m(c)+e_0+\cdots+e_d\pmod m

. Групираме членовете според стойността на

s_m(t)

. Получаваме

S=\sum_{i=0}^{m-1}a_iC_i,

където

C_i

е сумата на

(t+1)^d

по всички

(d+1)

-орки

(e_0,\ldots,e_d)

e_0+\cdots+e_d\equiv i-s_m(c)\pmod m

. Ще покажем, че

C_i

не зависи от

i

. Разлагаме

(t+1)^d

като полином по променливите

e_0,\ldots,e_d

. Всеки моном има обща степен най-много

d

, следователно пропуска поне една от

d+1

променливи. Ако фиксираме всички останали променливи, пропуснатата променлива се определя еднозначно по условието за остатъка по модул

m

. Затова сумата на този моном е една и съща за всеки остатък

i

. Следователно и целият коефициент

C_i

е независим от

i

. Понеже

a_0+a_1+\cdots+a_{m-1}=0

, получаваме

S=C_0(a_0+a_1+\cdots+a_{m-1})=0.

Така всеки блок с дължина

m^{d+1}

има нулев принос, а оттук сумите до

n=cm^{d+1}

са нула за безбройно много

n

Отвори задачатаEvan Chen VONVON TSTST 2024/3Условие — източник

Задача 4

Пълен запис

Условие

Нека

ABCD

е четириъгълник, вписан в окръжност с център

O

, а

E

е пресечната точка на отсечките

AC

BD

. Нека

\omega_1

е описаната окръжност на триъгълника

ADE

, а

\omega_2

- описаната окръжност на триъгълника

BCE

. Допирателната към

\omega_1

A

и допирателната към

\omega_2

C

се пресичат в

P

. Допирателната към

\omega_1

D

и допирателната към

\omega_2

B

се пресичат в

Q

. Да се докаже, че

OP=OQ

Решение

Нека

R=AD\cap BC

. Ще докажем първо, че

ACRP

е равнобедрен трапец с

AC\parallel PR

. По теоремата за ъгъла между допирателна и хорда имаме

\angle PAC=\angle ADE

. Понеже

B,D,E

са колинеарни и

A,B,C,D

лежат на една окръжност, това е същото като

\angle ADB=\angle ACB=\angle ACR

. Аналогично, от допирателната към

(BCE)

C

получаваме

\angle PCA=\angle CBE=\angle CAD=\angle CAR

. Следователно триъгълниците

PAC

RCA

са еднакви в огледален ред и получаваме

AC\parallel PR

AP=CR

. Тоест

ACRP

е равнобедрен трапец. Центърът

O

на описаната окръжност на

ABCD

лежи на симетралата на хордата

AC

; в този равнобедрен трапец същата симетрала разменя

P

R

, затова

OP=OR

. Същият аргумент, приложен към допирателните в

D

B

и към хордата

BD

, дава

OQ=OR

. От

OP=OR=OQ

следва търсеното равенство

OP=OQ

Отвори задачатаEvan Chen VONVON TSTST 2024/4Условие — източник

Задача 5

Пълен запис

Условие

За положително цяло число

k

нека

s(k)

означава броя на единиците в двоичния запис на

k

. Да се докаже, че за всяко положително цяло число

n

\sum_{i=1}^{n}(-1)^{s(3i)}\gt{}0.

Решение

Нека

F(n)=\sum_{i=0}^{n}(-1)^{s(3i)},

\qquad G(n)=\sum_{i=0}^{n}(-1)^{s(i)}.

Тъй като членът при

i=0

във

F(n)

1

, задачата е еквивалентна на това да докажем

F(n)\ge2

за всяко

n\ge1

. Първо ще използваме проста лема: за всяко

n

е изпълнено

|G(n)|\le1

. Наистина,

s(2i)=s(i)

, а

s(2i+1)=s(i)+1

, така че членовете за

2i

2i+1

се унищожават по двойки. Следователно

G(2n+1)=0

, а

G(2n)=(-1)^{s(2n)}

. Ще докажем

F(n)\ge2

със силна индукция. Случаите

n\le5

се проверяват директно. Нека

n\ge6

и нека

m=\left\lfloor\frac{3n-3}{4}\right\rfloor,

така че

4m+3\le3n

. Разглеждаме множеството

S=\{0,3,6,\ldots,3n\}

. За всяко

0\le k\le m

можем да добавим две двоични цифри към записа на

k

, т.е. да разглеждаме числата

4k+r

за

0\le r\lt{}4

. Ако

3\mid k

, тогава

4k

4k+3

са кратни на

3

; добавянето на

00

или

11

запазва четността на броя единици. Ако

3\nmid k

, точно едно от числата

4k+1

4k+2

е кратно на

3

; добавянето на

01

или

10

обръща четността. Така покриваме елементите на

S

еднозначно, с възможно най-много един пропуснат елемент. Затова

F(n)\ge

\begin{aligned}2\sum_{\substack{0\le i\le m\\ i\equiv0\pmod3}}(-1)^{s(i)}\end{aligned}

\begin{aligned}-\sum_{\substack{0\le i\le m\\ i\not\equiv0\pmod3}}(-1)^{s(i)}-1.\end{aligned}

Поставяме

\begin{aligned}x=\sum_{\substack{0\le i\le m\\ i\equiv0\pmod3}}(-1)^{s(i)},\end{aligned}

\begin{aligned}\qquad y=\sum_{\substack{0\le i\le m\\ i\not\equiv0\pmod3}}(-1)^{s(i)}.\end{aligned}

От лемата имаме

|x+y|\le1

, а от индукционното предположение

x\ge2

(защото това е същата сума

F(\lfloor m/3\rfloor)

\lfloor m/3\rfloor\lt{}n

). Следователно

F(n)\ge2x-y-1=3x-(x+y)-1\ge6-1-1\gt{}2,

което завършва индукцията.

Отвори задачатаEvan Chen VONVON TSTST 2024/5Условие — източник

Задача 6

Пълен запис

Условие

Да се определи дали съществува функция

f:\mathbb Z_{\gt{}0}\to\mathbb Z_{\gt{}0}

такава, че за всички положителни цели числа

m

n

f(m+nf(m))=f(n)^m+2024!\cdot m.

Решение

Ще докажем, че такава функция не съществува. Нека

C=2024!

и да означим даденото равенство с

P(m,n)

. Да допуснем, че функция

f

съществува, и нека

r=f(1)

. От

P(1,n)

получаваме

f(1+rn)=f(n)+C.

След итерация следва

f(1+r+r^2+\cdots+r^k)=r+kC

за всяко

k\ge0

. Ако

r=1

, тогава

f(t)=1+(t-1)C

за всяко

t\ge1

; но при

P(2,1)

получаваме противоречие, защото лявата страна е

f(2+f(2))=1+(1+C+1)C

, а дясната е

1+2C

. Следователно

r\ge2

. Ще използваме следната оценка. За всяко положително цяло число

a

е изпълнено

f(a)\ge\frac{2^a-1}{Ca}.

Действително, нека

c=a+af(a),\qquad b=f(c)+a,\qquad d=f(a).

Тогава

a+bf(a)=a+af(a)+f(a)f(c)=c+df(c).

Сравнявайки

P(a,b)

P(c,d)

, получаваме

f(b)^a+Ca=f(d)^c+Cc.

Понеже

c=a(1+f(a))

, това може да се запише като

f(b)^a-\bigl(f(d)^{1+f(a)}\bigr)^a=Caf(a).

Лявата страна е положителна разлика на две

a

-ти степени на положителни цели числа, следователно е поне

2^a-1

. Така получаваме исканата оценка. Сега поставяме

a=1+r+r^2+\cdots+r^k.

От вече доказаната формула имаме

f(a)=r+kC

, което расте само линейно по

k

. Оценката обаче дава

r+kC=f(a)\ge\frac{2^a-1}{Ca},

а дясната страна расте експоненциално по

a

, тоест много по-бързо от линейна функция на

k

, понеже

a=1+r+\cdots+r^k

расте експоненциално по

k

. За достатъчно голямо

k

това е невъзможно. Противоречието доказва, че търсената функция не съществува.

Отвори задачатаEvan Chen VONVON TSTST 2024/6Условие — източник

Задача 7

Пълен запис

Условие

Безкрайна редица

a_1,a_2,a_3,\ldots

от реални числа удовлетворява

a_{2n-1}+a_{2n}\gt{}a_{2n+1}+a_{2n+2}

a_{2n}+a_{2n+1}\lt{}a_{2n+2}+a_{2n+3}

за всяко положително цяло число

n

. Да се докаже, че съществува реално число

C

такова, че

a_na_{n+1}\lt{}C

за всяко положително цяло число

n

Решение

Достатъчно е да докажем твърдението за всички достатъчно големи

n

: после избираме

C

по-голямо и от крайния брой останали произведения. Поставяме

d_n=(-1)^{n-1}(a_{n+2}-a_n).

Двете дадени неравенства са точно твърдението, че редицата

d_1,d_2,\ldots

е строго растяща. Първо нека

d_k\gt{}0

за някое

k

. Тогава от някакъв индекс нататък всички

d_n

са положителни и получаваме

a_{2n+1}=a_1+(d_1+d_3+\cdots+d_{2n-1})\to+\infty,

докато

a_{2n}=a_2-(d_2+d_4+\cdots+d_{2n-2})\to-\infty.

Следователно всяко достатъчно късно произведение на два съседни члена е отрицателно; за опашката работи

C=0

, а крайният брой начални произведения се поглъща чрез увеличаване на

C

. Остава случаят

d_k\le0

за всички

k

. Тогава

(a_{2n+1})_{n\ge0}

е слабо намаляваща, а

(a_{2n})_{n\ge1}

е слабо растяща. Освен това от първите две формули следва

d_1+a_1+a_2\lt{}a_{2n}+a_{2n+1}\lt{}a_1+a_2.

Нечетната подпоредица или клони към

-\infty

, или има крайна граница; аналогично четната подпоредица или клони към

+\infty

, или има крайна граница. Ако нечетната подпоредица клони към

-\infty

, горната двустранна оценка принуждава четната да клони към

+\infty

, и тогава отново всички достатъчно късни съседни произведения са отрицателни. Ако четната подпоредица клони към

+\infty

, по същия начин нечетната клони към

-\infty

, така че пак сме готови. Накрая, ако и двете подпоредици имат крайни граници, то съществува границата

L=\lim_{n\to\infty}a_{2n}a_{2n+1}.

Същата граница имат и произведенията

a_{2n+1}a_{2n+2}

. Избираме

C\gt{}L

и, ако е нужно, го увеличаваме така, че да е по-голямо от крайния брой начални съседни произведения. Така

a_na_{n+1}\lt{}C

за всяко

n

Отвори задачатаEvan Chen VONVON TSTST 2024/7Условие — източник

Задача 8

Пълен запис

Условие

Нека

ABC

е разностранен триъгълник и нека

D

е точка върху страната

BC

, за която

\angle BAD=\angle DAC

. Нека

X

Y

са точки във вътрешността на

ABC

такива, че триъгълниците

ABX

ACY

са подобни, а четириъгълниците

ACDX

ABDY

са вписани. Правите

BX

CY

се пресичат в

S

, а правите

BY

CX

се пресичат в

T

. Да се докаже, че

DS\parallel AT

Решение

Ще използваме насочени ъгли. Първо доказваме ключовия факт, че

S

T

са изогонално спрегнати спрямо триъгълника

ABC

. От вписаността на

ABDY

и колинеарността на

B,D,C

имаме

\angle YBC=\angle YBD=\angle YAD

. Аналогично, от вписаността на

ACDX

получаваме

\angle XCB=\angle XCD=\angle XAD

. Понеже

AD

е ъглополовяща и

ABX

е подобен на

ACY

, правите

AX

AY

са изогонални в ъгъла

BAC

, следователно

\angle YAD=\angle XAD

. Значи

\angle YBC=\angle XCB

, откъдето

TB=TC

. Нека

T'

е изогонално спрегнатата точка на

S

спрямо

ABC

. От подобието имаме

\angle ABS=\angle ABX=\angle ACY=\angle ACS

, затова

T'B=T'C

; следователно и

T'

, и

T

лежат на симетралата на

BC

. Освен това стандартната двойствена теорема за инволюцията на Дезарг, приложена към пълния четириъгълник, образуван от правите

AB

AC

BX

CY

, дава, че

AS

AT

са изогонални в

\angle BAC

. Значи

A,T,T'

са колинеарни. Тъй като

ABC

е разностранен, тази права не съвпада със симетралата на

BC

, така че пресечната точка е единствена и

T=T'

. Така

S

T

наистина са изогонално спрегнати. Сега довършваме с пресмятане на ъгли. Нека

\angle DAX=\angle DAY=\angle ABX=\angle ACY=\theta.

Тогава

\angle XSY=\angle A+2\theta,

а от вписаните четириъгълници

\angle XDY=\angle BDY+\angle CDX-180^\circ=

180^\circ-(\angle BAY+\angle CAX)=180^\circ-(\angle A+2\theta).

Следователно

XSYD

е вписан. Освен това

\angle XTY=180^\circ-\angle YBC-\angle XCB=

180^\circ-2\theta=180^\circ-\angle XAY,

така че

AXTY

също е вписан. Накрая, с насочени ъгли,

\angle(AT,AX)=\angle TYX=\angle BYD+\angle DYX=

\angle BAD+\angle DSX=\angle BXA+\angle DSX=\angle(DS,AX).

Следователно правите

AT

DS

образуват един и същ насочен ъгъл с

AX

, тоест

DS\parallel AT

Отвори задачатаEvan Chen VONVON TSTST 2024/8Условие — източник

Задача 9

Пълен запис

Условие

Нека

n\ge2

е фиксирано цяло число. Клетките на таблица

n\times n

са запълнени с числата от

1

до

n^2

, като всяко число се среща точно веднъж. Нека

N

е броят на ненаредените четворки от клетки, които образуват правоъгълник със страни, успоредни на страните на таблицата, и при които двете по-малки числа стоят в срещуположни върхове на този правоъгълник. Да се намери най-голямата възможна стойност на

N

Решение

Отговорът е

N_{\max}=\frac{1}{12}n^2(n^2-1).

Ще наричаме правоъгълниците, които се броят в

N

, добри. Първо доказваме горната оценка. Наричаме тройка от числа

(a,b,c)

ъглова, ако

a

b

са в един ред,

b

c

са в един стълб и

a\lt{}b\gt{}c

. Във всеки правоъгълник най-голямото от четирите числа е връх на поне една такава ъглова тройка. Освен това един добър правоъгълник има точно две ъглови тройки: именно двата по-големи върха са центрове на такива тройки. Нека

E

е общият брой ъглови тройки, а

M

е броят на недобрите правоъгълници. Общият брой правоъгълници със страни, успоредни на таблицата, е

\binom n2^2

, затова

E\ge M+2N=\binom n2^2+N,

откъдето

N\le E-\binom n2^2.

Остава да оценим

E

отгоре. За клетка

c

нека

f(c)

е броят на клетките в същия ред с по-малко число от това в

c

, а

g(c)

- броят на клетките в същия стълб с по-малко число. Броят на ъгловите тройки с център

c

f(c)g(c)

. Следователно

\begin{align*} E&=\sum_c f(c)g(c)\\ &\le\sum_c\frac{f(c)^2+g(c)^2}{2}\\ &=n(0^2+1^2+\cdots+(n-1)^2)\\ &=\frac{n^2(n-1)(2n-1)}6. \end{align*}

Така

\begin{align*} N&\le E-\binom n2^2\\ &\le\frac{n^2(n-1)(2n-1)}6-\frac{n^2(n-1)^2}{4}\\ &=\frac{n^2(n^2-1)}{12}. \end{align*}

Остава конструкцията. Вземаме произволен латински квадрат от ред

n

със символи

0,1,\ldots,n-1

. След това заменяме всяко от

n

-те появявания на символа

k

с числата

kn+1,kn+2,\ldots,kn+n

в произволен ред. За всяка клетка

c

, в реда й има точно

k

символа по-малки от нейния символ

k

, и точно същото важи за стълба й. Следователно за тази конструкция

f(c)=g(c)

за всяка клетка

c

. Така в неравенството

f(c)g(c)\le\frac{f(c)^2+g(c)^2}{2}

навсякъде има равенство, а останалите стъпки от горната оценка също стават равенства. Получаваме точно

N=\frac{1}{12}n^2(n^2-1),

което доказва, че намерената горна оценка е достижима.

Отвори задачатаEvan Chen VONVON TSTST 2024/9Условие — източник