ОСНОВЫ МАТЕМАТИКИ
Базовая комбинаторика
Задача на монеты. Принцип Дирихле.
Условие задачи звучит следующим образом:
Есть монеты ценой 1,2,5 и 10 рублей. Каково необходимое и достаточное (минимальное) количество монет, чтобы всегда нашлись 6 монет одного достоинства?

Давайте попробуем увидеть здесь принцип Дирихле:
  • У нас 4 "ящика" (достоинства монет)
  • Нам нужно, чтобы в одном из ящиков было минимум 6 "кроликов" (монет)

Решение.
Если у нас есть 20 монет, их можно распределить поровну: по 5 монет каждого достоинства. В этом случае не будет 6 монет одного достоинства.
Но если у нас 21 монета, то по принципу Дирихле хотя бы одно достоинство должно содержать не менее 6 монет. Это происходит потому, что:
  • Максимально равномерное распределение: 5 + 5 + 5 + 5 = 20
  • С 21-й монетой хотя бы одна группа должна содержать 6 или более монет.
20 монет (недостаточно) 1 рубль 2 рубля 5 монет 5 монет 21 монета (достаточно) 5 рублей 10 рублей 5 монет 6 монет Формула принципа Дирихле: n > m × (k-1) 21 > 4 × 5 = 20 Ответ: 21 монета Обозначения: n - количество монет m - число достоинств (4) k - требуемое число монет одного типа (6) При 20 монетах условие не выполняется, при 21 — выполняется
Условие задачи звучит следующим образом:
Есть монеты ценой 1,2,5 и 10 рублей. Каково необходимое и достаточное (минимальное) количество монет, чтобы всегда нашлись 6 монет одного достоинства?

Давайте попробуем увидеть здесь принцип Дирихле:
  • У нас 4 "ящика" (достоинства монет)
  • Нам нужно, чтобы в одном из ящиков было минимум 6 "кроликов" (монет)

Решение.
Если у нас есть 20 монет, их можно распределить поровну: по 5 монет каждого достоинства. В этом случае не будет 6 монет одного достоинства.
Но если у нас 21 монета, то по принципу Дирихле хотя бы одно достоинство должно содержать не менее 6 монет. Это происходит потому, что:
  • Максимально равномерное распределение: 5 + 5 + 5 + 5 = 20
  • С 21-й монетой: хотя бы одна группа должна содержать 6 или более монет.