Состоятельный Крот подсчитал, что своими запасами зерна он может целиком заполнить либо 20 больших мешков зерна, либо 32 маленьких мешка. На месяц зимовки ему необходимо 7 больших мешков зерна. Крот может обменять у других кротов 2 больших мешка на 3 маленьких. Сможет ли Крот перезимовать три месяца или ему нужны дополнительные запасы?

   Решение

Темы:    [ Турниры и турнирные таблицы ] [ Теория графов (прочее) ] [ Четность и нечетность ]

Сложность: 3 Классы: 8,9,10

Прислать комментарий

Условие

20 футбольных команд проводят первенство. В первый день все команды сыграли по одной игре. Во второй также все команды сыграли по одной игре.
Докажите, что после второго дня можно указать такие 10 команд, что никакие две из них не играли друг с другом.

Решение

Рассмотрим граф, вершины которого соответствуют командам, а рёбра соединяют команды, сыгравшие между собой в первых двух турах. Все вершины имеют степень 2. Следовательно, граф разбивается на циклы. Каждый цикл состоит из чётного числа вершин, поскольку рёбра, соответствующие играм первого и второго дня чередуются. Из каждого цикла возьмём половину вершин – через одну. Это и будут 10 не игравших друг с другом команд.

Замечания

1. 7-8 кл. – 6 баллов, 9-10 кл. – 4 балла.

2. Общий случай (который практически не отличается от разобранного) см. в задаче 64514.

Источники и прецеденты использования