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

Evan Chen / USA TST Solutions

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

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

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

2015

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

11-12

3 задачи

Задача 2

Пълен запис
Условие
Докажете, че за всяко положително цяло число nn съществува множество SS от nn положителни цели числа със следното свойство: за всеки две различни числа a,b∈Sa,b\in S числото a−ba-b дели aa и bb, но не дели никой от останалите елементи на SS.
РешениеЩе построим числата в нарастващ редa+s1,a+s2,…,a+sn,a+s_1,a+s_2,\ldots,a+s_n,като първо изберем подходящи положителни разликиd1,d2,…,dn−1.d_1,d_2,\ldots,d_{n-1}.Некаs1=0,si=d1+d2+⋯+di−1(2≤i≤n),s_1=0,\qquad s_i=d_1+d_2+\cdots+d_{i-1}\quad (2\le i\le n),и за i<ji\lt{}j некаti,j=di+di+1+⋯+dj−1=sj−si.t_{i,j}=d_i+d_{i+1}+\cdots+d_{j-1}=s_j-s_i.Ще ни стигнат следните две условия върху разликите. (i) Никое от числата ti,jt_{i,j} не дели друго от тях. (ii) Съществува цяло число aa, за коетоa≡−si(modti,j)за всички i<j.a\equiv -s_i\pmod{t_{i,j}}\qquad\text{за всички }i\lt{}j.Ако тези условия са изпълнени, множествотоS={a+s1,a+s2,…,a+sn}S=\{a+s_1,a+s_2,\ldots,a+s_n\}работи, след евентуално прибавяне на общо кратно на всички ti,jt_{i,j} към aa, за да станат всички елементи положителни. Наистина, за двойката с индекси i<ji\lt{}j разликата е точно ti,jt_{i,j}. От (ii) имаме ti,j∣a+sit_{i,j}\mid a+s_i, а следователно и ti,j∣a+sjt_{i,j}\mid a+s_j. Ако пък ti,jt_{i,j} делеше и някое a+ska+s_k с k≠i,jk\ne i,j, тогава щеше да дели разликата между sks_k и едно от si,sjs_i,s_j. Това би означавало, че едно от числата tr,st_{r,s} дели друго такова число, в противоречие с (i). Остава да построим разликите. Ще го направим с индукция по nn. За n=1n=1 няма какво да доказваме. Да предположим, че вече имаме разлики d1,…,dn−1d_1,\ldots,d_{n-1}, които работят за nn числа. Избираме просто число pp, което не дели никое от числата ti,jt_{i,j}, и избираме число MM, което е кратно на произведението на всички ti,jt_{i,j} и е взаимнопросто с pp. Твърдим, че новата редица от разликиd1M,d2M,…,dn−1M,pd_1M,d_2M,\ldots,d_{n-1}M,pработи за n+1n+1 числа. Старите интервали стават Mti,jMt_{i,j}, а новите интервали, които завършват в последната точка, саp+Mti,n(1≤i≤n),p+Mt_{i,n}\qquad (1\le i\le n),като за i=ni=n това просто е pp. Първо проверяваме (i). Делимост между две стари разлики Mti,jMt_{i,j} е същата като делимост между старите ti,jt_{i,j}, така че не се появява. Всяко ново число p+Mti,np+Mt_{i,n} е взаимнопросто с MM, понеже е сравнимо с pp по модул MM. Ако общ делител на p+Mti,np+Mt_{i,n} и стара разлика Mtr,sMt_{r,s} съществува, той трябва да дели tr,st_{r,s}; но p+Mti,n≡p(modtr,s)p+Mt_{i,n}\equiv p\pmod{t_{r,s}}, а pp е взаимнопросто с tr,st_{r,s}. Значи всяко ново число е взаимнопросто със всяка стара разлика. По същия начин две различни нови числа p+Mti,np+Mt_{i,n} и p+Mtj,np+Mt_{j,n} са взаимнопрости: общият им делител дели разликата им, която е кратна на някое старо Mtr,sMt_{r,s}, а вече видяхме, че първото ново число е взаимнопросто с такива стари разлики. Следователно новите tt-числа не се делят едно друго. Сега проверяваме (ii). За първите nn члена можем да вземем старо решение a0a_0 и да го умножим по MM; така Ma0Ma_0 удовлетворява всички конгруенции по модул старите Mti,jMt_{i,j}. Всички нови модули p+Mti,np+Mt_{i,n} са взаимнопрости помежду си и със старите модули. Затова по Китайската теорема за остатъците можем едновременно да запазим старите конгруенции и да наложим новитеa≡−Msi(modp+Mti,n)(1≤i≤n).a\equiv -Ms_i\pmod{p+Mt_{i,n}}\qquad(1\le i\le n).Така получаваме разлики, удовлетворяващи (i) и (ii), за n+1n+1 числа. Индукцията завършва конструкцията за всяко nn.
Отвори задачатаEvan Chen VONVON TST 2015/2Условие — източник

Задача 3

Пълен запис
Условие
Физичка среща 20152015 атома, наречени юсамони. Всеки юсамон има или един електрон, или нула електрони, но физичката не може да различи случаите. Единственият инструмент, с който разполага, е диод. Тя може да свърже диода от произволен юсамон AA към произволен друг юсамон BB, като връзката е насочена. Ако при това AA има електрон, а BB няма, електронът прескача от AA към BB; във всички останали случаи нищо не се случва. Освен това физичката не може да разбере дали при дадена стъпка е прескочил електрон. Целта е да изолира два юсамона, за които е 100%100\% сигурна, че в момента са в едно и също състояние. Съществува ли последователност от използвания на диода, която гарантира това?
РешениеОтговорът е не. Нека юсамоните са U1,U2,…,UmU_1,U_2,\ldots,U_m, където m=2015m=2015. Ще разгледаме m+1m+1 възможни модела MkM_k за 0≤k≤m0\le k\le m: в модела MkM_k юсамонитеU1,U2,…,UkU_1,U_2,\ldots,U_kса заредени, а всички останали са незаредени. За всяка двойка различни юсамони има модел, в който те са в различни състояния: ако двойката е Ui,UjU_i,U_j с i<ji\lt{}j, вземаме kk с i≤k<ji\le k\lt{}j. Понеже физичката не получава никаква информация по време на опита, една стратегия е просто предварително фиксирана последователност от насочени включвания на диода. Ако стратегията можеше да гарантира успех, то след изпълнението на тази последователност върху всички модели M0,M1,…,MmM_0,M_1,\ldots,M_m трябваше да има една и съща двойка юсамони, която е в еднакво състояние във всеки от тези модели. Ще покажем, че това никога не се случва. Достатъчно е да видим как една операция Ui→UjU_i\to U_j действа върху семейството от модели. Ако i>ji\gt{}j, операцията никога не премества електрон в никой от моделите MkM_k. Наистина, ако UiU_i е зареден, то k≥i>jk\ge i\gt{}j, така че UjU_j също е зареден; ако UjU_j е незареден, то k<j<ik\lt{}j\lt{}i, така че UiU_i също е незареден. Ако i<ji\lt{}j, тогава действието на диода върху цялото семейство модели е същото като просто да разменим имената на UiU_i и UjU_j. За моделите с k<ik\lt{}i или k≥jk\ge j нищо не се променя. За i≤k<ji\le k\lt{}j юсамонът UiU_i е зареден, а UjU_j е незареден, така че електронът прескача от UiU_i към UjU_j; полученото множество от заредени юсамони е точно това, което би се получило от началния модел MkM_k след размяна на имената UiU_i и UjU_j. Следователно след всяка операция семейството от възможни модели остава изоморфно копие на първоначалното семейство M0,M1,…,MmM_0,M_1,\ldots,M_m: най-много сме преименували юсамоните. Но в такова семейство никоя двойка юсамони не е винаги в едно и също състояние, защото за всяка двойка има модел, който я разделя. Значи физичката никога не може да бъде 100%100\% сигурна за нито една двойка. Идеята може да се опише и така: с диодите физичката може да подреди юсамоните в някаква линия, така че заредените да са отляво на незаредените, но не може да определи колко са заредените.
Отвори задачатаEvan Chen VONVON TST 2015/3Условие — източник

Задача 4

Пълен запис
Условие
Нека f ⁣:Q→Qf\colon\mathbb Q\to\mathbb Q е функция, такава че за всички x,y∈Qx,y\in\mathbb Q числотоf(x+y)−f(x)−f(y)f(x+y)-f(x)-f(y)е цяло. Вярно ли е непременно, че съществува константа cc, за която f(x)−cxf(x)-cx е цяло число за всяко рационално число xx?
РешениеНе, такава константа не е задължително да съществува. Ще дадем контрапример. За положително цяло число qq некаAq=1!+2!+⋯+q!.A_q=1!+2!+\cdots+q!.Ако рационалното число е записано в несъкратим вид p/qp/q, където q>0q\gt{}0 и gcd⁡(p,q)=1\gcd(p,q)=1, дефинирамеf(pq)=pqAq.f\left(\frac pq\right)=\frac pq A_q.Първо проверяваме, че функцията удовлетворява условието на задачата. Ако LL е кратно на qq, тогаваAL≡Aq(modq),A_L\equiv A_q\pmod q,защото всеки член r!r! с r≥qr\ge q се дели на qq. Следователно за всяко рационално число x=p/qx=p/q и всяко кратно LL на знаменателя му имамеf(x)≡xAL(modZ).f(x)\equiv xA_L\pmod{\mathbb Z}.Сега вземаме две рационални числа xx и yy и избираме LL кратно на знаменателите на xx, yy и x+yx+y. Тогаваf(x+y)−f(x)−f(y)≡f(x+y)-f(x)-f(y)\equiv(x+y)AL−xAL−yAL≡0(modZ), (x+y)A_L-xA_L-yA_L\equiv0\pmod{\mathbb Z},тоест разликата е цяло число. Остава да докажем, че не съществува константа cc с исканото свойство. Ако такава константа съществува, от x=1x=1 получаваме, че cc е цяло число, защото f(1)=1f(1)=1 и f(1)−c∈Zf(1)-c\in\mathbb Z. При x=1/qx=1/q условието даваAq−cq∈Z,\frac{A_q-c}{q}\in\mathbb Z,тоестc≡Aq(modq)c\equiv A_q\pmod qза всяко положително цяло число qq. Сега поставяме q=m!q=m!. Понеже всички факториели r!r! с r≥mr\ge m се делят на m!m!, имамеAm!≡Am−1(modm!).A_{m!}\equiv A_{m-1}\pmod{m!}.Значи за всяко mm трябва да е изпълненоc≡Am−1(modm!).c\equiv A_{m-1}\pmod{m!}.За достатъчно голямо mm числата ∣c∣|c| и Am−1A_{m-1} са по-малки от m!m!, следователно последното сравнение принуждаваc=Am−1.c=A_{m-1}.Това е невъзможно за две различни достатъчно големи стойности на mm, защото редицата Am−1A_{m-1} строго расте. Полученото противоречие показва, че търсената константа cc не съществува.
Отвори задачатаEvan Chen VONVON TST 2015/4Условие — източник