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

Контролно за национален отбор за БОМ

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

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

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

2005

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

9

8 задачи

Задача 1

Пълен запис
Условие
Да се намерят всички положителни числа aa и bb такива, че [a[bn]]=n−1[a[b n]]=n-1 за произволно естествено число nn ( [x][x] означава най-голямото цяло число, ненадминаващо xx ).
РешениеРешение. Като използваме два пъти неравенствата x−1<[x]≤xx-1\lt{}[x] \leq x, получаваме, че abn−a−1<n−1≤abna b n-a-1\lt{}n-1 \leq a b n. Оттук n(ab−1)<an(a b-1)\lt{}a и n(1−ab)≤1n(1-a b) \leq 1. Ако ab≠1a b \neq 1, то в едно от последните две неравенства коефициентът пред nn е положителен и то не е изпълнено за достатъчно големи nn. Следователно ab=1a b=1 и изходното неравенство е еквивалентно наbn−b≤[bn]<bn.b n-b \leq[b n]\lt{}b n.Дясното неравенство означава, че за всяко nn числото bnb n не е цяло, т. е. bb е ирационално число. При b>1b\gt{}1 лявата неравенство в (1) очевидно е в сила. Ако 0<b<10\lt{}b\lt{}1, избираме n=[1b−1]n=\left[\frac{1}{b-1}\right]. Тогава n−2n−1<b<nn−1\frac{n-2}{n-1}\lt{}b\lt{}\frac{n}{n-1}, откъдето [bn]≤n−2[b n] \leq n-2 и следователно [[bn]b]<n−1\left[\frac{[b n]}{b}\right]\lt{}n-1, противоречие. И така, търсените aa и bb са произволни ирационални числа, за които ab=1a b=1 и b>1b\gt{}1.
Отвори задачатаБаза на maths.bgkbom2005-9-1

Задача 2

Пълен запис
Условие
Точки PP и QQ от вътрешността на △ABC\triangle A B C са такива, че ∠ACP=∠BCQ\angle A C P= \angle B C Q и ∠CAP=∠BAQ\angle C A P=\angle B A Q. С D,ED, E и FF са означени петите на перпендикулярите от PP съответно към правите BC,CAB C, C A и ABA B. Да се докаже, че ако ∠DEF=90∘\angle D E F= 90^{\circ}, то QQ е ортоцентърът на △BDF\triangle B D F.
РешениеИмаме, че ∠BCQ=∠ACP=∠EDP\angle B C Q=\angle A C P=\angle E D P. Тъй като PD⊥P D \perp BCB C, следва, че ED⊥CQE D \perp C Q. Аналогично AQ⊥EFA Q \perp E F. Понеже ∠DEF=90∘\angle D E F=90^{\circ}, заключаваме, че и ∠AQC=90∘\angle A Q C=90^{\circ}. Тогава △QCD∼△ACP\triangle Q C D \sim \triangle A C P, тъй като ∠QCD=∠ACP\angle Q C D= \angle A C P иDCQC=PCcos⁡∠PCDACcos⁡∠ACQ=PCAC\frac{D C}{Q C}=\frac{P C \cos \angle P C D}{A C \cos \angle A C Q}=\frac{P C}{A C}Следователно ∠DQC=∠PAC=∠PFE\angle D Q C=\angle P A C=\angle P F E. Понеже CQ∥EF(⊥ED)C Q \| E F(\perp E D), следва, че DQ∥PFD Q \| P F, т. е. DQ⊥ABD Q \perp A B. Аналогично FQ⊥BCF Q \perp B C и значи QQ е ортоцентърът на △BDF\triangle B D F. Забележка. Обратното твърдение също е вярно: ако QQ е ортоцентърът на △BDF\triangle B D F, то ∠DEF=90∘\angle D E F=90^{\circ}.
Отвори задачатаБаза на maths.bgkbom2005-9-2

Задача 3

Пълен запис
Условие
Съществува ли строго растяща редица от естествени числа a1,…,an,…a_{1}, \ldots, a_{n}, \ldots така, че an≤n3a_{n} \leq n^{3} за произволно nn и всяко естествено число може да се представи по единствен начин като разлика на два члена на редицата?
РешениеСъществува. Ще дефинираме индуктивно редица с исканите свойства. Полагаме a1=1a_{1}=1 и a2=2a_{2}=2. Да предположим, че вече сме определили a1,a2,…,a2ka_{1}, a_{2}, \ldots, a_{2 k}. Означаваме с mm най-малкото естествено число, което не може да се представи като във вида aj−ai,1≤i<j≤2ka_{j}-a_{i}, 1 \leq i\lt{}j \leq 2 k. Понеже тези разлики са d=k(2k−1)d=k(2 k-1) на брой, то m≤d+1m \leq d+1. Нека a2k+2=a2k+1+ma_{2 k+2}=a_{2 k+1}+m. Ще търсим a2k+1a_{2 k+1} така, че a2k+1≠al,a2k+1±m≠al,a2k+1−al≠aj−aj,a2k+1+m−al≠aj−aj,1≤l≤2k,1≤i<j≤2ka_{2 k+1} \neq a_{l}, a_{2 k+1} \pm m \neq a_{l}, a_{2 k+1}-a_{l} \neq a_{j}-a_{j}, a_{2 k+1}+m-a_{l} \neq a_{j}-a_{j}, 1 \leq l \leq 2 k, 1 \leq i\lt{}j \leq 2 k. Оттук следва, че a1,a2,…,a2k+2a_{1}, a_{2}, \ldots, a_{2 k+2} са две по две различни числа и всяко естествено число от 1 до mm се представя по единствен начин като разлика на две от тези числа. За a2k+1a_{2 k+1} имаме 6k+4kd6 k+4 k d "забранени"стойности и следователно можем да изберем a2k+1≤6k+4kd+1a_{2 k+1} \leq 6 k+4 k d+1. Тогаваa2k+1<a2k+2=a2k+1+m≤a_{2 k+1}\lt{}a_{2 k+2}=a_{2 k+1}+m \leq6k+4kd+1+d+1<(2k+1)3 6 k+4 k d+1+d+1\lt{}(2 k+1)^{3}и остава да подредим числата a1,a2,…,a2k+2a_{1}, a_{2}, \ldots, a_{2 k+2} по големина (съобразете, че неравенството an≤n3a_{n} \leq n^{3} се запазва). 4. Нека OO е произволна точка в равнината и A1,1A2,1…,An,1A_{1, 1} A_{2, 1} \ldots, A_{n, 1} е подобен на P\mathcal{P} многоъгълник, който съдържа OO. Да построим многоъгълниците OA1,1A1,2…A1,n−1,OA2,1A2,2…A2,n−1,…,OAn,1An,2…An,n−1O A_{1, 1} A_{1, 2} \ldots A_{1, n-1}, O A_{2, 1} A_{2, 2} \ldots A_{2, n-1}, \ldots, O A_{n, 1} A_{n, 2} \ldots A_{n, n-1}, еднакво ориентирани и подобни на A1A2…AnA_{1} A_{2} \ldots A_{n}. Като използваме въртяща хомотетия с център OO, следва, че A1,jA2,j,…,An,j,j=2,…,n−A_{1, j} A_{2, j}, \ldots, A_{n, j}, j=2, \ldots, n- 1, е еднакво ориентиран и подобен на A1,1A2,1…An,1A_{1, 1} A_{2, 1} \ldots A_{n, 1} многоъгълник. Да означим с oo и ai,ja_{i, j} числата, записани съответно в точките OO и Ai,jA_{i, j}. Като съберем равенстватаo+∑j=1n−1ai,j=0,i=1,…,no+\sum_{j=1}^{n-1} a_{i, j}=0, i=1, \ldots, nи след това използваме, че∑i=1nai,j=0,i=1,…,n−1,\sum_{i=1}^{n} a_{i, j}=0, i=1, \ldots, n-1,получаваме no=0n o=0, с което задачата е решена.
Отвори задачатаБаза на maths.bgkbom2005-9-3

Задача 4

Пълен запис
Условие
В равнината е даден изпъкнал многоъгълник P\mathcal{P} и на всяка точка от нея е съпоставено реално число. Известно е, че сумата от числата, съответстващи на върховете на произволен подобен на P\mathcal{P} многоъгълник, е равна на 0. Да се докаже, че всички числа са равни на 0.
РешениеРешение. Нека OO е произволна точка в равнината и A1,1A2,1…,An,1A_{1, 1} A_{2, 1} \ldots, A_{n, 1} е подобен на P\mathcal{P} многоъгълник, който съдържа OO. Да построим многоъгълниците OA1,1A1,2…A1,n−1,OA2,1A2,2…A2,n−1,…,OAn,1An,2O A_{1, 1} A_{1, 2} \ldots A_{1, n-1}, O A_{2, 1} A_{2, 2} \ldots A_{2, n-1}, \ldots, O A_{n, 1} A_{n, 2} …An,n−1\ldots A_{n, n-1}, еднакво ориентирани и подобни на A1A2…AnA_1 A_2 \ldots A_n. Като използваме въртяща хомотетия с център OO, следва, че A1,jA2,j,…,An,j,j=2,…,n−A_{1, j} A_{2, j}, \ldots, A_{n, j}, j=2, \ldots, n- 1, е еднакво ориентиран и подобен на A1,1A2,1…An,1A_{1, 1} A_{2, 1} \ldots A_{n, 1} многоъгълник. Да означим с oo и ai,ja_{i, j} числата, записани съответно в точките OO и Ai,jA_{i, j}. Като съберем равенстватаo+∑j=1n−1ai,j=0,i=1,…,no+\sum_{j=1}^{n-1} a_{i, j}=0, i=1, \ldots, nи след това използваме, че∑i=1nai,j=0,i=1,…,n−1,\sum_{i=1}^n a_{i, j}=0, i=1, \ldots, n-1,получаваме no=0n o=0, с което задачата е решена.
Отвори задачатаБаза на maths.bgkbom2005-9-4

Задача 5

Пълен запис
Условие
Ако a0=0a_{0}=0 и an=a[n2]+[n2],n≥1a_{n}=a_{\left[\frac{n}{2}\right]}+\left[\frac{n}{2}\right], n \geq 1, да се намери lim⁡n→+∞ann\lim _{n \rightarrow+\infty} \frac{a_{n}}{n}.
РешениеЩе докажем по индукция, че an=n−wt2(n)a_{n}=n-w t_{2}(n), където wt2(n)w t_{2}(n) означава броят на единиците в двоичното представяне на nn. Наистина при n=0n=0 имаме a0=0a_{0}=0 и твърдението е вярно. Да допуснем, че твърдението е вярно за всяко n≤k−1n \leq k-1. Ако k=2k0k=2 k_{0}, то като използваме, че wt2(k0)=wt2(k)w t_{2}\left(k_{0}\right)=w t_{2}(k) (тъй като двоичните представяния на k0k_{0} и k=2k0k=2 k_{0} имат равен брой единици) получавамеak=ak0+k0=k0−wt2(k0)+k0=a_{k}=a_{k_{0}}+k_{0}=k_{0}-w t_{2}\left(k_{0}\right)+k_{0}=k−wt2(k0)=k−wt2(k).k-w t_{2}\left(k_{0}\right)=k-w t_{2}(k).Ако k=2k0+1k=2 k_{0}+1, то като използваме, че wt2(2k0+1)=wt2(2k0)+1w t_{2}\left(2 k_{0}+1\right)=w t_{2}\left(2 k_{0}\right)+1 (тъй като в двоичното представяне на 2k0+12 k_{0}+1 има една единица повече от двоичното представяне на 2k02 k_{0} ) получавамеak=ak0+k0=k0−wt2(k0)+k0=2k0−wt2(2k0)a_{k}=a_{k_{0}}+k_{0}=k_{0}-w t_{2}\left(k_{0}\right)+k_{0}=2 k_{0}-w t_{2}\left(2 k_{0}\right)=2k0+1−wt2(2k0+1)=k−wt2(k).=2 k_{0}+1-w t_{2}\left(2 k_{0}+1\right)=k-w t_{2}(k).Тъй като ако wt2(n)=tw t_{2}(n)=t, то n≥2t−1n \geq 2^{t}-1, намираме0≤lim⁡n→+∞wt2(n)n≤lim⁡t→+∞t2t=0.0 \leq \lim _{n \rightarrow+\infty} \frac{w t_{2}(n)}{n} \leq \lim _{t \rightarrow+\infty} \frac{t}{2^{t}}=0.Следователно lim⁡n→+∞wt2(n)n=0\lim _{n \rightarrow+\infty} \frac{w t_{2}(n)}{n}=0 и за търсената граница получавамеlim⁡n→+∞ann=lim⁡n→+∞n−wt2(n)n=\lim _{n \rightarrow+\infty} \frac{a_{n}}{n}=\lim _{n \rightarrow+\infty} \frac{n-w t_{2}(n)}{n}=1−lim⁡n→+∞wt2(n)n=1.1-\lim _{n \rightarrow+\infty} \frac{w t_{2}(n)}{n}=1.\setcounter{enumi}{5} (∗)(*) Ще докажем твърдението с индукция по N=a1+a2+⋯+amN=a_{1}+a_{2}+\cdots+a_{m}. При N=1N=1 имаме m=1,a1=1m=1, a_{1}=1 и b1=1b_{1}=1 е търсеното число. Да допуснем, че твърдението е вярно за всеки набор със сума ненадминаваща NN и нека a1,a2,…,ama_{1}, a_{2}, \ldots, a_{m} са такива, че a1+a2+⋯+am=Na_{1}+a_{2}+\cdots+a_{m}=N. Ако всички числа a1,a2,…,ama_{1}, a_{2}, \ldots, a_{m} са четни, то числата a12,a22,…,am2\frac{a_{1}}{2}, \frac{a_{2}}{2}, \ldots, \frac{a_{m}}{2} имат сума N2\frac{N}{2} и по индукционното допускане съществува набор b1,b2,…,bnb_{1}, b_{2}, \ldots, b_{n} изпълняващ условието. Тогава търсените числа за a1,a2,…,ama_{1}, a_{2}, \ldots, a_{m} са 2b1,2b2,…,2bn2 b_{1}, 2 b_{2}, \ldots, 2 b_{n}. Нека измежду дадените числа има поне едно нечетно и без ограничение ama_{m} е най-малкото нечетно число. Да разгледаме числата a1′,a2′,…,am−1′a_{1}^{\prime}, a_{2}^{\prime}, \ldots, a_{m-1}^{\prime} получени по следния начинai′={ai2акоaiе четноai−am2акоaiе нечетноa_{i}^{\prime}= \begin{cases}\frac{a_{i}}{2} & \text{ако} a_{i} \text{е четно} \\ \frac{a_{i}-a_{m}}{2} & \text{ако} a_{i} \text{е нечетно}\end{cases}Сумата на тези числа не надминава NN и по индукционното допускане съществуват числа b1′,b2′,…,bk′b_{1}^{\prime}, b_{2}^{\prime}, \ldots, b_{k}^{\prime}, които изпълняват условието на задачата. Ще докаже, че търсените числа за набора a1,a2,…,ama_{1}, a_{2}, \ldots, a_{m} са 2b1′,2b2′,…,2bk′,am2 b_{1}^{\prime}, 2 b_{2}^{\prime}, \ldots, 2 b_{k}^{\prime}, a_{m}. Ако има две непресичащи се подмножества на {2b1′,2b2′,…,2bk′,am}\left\{2 b_{1}^{\prime}, 2 b_{2}^{\prime}, \ldots, 2 b_{k}^{\prime}, a_{m}\right\} с равни суми на елементите си, то ama_{m} като единствено нечетно число не участва в тези подмножества и тогава след съкращаване на 2 ще получим две подмножества на {b1′,b2′,…,bk′}\left\{b_{1}^{\prime}, b_{2}^{\prime}, \ldots, b_{k}^{\prime}\right\} с равни суми от елементите, което е противоречие. Лесно се вижда, че всеки елемент от a1,a2,…,ama_{1}, a_{2}, \ldots, a_{m} се представя като сума от елементи на 2b1′,2b2′,…,2bk′,am2 b_{1}^{\prime}, 2 b_{2}^{\prime}, \ldots, 2 b_{k}^{\prime}, a_{m}, с което задачата е решена.
Отвори задачатаБаза на maths.bgkbom2005-9-5

Задача 6

Пълен запис
Условие
Дадени са различни естествени числа a1,a2,…,ama_{1}, a_{2}, \ldots, a_{m}. Да се докаже, че съществуват различни естествени числа b1,b2,…,bn,n≤mb_{1}, b_{2}, \ldots, b_{n}, n \leq m, за които са изпълнени следните две условия: (1) Всички подмножества на {b1,b2,…,bn}\left\{b_{1}, b_{2}, \ldots, b_{n}\right\} имат различни суми на елементите си. (2) Всяко от числата a1,a2,…,ama_{1}, a_{2}, \ldots, a_{m} е сума на елементите на подмножество на {b1,b2,…,bn}\left\{b_{1}, b_{2}, \ldots, b_{n}\right\}.
РешениеРешение. Ще докажем твърдението с индукция по N=a1+a2+⋯+amN=a_1+a_2+\cdots+a_m. При N=1N=1 имаме m=1,a1=1m=1, a_1=1 и b1=1b_1=1 е търсеното число. Да допуснем, че твърдението е вярно за всеки набор със сума ненадминаваща NN и нека a1,a2,…,ama_1, a_2, \ldots, a_m са такива, че a1+a2+⋯+am=Na_1+a_2+\cdots+a_m=N. Ако всички числа a1,a2,…,ama_1, a_2, \ldots, a_m са четни, то числата a12,a22,…,am2\frac{a_1}{2}, \frac{a_2}{2}, \ldots, \frac{a_m}{2} имат сума N2\frac{N}{2} и по индукционното допускане съществува набор b1,b2,…,bnb_1, b_2, \ldots, b_n изпълняващ условието. Тогава търсените числа за a1,a2,…,ama_1, a_2, \ldots, a_m са 2b1,2b2,…,2bn2 b_1, 2 b_2, \ldots, 2 b_n. Нека измежду дадените числа има поне едно нечетно и без ограничение ama_m е най-малкото нечетно число. Да разгледаме числата a1′,a2′,…,am−1′a_1^{\prime}, a_2^{\prime}, \ldots, a_{m-1}^{\prime} получени по следния начинai′={ai2акоaiе четноai−am2акоaiе нечетноa_i^{\prime}= \begin{cases}\frac{a_i}{2} & \text{ако} a_i \text{е четно} \\ \frac{a_i-a_m}{2} & \text{ако} a_i \text{е нечетно}\end{cases}Сумата на тези числа не надминава NN и по индукционното допускане съществуват числа b1′,b2′,…,bk′b_1^{\prime}, b_2^{\prime}, \ldots, b_k^{\prime}, които изпълняват условието на задачата. Ще докаже, че търсените числа за набора a1,a2,…,ama_1, a_2, \ldots, a_m са 2b1′,2b2′,…,2bk′,am2 b_1^{\prime}, 2 b_2^{\prime}, \ldots, 2 b_k^{\prime}, a_m. Ако има две непресичащи се подмножества на {2b1′,2b2′,…,2bk′,am}\left\{2 b_1^{\prime}, 2 b_2^{\prime}, \ldots, 2 b_k^{\prime}, a_m\right\} с равни суми на елементите си, то ama_m като единствено нечетно число не участва в тези подмножества и тогава след съкращаване на 2 ще получим две подмножества на {b1′,b2′,…,bk′}\left\{b_1^{\prime}, b_2^{\prime}, \ldots, b_k^{\prime}\right\} с равни суми от елементите, което е противоречие. Лесно се вижда, че всеки елемент от a1,a2,…,ama_1, a_2, \ldots, a_m се представя като сума от елементи на 2b1′,2b2′,…,2bk′,am2 b_1^{\prime}, 2 b_2^{\prime}, \ldots, 2 b_k^{\prime}, a_m, с което задачата е решена.
Отвори задачатаБаза на maths.bgkbom2005-9-6

Задача 7

Пълен запис
Условие
Даден е изпъкнал четириъгълник ABCDA B C D, в който продълженията на страните ABA B и CDC D се пресичат в точка PP, а продълженията на страните BCB C и ADA D се пресичат в точка QQ. Точка OO от вътрешността на четириъгълника е такава, че ∠BOP=∠DOQ\angle B O P=\angle D O Q. Да се докаже, че ∠AOB+∠COD=180∘\angle A O B+\angle C O D=180^{\circ}
РешениеСинусова теорема за триъгълниците ODQO D Q и AOQA O Q даваsin⁡φsin⁡β=QDODи\frac{\sin \varphi}{\sin \beta}=\frac{Q D}{O D} \quad \text{и} \quadsin⁡(φ+∠AOD)sin⁡β=AQOA. \frac{\sin (\varphi+\angle A O D)}{\sin \beta}=\frac{A Q}{O A}.След разделяне получавамеsin⁡(φ+∠AOD)sin⁡φ=AQOA⋅ODQD.\frac{\sin (\varphi+\angle A O D)}{\sin \varphi}=\frac{A Q}{O A} \cdot \frac{O D}{Q D}.Аналогично намирамеsin⁡(φ+∠AOB)sin⁡φ=APOA⋅OBBP.\frac{\sin (\varphi+\angle A O B)}{\sin \varphi}=\frac{A P}{O A} \cdot \frac{O B}{B P}.След разделяне получаваме разделяне получавамеsin⁡(φ+∠AOD)sin⁡(φ+∠AOB)=\frac{\sin (\varphi+\angle A O D)}{\sin (\varphi+\angle A O B)}=AQAP⋅ODOB⋅BPQD.\frac{A Q}{A P} \cdot \frac{O D}{O B} \cdot \frac{B P}{Q D}.По същия начин получаваме и равенствотоsin⁡(∠DOC−φ)sin⁡(∠BOC−φ)=\frac{\sin (\angle D O C-\varphi)}{\sin (\angle B O C-\varphi)}=QCPC⋅OBOD⋅PDQB.\frac{Q C}{P C} \cdot \frac{O B}{O D} \cdot \frac{P D}{Q B}.От теоремата на Менелай за △ADC\triangle A D C и правата QPQ P, и △ABC\triangle A B C и правата QPQ P следваAQ⋅DPDQ⋅CP=ALCL\frac{A Q \cdot D P}{D Q \cdot C P}=\frac{A L}{C L} \quadиQC⋅BPQB⋅AP=CLAL. \text{и} \quad \frac{Q C \cdot B P}{Q B \cdot A P}=\frac{C L}{A L}.Ако положим φ+∠AOD=x,φ+∠AOB=y,∠DOC−φ=z\varphi+\angle A O D=x, \varphi+\angle A O B=y, \angle D O C-\varphi=z и ∠BOC−φ=t\angle B O C- \varphi=t, получавамеsin⁡x⋅sin⁡zsin⁡y⋅sin⁡t=\frac{\sin x \cdot \sin z}{\sin y \cdot \sin t}=AQ⋅DP⋅QC⋅BPDQ⋅CP⋅QB⋅AP=\frac{A Q \cdot D P \cdot Q C \cdot B P}{D Q \cdot C P \cdot Q B \cdot A P}=ALCLCLAL=1,\frac{A L}{C L} \frac{C L}{A L}=1,т. е. sin⁡x.sin⁡z=sin⁡y.sin⁡t\sin x. \sin z=\sin y. \sin t. Оттук лесно следва cos⁡(x−z)−cos⁡(x+z)=cos⁡(y−t)−cos⁡(y+t)\cos (x-z)-\cos (x+z)= \cos (y-t)-\cos (y+t) и тъй като x+y+z+t=360∘x+y+z+t=360^{\circ}, то cos⁡(x+z)=cos⁡(y+t)\cos (x+z)= \cos (y+t). Следователно cos⁡(x−z)=cos⁡(y−t)\cos (x-z)=\cos (y-t) и понеже x−z+y−t<360∘x-z+y-t\lt{} 360^{\circ}, а равенството x−z=t−yx-z=t-y означава, че OO лежи на PQP Q (проверете!), получаваме че x−z=y−tx-z=y-t, откъдето x+t=z+y=180∘x+t=z+y=180^{\circ}.
Отвори задачатаБаза на maths.bgkbom2005-9-7

Задача 8

Пълен запис
Условие
В група от BB младежи и GG девойки е известно, че G≥2B−1G \geq 2 B-1. Някои младежи познават някои девойки. Да се докаже, че в един танц всички младежи могат да танцуват с девойки по такъв начин, че всеки младеж, който не познава девойката, с която танцува, да познава само девойки, които не танцуват.
РешениеАко за всяко s=1,2,…,Bs=1, 2, \ldots, B всяка група от ss младежи познават заедно поне ss момичета. Тогава по теоремата на Хол за представителите следва, че всяко момче може да танцува с познато момиче и условието на задачата е изпълнено. Да допуснем противното и да изберем най-голямото s≤Bs \leq B, за което има ss младежи, които заедно познават общо не повече от s−1s-1 момичета. Да означим множеството на избраните ss младежи с SS, а множеството на познатите им момичета с LL. Ако някои tt от младежите извън SS познават не повече от tt от момичетата извън LL, то ще получим противоречие с максималността на ss. Следователно всеки tt от младежите извън SS познават поне t+1t+1 от момичетата извън LL. От теоремата на Хол следва, че всяко момче извън SS може да танцува с познато момиче извън LL. Извън LL нетанцуващи момичета остават поне G−(B−s)−(s−1)=G+1−B≥B(B−sG-(B-s)-(s-1)=G+1-B \geq B(B-s са момичетата, които танцуват с момчета извън SS, а s−1s-1 са най-много момичетата, познати на младежите от SS ). Ако момчетата от SS танцуват с някои ss от останалите нетанцуващи момичета извън SS, то условието е изпълнено.
Отвори задачатаБаза на maths.bgkbom2005-9-8