Задача 5.
Несколько древних русских богатырей (в том числе и Добрыня Никитич) устроили турнир по армрестлингу. Никакие два богатыря, сразившись друг с другом, повторно между собой не сражаются. Известно, что каждый богатырь сразился хотя бы с одним богатырём. Всего было проведено семь матчей. Богатырь соревновался с Добрыней Никитичем тогда и только тогда, когда соревновался с чётным числом соперников.
Сколько богатырей могло принять участие в турнире?
Ответ на Задачу 5.
Ответ: 5, 7, 9, 11, 13.
Решение:
Пусть было Б богатырей помимо Добрыни Никитича, причём ровно Д из них сражались с Добрыней. Тогда, подсчитав удвоенное количество матчей (сложив количества матчей, в которых участвовал каждый из богатырей), получим уравнение:
a1 + a2 + ... + aД + b1 + b2 + ... + bБ−Д + Д = 14
в котором ai и bj — количества матчей, в которых участвовали соответствующие богатыри. Взяв остаток при делении обеих частей равенства на 2, получим:
(Б − Д) + Д = 0 (по модулю 2)
Поэтому богатырей помимо Добрыни чётное количество. То есть общее количество богатырей нечётно.
- Если богатырей 3 или меньше, то матчей не более 6. Значит, богатырей хотя бы 5.
- Если богатырей 15 или больше, то матчей не менее 8.
Все остальные варианты подходят: для каждого из них можно привести соответствующий пример.
