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

Evan Chen / USA TST Solutions

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

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

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

2016

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

11-12

3 задачи

Задача 3

Пълен запис
Условие
Нека pp е просто число. С Fp\mathbb F_p означаваме остатъците по модул pp, а с Fp[x]\mathbb F_p[x] - множеството на полиномите с коефициенти в Fp\mathbb F_p. Дефинираме Ψ ⁣:Fp[x]→Fp[x]\Psi\colon\mathbb F_p[x]\to\mathbb F_p[x] чрезΨ(∑i=0naixi)=∑i=0naixpi.\Psi\left(\sum_{i=0}^n a_ix^i\right)=\sum_{i=0}^n a_ix^{p^i}.Докажете, че за ненулеви полиноми F,G∈Fp[x]F,G\in\mathbb F_p[x] е изпълненоΨ(gcd⁡(F,G))=gcd⁡(Ψ(F),Ψ(G)).\Psi(\gcd(F,G))=\gcd(\Psi(F),\Psi(G)).
РешениеЩе използваме, че Ψ\Psi е линеен оператор над Fp\mathbb F_p и че за всеки полином P∈Fp[x]P\in\mathbb F_p[x] е вярноΨ(xP)=Ψ(P)p.\Psi(xP)=\Psi(P)^p.По-общо, за всяко i≥0i\ge0 имаме Ψ(xiP)=Ψ(P)pi\Psi(x^iP)=\Psi(P)^{p^i}. Важно е да не се забравя, че Ψ(1)=x\Psi(1)=x, а не 11. Първо доказваме следното твърдение. Твърдение. Ако P∣QP\mid Q в Fp[x]\mathbb F_p[x], то Ψ(P)∣Ψ(Q)\Psi(P)\mid\Psi(Q). Нека Q=PRQ=PR, къдетоR=∑i=0krixi.R=\sum_{i=0}^k r_ix^i.Тогава, използвайки линейността на Ψ\Psi и горното свойство, получавамеΨ(Q)=Ψ(P∑i=0krixi)=∑i=0kriΨ(Pxi)=∑i=0kriΨ(P)pi.\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*}Всеки член в последната сума се дели на Ψ(P)\Psi(P), следователно и Ψ(Q)\Psi(Q) се дели на Ψ(P)\Psi(P). Нека D=gcd⁡(F,G)D=\gcd(F,G), като както обикновено вземаме най-големия общ делител моничен. Понеже D∣FD\mid F и D∣GD\mid G, твърдението даваΨ(D)∣Ψ(F)иΨ(D)∣Ψ(G).\Psi(D)\mid\Psi(F)\qquad\text{и}\qquad\Psi(D)\mid\Psi(G).СледователноΨ(D)∣gcd⁡(Ψ(F),Ψ(G)).\Psi(D)\mid\gcd(\Psi(F),\Psi(G)).За обратната делимост използваме тъждеството на Безу за полиноми над поле. Съществуват полиноми A,B∈Fp[x]A,B\in\mathbb F_p[x], за коитоAF+BG=D.AF+BG=D.Прилагаме Ψ\Psi към двете страни. Понеже Ψ\Psi е линеен оператор, получавамеΨ(AF)+Ψ(BG)=Ψ(D).\Psi(AF)+\Psi(BG)=\Psi(D).От вече доказаното твърдение имаме Ψ(F)∣Ψ(AF)\Psi(F)\mid\Psi(AF) и Ψ(G)∣Ψ(BG)\Psi(G)\mid\Psi(BG). Значи gcd⁡(Ψ(F),Ψ(G))\gcd(\Psi(F),\Psi(G)) дели лявата страна, а следователно дели и Ψ(D)\Psi(D). Получихме делимост и в двете посоки. Накрая, ако PP е моничен, тогава и Ψ(P)\Psi(P) е моничен, защото водещият член xdeg⁡Px^{\deg P} преминава във водещ член xpdeg⁡Px^{p^{\deg P}}. Затова двата монични полиномаΨ(gcd⁡(F,G))иgcd⁡(Ψ(F),Ψ(G))\Psi(\gcd(F,G))\qquad\text{и}\qquad\gcd(\Psi(F),\Psi(G))са равни.
Отвори задачатаEvan Chen VONVON TST 2016/3Условие — източник

Задача 4

Пълен запис
Условие
Нека3=1.b1b2b3…(2)\sqrt3=1.b_1b_2b_3\ldots_{(2)}е двоичното представяне на 3\sqrt3. Докажете, че за всяко положително цяло число nn поне една от цифритеbn,bn+1,…,b2nb_n,b_{n+1},\ldots,b_{2n}е равна на 11.
РешениеДа допуснем противното. Тогава за някое положително цяло число nn всички цифри bn,bn+1,…,b2nb_n,b_{n+1},\ldots,b_{2n} са нули. След умножение на двоичното представяне по 2n−12^{n-1} това означава, че съществува цяло число kk, за коетоk<2n−13<k+12n+1.k\lt{}2^{n-1}\sqrt3\lt{}k+\frac1{2^{n+1}}.Неравенствата са строги, защото 3\sqrt3 е ирационално число. Повдигаме на квадрат. Получавамеk2<3⋅22n−2<k2+k2n+122n+2≤k2+2n−132n+122n+2=k2+32+122n+2≤k2+32+116<k2+1.\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⋅22n−23\cdot2^{2n-2} е цяло, а последната верига го поставя строго между две последователни цели числа k2k^2 и k2+1k^2+1. Това е невъзможно. Следователно сред цифрите bn,bn+1,…,b2nb_n,b_{n+1},\ldots,b_{2n} винаги има поне една единица.
Отвори задачатаEvan Chen VONVON TST 2016/4Условие — източник

Задача 5

Пълен запис
Условие
Нека n≥4n\ge4 е цяло число. Намерете всички функцииW ⁣:{1,2,…,n}2→R,W\colon\{1,2,\ldots,n\}^2\to\mathbb R,за които при всяко разбиване [n]=A∪B∪C[n]=A\cup B\cup C на непресичащи се множества е изпълнено∑a∈A∑b∈B∑c∈CW(a,b)W(b,c)=\sum_{a\in A}\sum_{b\in B}\sum_{c\in C}W(a,b)W(b,c)=∣A∣∣B∣∣C∣.|A||B||C|.
РешениеОтговорът е следният: стойностите W(k,k)W(k,k) върху диагонала са произволни, а извън диагонала всички стойности са равни на една и съща константа ε\varepsilon, къдетоε∈{−1,1}.\varepsilon\in\{-1,1\}.Тези функции очевидно работят, защото при a∈Aa\in A, b∈Bb\in B, c∈Cc\in C трите индекса са различни и всеки множител W(a,b)W(b,c)W(a,b)W(b,c) е равен на ε2=1\varepsilon^2=1. Остава да докажем, че други функции няма. За различни a,b,ca,b,c поставямеXabc=W(a,b)W(b,c).X_{abc}=W(a,b)W(b,c).Първо забелязваме, че W(a,b)≠0W(a,b)\ne0 за a≠ba\ne b. Наистина, ако вземем разбиването A={a}A=\{a\}, B={b}B=\{b\} и C=[n]∖{a,b}C=[n]\setminus\{a,b\}, получаваме∑c∈CW(a,b)W(b,c)=n−2,\sum_{c\in C}W(a,b)W(b,c)=n-2,а дясната страна е ненулева. Сега ще извлечем локално равенство от условието. Нека a,b,ca,b,c са три различни елемента и некаR=[n]∖{a,b,c}.R=[n]\setminus\{a,b,c\}.Прилагаме условието към трите разбиванияA={a},B={b},C={c}∪R,A=\{a\},\quad B=\{b\},\quad C=\{c\}\cup R,A={a},B={c},C={b}∪R,A=\{a\},\quad B=\{c\},\quad C=\{b\}\cup R,иA={a},B={b,c},C=R.A=\{a\},\quad B=\{b,c\},\quad C=R.Получаваме съответноXabc+∑r∈RXabr=n−2,Xacb+∑r∈RXacr=n−2,∑r∈RXabr+∑r∈RXacr=2(n−3).\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*}Като съберем първите две равенства и извадим третото, намирамеXabc+Xacb=2.X_{abc}+X_{acb}=2.Аналогично, използвайки разбиванията с едноточковите множества {a}\{a\} и {c}\{c\} от двете страни на {b}\{b\}, получавамеXabc+Xcba=2.X_{abc}+X_{cba}=2.Следователно Xacb=XcbaX_{acb}=X_{cba}, тоестW(a,c)W(c,b)=W(c,b)W(b,a).W(a,c)W(c,b)=W(c,b)W(b,a).Понеже W(c,b)≠0W(c,b)\ne0, заключаваме, чеW(a,c)=W(b,a)W(a,c)=W(b,a)за всеки три различни a,b,ca,b,c. От това вече следва, че всички извъндиагонални стойности на WW са равни. Фиксираме индекс aa. Ако cc и dd са различни от aa, избираме bb, различен от a,c,da,c,d; това е възможно, защото n≥4n\ge4. ТогаваW(a,c)=W(b,a)=W(a,d),W(a,c)=W(b,a)=W(a,d),следователно всички стойности в ред aa извън диагонала са равни. Освен това от същото равенство W(a,c)=W(b,a)W(a,c)=W(b,a) виждаме, че тази обща стойност в ред aa е равна и на всяка извъндиагонална стойност в стълб aa. Накрая, за два различни индекса aa и bb стойността W(a,b)W(a,b) едновременно принадлежи на ред aa и на стълб bb, така че общите стойности за всички редове и стълбове съвпадат. Нека тази обща стойност бъде ε\varepsilon. Накрая от равенството Xabc+Xacb=2X_{abc}+X_{acb}=2 за произволни различни a,b,ca,b,c получаваме2ε2=2,2\varepsilon^2=2,тоест ε=1\varepsilon=1 или ε=−1\varepsilon=-1. Това дава точно описаните по-горе функции.
Отвори задачатаEvan Chen VONVON TST 2016/5Условие — източник