Question

В коробке лежит 50 карточек, на каждой из которых написано одно из чисел от 1 до 50 (каждое число по одному разу). Мистер Фокс достаёт случайным образом две карточки из коробки и записывает на доску наибольший общий делитель двух чисел, увиденных на карточках, после чего одну из карточек выбрасывает, а вторую возвращает в коробку. Это продолжается, пока в коробке не останется одна карточка. Какое наибольшее количество раз мистер Фокс мог написать на доску число 3? Полтинник на кон.

Answer 1

Ответ:

15

Объяснение:

Необходимым условием того, что у двух чисел общий делитель равен 3, является то, что оба числа делятся на 3. Среди чисел от 1 до 50 таких 16 (3,6,9,...,48). Если мы выберем 15 пар вида (3,6),(3,9),...(3,48) то для каждой из них общий делитель будет 3. Значит 3 будет записана на доске 15 раз.

Мы учитываем только отдельные тройки. Такие числа как 26 и 39 имеют общий делитель 13, и выписывая его, мистер Фокс напишет на доске цифру 3. Но такие тройки в наше решение не попадают.

Answer 2

Чтобы определить максимальное количество раз, которое мистер Фокс мог записать число 3, нужно рассмотреть расположение чисел от 1 до 50 на карточках и их наибольшие общие делители.

Очевидно, что число 3 будет записано на доску только в том случае, если оно является наибольшим общим делителем двух выбранных чисел. Известно, что 3 является делителем всех чисел, кратных 3, а также самого себя. Таким образом, чтобы мистер Фокс записал число 3, ему нужно выбрать две карточки с числами, одно из которых кратно 3.

Максимальное количество чисел, кратных 3, в диапазоне от 1 до 50, равно 16 (3, 6, 9, ..., 48). Значит, мистер Фокс мог выбрать две карточки с числами, кратными 3, и записать число 3 на доску максимум 16 раз.

Однако, чтобы это произошло, мистер Фокс должен был выбрать только карточки с числами, кратными 3, на каждом шаге. Это означает, что изначально в коробке должно быть четное количество карточек с числами, кратными 3 (чтобы сохранить четность числа карточек после каждого выброса).

Поскольку в коробке находится 50 карточек, а максимальное количество чисел, кратных 3, равно 16, то мистер Фокс мог записать число 3 на доску максимум 16 раз.