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

Evan Chen / USA TST Solutions

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

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

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

2019

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

11-12

3 задачи

Задача 2

Пълен запис
Условие
Нека Z/nZ\mathbb Z/n\mathbb Z означава множеството от целите числа по модул nn. Намерете всички положителни цели числа nn, за които съществува биекцияg ⁣:Z/nZ→Z/nZ,g\colon\mathbb Z/n\mathbb Z\to\mathbb Z/n\mathbb Z,такава че функциитеg(x),g(x)+x,g(x)+2x,g(x),\quad g(x)+x,\quad g(x)+2x,…,g(x)+100x\quad\ldots,\quad g(x)+100xса биекции на Z/nZ\mathbb Z/n\mathbb Z.
РешениеОтговорът е: всички положителни цели числа nn, взаимно прости с 101!101!. Първо, ако gcd⁡(n,101!)=1\gcd(n,101!)=1, вземаме g(x)=xg(x)=x. Тогава g(x)+tx=(t+1)xg(x)+tx=(t+1)x за t=0,1,…,100t=0,1,\ldots,100, а умножението по t+1t+1 е биекция по модул nn, понеже t+1t+1 е взаимно просто с nn. Остава обратната посока. Да допуснем, че такава биекция gg съществува, и нека p≤101p\le101 е най-малкият прост делител на nn. Ще стигнем до противоречие. Първо доказваме, че за всяко k=0,1,…,100k=0,1,\ldots,100 е изпълненоk!∑x∈Z/nZxk≡0(modn).k!\sum_{x\in\mathbb Z/n\mathbb Z}x^k\equiv0\pmod n.За фиксирано xx разглеждаме полиномаGx(T)=g(x)+Tx.G_x(T)=g(x)+Tx.Крайната разлика от ред kk на полинома Gx(T)kG_x(T)^k даваk!xk=∑i=0k(−1)k−i(ki)Gx(i)k.k!x^k=\sum_{i=0}^k(-1)^{k-i}\binom ki G_x(i)^k.Сумираме по всички остатъци xx по модул nn. За всяко i=0,1,…,ki=0,1,\ldots,k функцията x↦Gx(i)=g(x)+ixx\mapsto G_x(i)=g(x)+ix е биекция, следователно сумата на Gx(i)kG_x(i)^k по всички xx е една и съща, а коефициентите в крайната разлика имат сума 00. Получаваме желаното сравнение. Понеже pp е най-малкият прост делител на nn, числото k!k! е обратимо по модул nn за 0≤k≤p−10\le k\le p-1. Значи∑x∈Z/nZxk≡0(modn)(k=0,1,…,p−1).\sum_{x\in\mathbb Z/n\mathbb Z}x^k\equiv0\pmod n\qquad(k=0,1,\ldots,p-1).Това е същото като n∣1k+2k+⋯+nkn\mid 1^k+2^k+\cdots+n^k за тези kk. Сега използваме стандартна лема за суми от степени. Ако MM дели 1k+2k+⋯+nk1^k+2^k+\cdots+n^k за k=0,1,…,p−1k=0,1,\ldots,p-1 и p∣np\mid n, тогава νp(M)<νp(n)\nu_p(M)\lt{}\nu_p(n). Наистина, всяка целочислена полиномна функция от степен най-много p−1p-1 има сума, деляща се на MM. Прилагаме това към(x−1)(x−2)⋯(x−(p−1))=(p−1)!(x−1p−1).(x-1)(x-2)\cdots(x-(p-1))=(p-1)!\binom{x-1}{p-1}.ПолучавамеM∣(p−1)!∑x=1n(x−1p−1)=(p−1)!(np).M\mid (p-1)!\sum_{x=1}^n\binom{x-1}{p-1}=(p-1)!\binom np.Но pp не дели (p−1)!(p-1)!, а νp(np)=νp(n)−1\nu_p\binom np=\nu_p(n)-1, така че νp(M)<νp(n)\nu_p(M)\lt{}\nu_p(n). Прилагаме лемата с M=nM=n. Тя казва νp(n)<νp(n)\nu_p(n)\lt{}\nu_p(n), невъзможно. Следователно никой прост делител на nn не е най-много 101101, тоест nn е взаимно просто с 101!101!.
Отвори задачатаEvan Chen VONVON TST 2019/2Условие — източник

Задача 3

Пълен запис
Условие
Змия с дължина kk е фигура, която заема наредена kk-торка (s1,…,sk)(s_1,\ldots,s_k) от клетки в квадратна мрежа n×nn\times n от единични квадратчета. Клетките са две по две различни, а sis_i и si+1s_{i+1} имат обща страна за i=1,…,k−1i=1,\ldots,k-1. Ако в момента змията заема (s1,…,sk)(s_1,\ldots,s_k) и ss е незаета клетка с обща страна със s1s_1, тя може да се премести в (s,s1,…,sk−1)(s,s_1,\ldots,s_{k-1}). Казваме, че змията се е обърнала, ако първоначално е заемала (s1,s2,…,sk)(s_1,s_2,\ldots,s_k), а след краен брой ходове заема (sk,sk−1,…,s1)(s_k,s_{k-1},\ldots,s_1). Съществува ли цяло число n>1n\gt{}1, за което в мрежа n×nn\times n може да се постави змия с дължина поне 0.9n20.9n^2, която може да се обърне?
РешениеДа, съществува. Ще дадем конструкция, която всъщност позволява змия с дължина, заемаща произволно голяма част от мрежата. Първо формулираме графова версия. Нека GG е неориентиран граф. Змия с дължина kk в GG заема наредени kk различни върха, като съседни части на змията лежат в съседни върхове; един ход премества главата в свободен съседен връх, а останалите части я следват. Ще построим граф GG, в който много дълга змия може да се обърне. Избираме положителни цели числа rr и ℓ\ell. Вземаме rr дълги главни пътя p1,…,prp_1,\ldots,p_r, като pip_i води от AiA_i до BiB_i и има дължина поне ℓ\ell. Добавяме свързващи пътища от BiB_i до Ai+1A_{i+1} за i=1,…,r−1i=1,\ldots,r-1 и от BrB_r до A1A_1. Така получаваме голям цикълA1B1A2B2⋯ArBrA1.A_1B_1A_2B_2\cdots A_rB_rA_1.Накрая добавяме транзитни пътища от A1A_1 до всеки от A2,…,ArA_2,\ldots,A_r и от BrB_r до всеки от B1,…,Br−1B_1,\ldots,B_{r-1}. Всички пътища са вътрешно несечащи се, освен че транзитните пътища от едно и също семейство могат да се срещат. Поставяме змия с дължина (r−1)ℓ(r-1)\ell с опашка в A1A_1 и тяло по големия цикъл в посоката A1,B1,A2,B2,…A_1,B_1,A_2,B_2,\ldots. Тази змия може да се обърне така. В първата фаза главата върви по големия цикъл до Br−1B_{r-1}, минава по транзитен път до BrB_r и после върви по големия цикъл в обратната посока до ArA_r. Във фаза i=2,3,…,r−1i=2,3,\ldots,r-1 тя минава по транзитен път до A1A_1, после напред по големия цикъл до Br−iB_{r-i}, по транзитен път до BrB_r, и назад по големия цикъл до Ar−i+1A_{r-i+1}. В последната фаза върви назад по големия цикъл до A1A_1. Понеже змията е по-къса от сумарната дължина на r−1r-1 главни пътя, в моментите на тези обходи нужните транзитни пътища са свободни; описаното движение точно обръща реда на частите на змията. Остава да вложим такъв граф почти плътно в квадратна мрежа. В голяма мрежа n×nn\times n избираме точки a1,…,ar+1a_1, \ldots,a_{r+1} приблизително равномерно по втората колона, от близо до долния край до близо до горния край. Избираме точки b1,…,brb_1, \ldots,b_r по колоната n−2n-2, като bib_i е в реда на ai+1a_{i+1}. Главният път от aia_i до bib_i запълва почти изцяло правоъгълната лента между тези две точки. Свързващите пътища минават по съответните редове, а последният свързващ път използва горния ред, последната колона и долния ред. Двете семейства транзитни пътища се реализират съответно по първата и по (n−1)(n-1)-вата колона, без крайните клетки. Така получаваме подграф на мрежата, изоморфен на описания GG, в който главните пътища заемат почти цялата площ. При фиксирано rr и n→∞n\to\infty дължината на обръщащата се змия е приблизителноr−1rn2.\frac{r-1}{r}n^2.Избираме rr достатъчно голямо, така че (r−1)/r>0.9(r-1)/r\gt{}0.9, а после избираме nn достатъчно голямо. Получаваме исканата змия.
Отвори задачатаEvan Chen VONVON TST 2019/3Условие — източник

Задача 4

Пълен запис
Условие
Наричаме функция f ⁣:Z≥0×Z≥0→Zf\colon\mathbb Z_{\ge0}\times\mathbb Z_{\ge0}\to\mathbb Z чудесна, ако за всички неотрицателни цели числа mm и nn е изпълненоf(m+1,n+1)f(m,n)−f(m+1,n)f(m,n+1)=1.f(m+1,n+1)f(m,n)-f(m+1,n)f(m,n+1)=1.Ако A=(a0,a1,…)A=(a_0,a_1,\ldots) и B=(b0,b1,…)B=(b_0,b_1,\ldots) са две редици от цели числа, пишем A∼BA\sim B, ако съществува чудесна функция ff, за която f(n,0)=anf(n,0)=a_n и f(0,n)=bnf(0,n)=b_n за всяко неотрицателно цяло число nn; в частност a0=b0a_0=b_0. Докажете, че ако AA, BB, CC и DD са четири редици от цели числа, за които A∼BA\sim B, B∼CB\sim C и C∼DC\sim D, то D∼AD\sim A.
РешениеЩе използваме следната класификация. Двойката редици (A,B)(A,B) е чудесна, тоест A∼BA\sim B, точно когато са изпълнени условиятаa0=b0,a0∣a1b1+1,a_0=b_0,\qquad a_0\mid a_1b_1+1,и за всяко n≥1n\ge1an∣an−1+an+1,bn∣bn−1+bn+1.a_n\mid a_{n-1}+a_{n+1},\qquad b_n\mid b_{n-1}+b_{n+1}.Първо доказваме необходимостта. Равенството a0=b0a_0=b_0 е ясно. От условието за квадрата с върхове (0,0),(1,0),(0,1),(1,1)(0,0),(1,0),(0,1),(1,1) получавамеa0f(1,1)−a1b1=1,a_0f(1,1)-a_1b_1=1,следователно a0∣a1b1+1a_0\mid a_1b_1+1. Сега гледаме шест стойности в две съседни колони:u=f(n−1,1),v=f(n,1),w=f(n+1,1).u=f(n-1,1),\quad v=f(n,1),\quad w=f(n+1,1).От чудесното условие за двата съседни квадрата имамеvan−1−uan=1,wan−van+1=1.va_{n-1}-ua_n=1,\qquad wa_n-va_{n+1}=1.Като съберем подходящо, получавамеu+w=v(an−1+an+1)an.u+w=\frac{v(a_{n-1}+a_{n+1})}{a_n}.Освен това gcd⁡(v,an)=1\gcd(v,a_n)=1, затова an∣an−1+an+1a_n\mid a_{n-1}+a_{n+1}. Същият аргумент по другата ос дава условието за редицата BB. Ако an=0a_n=0, двете равенства принуждават van−1=1va_{n-1}=1 и van+1=−1va_{n+1}=-1, така че делимостта пак е валидна в обичайния смисъл. За достатъчността строим чудесната функция по индукция. Първо избираме f(1,1)f(1,1) от равенствотоa0f(1,1)−a1b1=1,a_0f(1,1)-a_1b_1=1,което е възможно по условието. После попълваме таблицата клетка по клетка. Ако пет стойностиuxvywz\begin{matrix}u&x\\ v&y\\ w&z\end{matrix}са известни без zz, избирамеz=y⋅u+wv−xz=y\cdot\frac{u+w}{v}-xкогато v≠0v\ne0; това е цяло число по делимостното условие и запазва детерминантата 11 на новия квадрат. Ако v=0v=0, от съседните детерминанти следва, че съседните стойности са ±1\pm1, и липсващата стойност може да се избере така, че новата детерминанта да е 11. Същите кратки проверки запазват и делимостта за всяка нова тройка поредни стойности. Така индукцията построява чудесна функция. Сега завършваме задачата. НекаA=(an),B=(bn),C=(cn),D=(dn).A=(a_n),\quad B=(b_n),\quad C=(c_n),\quad D=(d_n).От A∼BA\sim B, B∼CB\sim C и C∼DC\sim D следваa0=b0=c0=d0=k.a_0=b_0=c_0=d_0=k.Освен това всяка от четирите редици удовлетворява вътрешното условие xn∣xn−1+xn+1x_n\mid x_{n-1}+x_{n+1} за n≥1n\ge1. Остава само да проверим началната делимост за (D,A)(D,A). Имамеk∣a1b1+1,k∣b1c1+1,k∣c1d1+1.k\mid a_1b_1+1,\qquad k\mid b_1c_1+1,\qquad k\mid c_1d_1+1.Умножавайки трите сравнения, получаваме(a1b1)(b1c1)(c1d1)≡−1(modk).(a_1b_1)(b_1c_1)(c_1d_1)\equiv -1\pmod k.Но от средното сравнение (b1c1)2≡1(modk)(b_1c_1)^2\equiv1\pmod k, следователноa1d1≡−1(modk),a_1d_1\equiv -1\pmod k,тоест k∣d1a1+1k\mid d_1a_1+1. По класификацията това означава D∼AD\sim A.
Отвори задачатаEvan Chen VONVON TST 2019/4Условие — източник