Question

СРОЧНО 30 баллов даю У Константина есть 685 карточек, с числами не кратными 6, от 1 до 822. Он собирается взять их так, чтобы на любых трёх карточках числа имели общий делитель, больший 1. Какое наибольшее количество карточек можно выбрать таким образом?

Answer 1

Ответ:

654

Пошаговое объяснение:

Answer 2

Чтобы решить эту задачу, мы можем воспользоваться принципом Дирихле о ящиках и шарах.

Принцип Дирихле гласит, что если мы распределяем n+1 объектов на n корзин, то как минимум в одной из корзин будет находиться два или более объекта.

В данном случае, число наших карточек (685) больше, чем количество возможных делителей (не считая 1) для чисел от 1 до 822, которое составляет примерно 270. Исходя из принципа Дирихле, мы можем заключить, что больше чем 270 карточек не могут иметь общий делитель больший 1.

Таким образом, наибольшее количество карточек, которое можно выбрать таким образом, равно 270.