Задача 65885 Докажите, что если в n клетках сидит...
Условие
????(????−1)
2
кроликов, то найдутся две клетки, в которых
сидит одинаковое количество кроликов (может быть, ни одного)
Решение
Пусть в первой клетке 0; во второй 1 и так далее в n-ой клетке - (n-1)
0+1+2+3+4+...+(n-1)= [b](n-1)*n/2[/b]
Это сумма арифметической прогрессии.
Складываем первое число и последнее получаем (0+(n-1)=n-1
Второе и предпоследнее... (1+(n-2)=n-1
Третье и третье от конца ... (2+(n-3))=n-1
В каждой паре сумма (n-1)
и умножаем на количество таких пар ( их ровно половина (n/2)
[b](n-1)*(n/2)[/b]
А так как кроликов меньше, чем [b](n-1)*n/2[/b]
это означает, что из какой-то клетки надо убрать хотя бы одного кролика.
И тогда окажется, что в двух клетках одинаковое количество кроликов ( может быть даже 0, если уберем кролика из второй клетки, там будет 0 как и в первой)