** 100 карточках написали все натуральные числа от 1 до 100. Карточки перевернули. Какое...

Question

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

Comments

это значит что не имеют никаких общих делителей кроме 1!

---

это типа 3, 7,11,17,31?

---

да

---

не только такие, но и числа 15 и 8 тоже взаимно простые

---

короче я не понял что это за взаимно простые

---

Ну вам ведь написали, что это такие числа которые НЕ ИМЕЮТ ОБЩИХ ДЕЛИТЕЛЕЙ КРОМЕ 1

---

Вы привели пример простых чисел, но я вам привел пример что и не только простые числа могут быть взаимно простые например 15 и 28 тоже взаимно простые! Так как 15=1*3*5 а 28=1*4*7

---

думаю, что 52

---

или 51

---

если 1 и 2 замно-простые то ответ 51

Answer 1

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

Comments

Числа 3 и 6 - разной четности, но не взаимно просты.

---

Или надо пояснить, почему найдутся... Например, так. Если 2 не является общим делителем, то на неё можно сократить. А дальше - тривиальное утверждение: если взять все числа 1..50 и любое натуральное число x из [1, 100], то среди них найдутся два вз. простых числа.
"Доказательство". x не может одновременно делиться, например, на 11 и 13 (иначе оно не меньше 11*13=143). Тогда хотя бы с одним из этих чисел оно взаимно просто.

---

Или надо пояснить, почему найдутся... Например, так. Если 2 не является общим делителем, то на неё можно сократить. А дальше - тривиальное утверждение: если взять все числа 1..50 и любое натуральное число x из [1, 100], то среди них найдутся два вз. простых числа.
"Доказательство". x не может одновременно делиться, например, на 11 и 13 (иначе оно не меньше 11*13=143). Тогда хотя бы с одним из этих чисел оно взаимно просто.