ПВГ 2025, 9–10 классы, задача 6

Простая

Источник:

Покори Воробьёвы горы!, Отборочный этап, 2025, 10 класс Покори Воробьёвы горы!, Отборочный этап, 2025, 9 класс

В спортивный клуб ходит школьников. На каждой тренировке они делятся на команды (не обязательно одинакового размера) и играют в футбол. За какое наименьшее число тренировок можно их разделить на команды так, чтобы любые два школьника хотя бы один раз сыграли в разных командах?

Ответ

Ответ: .

Решение: пронумеруем участников и запишем номер в двоичной системе счисления ( цифры, могут начинаться с нуля). Будем считать, что если -я цифра , то он на -й тренировке играет за «синих», а если – то за «красных». Поскольку любые два номера отличаются хотя бы в одном разряде, то, соответственно, два игрока попадут в разные команды. За три тренировки так разбить нельзя, поскольку всего последовательностей из нулей и единиц длины . Т.е. у каких-то двух школьников последовательности совпадут, и они все время будут играть в одной команде.

Похожие задачи

ПВГ 2024, 7–10 классы, задача 5 (7–8), задача 3 (9), задача 2 (10)

Коле на день рождения подарили набор из 12 фломастеров разных цветов. Коля начал рисовать одинаковые по размеру правильные треугольники и раскрашивать их стороны новыми фломастерами, каждую сторону треугольника он раскрашивает одним из 12 цветов. Коля хочет, чтобы у него не оказалось одинаково раскр

Простая

Комбинаторика

ПВГ 2021, 7–8 классы, задача 3

В выражении 012345678*9 вместо «звездочек» можно ставить знаки «+» или «-». Сколько различных положительных чисел можно получить таким образом?

Простая

Выражения и преобразования

Комбинаторика

ПВГ 2021, 7–8 классы, задача 1

Остров Рыцарей и Лжецов. Рыцари всегда говорят правду, лжецы — всегда лгут. Однажды путешественник пришел на перекресток и спросил, где находится город Рыцарей у 4 аборигенов — А, Б, В и Г. А ответил — Идите на север, там город Рыцарей Б ответил — Нет, город Рыцарей на юге В сказал — не верьте, А и

Простая

Комбинаторика

ПВГ 2022, 7–9 классы, задача 5 (7–8), задача 3 (9)

Коля разобрал часы со стрелками и неправильно их собрал: перепутал часовую стрелку с минутной, кроме того, они начали идти в обратную сторону. Коля запустил часы в полдень, выставив точное время. Сколько раз за период с 12{:}01 до 23{:}59 такие часы покажут правильное время?

Простая

Комбинаторика