Петя написал компьютерную программу, которая по нажатию кнопки генерирует случайное натуральное число и записывает его в файл (до начала работы программы файл пустой).
1. Сколько раз Пете нужно нажать на кнопку, чтобы знать наверняка, что в файле найдутся три числа с суммой, кратной трём?
Дайте как можно более расширенное объяснения.
Ответы
Натуральные числа условно поделим на три группы:
1) остаток от деления на 3 равен нулю
2) равен 1
3) равен 2
Перечислим всевозможные комбинации троек чисел из указанных групп, сумма которых заведомо кратна 3:
1-1-1, 2-2-2, 3-3-3, 1-2-3 (1,2 и 3 обозначают группы)
Таким образом, нужно найти количество чисел n, среди которых гарантированно получим одну из этих четырёх комбинаций.
n = 3 и n = 4 очевидно недостаточно.
n = 5. Докажем, что в данном случае искомая тройка найдётся. Цифрами буду обозначать группы, к которым принадлежат числа.
Если в пяти числах нашлась комбинация групп 1-1-1 или 2-2-2 или 3-3-3, то тройка нашлась.
Предположим, что таких комбинаций нет. Но тогда это означает, что в пятёрке чисел встретятся числа из всех трёх групп. Такая тройка нам также подходит.
Ответ: 5 раз