Задача по дискретна математика

[Гост]

Нека сме избрали n+1 елемента от множеството S={1,2,3.....2n}.
Покажете, че поне едно от избраните числа дели друго от избраните числа.

[Гост]

туй ньещу на гълъбарник ми мириши

[peyo]

Нека сме избрали n+1 елемента от множеството S={1,2,3.....2n}.
Покажете, че поне едно от избраните числа дели друго от избраните числа.

Добре, измислих следното доказателство.

Да допуснем, че всъщност твърдението е невярно и можем да изберем числата така, е нито едно от избраните да не дели някое от останалите?! Веднага ни хрумва на да изберем от горната половина или по-точно взимаме n-те числа n+1,n+2...,2n и нито едно от тях няма да дели друго. Дотук добре, остава ни да изберем последното число так,че да станат n+1. Уви, което и число да вземем от останалите от 1,2,3,..n, то ще дели някое от по-голените ече избрани. Така, че нашата първоначална идея да изберем цялата горна половина отпада.

Добре ами ако изберем n-1 от големите числа и само 1 от малките, може би ще успеем да вмъкнем и последното? Да видим. Избираме пак големите n числа както преди и сега да видим кое да махнем и да изберем някое малко (по-малко от n) вместо него?! Първо да изберем малкото число x такова, че 3x да е по-голямо от 2n. Например x=n-1 ще ни свърши работа. Тогава махаме 2x или 2(n-1) и така имаме x,n,n+1,...,2n което са пак n числа и ни оставва да изберем само още едно. Уви ако изберем по-малко от x , то ще дели някое от вече избраните, ако е по-голямо от x пак. И така не можем да изберем последното число ако само едно е от малките.

Амо ако изберем 2 малки? Да видим, избираме пак n-те големи, избираме 2 малки $x_1,x_2$ на мястото на $2x_1,2x_2$ така, че $3x_1,3x_2$ да са по-големи от 2n. Тогава пак не можем да сложим последното никъде.

Амо ако изберем 3 малки? Да видим, избираме пак n-те големи, избираме 3 малки $x_1,x_2,x_3$ на мястото на $2x_1,2x_2,2x_2$ така, че $3x_1,3x_2,3x_3$ да са по-големи от 2n. Тогава пак не можем да сложим последното никъде.

И така натaтък 4,5,6 ... това можем да правим не повече от n-2n/3 = n/3 пъти, защото тогава няма да можем да изберем достатъчно на брой $x_i$-та такива, че $3x_i$ да бъде по-голямо от 2n.

С което нашето допускане, че твърдението е невярно е невярно. А логиката казва, че двойното отрицание е положително, значи твърдението в задачата е вярно.

[Davids]

Нека сме избрали n+1 елемента от множеството S={1,2,3.....2n}.
Покажете, че поне едно от избраните числа дели друго от избраните числа.

Ето тема по въпроса тук, решението е достатъчно семпло и елегантно, според мен.