Два пирата делят добычу, состоящую из двух мешков монет и алмаза, действуя по следующим правилам. Вначале первый пират забирает себе из любого мешка несколько монет и перекладывает из этого мешка в другой такое же количество монет. Затем также поступает второй пират (выбирая мешок, из которого он берет монеты, по своему усмотрению) и т.д. до тех пор, пока можно брать монеты по этим правилам. Пирату, взявшему монеты последним, достается алмаз. Кому достанется алмаз, если каждый из пиратов старается получить его? Дайте ответ в зависимости от первоначального количества монет в мешках.

   Решение

Темы:    [ Доказательство от противного ] [ Упорядочивание по возрастанию (убыванию) ]

Сложность: 3+ Классы: 8,9,10

Прислать комментарий

Условие

На доске написаны  n > 3  различных натуральных чисел, меньших чем  (n – 1)!.  Для каждой пары этих чисел Серёжа поделил большее на меньшее с остатком и записал в тетрадку полученное неполное частное (так, если бы он делил 100 на 7, то он бы получил  100 = 14·7 + 2  и записал бы в тетрадку число 14). Докажите, что среди чисел в тетрадке найдутся два равных.

Решение

Предположим противное. Пусть a₁, a₂, ..., a_n – числа на доске в порядке возрастания, а q_i – неполное частное от деления a_i+1 на a_i  (i = 1, 2, ...,
n – 1);  тогда  a_i+1 ≥ q_ia_i.  Так как все q_i различны, то  q₁q₂...q_n–1 ≥ (n – 1)!.  Значит,  ^a_n/_a1 = ^a_n/_an–1·^a_n–1/_an–2·...·^a₂/_a1 ≥ q₁q₂...q_n–1 ≥ (n – 1)!.  Но это невозможно, поскольку a₁ и a_n – натуральные числа, меньшие  (n – 1)!.

Источники и прецеденты использования