TST

Evan Chen / USA TST Solutions

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

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

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

Избран клас

11-12

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

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

2024 · 11-12: липсва задача 2, 4
2023 · 11-12: липсва задача 5
2020 · 11-12: липсва задача 2
2018 · 11-12: липсва задача 3, 5
2017 · 11-12: липсва задача 2, 5

2014

5 задачи

Задача 2

Пълен запис

Условие

Нека

a_1,a_2,a_3,\ldots

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

n

k

числото

\frac{a_n+a_{n+1}+\cdots+a_{n+k-1}}{k}

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

a_i

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

Решение

Нека

\nu_p(n)

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

p

дели

n

. Ще докажем следното по-силно твърдение. Твърдение. Нека

(a_n)

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

p

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

p

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

\nu_p(a_i)

не зависи от

i

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

p

, то всички членове

a_i

имат еднакви

p

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

p

. Понеже при

k=1

всеки

a_i

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

a_i

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

\nu_p(a_i)

. Тази стойност е четна, защото всяко

a_i

е квадрат. Първо ще използваме две леми. Първа лема. Ако

j\equiv k\pmod p

, то

a_j\equiv a_k\pmod p

. Действително, от условието за групи с дължина

p

имаме

p\mid a_j+a_{j+1}+\cdots+a_{j+p-1}

p\mid a_{j+1}+a_{j+2}+\cdots+a_{j+p}.

След изваждане получаваме

a_j\equiv a_{j+p}\pmod p

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

p

. Втора лема. Ако някой член

a_i

се дели на

p

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

p

. За

p=2

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

p\ge3

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

a_1\equiv0\pmod p

. Нека

S_n=a_1+a_2+\cdots+a_n\equiv a_2+a_3+\cdots+a_n\pmod p.

Ще наричаме число

k

2\le k\lt{}p

пивот, ако

1-k^{-1}

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

p

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

k

е изпълнено

S_k\equiv0\pmod p

. Ако не е така, то числата

\frac{a_1+a_2+\cdots+a_k}{k}\qquad\text{и}\qquad\frac{a_2+a_3+\cdots+a_k}{k-1}

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

p

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

\frac{k-1}{k}=1-k^{-1}

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

2

е пивот, вземаме

m=1

, защото

S_1\equiv0

и току-що доказахме

S_2\equiv0

. Ако

2

не е пивот, тогава пивотите са точно

\frac{p-1}{2}

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

0

1

. Всички те лежат сред числата

3,4,\ldots,p-1

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

m

S_m\equiv S_{m+1}\equiv0\pmod p,

откъдето

p\mid a_{m+1}

. Повтаряйки същата процедура, започвайки от

a_{m+1}

вместо от

a_1

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

a_{2m+1},a_{3m+1},a_{4m+1},\ldots

също се делят на

p

. Тъй като

m\lt{}p

, числата

1,m+1,2m+1,\ldots

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

p

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

a_i

се дели на

p

. Втората лема е доказана. Втората лема дава базата на индукцията. Ако най-малката

p

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

0

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

p

, иначе всички биха се делили; следователно всички валуации са

0

. Нека сега всички

a_i

се делят на

p

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

p^2

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

p

, то се дели на

p^2

. Значи след замяната

a_i\longmapsto \frac{a_i}{p^2}

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

p

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

\nu_p(a_i/p^2)

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

i

, а оттук и

\nu_p(a_i)

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

i

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

p

и завършва решението. Забележката в доказателството е важна: условието за дължини най-много

p

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

p^2

члена, всички делящи се на

p

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

p

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

Задача 3

Пълен запис

Условие

Нека

n

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

G

е прост граф с

n

върха и точно

\frac{n^2}{4}

ребра. Неподредена двойка различни върхове

\{x,y\}

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

z

, за който

xz

yz

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

G

има поне

2\binom{n/2}{2}

приятелски двойки върхове.

Решение

Ще използваме графовата форма на парадокса на приятелството: средно вашите приятели имат поне толкова приятели, колкото имате вие. Лема. За връх

v

нека

a(v)

е средната степен на съседите на

v

, като при изолиран връх полагаме

a(v)=0

. Тогава

\sum_v a(v)\ge \sum_v \deg v=2\#E,

където

\#E

е броят на ребрата. Доказателство. Пренебрегваме изолираните върхове, защото те нямат принос. Тогава

\begin{align*} \sum_v a(v) &=\sum_v\frac{\sum_{w\sim v}\deg w}{\deg v}\\ &=\sum_v\sum_{w\sim v}\frac{\deg w}{\deg v}\\ &=\sum_{\text{ребра }vw}\left(\frac{\deg w}{\deg v}+\frac{\deg v}{\deg w}\right)\\ &\ge\sum_{\text{ребра }vw}2=2\#E. \end{align*}

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

\deg w/\deg v

\deg v/\deg w

. Следствие. За връх

v

нека

m(v)

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

v

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

m(v)=0

, ако

v

е изолиран. Тогава

\sum_v m(v)\ge2\#E.

Наистина, за всеки връх имаме

m(v)\ge a(v)

. Сега броим приятелските двойки. Фиксираме връх

v

и избираме негов съсед

w

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

m(v)

. Всеки друг съсед на

w

образува с

v

приятелска двойка, защото общият им съсед е

w

. Така върхът

v

участва в поне

m(v)-1

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

\frac12\sum_v(m(v)-1)\ge \#E-\frac12\#V.

Тук

\#V=n

и по условие

\#E=n^2/4

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

\#E-\frac12\#V=\frac{n^2}{4}-\frac n2=\frac{n(n-2)}4=2\binom{n/2}{2},

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

K_{n/2,n/2}

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

Задача 4

Пълен запис

Условие

Нека

n

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

c_1,c_2,\ldots,c_{n-1}

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

\sum_{i=1}^{n-1}|c_i-1|\lt{}1.

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

2x^n-c_{n-1}x^{n-1}+c_{n-2}x^{n-2}-\cdots-c_1x+2

няма реални корени.

Решение

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

x

. Първо, от

\sum_{i=1}^{n-1}|c_i-1|\lt{}1

следва

|c_i-1|\lt{}1

за всяко

i

, тоест

c_i\gt{}0

. Ако

x\le0

, тогава

n

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

x^i

има знак

(-1)^i

, а самото

x^i

също има знак

(-1)^i

при

x\lt{}0

. Следователно целият полином е положителен за

x\le0

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

x\gt{}0

. Пишем

c_i=1-d_i,

така че

\sum_{i=1}^{n-1}|d_i|\lt{}1.

Нека

P(x)

е даденият полином. Понеже

n

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

\begin{align*} P(x) &=2x^n+2+\sum_{i=1}^{n-1}(-1)^i(1-d_i)x^i\\ &=\left(x^n+1+\sum_{i=0}^n(-1)^ix^i\right)-\sum_{i=1}^{n-1}(-1)^id_ix^i\\ &=x^n+1+\frac{x^{n+1}+1}{x+1}-\sum_{i=1}^{n-1}(-1)^id_ix^i. \end{align*}

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

x^n+1\gt{}\sum_{i=1}^{n-1}|d_i|x^i,

защото добавката

\frac{x^{n+1}+1}{x+1}

е положителна. Но за

x\gt{}0

и всяко

1\le i\le n-1

е вярно

x^n+1\gt{}x^i.

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

0\lt{}x\le1

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

1

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

1

; ако

x\gt{}1

, тогава

x^n\gt{}x^i

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

|d_i|

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

\sum_{i=1}^{n-1}|d_i|x^i\lt{}

\left(\sum_{i=1}^{n-1}|d_i|\right)(x^n+1)\lt{}x^n+1.

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

P(x)\gt{}0

и за

x\gt{}0

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

x

, така че няма реални корени.

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

Задача 5

Пълен запис

Условие

Нека

ABCD

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

E,F,G,H

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

AB,BC,CD,DA

. Нека

W,X,Y,Z

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

AHE

BEF

CFG

DGH

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

ABCD

WXYZ

имат равни лица.

Решение

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

ABCD

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

0

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

A,B,C,D

са съответно

a,b,c,d

, а тези на

W,X,Y,Z

са

w,x,y,z

. Първо ще намерим

w

. В триъгълника с върхове

D,A,B

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

d+a+b.

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

E

H

са средите на

AB

AD

, затова триъгълникът

AHE

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

DAB

с център

A

и коефициент

\frac12

. Следователно неговият ортоцентър е образът на ортоцентъра на

DAB

при тази хомотетия, тоест

w=a+\frac12\big((d+a+b)-a\big)=\frac12(2a+b+d).

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

\begin{align*} w&=\frac12(2a+b+d),\\ x&=\frac12(2b+c+a),\\ y&=\frac12(2c+d+b),\\ z&=\frac12(2d+a+c). \end{align*}

Оттук

w-y=a-c,\qquad x-z=b-d.

С други думи, диагоналите на

WXYZ

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

ABCD

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

[WXYZ]=[ABCD].

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

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

Задача 6

Пълен запис

Условие

За просто число

p

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

S

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

p

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

\mathbb F_p

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

\alpha

по модул

p

, такъв че

S=\{1,\alpha^1,\alpha^2,\ldots\}

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

p

; - не съществуват

a,b,c\in S

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

a+b\equiv c\pmod p.

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

N

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

p

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

S

на

\mathbb F_p

, за които

|S|\ge N

Решение

Първо доказваме обща лема за полиноми. Лема. Ако

f,g\in\mathbb Z[X]

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

p

те нямат общ корен по модул

p

. Доказателство. По теоремата на Безу, след евентуално умножение с общ знаменател, съществуват полиноми

A(X),B(X)\in\mathbb Z[X]

и ненулево цяло число

c

, за които

A(X)f(X)+B(X)g(X)=c.

Ако

r

е общ корен на

f

g

по модул

p

, след заместване

X=r

получаваме

p\mid c

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

p

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

n\ge N

, за което

3\nmid n

. По теоремата на Дирихле има произволно големи прости числа

p\equiv1\pmod n

. Ще изберем такова

p

достатъчно голямо. Тъй като

\mathbb F_p^\times

е циклична група с ред

p-1

, в нея има примитивен

n

-ти корен на единицата; нека това бъде

\alpha

. Поставяме

S=\{1,\alpha,\alpha^2,\ldots,\alpha^{n-1}\}.

Тогава

S

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

|S|=n\ge N

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

p

множеството

S

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

a+b\equiv c\pmod p

за някакви

a,b,c\in S

, делим на

a

и получаваме

1+\alpha^k\equiv\alpha^m\pmod p

за подходящи цели числа

k

m

. Оттук

X=\alpha^k

е общ корен по модул

p

на двата полинома

(X+1)^n-1\qquad\text{и}\qquad X^n-1.

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

\mathbb Z[X]

, когато

3\nmid n

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

\omega

е такъв корен, то

\omega^n=1\qquad\text{и}\qquad(1+\omega)^n=1.

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

|\omega|=1

|1+\omega|=1

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

\omega=-\frac12\pm\frac{\sqrt3}{2}i,

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

\omega^n=1

би наложило

3\mid n

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

(X+1)^n-1

X^n-1

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

p

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

p\equiv1\pmod n

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

1+\alpha^k\equiv\alpha^m\pmod p

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

S

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

\mathbb F_p

|S|=n\ge N

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

2015

3 задачи

Задача 2

Пълен запис

Условие

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

n

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

S

от

n

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

a,b\in S

числото

a-b

дели

a

b

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

S

Решение

Ще построим числата в нарастващ ред

a+s_1,a+s_2,\ldots,a+s_n,

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

d_1,d_2,\ldots,d_{n-1}.

Нека

s_1=0,\qquad s_i=d_1+d_2+\cdots+d_{i-1}\quad (2\le i\le n),

и за

i\lt{}j

нека

t_{i,j}=d_i+d_{i+1}+\cdots+d_{j-1}=s_j-s_i.

Ще ни стигнат следните две условия върху разликите. (i) Никое от числата

t_{i,j}

не дели друго от тях. (ii) Съществува цяло число

a

, за което

a\equiv -s_i\pmod{t_{i,j}}\qquad\text{за всички }i\lt{}j.

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

S=\{a+s_1,a+s_2,\ldots,a+s_n\}

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

t_{i,j}

към

a

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

i\lt{}j

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

t_{i,j}

. От (ii) имаме

t_{i,j}\mid a+s_i

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

t_{i,j}\mid a+s_j

. Ако пък

t_{i,j}

делеше и някое

a+s_k

k\ne i,j

, тогава щеше да дели разликата между

s_k

и едно от

s_i,s_j

. Това би означавало, че едно от числата

t_{r,s}

дели друго такова число, в противоречие с (i). Остава да построим разликите. Ще го направим с индукция по

n

. За

n=1

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

d_1,\ldots,d_{n-1}

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

n

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

p

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

t_{i,j}

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

M

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

t_{i,j}

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

p

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

d_1M,d_2M,\ldots,d_{n-1}M,p

работи за

n+1

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

Mt_{i,j}

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

p+Mt_{i,n}\qquad (1\le i\le n),

като за

i=n

това просто е

p

. Първо проверяваме (i). Делимост между две стари разлики

Mt_{i,j}

е същата като делимост между старите

t_{i,j}

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

p+Mt_{i,n}

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

M

, понеже е сравнимо с

p

по модул

M

. Ако общ делител на

p+Mt_{i,n}

и стара разлика

Mt_{r,s}

съществува, той трябва да дели

t_{r,s}

; но

p+Mt_{i,n}\equiv p\pmod{t_{r,s}}

, а

p

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

t_{r,s}

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

p+Mt_{i,n}

p+Mt_{j,n}

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

Mt_{r,s}

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

t

-числа не се делят едно друго. Сега проверяваме (ii). За първите

n

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

a_0

и да го умножим по

M

; така

Ma_0

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

Mt_{i,j}

. Всички нови модули

p+Mt_{i,n}

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

a\equiv -Ms_i\pmod{p+Mt_{i,n}}\qquad(1\le i\le n).

Така получаваме разлики, удовлетворяващи (i) и (ii), за

n+1

числа. Индукцията завършва конструкцията за всяко

n

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

Задача 3

Пълен запис

Условие

Физичка среща

2015

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

A

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

B

, като връзката е насочена. Ако при това

A

има електрон, а

B

няма, електронът прескача от

A

към

B

; във всички останали случаи нищо не се случва. Освен това физичката не може да разбере дали при дадена стъпка е прескочил електрон. Целта е да изолира два юсамона, за които е

100\%

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

Решение

Отговорът е не. Нека юсамоните са

U_1,U_2,\ldots,U_m

, където

m=2015

. Ще разгледаме

m+1

възможни модела

M_k

за

0\le k\le m

: в модела

M_k

юсамоните

U_1,U_2,\ldots,U_k

са заредени, а всички останали са незаредени. За всяка двойка различни юсамони има модел, в който те са в различни състояния: ако двойката е

U_i,U_j

i\lt{}j

, вземаме

k

i\le k\lt{}j

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

M_0,M_1,\ldots,M_m

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

U_i\to U_j

действа върху семейството от модели. Ако

i\gt{}j

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

M_k

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

U_i

е зареден, то

k\ge i\gt{}j

, така че

U_j

също е зареден; ако

U_j

е незареден, то

k\lt{}j\lt{}i

, така че

U_i

също е незареден. Ако

i\lt{}j

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

U_i

U_j

. За моделите с

k\lt{}i

или

k\ge j

нищо не се променя. За

i\le k\lt{}j

юсамонът

U_i

е зареден, а

U_j

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

U_i

към

U_j

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

M_k

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

U_i

U_j

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

M_0,M_1,\ldots,M_m

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

100\%

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

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

Задача 4

Пълен запис

Условие

Нека

f\colon\mathbb Q\to\mathbb Q

е функция, такава че за всички

x,y\in\mathbb Q

числото

f(x+y)-f(x)-f(y)

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

c

, за която

f(x)-cx

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

x

Решение

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

q

нека

A_q=1!+2!+\cdots+q!.

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

p/q

, където

q\gt{}0

\gcd(p,q)=1

, дефинираме

f\left(\frac pq\right)=\frac pq A_q.

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

L

е кратно на

q

, тогава

A_L\equiv A_q\pmod q,

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

r!

r\ge q

се дели на

q

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

x=p/q

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

L

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

f(x)\equiv xA_L\pmod{\mathbb Z}.

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

x

y

и избираме

L

кратно на знаменателите на

x

y

x+y

. Тогава

f(x+y)-f(x)-f(y)\equiv

(x+y)A_L-xA_L-yA_L\equiv0\pmod{\mathbb Z},

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

c

с исканото свойство. Ако такава константа съществува, от

x=1

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

c

е цяло число, защото

f(1)=1

f(1)-c\in\mathbb Z

. При

x=1/q

условието дава

\frac{A_q-c}{q}\in\mathbb Z,

тоест

c\equiv A_q\pmod q

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

q

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

q=m!

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

r!

r\ge m

се делят на

m!

, имаме

A_{m!}\equiv A_{m-1}\pmod{m!}.

Значи за всяко

m

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

c\equiv A_{m-1}\pmod{m!}.

За достатъчно голямо

m

числата

|c|

A_{m-1}

са по-малки от

m!

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

c=A_{m-1}.

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

m

, защото редицата

A_{m-1}

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

c

не съществува.

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

2016

3 задачи

Задача 3

Пълен запис

Условие

Нека

p

е просто число. С

\mathbb F_p

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

p

, а с

\mathbb F_p[x]

- множеството на полиномите с коефициенти в

\mathbb F_p

. Дефинираме

\Psi\colon\mathbb F_p[x]\to\mathbb F_p[x]

чрез

\Psi\left(\sum_{i=0}^n a_ix^i\right)=\sum_{i=0}^n a_ix^{p^i}.

Докажете, че за ненулеви полиноми

F,G\in\mathbb F_p[x]

е изпълнено

\Psi(\gcd(F,G))=\gcd(\Psi(F),\Psi(G)).

Решение

Ще използваме, че

\Psi

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

\mathbb F_p

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

P\in\mathbb F_p[x]

е вярно

\Psi(xP)=\Psi(P)^p.

По-общо, за всяко

i\ge0

имаме

\Psi(x^iP)=\Psi(P)^{p^i}

. Важно е да не се забравя, че

\Psi(1)=x

, а не

1

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

P\mid Q

\mathbb F_p[x]

, то

\Psi(P)\mid\Psi(Q)

. Нека

Q=PR

, където

R=\sum_{i=0}^k r_ix^i.

Тогава, използвайки линейността на

\Psi

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

\begin{align*} \Psi(Q) &=\Psi\left(P\sum_{i=0}^k r_ix^i\right)\\ &=\sum_{i=0}^k r_i\Psi(Px^i)\\ &=\sum_{i=0}^k r_i\Psi(P)^{p^i}. \end{align*}

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

\Psi(P)

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

\Psi(Q)

се дели на

\Psi(P)

. Нека

D=\gcd(F,G)

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

D\mid F

D\mid G

, твърдението дава

\Psi(D)\mid\Psi(F)\qquad\text{и}\qquad\Psi(D)\mid\Psi(G).

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

\Psi(D)\mid\gcd(\Psi(F),\Psi(G)).

За обратната делимост използваме тъждеството на Безу за полиноми над поле. Съществуват полиноми

A,B\in\mathbb F_p[x]

, за които

AF+BG=D.

Прилагаме

\Psi

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

\Psi

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

\Psi(AF)+\Psi(BG)=\Psi(D).

От вече доказаното твърдение имаме

\Psi(F)\mid\Psi(AF)

\Psi(G)\mid\Psi(BG)

. Значи

\gcd(\Psi(F),\Psi(G))

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

\Psi(D)

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

P

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

\Psi(P)

е моничен, защото водещият член

x^{\deg P}

преминава във водещ член

x^{p^{\deg P}}

. Затова двата монични полинома

\Psi(\gcd(F,G))\qquad\text{и}\qquad\gcd(\Psi(F),\Psi(G))

са равни.

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

Задача 4

Пълен запис

Условие

Нека

\sqrt3=1.b_1b_2b_3\ldots_{(2)}

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

\sqrt3

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

n

поне една от цифрите

b_n,b_{n+1},\ldots,b_{2n}

е равна на

1

Решение

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

n

всички цифри

b_n,b_{n+1},\ldots,b_{2n}

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

2^{n-1}

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

k

, за което

k\lt{}2^{n-1}\sqrt3\lt{}k+\frac1{2^{n+1}}.

Неравенствата са строги, защото

\sqrt3

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

\begin{align*} k^2\lt{}3\cdot2^{2n-2} &\lt{}k^2+\frac{k}{2^n}+\frac1{2^{2n+2}}\\ &\le k^2+\frac{2^{n-1}\sqrt3}{2^n}+\frac1{2^{2n+2}}\\ &=k^2+\frac{\sqrt3}{2}+\frac1{2^{2n+2}}\\ &\le k^2+\frac{\sqrt3}{2}+\frac1{16}\\ &\lt{}k^2+1. \end{align*}

Но числото

3\cdot2^{2n-2}

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

k^2

k^2+1

. Това е невъзможно. Следователно сред цифрите

b_n,b_{n+1},\ldots,b_{2n}

винаги има поне една единица.

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

Задача 5

Пълен запис

Условие

Нека

n\ge4

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

W\colon\{1,2,\ldots,n\}^2\to\mathbb R,

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

[n]=A\cup B\cup C

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

\sum_{a\in A}\sum_{b\in B}\sum_{c\in C}W(a,b)W(b,c)=

|A||B||C|.

Решение

Отговорът е следният: стойностите

W(k,k)

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

\varepsilon

, където

\varepsilon\in\{-1,1\}.

Тези функции очевидно работят, защото при

a\in A

b\in B

c\in C

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

W(a,b)W(b,c)

е равен на

\varepsilon^2=1

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

a,b,c

поставяме

X_{abc}=W(a,b)W(b,c).

Първо забелязваме, че

W(a,b)\ne0

за

a\ne b

. Наистина, ако вземем разбиването

A=\{a\}

B=\{b\}

C=[n]\setminus\{a,b\}

, получаваме

\sum_{c\in C}W(a,b)W(b,c)=n-2,

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

a,b,c

са три различни елемента и нека

R=[n]\setminus\{a,b,c\}.

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

A=\{a\},\quad B=\{b\},\quad C=\{c\}\cup R,

A=\{a\},\quad B=\{c\},\quad C=\{b\}\cup R,

A=\{a\},\quad B=\{b,c\},\quad C=R.

Получаваме съответно

\begin{align*} X_{abc}+\sum_{r\in R}X_{abr}&=n-2,\\ X_{acb}+\sum_{r\in R}X_{acr}&=n-2,\\ \sum_{r\in R}X_{abr}+\sum_{r\in R}X_{acr}&=2(n-3). \end{align*}

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

X_{abc}+X_{acb}=2.

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

\{a\}

\{c\}

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

\{b\}

, получаваме

X_{abc}+X_{cba}=2.

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

X_{acb}=X_{cba}

, тоест

W(a,c)W(c,b)=W(c,b)W(b,a).

Понеже

W(c,b)\ne0

, заключаваме, че

W(a,c)=W(b,a)

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

a,b,c

. От това вече следва, че всички извъндиагонални стойности на

W

са равни. Фиксираме индекс

a

. Ако

c

d

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

a

, избираме

b

, различен от

a,c,d

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

n\ge4

. Тогава

W(a,c)=W(b,a)=W(a,d),

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

a

извън диагонала са равни. Освен това от същото равенство

W(a,c)=W(b,a)

виждаме, че тази обща стойност в ред

a

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

a

. Накрая, за два различни индекса

a

b

стойността

W(a,b)

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

a

и на стълб

b

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

\varepsilon

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

X_{abc}+X_{acb}=2

за произволни различни

a,b,c

получаваме

2\varepsilon^2=2,

тоест

\varepsilon=1

или

\varepsilon=-1

. Това дава точно описаните по-горе функции.

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

2017

4 задачи

Задача 1

Пълен запис

Условие

В спортна лига всеки отбор използва множество от най-много

t

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

S

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

S

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

S

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

S

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

n

t

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

g(n,t)

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

n

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

g(n,t)

отбора.

Решение

Отговорът е

g(n,t)=\left\lceil\frac nt\right\rceil.

Първо това е горна граница. Разделяме

n

-те цвята на

\left\lceil n/t\right\rceil

групи, всяка с най-много

t

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

\left\lceil n/t\right\rceil

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

S

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

S

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

S

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

n

цвята още се срещат в оставащите отбори. Понеже всеки отбор има най-много

t

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

\left\lceil n/t\right\rceil

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

S

е цветово разпознаваемо. За всеки отбор

T\in S

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

S

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

T

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

S

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

\left\lceil n/t\right\rceil

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

Задача 3

Пълен запис

Условие

Нека

P,Q\in\mathbb R[x]

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

\lambda

, за които

P+\lambda Q

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

Решение

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

\mathbb C

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

\lambda_1,\lambda_2,\lambda_3,\lambda_4\in\mathbb C

и полиноми

R_i\in\mathbb C[x]

, за които

P+\lambda_iQ=R_i^2\qquad (i=1,2,3,4).

Можем да приемем, че

\deg P\ne\deg Q

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

P

P+cQ

за подходяща константа

c

; това само преименува параметъра

\lambda

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

P'+\lambda_iQ'=2R_iR_i'.

Умножаваме първоначалното равенство по

Q'

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

Q

, след което изваждаме. Така

Q'(P+\lambda_iQ)-Q(P'+\lambda_iQ')=Q'P-QP'.

Лявата страна се дели на

R_i

, защото

P+\lambda_iQ=R_i^2

P'+\lambda_iQ'

се дели на

R_i

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

R_i\mid Q'P-QP'

за всяко

i

. Полиномите

R_i

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

R_i

, и

R_j

при

i\ne j

, той дели разликата

(P+\lambda_iQ)-(P+\lambda_jQ)=(\lambda_i-\lambda_j)Q,

а също дели

P+\lambda_iQ

; оттук дели и

P

, и

Q

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

R_1R_2R_3R_4

дели

Q'P-QP'

. Ако

d=\max(\deg P, \deg Q)

, понеже

\deg P\ne\deg Q

, всеки полином

P+\lambda_iQ

има степен

d

. Така

\deg(R_1R_2R_3R_4)=4\cdot\frac d2=2d.

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

\deg(Q'P-QP')\le \deg P+\deg Q-1\lt{}2d.

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

Q'P-QP'=0

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

(P/Q)'=0

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

P/Q

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

P

Q

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

\lambda

няма.

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

Задача 4

Пълен запис

Условие

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

n\gt{}1

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

0

точки. Грешен отговор носи

-2

точки за останалите участници, но само

-1

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

2^{n-1}

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

Решение

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

2^{n-2}+1

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

1

точка, участниците с отговора, който копирате и който се оказва грешен, губят

1

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

1

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

1

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

S

от участници е спечелило точка, а в по-късен кръг всички участници от

S

дават един и същ отговор, тогава можем да копираме този отговор. Ако той е грешен, всички от

S

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

\mathcal L

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

n

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

S

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

S\in\mathcal L

, копираме техния отговор и изтриваме

S

от

\mathcal L

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

T

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

|T|\ge n/2

. Нека

S

е множеството на участниците с верен отговор. Тогава

S

е непресичащо се с

T

, така че

|S|\le n/2

, и добавяме

S

в списъка

\mathcal L

. По построение в

\mathcal L

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

n/2

. За фиксиран участник броят на подмножествата на

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

с размер най-много

n/2

, които го съдържат, е най-много

2^{n-2}

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

2^{n-2}

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

2^{n-2}+1

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

2^{n-1}

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

Задача 6

Пълен запис

Условие

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

(a,b,p)

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

p

е просто число и

0\lt{}a\le b\lt{}p

, за които

p^5

дели

(a+b)^p-a^p-b^p.

Решение

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

p\equiv1\pmod3

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

a,b

0\lt{}a\le b\lt{}p

, за които

p^2\mid a^2+ab+b^2.

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

x^2+x+1\equiv0\pmod{p^2}

; еквивалентно, теорията на формата

x^2+xy+y^2

дава представяне

p^2=a^2+ab+b^2

. Сега ще докажем ключовата полиномиална делимост. Ако

p\equiv1\pmod3

, тогава

p(x^2+xy+y^2)^2\mid (x+y)^p-x^p-y^p

като полиноми с цели коефициенти. Първо всички вътрешни биномиални коефициенти

\binom pk

се делят на

p

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

(x+y)^p-x^p-y^p

се дели на

p

. Остава да видим двойния множител

x^2+xy+y^2

. След хомогенизация е достатъчно да докажем, че

(x^2+x+1)^2\mid F(x),\qquad F(x)=(x+1)^p-x^p-1.

Нека

\zeta

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

p\equiv1\pmod3

, имаме

\zeta^p=\zeta

, а също

1+\zeta=-\zeta^2

. Тогава

F(\zeta)=(1+\zeta)^p-\zeta^p-1=

(-\zeta^2)^p-\zeta-1=-\zeta^2-\zeta-1=0.

Освен това

F'(x)=p(x+1)^{p-1}-px^{p-1},

и при

x=\zeta

получаваме

F'(\zeta)=p-p=0

, защото

p-1

се дели на

3

. Значи

\zeta

е двоен корен на

F

, а същото важи и за спрегнатия корен

\zeta^2

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

(x^2+x+1)^2

дели

F(x)

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

p\equiv1\pmod3

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

a,b

от стандартното твърдение. Тогава

p(a^2+ab+b^2)^2\mid (a+b)^p-a^p-b^p.

Понеже

p^2\mid a^2+ab+b^2

, дясната страна се дели на

p\cdot p^4=p^5

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

p\equiv1\pmod3

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

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

2018

4 задачи

Задача 1

Пълен запис

Условие

Нека

n\ge2

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

\sigma(n)

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

n

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

n

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

n

, е поне

\sigma(n)

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

n

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

Решение

Равенство се достига точно когато

n=p^e

, където

p

е просто число и

e

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

n=p^e

, тогава

\sigma(n)=1+p+p^2+\cdots+p^e.

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

\sigma(n)

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

n

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

p

\sigma(n)-\left\lfloor\frac{\sigma(n)}p\right\rfloor=

(1+p+\cdots+p^e)-(1+p+\cdots+p^{e-1})=p^e=n.

Освен това

\sigma(n)

не се дели на

p

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

\sigma(n)

n

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

d_1,d_2,\ldots,d_k

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

n

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

I_1=[1,d_1],\quad I_2=[d_1+1,d_1+d_2],\quad \ldots,

\quad I_k=[d_1+\cdots+d_{k-1}+1,d_1+\cdots+d_k].

Интервалът

I_j

има дължина

d_j

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

d_j

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

\varphi(d_j)

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

d_j

. Понеже

d_j\mid n

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

n

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

d_j

; следователно в

I_j

има най-много

\varphi(d_j)

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

n

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

[1,\sigma(n)]

има най-много

\sum_{d\mid n}\varphi(d)=n

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

n

. Ако

n

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

p\lt{}q

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

q

, тоест

d_1=q

. Тогава и

p

, и

q

лежат в

I_1=[1,q]

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

n

. Значи в

I_1

има строго по-малко от

\varphi(q)=q-1

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

n

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

[1,\sigma(n)]

има строго по-малко от

n

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

n

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

n

, е строго по-голямо от

\sigma(n)

. Значи равенство е възможно само за простите степени, а те вече бяха проверени.

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

Задача 2

Пълен запис

Условие

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

f\colon\mathbb Z^2\to[0,1]

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

x

y

е изпълнено

f(x,y)=\frac{f(x-1,y)+f(x,y-1)}2.

Решение

Ще докажем, че единствените решения са константните функции. Ясно е, че всяка константна функция работи. Итерираме даденото равенство

n

пъти. Получаваме

f(x,y)=\frac1{2^n}\sum_{i=0}^n\binom ni f(x-i,y-(n-i)).

Сравняваме тази формула за точките

(x,y)

(x-1,y+1)

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

\begin{align*} |f(x,y)-f(x-1,y+1)| &\le \frac1{2^n}\sum_{i=0}^{n+1}\left|\binom ni-\binom n{i-1}\right|, \end{align*}

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

\binom n{-1}=\binom n{n+1}=0

. Разликите на последователните биномиални коефициенти първо са неотрицателни, а после неположителни, затова сумата от абсолютните стойности е два пъти най-големият биномен коефициент. Следователно

|f(x,y)-f(x-1,y+1)|\le \frac{2\binom n{\lfloor n/2\rfloor}}{2^n}.

Но

\binom n{\lfloor n/2\rfloor}=o(2^n)

, така че при

n\to\infty

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

0

. Значи

f(x,y)=f(x-1,y+1)

за всички цели

x,y

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

f

е константна върху всяка права

x+y=\text{const}

. Нека стойността върху правата

x+y=s

g(s)

. Даденото уравнение дава

g(s)=\frac{g(s-1)+g(s-1)}2=g(s-1).

Значи всички стойности

g(s)

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

f

е константна върху цялото

\mathbb Z^2

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

Задача 4

Пълен запис

Условие

Нека

n

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

S\subseteq\{0,1\}^n

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

n

. За нечетен брой низове

x_1,\ldots,x_{2k+1}\in S

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

y\in\{0,1\}^n

, чийто

i

-ти бит е най-често срещаният бит измежду

i

-тите битове на

x_1,\ldots,x_{2k+1}

. Например при

n=4

мнозинството на

0000,0000,1101,1100,0101

0100

. Да кажем, че

S

има свойството

P_k

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

2k+1

низа от

S

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

S

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

S

има свойството

P_k

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

k

, то

S

има свойството

P_r

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

r

Решение

Ще докажем по-силно, че за фиксирано

n

всички свойства

P_k

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

n

. При

n=1

твърдението е очевидно, а при

n=2

се проверява директно: всяко множество от двумерни двоични низове, затворено относно някакво нечетно мнозинство, е затворено и относно мнозинство на три низа. Нека

n\ge3

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

n-1

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

S\subseteq\{0,1\}^n

има свойството

P_\ell

, но няма свойството

P_k

. Тогава съществуват низове

x_1,\ldots,x_{2k+1}\in S

, чието мнозинство

y=M(x_1,\ldots,x_{2k+1})

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

S

. Ще докажем следното твърдение. Нека

y_i

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

y

само в

i

-тия бит. Тогава

y_i\in S

. Наистина, за низ

s

нека

\widehat s

е низът, получен от

s

чрез изтриване на

i

-тия бит. Разглеждаме

T=\{\widehat s\mid s\in S\}\subseteq\{0,1\}^{n-1}.

Понеже изтриването на един бит комутира с вземането на мнозинство, от свойството

P_\ell

за

S

следва свойството

P_\ell

за

T

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

T

има и свойството

P_k

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

M(\widehat{x}_1,\ldots,\widehat{x}_{2k+1})=\widehat y

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

T

. Значи има

s\in S

\widehat s=\widehat y

. Такъв низ

s

може да бъде само

y

или

y_i

. Но

y\notin S

, затова

s=y_i

, както искахме. Сега вземаме общо

2\ell+1

низа измежду

y_1,\ldots,y_n

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

1

. Понеже

n\ge3

, нито един от низовете

y_i

не е взет повече от

\ell

пъти. При фиксирана координата

i

само низът

y_i

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

y

; всички останали избрани низове имат бита на

y

. Затова мнозинството на избраните

2\ell+1

низа е точно

y

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

S

, а

S

има свойството

P_\ell

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

y

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

S

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

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

Задача 6

Пълен запис

Условие

Алиса и Боб играят игра. Първо Алиса тайно избира крайно множество

S

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

\ell

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

+1

или

-1

, тя казва на Боб броя на точките от

S

, лежащи на

\ell

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

S

. Докажете, че ако Алиса избере

S

във вида

S=\{(x,y)\in\mathbb Z^2\mid m\le x^2+y^2\le n\}

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

m

n

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

S

е от този вид.

Решение

Боб веднага знае броя

N=|S|

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

m

n

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

T\subseteq\mathbb Z^2

N

точки множеството

S

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

F(T)=\sum_{(x,y)\in T}(x^2+y^2)(m+n-(x^2+y^2)).

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

r=x^2+y^2

и е

r(m+n-r)=\left(\frac{m+n}2\right)^2-\left(r-\frac{m+n}2\right)^2.

Тя е най-голяма точно за стойности на

r

, най-близки до

(m+n)/2

. Понеже

S

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

m\le r\le n

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

N

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

F(S)

. Нека

(X,Y)

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

S

. Данните по вертикалните прави дават разпределението на

X

, данните по хоризонталните прави дават разпределението на

Y

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

-1

+1

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

X+Y

X-Y

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

X

Y

X+Y

X-Y

. Сега

\begin{align*} \frac{F(S)}N &=\mathbb E\left[(m+n)(X^2+Y^2)-(X^2+Y^2)^2\right]\\ &=(m+n)(\mathbb E[X^2]+\mathbb E[Y^2])-\mathbb E[X^4]-\mathbb E[Y^4]-2\mathbb E[X^2Y^2]. \end{align*}

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

\mathbb E[X^2Y^2]=

\frac{\mathbb E[(X+Y)^4]+\mathbb E[(X-Y)^4]-2\mathbb E[X^4]-2\mathbb E[Y^4]}{12}.

Така

F(S)

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

T

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

X

Y

X+Y

X-Y

, следователно същата стойност на

F

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

T=S

. Значи данните определят

S

еднозначно и Боб може да спечели.

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

2019

3 задачи

Задача 2

Пълен запис

Условие

Нека

\mathbb Z/n\mathbb Z

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

n

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

n

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

g\colon\mathbb Z/n\mathbb Z\to\mathbb Z/n\mathbb Z,

такава че функциите

g(x),\quad g(x)+x,\quad g(x)+2x,

\quad\ldots,\quad g(x)+100x

са биекции на

\mathbb Z/n\mathbb Z

Решение

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

n

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

101!

. Първо, ако

\gcd(n,101!)=1

, вземаме

g(x)=x

. Тогава

g(x)+tx=(t+1)x

за

t=0,1,\ldots,100

, а умножението по

t+1

е биекция по модул

n

, понеже

t+1

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

n

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

g

съществува, и нека

p\le101

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

n

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

k=0,1,\ldots,100

е изпълнено

k!\sum_{x\in\mathbb Z/n\mathbb Z}x^k\equiv0\pmod n.

За фиксирано

x

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

G_x(T)=g(x)+Tx.

Крайната разлика от ред

k

на полинома

G_x(T)^k

дава

k!x^k=\sum_{i=0}^k(-1)^{k-i}\binom ki G_x(i)^k.

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

x

по модул

n

. За всяко

i=0,1,\ldots,k

функцията

x\mapsto G_x(i)=g(x)+ix

е биекция, следователно сумата на

G_x(i)^k

по всички

x

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

0

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

p

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

n

, числото

k!

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

n

за

0\le k\le p-1

. Значи

\sum_{x\in\mathbb Z/n\mathbb Z}x^k\equiv0\pmod n\qquad(k=0,1,\ldots,p-1).

Това е същото като

n\mid 1^k+2^k+\cdots+n^k

за тези

k

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

M

дели

1^k+2^k+\cdots+n^k

за

k=0,1,\ldots,p-1

p\mid n

, тогава

\nu_p(M)\lt{}\nu_p(n)

. Наистина, всяка целочислена полиномна функция от степен най-много

p-1

има сума, деляща се на

M

. Прилагаме това към

(x-1)(x-2)\cdots(x-(p-1))=(p-1)!\binom{x-1}{p-1}.

Получаваме

M\mid (p-1)!\sum_{x=1}^n\binom{x-1}{p-1}=(p-1)!\binom np.

Но

p

не дели

(p-1)!

, а

\nu_p\binom np=\nu_p(n)-1

, така че

\nu_p(M)\lt{}\nu_p(n)

. Прилагаме лемата с

M=n

. Тя казва

\nu_p(n)\lt{}\nu_p(n)

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

n

не е най-много

101

, тоест

n

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

101!

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

Задача 3

Пълен запис

Условие

Змия с дължина

k

е фигура, която заема наредена

k

-торка

(s_1,\ldots,s_k)

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

n\times n

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

s_i

s_{i+1}

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

i=1,\ldots,k-1

. Ако в момента змията заема

(s_1,\ldots,s_k)

s

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

s_1

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

(s,s_1,\ldots,s_{k-1})

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

(s_1,s_2,\ldots,s_k)

, а след краен брой ходове заема

(s_k,s_{k-1},\ldots,s_1)

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

n\gt{}1

, за което в мрежа

n\times n

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

0.9n^2

, която може да се обърне?

Решение

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

G

е неориентиран граф. Змия с дължина

k

G

заема наредени

k

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

G

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

r

\ell

. Вземаме

r

дълги главни пътя

p_1,\ldots,p_r

, като

p_i

води от

A_i

до

B_i

и има дължина поне

\ell

. Добавяме свързващи пътища от

B_i

до

A_{i+1}

за

i=1,\ldots,r-1

и от

B_r

до

A_1

. Така получаваме голям цикъл

A_1B_1A_2B_2\cdots A_rB_rA_1.

Накрая добавяме транзитни пътища от

A_1

до всеки от

A_2,\ldots,A_r

и от

B_r

до всеки от

B_1,\ldots,B_{r-1}

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

(r-1)\ell

с опашка в

A_1

и тяло по големия цикъл в посоката

A_1,B_1,A_2,B_2,\ldots

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

B_{r-1}

, минава по транзитен път до

B_r

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

A_r

. Във фаза

i=2,3,\ldots,r-1

тя минава по транзитен път до

A_1

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

B_{r-i}

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

B_r

, и назад по големия цикъл до

A_{r-i+1}

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

A_1

. Понеже змията е по-къса от сумарната дължина на

r-1

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

n\times n

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

a_1, \ldots,a_{r+1}

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

b_1, \ldots,b_r

по колоната

n-2

, като

b_i

е в реда на

a_{i+1}

. Главният път от

a_i

до

b_i

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

(n-1)

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

G

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

r

n\to\infty

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

\frac{r-1}{r}n^2.

Избираме

r

достатъчно голямо, така че

(r-1)/r\gt{}0.9

, а после избираме

n

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

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

Задача 4

Пълен запис

Условие

Наричаме функция

f\colon\mathbb Z_{\ge0}\times\mathbb Z_{\ge0}\to\mathbb Z

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

m

n

е изпълнено

f(m+1,n+1)f(m,n)-f(m+1,n)f(m,n+1)=1.

Ако

A=(a_0,a_1,\ldots)

B=(b_0,b_1,\ldots)

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

A\sim B

, ако съществува чудесна функция

f

, за която

f(n,0)=a_n

f(0,n)=b_n

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

n

; в частност

a_0=b_0

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

A

B

C

D

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

A\sim B

B\sim C

C\sim D

, то

D\sim A

Решение

Ще използваме следната класификация. Двойката редици

(A,B)

е чудесна, тоест

A\sim B

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

a_0=b_0,\qquad a_0\mid a_1b_1+1,

и за всяко

n\ge1

a_n\mid a_{n-1}+a_{n+1},\qquad b_n\mid b_{n-1}+b_{n+1}.

Първо доказваме необходимостта. Равенството

a_0=b_0

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

(0,0),(1,0),(0,1),(1,1)

получаваме

a_0f(1,1)-a_1b_1=1,

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

a_0\mid a_1b_1+1

. Сега гледаме шест стойности в две съседни колони:

u=f(n-1,1),\quad v=f(n,1),\quad w=f(n+1,1).

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

va_{n-1}-ua_n=1,\qquad wa_n-va_{n+1}=1.

Като съберем подходящо, получаваме

u+w=\frac{v(a_{n-1}+a_{n+1})}{a_n}.

Освен това

\gcd(v,a_n)=1

, затова

a_n\mid a_{n-1}+a_{n+1}

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

B

. Ако

a_n=0

, двете равенства принуждават

va_{n-1}=1

va_{n+1}=-1

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

f(1,1)

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

a_0f(1,1)-a_1b_1=1,

което е възможно по условието. После попълваме таблицата клетка по клетка. Ако пет стойности

\begin{matrix}u&x\\ v&y\\ w&z\end{matrix}

са известни без

z

, избираме

z=y\cdot\frac{u+w}{v}-x

когато

v\ne0

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

1

на новия квадрат. Ако

v=0

, от съседните детерминанти следва, че съседните стойности са

\pm1

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

1

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

A=(a_n),\quad B=(b_n),\quad C=(c_n),\quad D=(d_n).

От

A\sim B

B\sim C

C\sim D

следва

a_0=b_0=c_0=d_0=k.

Освен това всяка от четирите редици удовлетворява вътрешното условие

x_n\mid x_{n-1}+x_{n+1}

за

n\ge1

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

(D,A)

. Имаме

k\mid a_1b_1+1,\qquad k\mid b_1c_1+1,\qquad k\mid c_1d_1+1.

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

(a_1b_1)(b_1c_1)(c_1d_1)\equiv -1\pmod k.

Но от средното сравнение

(b_1c_1)^2\equiv1\pmod k

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

a_1d_1\equiv -1\pmod k,

тоест

k\mid d_1a_1+1

. По класификацията това означава

D\sim A

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

2020

4 задачи

Задача 1

Пълен запис

Условие

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

b_1,b_2,\ldots

, така че

1=\frac{b_1}{1^2}\gt{}\frac{b_2}{2^2}\gt{}\frac{b_3}{3^2}\gt{}\frac{b_4}{4^2}\gt{}\cdots.

Нека

r

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

\frac{b_n}{n^2}\ge r

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

n

. Намерете всички възможни стойности на

r

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

(b_n)

Решение

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

r

0\le r\le\frac12

. Първо, очевидно

r\ge0

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

n\ge1

е изпълнено

\frac{b_n}{n^2}\le \frac12+\frac1{2n}.

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

n=1

това следва от

b_1=1

. За индукционната стъпка имаме

\begin{align*} b_n&\lt{}n^2\frac{b_{n-1}}{(n-1)^2}\le n^2\left(\frac12+\frac1{2(n-1)}\right)\\ &=\frac{n^3}{2(n-1)}=\frac12\left(n^2+n+1+\frac1{n-1}\right)\\ &=\frac{n(n+1)}2+\frac12\left(1+\frac1{n-1}\right)\le \frac{n(n+1)}2+1. \end{align*}

Понеже

b_n

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

b_n\le\frac{n(n+1)}2

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

n\to\infty

получаваме

r\le\frac12

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

r=\frac12

вземаме

b_n=\frac{n(n+1)}2,

а за

r=0

вземаме

b_n=1

за всяко

n

. Нека сега

0\lt{}r\lt{}\frac12

. Избираме

N

достатъчно голямо, така че

\left\lceil rn^2+n\right\rceil\lt{}\frac{n(n+1)}2

за всяко

n\ge N

, и дефинираме

b_n=\begin{cases}\left\lceil rn^2+n\right\rceil,& n\ge N,\\ \frac{n^2+n}2,& n\lt{}N.\end{cases}

Тогава

\frac{b_n}{n^2}=\frac{rn^2+n+O(1)}{n^2}\to r,

така че най-голямата долна граница е

r

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

n\lt{}N

от формулата

\frac{n+1}{2n}

, а преходът през

N

е осигурен от избора на

N

. За

n\ge N

имаме

\frac{b_n}{n^2}\ge\frac{rn^2+n}{n^2}\gt{}

\frac{r(n+1)^2+(n+1)+1}{(n+1)^2}\ge\frac{b_{n+1}}{(n+1)^2},

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

\frac1n\gt{}\frac{n+2}{(n+1)^2}

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

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

Задача 3

Пълен запис

Условие

Нека

\alpha\ge1

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

n

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

\alpha n

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

\alpha

Хефест може да си гарантира победа за краен брой ходове, независимо кои клетки е наводнил Посейдон в началото?

Решение

Отговорът е

\alpha\gt{}2.

Ще докажем, че при

\alpha\gt{}2

Хефест има печеливша стратегия, а при

\alpha=2

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

\alpha\le2

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

\alpha\gt{}2

. Въвеждаме координати от

\mathbb Z^2

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

(x,y)

|x|+|y|\le d

за някое

d\ge2

. Тогава на

k

-тия ход на Хефест водата се съдържа в областта

|x|+|y|\le d+k-1

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

N_1

N_2

, за които

\begin{align*} \alpha N_1&\gt{}2N_1+(2d+3),\\ \alpha(N_1+N_2)&\gt{}2N_2+(6N_1+8d+4). \end{align*}

Маркираме точките

X_i,Y_i

за

1\le i\le6

, както е показано на схемата; червените означения показват съответните разстояния по страните на правоъгълника.Стратегията е следната. 1. На ход

1

Хефест поставя стената

X_1Y_1

. Така спира разпространението на север. 2. От ход

2

до ход

N_1+1

той удължава дигата до отсечката

X_2Y_2

, като продължава да не допуска вода на север. 3. На ход

N_1+2

добавя наведнъж начупените линии

X_4X_3X_2

Y_4Y_3Y_2

. Така спира потопа от запад и от изток. 4. От ход

N_1+2

до ход

N_1+N_2+1

удължава дигата по отсечките

X_4X_5

Y_4Y_5

, като държи водата между тях. 5. На ход

N_1+N_2+2

добавя наведнъж начупената линия

X_5X_6Y_6Y_5

и затваря контура. Изборът на

N_1

N_2

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

\alpha n

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

\alpha\gt{}2

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

\alpha=2

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

(n+1)

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

2n+4

стени. Нека

c_0,c_1,\ldots,c_n

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

c_0

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

i\ge1

клетката

c_i

се наводнява на

i

-тия ход на Посейдон от клетката

c_{i-1}

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

c_i

c_j

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

|i-j|=1

. Наистина, ако са съседни и

|i-j|\gt{}1

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

c_i

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

c_i

; това са ребрата от границата на полученото полимино. Понеже полиминото има

n+1

клетки и точно

n

вътрешни общи ребра, зелените ребра са точно

4(n+1)-2n=2n+4.

От центъра на всяка клетка

c_i

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

2n+4

лазера. На схемата е показан пример за

n=6

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

w

е улучена от лазери, излизащи от

c_i

c_j

. Без загуба на общност тези два лазера са вертикални, така че

c_i

c_j

са в една и съща колона. Ако

w

лежи между

c_i

c_j

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

w

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

i\lt{}j

. Тогава между

c_i

c_j

няма стена. Нека

\rho\ge1

е разстоянието между центровете на

c_i

c_j

. Клетката

c_j

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

c_i

по права линия за най-много

\rho

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

j=i+\rho

и клетките

c_i,c_{i+1},\ldots,c_j

образуват една колона. Но тогава вертикалните лазери от

c_i

c_j

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

2n+4

-те лазерни отсечки удря различна стена. Значи на

(n+1)

-вия ход дължината на дигата е поне

2n+4

, откъдето

\alpha\ge\frac{2n+4}{n+1}\gt{}2.

Това доказва, че при

\alpha=2

Хефест няма гарантирана победа, и завършва решението.

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

Задача 4

Пълен запис

Условие

За краен прост граф

G

дефинираме

G'

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

u

v

двойката

\{u,v\}

е ребро в

G'

точно когато

u

v

имат общ съсед в

G

. Докажете, че ако крайният прост граф

G

е изоморфен на

(G')'

, то

G

е изоморфен и на

G'

Решение

Ще наречем връх на графа опасен, ако има степен поне

3

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

G'

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

G

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

G

има опасен връх. Наистина, всеки триъгълник в

G

остава триъгълник в

G'

, защото всяка двойка негови върхове има третия за общ съсед. Ако

v

е опасен връх, съседите на

v

образуват клика в

G'

, която не е била клика в

G

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

G\cong(G')'

, броят на триъгълниците в

G

и в

(G')'

е един и същ. От току-що доказаното следва, че нито

G

, нито

G'

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

3

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

2

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

G'

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

G

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

G'

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

G

, а

(G')'

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

G'

. Това е несъвместимо с

G\cong(G')'

. Затова графите, които могат да удовлетворят

G\cong(G')'

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

G'\cong G

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

G\cong G'

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

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

Задача 5

Пълен запис

Условие

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

n\ge2

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

m

и полином

P(x)

с цели коефициенти, удовлетворяващи следните три условия: -

m\gt{}1

\gcd(m,n)=1

; - числата

P(0),P^2(0),\ldots,P^{m-1}(0)

не се делят на

n

; - числото

P^m(0)

се дели на

n

. Тук

P^k

означава

k

-кратно прилагане на

P

, така че

P^1(0)=P(0)

P^2(0)=P(P(0))

и т.н.

Решение

Отговорът е: това е възможно точно когато съществуват прости числа

p'\lt{}p

, такива че

p\mid n

, но

p'\nmid n

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

n

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

P

и цяло число

N

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

\mathbf{zord}(P\bmod N)=\min\{e\gt{}0\mid P^e(0)\equiv0\pmod N\},

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

0

. По китайската теорема за остатъците имаме

\mathbf{zord}(P\bmod N)=\operatorname*{lcm}_{q\mid N}\mathbf{zord}(P\bmod q),\tag{1}

където

q

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

N

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

p^e

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

1\le k\lt{}p

. Тогава полиномът

f(X)=

X+1-k\cdot\frac{X(X-1)(X-2)\cdots(X-(k-2))}{(k-1)!},

разглеждан в

(\mathbb Z/p^e\mathbb Z)[X]

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

\mathbf{zord}(f\bmod p^e)=k.

При

k=1

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

1

. Наистина, понеже

(k-1)!

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

p^e

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

f(0)=1,\quad f(1)=2,\quad\ldots,

\quad f(k-2)=k-1,\quad f(k-1)=0.

Сега нека

p'\lt{}p

са прости числа,

p\mid n

p'\nmid n

. За простата степен

p^e\mid n

с основа

p

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

\mathbf{zord}=p'

. За всяка друга проста степен

q

, деляща

n

, изискваме

P(0)\equiv0\pmod q

, тоест

\mathbf{zord}(P\bmod q)=1

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

P\in\mathbb Z[x]

, който удовлетворява всички тези условия едновременно. От (1) следва

\mathbf{zord}(P\bmod n)=p'.

Поставяме

m=p'

. Тогава

m\gt{}1

\gcd(m,n)=1

, защото

p'\nmid n

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

q=p^e

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

f(x)\in\mathbb Z[x]

, а

\mathbf{zord}(f\bmod q)

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

p

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

e

. При

e=1

принципът на Дирихле дава веднага

\mathbf{zord}(f\bmod p)\le p

, защото преди първото попадане в

0

остатъците

0,f(0),f^2(0),\ldots

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

0

. Нека

e\ge2

и поставим

k=\mathbf{zord}(f\bmod p^{e-1}),\qquad Q=f^k.

За да се стигне до

0

по модул

p^e

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

0

по модул

p^{e-1}

, затова

\mathbf{zord}(f\bmod p^e)=k\cdot\mathbf{zord}(Q\bmod p^e).

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

k

са най-много

p

. Освен това

Q(0)\equiv0\pmod{p^{e-1}}

, а оттук и всички числа

Q(0),Q^2(0),\ldots

са кратни на

p^{e-1}

. По модул

p^e

има само

p

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

\mathbf{zord}(Q\bmod p^e)\le p.

Така и

\mathbf{zord}(f\bmod p^e)

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

p

. Сега нека за дадено

n

съществуват

m

P

от условието. Тогава

m=\mathbf{zord}(P\bmod n)

\gcd(m,n)=1

. От (1) някоя проста степен

p^e\mid n

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

p'

на

m

. По току-що доказаното

p'\le p

, а от

\gcd(m,n)=1

следва

p'\nmid n

. Ако беше

p'=p

, това би противоречало на

p\mid n

, значи

p'\lt{}p

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

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

2021

1 задача

Задача 1

Пълен запис

Условие

Да се определят всички цели числа

s\ge4

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

a,b,c,d

такива, че

s=a+b+c+d

s

дели

abc+abd+acd+bcd

Решение

Отговорът е: точно съставните числа

s

. Първо нека

s

е съставно. Записваме

s=(w+x)(y+z)

, където

w,x,y,z

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

s=uv

u,v\ge2

, можем да вземем

w=1

x=u-1

y=1

z=v-1

. Поставяме

a=wy,\qquad b=wz,\qquad c=xy,\qquad d=xz.

Тогава

a+b+c+d=(w+x)(y+z)=s

abc+abd+acd+bcd=wxyz(w+x)(y+z),

което е кратно на

s

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

s

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

s

не може да работи. Ако такива

a,b,c,d

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

\begin{align*} (a+b)(a+c)(a+d)&=abc+abd+acd+bcd+a^2(a+b+c+d)\\ &\equiv0\pmod s. \end{align*}

Понеже

a,b,c,d

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

s

, всяко от числата

a+b

a+c

a+d

е положително и по-малко от

s

. Ако

s

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

s

. Значи

s

не е просто. Алтернативно, при просто

s

полиномът

(x-a)(x-b)(x-c)(x-d)\in\mathbb F_s[x]

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

x^3

и пред

x

, понеже

a+b+c+d\equiv0\pmod s

abc+abd+acd+bcd\equiv0\pmod s

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

\mathbb F_s

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

s

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

a,b,c,d

би бил поне

2s

, противоречие.

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

2023

3 задачи

Задача 3

Пълен запис

Условие

Разглеждаме двойки

(f,g)

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

f(0)\ge f(1)\ge f(2)\ge\dots\ge f(300)\ge0

; -

f(0)+f(1)+f(2)+\dots+f(300)\le300

; - за произволни

20

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

n_1,n_2,\ldots,n_{20}

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

g(n_1+n_2+\dots+n_{20})\le

f(n_1)+f(n_2)+\dots+f(n_{20}).

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

g(0)+g(1)+\dots+g(6000)

Решение

Ще докажем малко по-общо твърдение. Нека

300

се замени с

\frac{s(s+1)}2

, където тук

s=24

, а числото

20

се замени с

k

. Отговорът тогава е

\frac{ks(ks+1)}2,

което за

s=24

k=20

дава

115440

. Равенство се достига при

f(n)=\max(s-n,0),\qquad g(n)=\max(ks-n,0).

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

\max(x_1+\dots+x_k,0)\le \max(x_1,0)+\dots+\max(x_k,0),

където

x_i=s-n_i

. То следва от случая

k=2

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

p\colon\mathbb Z_{\ge0}\to\mathbb Z_{\ge0}

, която от някой момент нататък е нула. Нейният сбор е

\sum_{n=0}^{\infty}p(n)

. Диаграмата на Юнг на

p

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

\mathcal P=\{(x,y)\in\mathbb Z_{\ge0}^2:y\lt{}p(x)\}.

Броят точки в

\mathcal P

е точно сборът на

p

. Спрегнатото разбиение е

p_*(n)=\#\{i:p(i)\gt{}n\},

и има същия сбор; геометрично неговата диаграма на Юнг е отражението на

\mathcal P

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

x=y

. Понеже всяка стойност на

g(n)

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

g(n)=\min_{n_1+\dots+n_k=n}\bigl(f(n_1)+\dots+f(n_k)\bigr).\tag{1}

От условията следва

f\bigl(\frac{s(s+1)}2\bigr)=0

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

n\le k\frac{s(s+1)}2

в минимума в (1) може да се избере оптимална

k

-торка, в която всяко

n_i

е най-много

\frac{s(s+1)}2

: ако някой член е по-голям, заменяме го с

\frac{s(s+1)}2

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

f

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

f

с нули след

\frac{s(s+1)}2

и да разглеждаме

f

като разбиение със сбор

\frac{s(s+1)}2

. Тогава и

g

е разбиение. Ключовото твърдение е, че задачата е инвариантна при спрегнато разбиение:

g_*(n)=

\min_{n_1+\dots+n_k=n}\bigl(f_*(n_1)+\dots+f_*(n_k)\bigr).\tag{2}

Нека

\mathcal F

\mathcal G

са диаграмите на Юнг на

f

g

, а

\overline{\mathcal F}

\overline{\mathcal G}

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

\mathbb Z_{\ge0}^2

. Долната граница на

\overline{\mathcal F}

се състои от точките

(n,f(n))

. По дефиницията на

g

долната граница на

\overline{\mathcal G}

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

k

точки от

\overline{\mathcal F}

, тоест

\overline{\mathcal G}=\underbrace{\overline{\mathcal F}+\dots+\overline{\mathcal F}}_{k\text{ пъти}},

където

+

е събиране на множества. Това описание не се променя при отражение спрямо

x=y

, което разменя всяко разбиение със спрегнатото му. Следователно (2) е вярно. Нека

A

е сборът на

g

. Първо, от тъждеството на Ермит

n=\sum_{i=0}^{k-1}\left\lfloor\frac{n+i}{k}\right\rfloor

получаваме

\begin{align*} A&=\sum_{n=0}^{\infty}g(n)\\ &\le \sum_{n=0}^{\infty}\sum_{i=0}^{k-1}f\left(\left\lfloor\frac{n+i}{k}\right\rfloor\right)\\ &=k^2\sum_{n=0}^{\infty}f(n)-\frac{k(k-1)}2f(0)\\ &=k^2\frac{s(s+1)}2-\frac{k(k-1)}2f(0).\tag{3} \end{align*}

От инвариантността при спрегнато разбиение имаме и

A\le k^2\frac{s(s+1)}2-\frac{k(k-1)}2f_*(0).\tag{4}

За трета оценка забелязваме, че

f(f_*(0))=0

, а значи

g(kf_*(0))=0

. Освен това за

0\le q\lt{}k

0\le r\lt{}f_*(0)

имаме

g(qf_*(0)+r)\le

qf(f_*(0))+(k-q-1)f(0)+f(r)=

(k-q-1)f(0)+f(r).

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

\begin{align*} A&=\sum_{\substack{0\le q\lt{}k\\0\le r\lt{}f_*(0)}}g(qf_*(0)+r)\\ &\le \frac{k(k-1)}2f_*(0)f(0)+k\sum_{0\le r\lt{}f_*(0)}f(r)\\ &=\frac{k(k-1)}2f_*(0)f(0)+k\frac{s(s+1)}2.\tag{5} \end{align*}

Сега разглеждаме три случая. Ако

f(0)\ge s

, то от (3)

A\le k^2\frac{s(s+1)}2-\frac{k(k-1)}2s=\frac{ks(ks+1)}2.

Ако

f_*(0)\ge s

, аналогично от (4) получаваме същата оценка. В оставащия случай

f(0)\lt{}s

f_*(0)\lt{}s

, откъдето

f(0)f_*(0)\le s^2

; тогава (5) дава

A\le \frac{k(k-1)}2s^2+k\frac{s(s+1)}2=\frac{ks(ks+1)}2.

Във всички случаи

A\le\frac{ks(ks+1)}2

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

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

Задача 4

Пълен запис

Условие

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

a

b

означаваме с

a\oplus b

тяхното побитово xor. Например

9\oplus10=1001_2\oplus1010_2=0011_2=3.

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

a

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

x\gt{}y\ge0

е изпълнено

x\oplus ax\ne y\oplus ay.

Решение

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

a

. Първо нека

a

е четно и

\nu_2(a)=k\gt{}0

. Ще покажем, че числото

x

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

c=x\oplus ax.

Понеже

a

е кратно на

2^k

, последните

k

бита на

ax

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

k

бита на

c

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

k

бита на

x

. След като ги знаем, знаем и последните

2k

бита на

ax

, защото умножението по

a

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

k

позиции. Следователно можем да възстановим последните

2k

бита на

x

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

3k

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

4k

бита и т.н. Така всички битове на

x

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

c

, следователно функцията

x\mapsto x\oplus ax

е инжективна. Сега нека

a

е нечетно. Избираме

n

така, че

2^n\gt{}a

, и поставяме

x=\underbrace{11\dots1}_n=2^n-1,\qquad y=2^n+1=1\underbrace{00\dots0}_{n-1}1.

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

x\oplus ax=y\oplus ay

. Нека

P

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

a

, допълнен с водещи нули до дължина

n

, а

Q

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

a-1

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

n

. Нека

R

е побитовото допълнение на

Q

. Тогава

P,Q,R

са двоични низове с дължина

n

. Понеже

a

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

P

към

Q

само сменя последния бит от

1

на

0

. Имаме

ax=a(2^n-1)=a2^n-a=(a-1)2^n+(2^n-a),

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

ax

по блокове с дължина

n

\overline{QR}

. Понеже

x

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

n

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

x\oplus ax=\overline{QQ}.

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

ay=a(2^n+1)=a2^n+a,

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

ay

по същите блокове е

\overline{PP}

. Числото

y

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

y\oplus ay=\overline{QQ}.

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

a

не работи.

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

Задача 6

Пълен запис

Условие

Фиксирана е функция

f\colon\mathbb N\to\mathbb N

. За

m,n\in\mathbb N

дефинираме

\Delta(m,n)=f^{f(n)}(m)-f^{f(m)}(n),

където

f^r

означава

r

-кратно прилагане на

f

. Ако

\Delta(m,n)\ne0

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

m,n\in\mathbb N

, докажете, че

\Delta

е неограничена: за всяка константа

C

съществуват

m,n\in\mathbb N

\left\lvert\Delta(m,n)\right\rvert\gt{}C

Решение

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

N

, за което

\left\lvert\Delta(m,n)\right\rvert\le N

за всички

m,n

. Първо,

f

е инжективна, защото

f(m)=f(n)\implies \Delta(m,n)=0\implies m=n.

Нека

G

е насоченият граф на стрелките на

f

: върховете са положителните цели числа, а от

n

излиза ребро към

f(n)

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

G

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

G

няма цикли. Ако

f^k(n)=n

за някои

k\ge2

n

, то при променливо

m

числата

\Delta(m,n)

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

f^{f(m)}(n)

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

n

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

f^{f(n)}(m)

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

m_1,m_2

бихме имали

f^{f(n)}(m_1)=f^{f(n)}(m_2)

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

f

. Второ,

G

има най-много

2N+1

вериги. Наистина, нека

m_1,\ldots,m_k

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

B\gt{}\max\{f(m_1),\ldots,f(m_k)\}

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

\left\lvert\Delta\left(m_i,f^{B-f(m_i)}(1)\right)\right\rvert\le N,

тоест

\left\lvert f^B(1)-f^{f^{B-f(m_i)+1}(1)}(m_i)\right\rvert\le N.

Понеже върховете

m_i

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

f^{f^{B-f(m_i)+1}(1)}(m_i)

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

2N+1

цели числа около

f^B(1)

, така че

k\le2N+1

. Трето,

G

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

c

. Наричаме число лошо, ако не е от вида

f^k(c)

за никое

k\ge0

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

f^{f(c)}(n)

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

M

нататък. Избираме

B\gt{}A\ge M

. Ако

f^{f(c)}(n)\in[A,B]

, тогава от

\left\lvert\Delta(c,n)\right\rvert\le N

имаме

f^{f(n)}(c)\in[A-N,B+N]

. При различни

n

тези стойности са различни, защото в графа няма цикли и има само вериги. Значи в интервала

[A-N,B+N]

има поне

B-A+1

добри числа и най-много

2N

лоши числа. Като оставим

B

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

A-N

има най-много

2N

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

c

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

c

, ако има такива, са крайно много; преместваме

c

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

f^k(c)

за единствено

k\ge0

. Дефинираме биекция

g\colon\mathbb Z_{\ge0}\to\mathbb N

чрез

g(k)=f^k(c).

Тогава

\delta(a,b):=\Delta(f^a(c),f^b(c))=

g(g(b+1)+a)-g(g(a+1)+b).

Условията стават

\left\lvert\delta(a,b)\right\rvert\le N

за всички

a,b\ge0

\delta(a,b)\ne0

при

a\ne b

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

g(a+1)-a\ne g(b+1)-b\qquad(a\ne b),

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

g(x)-x

е инжективна за

x\ge1

. Нужна ни е една лема. За всяко

M

съществува

x\ge0

, за което

g(x)\le x-M

. Ако това не е вярно, то

g(x)-x

е ограничена отдолу. Вземаме голямо положително

K

. Понеже стойностите

g(x)-x

за

x\ge1

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

B

, такова че

g(x)-x\ge K

за всички

x\ge B

. Тогава всички стойности

g(B+1),g(B+2),\ldots

са поне

B+K

, а първите

B+1

стойности

g(0),\ldots,g(B)

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

B+1

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

K-1

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

g

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

B

, за които

g(B)+N\le B\qquad\text{и}\qquad g(B)\gt{}N.

Такива

B

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

M

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

g(B)\le N

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

M

. Поставяме

t=

\max\{g^{-1}(g(B)-N),g^{-1}(g(B)-N+1),\ldots,g^{-1}(g(B)+N)\}.

Понеже

g(t)\le g(B)+N\le B

, имаме

\left\lvert\delta(t-1,B-g(t))\right\rvert=

\left\lvert g(B)-g(t-1+g(B+1-g(t)))\right\rvert\le

N.

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

t-1+g(B+1-g(t))\in

\{g^{-1}(g(B)-N),\ldots,g^{-1}(g(B)+N)\}.

По максималността на

t

получаваме

g(B+1-g(t))=1

, тоест

B+1-g(t)=g^{-1}(1).

А от

\left\lvert g(t)-g(B)\right\rvert\le N

следва

\left\lvert (B-g(B))+1-g^{-1}(1)\right\rvert\le N.

Това е вярно за безкрайно много стойности на

B

. Но за различни такива

B

стойностите

B-g(B)

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

g(x)-x

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

\Delta

е невъзможно.

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

2024

4 задачи

Задача 1

Пълен запис

Условие

Да се намери най-малката константа

C\gt{}1

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

n\ge2

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

a_1,a_2,\ldots,a_n

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

\frac1{a_1}+\frac1{a_2}+\cdots+\frac1{a_n}=1,

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

b_i

, такива че: (i) за всяко

i=1,2,\ldots,n

имаме или

b_i=\lfloor a_i\rfloor

, или

b_i=\lfloor a_i\rfloor+1

; (ii) изпълнено е

1\lt{}\frac1{b_1}+\frac1{b_2}+\cdots+\frac1{b_n}\le C.

Решение

Отговорът е

C=\frac32.

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

a_1=\frac{4n-3}{2n-1},\qquad a_i=\frac{4n-3}{2}\quad(i\gt{}1).

Тогава

b_1\in\{1,2\}

, а за

i\gt{}1

имаме

b_i\in\{2n-2,2n-1\}

. Ако изберем

b_1=2

, получаваме

\frac1{b_1}+\frac1{b_2}+\cdots+\frac1{b_n}\le

\frac12+(n-1)\cdot\frac1{2n-2}=1,

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

b_1=1

, а тогава

\frac1{b_1}+\frac1{b_2}+\cdots+\frac1{b_n}\ge

1+(n-1)\cdot\frac1{2n-1}=\frac{3n-2}{2n-1}.

При

n\to\infty

това показва

C\ge\frac32

. Остава да докажем, че

C=\frac32

винаги стига. За

0\le k\le n

положете

c_k=

\sum_{i=1}^{k}\frac1{\lfloor a_i\rfloor}+\sum_{i=k+1}^{n}\frac1{\lfloor a_i\rfloor+1}.

Понеже всяко

a_i

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

\lfloor a_i\rfloor+1

\lfloor a_i\rfloor

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

c_0\lt{}c_1\lt{}\cdots\lt{}c_n.

Освен това

c_0\lt{}\frac1{a_1}+\frac1{a_2}+\cdots+\frac1{a_n}=1\lt{}c_n.

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

k

, за което

c_{k-1}\lt{}1\lt{}c_k.

За това

k

имаме

1\lt{}c_k=c_{k-1}+\frac1{\lfloor a_k\rfloor(\lfloor a_k\rfloor+1)}\lt{}

1+\frac1{1\cdot2}=\frac32.

Избираме

b_i=\lfloor a_i\rfloor

за

i\le k

b_i=\lfloor a_i\rfloor+1

за

i\gt{}k

. Тогава сумата на реципрочните стойности е точно

c_k

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

\frac32

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

Задача 3

Пълен запис

Условие

Нека

n\gt{}k\ge1

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

p

дели

\binom nk

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

k

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

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

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

p

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

Решение

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

S

означаваме с

\sigma(S)

сумата на неговите елементи и разглеждаме генериращата функция

\begin{aligned}P(x):=\sum_{\substack{S\subseteq\{1,2,\ldots,n\}\\ |S|=k}}x^{\sigma(S)}.\end{aligned}

Нека

c_j

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

x^j

P(x)

, тоест броят на

k

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

j

. По формулата на Льожандр имаме

\nu_p\binom nk=

\sum_{r=1}^{\infty}\left(\left\lfloor\frac n{p^r}\right\rfloor-\left\lfloor\frac k{p^r}\right\rfloor-\left\lfloor\frac{n-k}{p^r}\right\rfloor\right).

Тъй като

p\mid\binom nk

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

r

, за което

\left\lfloor\frac n{p^r}\right\rfloor-\left\lfloor\frac k{p^r}\right\rfloor-\left\lfloor\frac{n-k}{p^r}\right\rfloor\gt{}0.

Ключовото твърдение е, че

P(x)

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

\Phi_{p^r}(x)=

x^{(p-1)p^{r-1}}+x^{(p-2)p^{r-1}}+\cdots+x^{p^{r-1}}+1.

Първо ще видим защо това решава задачата. Пишем

P(x)=\Phi_{p^r}(x)Q(x)

, където

Q

е полином с цели коефициенти. За

0\le i\lt{}p^r

положете

s_i=\sum_{j\equiv i\pmod{p^r}}c_j.

От множителя

\Phi_{p^r}

следва, че за всяко

0\le t\lt{}p^{r-1}

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

s_t=s_{t+p^{r-1}}=s_{t+2p^{r-1}}=\cdots=s_{t+(p-1)p^{r-1}}.

Сега поставяме подмножество със сума

z

в класа

\left\lfloor\frac{z\bmod p^r}{p^{r-1}}\right\rfloor\in\{0,1,\ldots,p-1\}.

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

s_i

показват, че

p

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

\ell=n-k

. Между

k

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

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

и двоичните низове с

k

нули и

\ell

единици има естествена биекция: подмножеството

\{a_1\lt{}a_2\lt{}\cdots\lt{}a_k\}

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

a_1,a_2,\ldots,a_k

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

(a_1+a_2+\cdots+a_k)-\frac{k(k+1)}2.

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

x

, нашият полином

P(x)

q

-биномният коефициент

\frac{(x-1)(x^2-1)\cdots(x^n-1)}{\big((x-1)(x^2-1)\cdots(x^k-1)\big)\big((x-1)(x^2-1)\cdots(x^{\ell}-1)\big)}.

Множителят

\Phi_{p^r}(x)

участва в

x^m-1

точно когато

p^r\mid m

. Затова кратността му в горния израз е

\left\lfloor\frac n{p^r}\right\rfloor-\left\lfloor\frac k{p^r}\right\rfloor-\left\lfloor\frac{n-k}{p^r}\right\rfloor,

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

r

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

\Phi_{p^r}(x)

дели

P(x)

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

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

Задача 5

Пълен запис

Условие

Нека

a_1\lt{}a_2\lt{}\cdots\lt{}a_{2024}

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

b_1\lt{}b_2\lt{}\cdots\lt{}b_{2024}

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

Решение

Отговорът е

11

. Първо този брой се достига: вземаме

a_i=i,\qquad b_i=2^{i-1}.

Общите членове са

1,2,4,\ldots,1024

, общо

11

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

p

е просто число и разгледаме редицата

\nu_p(a_1),\nu_p(a_2),\ldots,\nu_p(a_{2024}).

Ако

C=\left\lfloor\log_p 2023\right\rfloor,

то в тази редица има най-много

C+2

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

a_i=a+di

\gcd(a,d)=1

. Ако

p\mid d

, тогава

p\nmid a

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

\nu_p(a_i)

са равни на

0

. Нека сега

p\nmid d

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

\{0,1,\ldots,C\}

, с най-много едно изключение. Нека

M=\max_i\nu_p(a_i)

. Ако

M\le C

, няма какво да доказваме. Иначе избираме индекс

m

, за който

\nu_p(a_m)=M

. За всеки

i\ne m

имаме

|i-m|\le2023

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

\nu_p(d(i-m))=\nu_p(i-m)\le C\lt{}M=\nu_p(a_m).

Понеже

a_i=a_m+d(i-m)

, получаваме

\nu_p(a_i)=\nu_p(d(i-m))\le C.

Така

a_m

е единственото възможно изключение и твърдението е доказано. Връщаме се към геометричната прогресия. Нека

r\in\mathbb Q

е нейното частно. Ако съществува просто число

p\ge3

\nu_p(r)\ne0

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

p

-адични валуации. Следователно общите членове са най-много броя на различните стойности в редицата

\nu_p(a_i)

, което е не повече от

2+\log_3 2023\lt{}11.

Остава случаят, когато частното

r

е степен на

2

. Понеже геометричната прогресия е растяща и от цели числа, можем да пишем

r=2^t

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

t

. От вече доказаното за

p=2

имаме груба горна граница

12

, защото

\lfloor\log_2 2023\rfloor=10

. Ако

t\ge2

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

12

. Значи единственият начин да се надяваме на

12

общи члена е

r=2

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

r=2

има

12

общи члена. Тогава стойностите на

\nu_2(a_i)

сред тях трябва да са

0,1,\ldots,10,M

за някое

M\ge11

. Нека

b

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

2b

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

b

. Но прогресия от

2024

члена, която съдържа

b

и има разлика най-много

b

, не може да има член по-голям от

b+2023b=2024b.

От друга страна, общият член с валуация

M\ge11

2^M b\gt{}2024b

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

12

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

11

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

Задача 6

Пълен запис

Условие

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

f:\mathbb R\to\mathbb R

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

x

y

е изпълнено функционалното уравнение

f(xf(y))+f(y)=f(x+y)+f(xy).

Решение

Всички константни функции са решения, а също така работи и

f(x)\equiv x+1

. Ще докажем, че други решения няма. Нека

P(x,y)

означава даденото равенство. Твърдение 1. Ако

f

е периодична, то

f

е константна. Нека

d\ne0

е период на

f

. От

P(x,y+d)

получаваме

f(x(y+d))=f(x+y+d)-f(y+d)-f(xf(y+d))=

f(x+y)-f(y)-f(xf(y)).

Сравнено с

P(x,y)

, това дава

f(x(y+d))=f(xy)

. При

y=0

следва

f(dx)=f(0)

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

x

, а понеже

d\ne0

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

x,y

е изпълнено

f(f(x)+y)=f(f(y)+x).

Наистина, от

P(f(x),y)

и после от

P(y,x)

имаме

\begin{align*} f(f(x)f(y))&=f(f(x)+y)+f(f(x)y)-f(y)\\ &=f(f(x)+y)+f(x+y)+f(xy)-f(x)-f(y). \end{align*}

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

x

y

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

f

не е константна, то

f(f(x)+y)=f(x)+f(y)

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

x,y

. Нека

d=f(f(x)+y)-f(x)-f(y).

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

z

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

\begin{align*} f(z+f(f(x)+y))&=f(f(z)+f(x)+y)\\ &=f(f(x)+f(z)+y)\\ &=f(x+f(f(z)+y))\\ &=f(x+f(f(y)+z))\\ &=f(f(x)+f(y)+z)\\ &=f(z+f(x)+f(y)). \end{align*}

Ако

d\ne0

, това прави

f

периодична с период

d

, противоречие с Твърдение 1. Значи

d=0

. Твърдение 4. Ако

f

не е константна, то

f(0)=1

f(x+1)=f(x)+1.

От

P(z,0)

имаме

f(zf(0))=f(z)

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

z

. От друга страна, сравнявайки

P(xf(0),y)

P(x,y)

, получаваме

\begin{align*} f(xf(0)+y)&=f(y)+f(xf(0)f(y))-f(xf(0)y)\\ &=f(y)+f(xf(y))-f(xy)=f(x+y). \end{align*}

Ако

f(0)\ne1

, тогава

xf(0)-x

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

f

за всеки

x

, което противоречи на Твърдение 1. Следователно

f(0)=1

. После, при

x=0

в Твърдение 3, получаваме

f(y+1)=f(y)+1

. Твърдение 5. Ако

f

не е константна, то

f(x)+f(y)=f(x+y)+1.

От

P(x+1,y)

и Твърдение 4 имаме

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

f(x+y)+f(xy+y)-f(y)+1.

От Твърдение 3 и

P(x,y)

пък следва

f((x+1)f(y))=

f(xf(y))+f(y)=f(x+y)+f(xy).

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

f(xy)=f(xy+y)-f(y)+1.

Като заменим

x

x/y

при

y\ne0

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

y=0

следва от

f(0)=1

. Накрая, ако

f

не е константна, от Твърдения 3, 5 и 4 имаме

f(f(x)+y)=f(x)+f(y)=f(x+y)+1=f(x+y+1).

Ако за някое

x

имаме

f(x)\ne x+1

, Твърдение 1 отново дава противоречие, защото

f(x)-x-1

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

f(x)=x+1

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

x

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

f(x)=x+1

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