Question

В кармане Пети лежит 100 одинаковых по размеру карточек, на каждой из которых написано по одному натуральному числу от 1 до 100. Петя вынимает наугад часть карточек и смотрит, какие числа на них написаны. Какое наименьшее число карточек должен достать Петя, чтобы среди записанных на них чисел заведомо нашлось четыре, сумма которых делится на 3? Каждое число пишется только на одной карточке. (В ОТВЕТЕ УКАЗЫВАЕТСЯ ТОЛЬКО ЧИСЛО)

Answer 1

Ответ:

Используем принцип ящиков (принцип Дирихле) для решения этой задачи. Мы хотим, чтобы среди выбранных карточек было четыре, сумма чисел на которых делится на 3. Рассмотрим остатки от деления чисел от 1 до 100 на 3:

1. Остаток 0: 3, 6, 9, ..., 99 (всего 33 числа).

2. Остаток 1: 1, 4, 7, ..., 97 (всего 33 числа).

3. Остаток 2: 2, 5, 8, ..., 98 (всего 34 числа).

Если Петя вытаскивает карточки, он может неудачно выбирать до трех карточек из каждой группы (остатка). Но как только он вытаскивает четвертую карточку из любой группы, то сумма чисел на этих карточках обязательно будет делиться на 3.

Итак, Пете нужно вытянуть минимум 3 карточки из первой группы (остаток 0), 3 карточки из второй группы (остаток 1) и 3 карточки из третьей группы (остаток 2). Теперь у нас уже есть 9 карточек, и даже если следующие три карточки будут из любой из групп, то среди них обязательно найдутся четыре, сумма чисел на которых делится на 3.

Итак, Пете нужно вытянуть минимум 12 карточек, чтобы быть уверенным, что среди них найдутся четыре,сумма чисел на которых делится 3