В кармане Пети лежит 100 одинаковых по размеру карточек, на каждой из которых написано по одному натуральному числу от 1 до 100. Петя вынимает наугад часть карточек и смотрит, какие числа на них написаны. Какое наименьшее число карточек должен достать Петя, чтобы среди записанных на них чисел заведомо нашлось четыре, сумма которых делится на 3? Каждое число пишется только на одной карточке.
Ответы
Мы можем рассмотреть самый неблагоприятный сценарий, когда Петя вытаскивает карточки без каких-либо чисел, делящихся на 3, затем вытаскивает карточки с числами, сумма которых не делится на 3.
Если мы возьмем 9 карточек, то среди них могут быть 6 карточек с числами, не делящимися на 3, и 3 карточки с числами, делящимися на 3 (например, числа 3, 6 и 9). Тогда сумма чисел на карточках, не делящихся на 3, может быть:
2+5+8+11+14+17=57
Теперь, даже если Петя достанет еще одну карточку, чтобы достичь минимума в 10 карточек, он может взять две карточки, сумма чисел на которых даст 2 + 4 + 57 = 63 (делящееся на 3), либо 5 + 6 + 57 = 68 (не делящееся на 3). Не существует суммы трех чисел среди карточек, не делящихся на 3, которая даст число, делящееся на 3, если уже выбраны 9 карточек.
Следовательно, минимальное количество карточек, которое Пете нужно вытащить, чтобы среди них заведомо было 4 числа, сумма которых делится на 3, составляет 10.