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

Evan Chen / USA TSTST Solutions

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

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

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

2011

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

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

  • 2011 · 11-12: липсва задача 2, 3, 4

11-12

6 задачи

Задача 1

Пълен запис
Условие
Да се намерят всички функции ff, дефинирани върху наредени двойки реални числа и приемащи реални стойности, със следното свойство: за всички реални числа a,b,ca,b,c медианата на числата f(a,b)f(a,b), f(b,c)f(b,c) и f(c,a)f(c,a) е равна на медианата на a,b,ca,b,c. Тук медианата на три реални числа, не непременно различни, е числото, което стои по средата, когато трите числа се подредят в ненамаляващ ред.
РешениеОтговорът еf(x,y)=xза всички x,yf(x,y)=x\quad\text{за всички }x,yиf(x,y)=yза всички x,y.f(x,y)=y\quad\text{за всички }x,y.Лесно се проверява, че и двете функции работят. Първо ще докажем основното твърдение от решението на Evan Chen и Andrew He. Нека a<b<ca\lt{}b\lt{}c са произволни. Върху множеството {a,b,c}2\{a,b,c\}^2 функцията ff има един от следните два вида, като колоната показва първата променлива, а редът - втората:fabcaab≥cb≤ab≥cc≤abcилиfabcaa≤a≤abbbbc≥c≥cc.\begin{array}{c|ccc} f & a & b & c \cr \hline a & a & b & \ge c \cr b & \le a & b & \ge c \cr c & \le a & b & c \end{array} \qquad\text{или}\qquad \begin{array}{c|ccc} f & a & b & c \cr \hline a & a & \le a & \le a \cr b & b & b & b \cr c & \ge c & \ge c & c \end{array}.Наистина, от тройката (x,x,x)(x,x,x) следва f(x,x)=xf(x,x)=x за всяко xx. От тройките (a,a,c)(a,a,c) и (a,c,c)(a,c,c) получаваме, че едно от f(a,c)f(a,c) и f(c,a)f(c,a) е поне cc, а другото е най-много aa. После от тройката (a,b,c)(a,b,c) следва, че едно от f(a,b)f(a,b) и f(b,c)f(b,c) е равно на bb; аналогично едно от f(b,a)f(b,a) и f(c,b)f(c,b) е равно на bb. Без ограничение нека f(b,a)=bf(b,a)=b. Ще получим първата таблица. От тройката (a,a,b)(a,a,b) следва f(a,b)≤af(a,b)\le a, следователно от предишния абзац f(b,c)=bf(b,c)=b, а после f(c,b)≥cf(c,b)\ge c. Накрая, като разгледаме тройката (c,b,a)(c,b,a) заедно с вече установеното за f(a,c)f(a,c) и f(c,a)f(c,a), получаваме f(a,c)≤af(a,c)\le a и f(c,a)≥cf(c,a)\ge c. Това е първата таблица. Ако вместо това започнем с f(a,b)=bf(a,b)=b, симетрично получаваме втората таблица. Остава да глобализираме този локален избор. За две различни числа x<yx\lt{}y ще казваме, че двойката има тип I, ако f(y,x)=yf(y,x)=y и f(x,y)≤xf(x,y)\le x, и тип II, ако f(x,y)=yf(x,y)=y и f(y,x)≤xf(y,x)\le x. Основното твърдение показва, че всяка двойка има поне един от тези два типа, като типът не зависи от третото число, с което я поставяме в тройка: двата типа не могат да са едновременно верни, защото биха дали например f(x,y)=yf(x,y)=y и f(x,y)≤xf(x,y)\le x. Ако x<y<zx\lt{}y\lt{}z, първата таблица означава, че и двойките (x,y)(x,y) и (y,z)(y,z) са от тип I, а втората - че и двете са от тип II. Следователно всички двойки реални числа имат един и същ тип. Ако този общ тип е I, то за x<yx\lt{}y вземаме произволно u<xu\lt{}x и прилагаме първата таблица към u<x<yu\lt{}x\lt{}y; получаваме f(x,y)=xf(x,y)=x, а вече имаме и f(y,x)=yf(y,x)=y. Значи f(x,y)=xf(x,y)=x за всички различни x,yx,y, а също и за x=yx=y. Ако общият тип е II, аналогично получаваме f(x,y)=yf(x,y)=y за всички x,yx,y. Така намерихме точно двете функции, посочени в началото.
Отвори задачатаEvan Chen VONVON TSTST 2011/1Условие — източник

Задача 5

Пълен запис
Условие
В едно сиропиталище всяка двойка сираци са или приятели, или врагове. За всеки три приятеля на един сирак четен брой от трите двойки между тях са вражески двойки. Докажете, че е възможно на всеки сирак да се назначат двама родители така, че всяка двойка приятели да има точно един общ родител, никоя двойка врагове да няма общ родител и да няма трима родители, които образуват любовен триъгълник, т.е. всяка двойка от тях има общо дете.
РешениеЩе използваме езика на графите. Върховете са сираците, а ребрата свързват двойките приятели. Разглеждаме всички максимални клики в този граф. Първо твърдим, че всеки връх участва в най-много две максимални клики. Наистина, нека vv е приятел с w1w_1 и w2w_2, но w1w_1 и w2w_2 не са приятели. Ако uu е друг приятел на vv, тогава в тройката w1,w2,uw_1,w_2,u вече имаме една вражеска двойка, а броят на вражеските двойки трябва да е четен. Следователно uu е приятел с точно един от w1w_1 и w2w_2. Освен това, ако uu и u′u' са приятели на vv и и двамата са приятели с w1w_1, тогава в тройката w1,u,u′w_1,u,u' първите две двойки са приятелски, така че и u,u′u,u' трябва да са приятели. Аналогично за страната на w2w_2. Значи всички приятели на vv се разделят на най-много две групи, всяка от които заедно с vv образува клика. Това доказва твърдението. Ако пък всички приятели на vv са помежду си приятели, тогава vv участва само в една максимална клика. Сега за всяка максимална клика създаваме един родител и го назначаваме на всички сираци в тази клика. Ако някой сирак участва само в една или в нито една такава клика, добавяме му допълнителни нови родители, различни от всички останали, докато има точно двама родители. Тази конструкция изпълнява условията. Двама врагове не лежат в обща клика, а допълнителните родители са лични, следователно враговете нямат общ родител. Двама приятели лежат в поне една максимална клика. Те не могат да лежат в две различни максимални клики, защото тогава обединението на тези две клики пак би било клика: ако xx и yy са върхове от двете клики, съдържащи общото ребро, условието за тройката приятели на единия край на това ребро принуждава xx и yy също да са приятели. Значи всяка двойка приятели има точно един общ родител. Остава любовният триъгълник. Ако деца a,b,ca,b,c са такива, че aa и bb имат един общ родител, а aa и cc имат друг общ родител, то това означава, че aa участва в две различни максимални клики. По доказаното твърдение това са всичките му максимални клики, така че bb и cc не могат да имат трети общ родител. Следователно любовен триъгълник от родители не се появява.
Отвори задачатаEvan Chen VONVON TSTST 2011/5Условие — източник

Задача 6

Пълен запис
Условие
Нека a,b,ca,b,c са реални числа в интервала [0,1][0,1], за които a+b,b+c,c+a≥1a+b,b+c,c+a\ge1. Докажете, че1≤1\le(1−a)2+(1−b)2+(1−c)2 (1-a)^2+(1-b)^2+(1-c)^2+22abcx2a2+b2+c2.+\frac{2\sqrt2abc}{\sqrt{\vphantom{x^2}a^2+b^2+c^2}}.
РешениеЩе използваме подхода на Ashwin Sah. От условията следва, че a,b,ca,b,c могат да бъдат страни на евентуално изроден триъгълник: например a+b≥1≥ca+b\ge1\ge c, а другите две неравенства са аналогични. По-хубаво е първо да докажем хомогенизираната форма. Ще покажем, че за всеки kk и за всички a,b,ca,b,c, които са страни на евентуално изроден триъгълник, е вярноk2≤k^2\le(k−a)2+(k−b)2+(k−c)2 (k-a)^2+(k-b)^2+(k-c)^2+22abcx2a2+b2+c2.+\frac{2\sqrt2abc}{\sqrt{\vphantom{x^2}a^2+b^2+c^2}}.Първоначалната задача е случаят k=1k=1. Фиксираме a,b,ca,b,c. Разликата между дясната и лявата страна е квадратен тричлен по kk от вида2k2−2(a+b+c)k+C,2k^2-2(a+b+c)k+C,с положителен водещ коефициент. Затова е достатъчно да проверим неравенството при неговия минимум, т.е. приk=a+b+c2.k=\frac{a+b+c}{2}.Поставямеx=b+c−a2,y=c+a−b2,z=a+b−c2.x=\frac{b+c-a}{2},\qquad y=\frac{c+a-b}{2},\qquad z=\frac{a+b-c}{2}.Тогава x,y,z≥0x,y,z\ge0 и a=y+za=y+z, b=z+xb=z+x, c=x+yc=x+y. След заместване неравенството се свежда до(x+y+z)2≤(x+y+z)^2\lex2+y2+z2 x^2+y^2+z^2+2(x+y)(y+z)(z+x)x2x2+y2+z2+xy+yz+zx.+\frac{2(x+y)(y+z)(z+x)}{\sqrt{\vphantom{x^2}x^2+y^2+z^2+xy+yz+zx}}.След прехвърляне това е еквивалентно наx2+y2+z2+xy+yz+zx≤x^2+y^2+z^2+xy+yz+zx\le((x+y)(y+z)(z+x)xy+yz+zx)2.\left(\frac{(x+y)(y+z)(z+x)}{xy+yz+zx}\right)^2.Нека t=xy+yz+zxt=xy+yz+zx. Понеже (x+y)(x+z)=x2+t(x+y)(x+z)=x^2+t, последното неравенство ставаt2(x2+y2+z2+t)≤(x2+t)(y2+t)(z2+t).t^2(x^2+y^2+z^2+t)\le (x^2+t)(y^2+t)(z^2+t).То е очевидно след разкриване на скобите: дясната страна съдържа всички членове от лявата и още неотрицателни членове. Това доказва хомогенизираната форма, а с k=1k=1 получаваме точно исканото неравенство.
Отвори задачатаEvan Chen VONVON TSTST 2011/6Условие — източник

Задача 7

Пълен запис
Условие
Нека ABCABC е триъгълник. Неговите външновписани окръжности се допират съответно до страните BCBC, CACA, ABAB в точките D,E,FD,E,F. Докажете, че периметърът на триъгълника ABCABC е най-много два пъти периметъра на триъгълника DEFDEF.
РешениеНека a=BCa=BC, b=CAb=CA, c=ABc=AB, нека s=(a+b+c)/2s=(a+b+c)/2 е полупериметърът, а RR - радиусът на описаната окръжност на ABCABC. Трябва да докажемEF+FD+DE≥s.EF+FD+DE\ge s.Ще оценим всяка страна на DEFDEF чрез ортогонална проекция. За страната EFEF проектираме отсечката върху правата BCBC. От равенството на допирателните отсечки към съответните външновписани окръжности имамеAE=AF=s−a.AE=AF=s-a.Затова ориентираната дължина на проекцията на EFEF върху BCBC еa−(s−a)(cos⁡B+cos⁡C).a-(s-a)(\cos B+\cos C).Понеже дължината на една отсечка е поне колкото дължината на проекцията ѝ, получавамеEF≥a−(s−a)(cos⁡B+cos⁡C).EF\ge a-(s-a)(\cos B+\cos C).Прилагаме това циклично и събираме:−s+∑cycEF≥−s+∑cyc(a−(s−a)(cos⁡B+cos⁡C))=s−∑cycacos⁡A=∑cyca(12−cos⁡A)=R∑cycsin⁡A(1−2cos⁡A)=R∑cyc(sin⁡A−sin⁡2A).\begin{align*} -s+\sum_{\rm cyc} EF &\ge -s+\sum_{\rm cyc}\left(a-(s-a)(\cos B+\cos C)\right)\\ &=s-\sum_{\rm cyc}a\cos A\\ &=\sum_{\rm cyc}a\left(\frac12-\cos A\right)\\ &=R\sum_{\rm cyc}\sin A(1-2\cos A)\\ &=R\sum_{\rm cyc}(\sin A-\sin2A). \end{align*}Остава да видим, че последният сбор е неотрицателен. Наистина,sin⁡2B+sin⁡2C2=sin⁡(B+C)cos⁡(B−C)=sin⁡Acos⁡(B−C)≤\frac{\sin2B+\sin2C}{2}=\sin(B+C)\cos(B-C)=\sin A\cos(B-C)\lesin⁡A.\sin A.След сумиране на това неравенство по цикличните размествания получаваме∑cycsin⁡2A≤∑cycsin⁡A.\sum_{\rm cyc}\sin2A\le\sum_{\rm cyc}\sin A.Следователно −s+EF+FD+DE≥0-s+EF+FD+DE\ge0, тоест EF+FD+DE≥sEF+FD+DE\ge s. Това е еквивалентно на твърдението, защото периметърът на ABCABC е 2s2s.
Отвори задачатаEvan Chen VONVON TSTST 2011/7Условие — източник

Задача 8

Пълен запис
Условие
Нека x0,x1,…,xn0−1x_0,x_1,\ldots,x_{n_0-1} са цели числа, а d1,d2,…,dkd_1,d_2,\ldots,d_k са положителни цели числа, за коитоn0=d1>d2>⋯>dkиgcd⁡(d1,d2,…,dk)=1.n_0=d_1\gt{}d_2\gt{}\dotsb\gt{}d_k\quad\text{и}\quad \gcd(d_1,d_2,\ldots,d_k)=1.За всяко цяло число n≥n0n\ge n_0 дефинирамеxn=⌊xn−d1+xn−d2+⋯+xn−dkk⌋.x_n=\left\lfloor\frac{x_{n-d_1}+x_{n-d_2}+\dots+x_{n-d_k}}{k}\right\rfloor.Да се докаже, че редицата (xn)(x_n) е константна от някой член нататък.
РешениеНека началните членове лежат в интервала [A,B][A,B]. От формулата веднага следва по индукция, че всички следващи членове също лежат в [A,B][A,B]. Понеже членовете са цели числа, има само краен брой възможни блокове от n0n_0 последователни члена; следователно редицата е периодична от някой член нататък. Премахваме крайно много начални членове и считаме, че редицата вече е периодична с период TT. Ще разглеждаме индексите по модул TT. Нека MM е максималната стойност на член на периодичната редица. Ако xn=Mx_n=M, тогава в средното аритметичноxn−d1+xn−d2+⋯+xn−dkk\frac{x_{n-d_1}+x_{n-d_2}+\dots+x_{n-d_k}}{k}всички събираеми са най-много MM. За да може цялата част да бъде MM, самото средно трябва да е поне MM, а това е възможно само акоxn−di=Mза всички i=1,2,…,k.x_{n-d_i}=M\quad\text{за всички }i=1,2,\ldots,k.Значи множеството от остатъци n(modT)n\pmod T, за които xn=Mx_n=M, е затворено при изваждане на всяко от числата did_i. От gcd⁡(d1,d2,…,dk)=1\gcd(d_1,d_2,\ldots,d_k)=1 следва, че остатъците d1,d2,…,dkd_1,d_2,\ldots,d_k пораждат цялата група Z/TZ\mathbb Z/T\mathbb Z; еквивалентно, чрез теоремата на Безу можем да получим всяка разлика от тях по модул TT. Понеже поне един остатък има стойност MM, затвореността при изваждане на всички did_i принуждава всички остатъци по модул TT да имат стойност MM. Следователно периодичната опашка е константна, което доказва твърдението.
Отвори задачатаEvan Chen VONVON TSTST 2011/8Условие — източник

Задача 9

Пълен запис
Условие
Нека nn е положително цяло число. Дадени са 2n+12^n+1 различни множества, всяко от които съдържа краен брой обекти. Разпределяме всяко множество в една от две категории - червени множества и сини множества - така, че във всяка категория има поне едно множество. Симетричната разлика на две множества е множеството от обектите, които принадлежат на точно едно от тях. Да се докаже, че има поне 2n2^n различни множества, които могат да се получат като симетрична разлика на червено множество и синьо множество.
РешениеНека всички обекти, които се срещат в някое от дадените множества, са общо ℓ\ell на брой. Представяме всяко множество чрез неговия характеристичен вектор в F2ℓ\mathbb F_2^\ell. Тогава симетричната разлика е просто събиране на вектори. Понеже имаме 2n+12^n+1 различни вектора, непременно 2ℓ≥2n+12^\ell\ge2^n+1, тоест ℓ≥n+1\ell\ge n+1. Идентифицираме адитивната група F2ℓ\mathbb F_2^\ell с крайното поле FF с 2ℓ2^\ell елемента. Нека R⊆FR\subseteq F е множеството от червените вектори, а B⊆FB\subseteq F - множеството от сините. Трябва да докажем, че∣B+R∣≥2n.|B+R|\ge2^n.Да допуснем противното. Тогава можем да изберем множество X⊆FX\subseteq F с ∣X∣=2n−1|X|=2^n-1, което съдържа всички суми b+rb+r с b∈Bb\in B и r∈Rr\in R. Разглеждаме полиномаP(b,r)=∏x∈X(b+r−x)∈F[b,r].P(b,r)=\prod_{x\in X}(b+r-x)\in F[b,r].За всяко b∈Bb\in B и r∈Rr\in R имаме b+r∈Xb+r\in X, така че P(b,r)=0P(b,r)=0. От друга страна, степента на PP е 2n−12^n-1, а∣B∣−1+∣R∣−1=∣B∣+∣R∣−2=2n−1.|B|-1+|R|-1=|B|+|R|-2=2^n-1.Коефициентът пред b∣B∣−1r∣R∣−1b^{|B|-1}r^{|R|-1} идва от най-високостепенната част (b+r)2n−1(b+r)^{2^n-1} и е(2n−1∣B∣−1).\binom{2^n-1}{|B|-1}.По теоремата на Лукас това число е нечетно, следователно е ненулево в поле с характеристика 22. Сега комбинаторната Nullstellensatz, приложена към множествата BB и RR, показва, че трябва да съществуват b∈Bb\in B и r∈Rr\in R, за които P(b,r)≠0P(b,r)\ne0. Това противоречи на предишния абзац. Следователно допускането е невъзможно и ∣B+R∣≥2n|B+R|\ge2^n, както се искаше.
Отвори задачатаEvan Chen VONVON TSTST 2011/9Условие — източник