Question

На 100 карточках написали все натуральные числа от 1 до 100. Карточки перевернули. Какое наименьшее количество карточек надо взять наугад, чтобы быть уверенным, что среди чисел на выбранных карточках окажется не меньше двух взаимно простых?

Answer 1

Самая длинная последовательность невзаимнопростых чисел - четные числа
их 50
если чисел 51 то обязательно будет хоть одно четное и хоть одно нечетное - пара взаимнопростых чисел

Answer 2

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

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

В данном случае, мы можем рассмотреть карточки с числами от 1 до 100 как объекты, а взаимно простые числа как ящики. Нам нужно найти наименьшее количество карточек, чтобы быть уверенным, что среди выбранных карточек окажется не меньше двух взаимно простых чисел.

Для этого, мы можем рассмотреть наибольшее взаимно простое число с каждым числом от 1 до 100. Например, наибольшее взаимно простое число с числом 1 равно 2, с числом 2 равно 3, с числом 3 равно 5 и так далее.

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

Ответ: 100 карточек.