Matematyka dyskretna, zadanie nr 1573
ostatnie wiadomo艣ci | regulamin | latex
| Autor | Zadanie / Rozwi膮zanie |
wojtolino post贸w: 1 |  2013-10-11 11:44:24Witam! Prosz臋 o jakie艣 wskaz贸wki w poni偶szym zadaniu. Mamy zbi贸r $A \subseteq \mathbb{Z}$ taki, 偶e $\left| A+A\right|=2\left| A\right|-1$ (gdzie $A+A=\left\{ a_{1}+a_{2},\quad a_{1},a_{2}\in A\right\}$). Trzeba pokaza膰, 偶e elementy $A$ tworz膮 ci膮g arytmetycznym. Jasne jest, 偶e pewne elementy w zbiorze sum musz膮 si臋 powtarza膰 (bo inaczej $\left| A\right| =\frac{1}{2}n(n+1)$). Wiemy te偶, 偶e $\forall_{A}\quad 2\left| A\right| -1 \le \left| A+A\right| \le {\left| A\right|+1 \choose 2}$ (tw. z wyk艂adu), ale nie mog臋 st膮d nic wywnioskowa膰. Z g贸ry dzi臋kuj臋 za pomoc. |
tumor post贸w: 8070 | 2013-10-22 21:18:16 We藕my liczby $a_1 <a_2<a_3<...<a_n$, gdzie $|A|=n$ i $A\subset Z$. Zauwa偶my, 偶e mamy pewno艣膰 istnienia 2n-1 r贸偶nych sum: $a_1+a_1<a_1+a_2<a_2+a_2<a_2+a_3<a_3+a_3<...<a_{n-1}+a_n<a_n+a_n$. Przypu艣膰my teraz, 偶e wyrazy $a_i$ nie tworz膮 ci膮gu arytmetycznego. Oznacza to, 偶e istniej膮 wyrazy $a_k, a_{k+1}, a_{k+2}$ dla $1\le k <n-1$ takie, 偶e zachodzi jeden z poni偶szych warunk贸w: 1) $a_{k+2}-a_{k+1} > a_{k+1} - a_{k}$ 2) $ a_{k+2}-a_{k+1} < a_{k+1} - a_{k}$ czyli, m贸wi膮c po polsku, 偶e dwie s膮siednie r贸偶nice kolejnych element贸w nie s膮 r贸wne. Ad.1) Po przerzuceniu mamy $a_{k+2}+a_k>2a_{k+1}$ Zarazem jednak $a_{k+2}+a_{k+1}>a_{k+2}+a_k$. Oznacza to, 偶e suma $a_{k+2}+a_k$ nie zosta艂a wymieniona w ci膮gu sum powy偶ej, czyli sum jest co najmniej $2n$. Ad.2) Analogicznie, zostawiam pa艅stwu jako 膰wiczenie do domu. ----- Zasadniczo nie trzeba pokazywa膰 w zadaniu, 偶e dla element贸w b臋d膮cych wyrazami ci膮gu arytmetycznego rzeczywi艣cie mamy $|A+A|=2|A|-1$. |
| strony: 1 | |
Prawo do pisania przys艂uguje tylko zalogowanym u偶ytkownikom. Zaloguj si臋 lub zarejestruj