Matematyka.pl

Mamy \(\displaystyle{ n+1}\) różnych liczb naturalnych mniejszych od \(\displaystyle{ 2n}\). Uzasadnij że można wybrać takie trzy, że jedna jest równa sumie dwóch pozostałych.

Załóżmy przez sprzeczność, że jesteśmy w stanie wybrać n+1 liczb naturalnych z zadanego zbioru tak, aby dla żadnych 3 liczb które wybraliśmy, suma dwóch mniejszych z tej trójki nie była równa trzeciej. Niech k oznacza największą wybraną przez nas liczbę. Teraz można pokazać z zasady szufladkowej, że pewne dwie liczby z naszego zbioru będą się sumować do k.

Satansoldier, lecz jak to pokazać??

Ruahyin, jesteś pewny, że liczby te mają być mniejsze, a nie mniejsze lub równe \(\displaystyle{ 2n}\)?-- 15 sty 2017, o 10:49 --Dobra, już wiem:
Tak jak zasugerował Satansoldier. przypuśćmy, że wśród wybranych \(\displaystyle{ n+1}\) liczb nie istnieją takie trzy, że suma dwóch równa jest trzeciej. Oznaczmy przez \(\displaystyle{ k}\) największą spośród danych liczb. Wśród pozostałych \(\displaystyle{ n}\) liczb nie istnieją jednocześnie liczby \(\displaystyle{ l}\) i \(\displaystyle{ k-l}\). Wtedy jednak wybranych liczb byłoby co najwyżej \(\displaystyle{ \frac{k}{2}+1<n+1}\) i otrzymana sprzeczność kończy dowód.