Задача 65145

Темы:    [ Турниры и турнирные таблицы ] [ Теория алгоритмов ] [ Упорядочивание по возрастанию (убыванию) ]

Сложность: 4- Классы: 6,7

Условие

Автор: Фольклор

Среди 25 жирафов, каждые два из которых различного роста, проводится конкурс "Кто выше?". За один раз на сцену выходят пять жирафов, а жюри справедливо (согласно росту) присуждает им места с первого по пятое. Каким образом надо организовать выходы жирафов, чтобы после семи выходов определить первого, второго и третьего призёров конкурса?

Решение

  Разобьём всех жирафов на пять групп по пять жирафов в каждой. Сравним жирафов внутри каждой группы. На это потребуется 5 выходов. Шестым выходом сравним самых высоких жирафов каждой группы. После этого обозначим группы буквами А, Б, В, Г, Д в порядке убывания роста самых высоких в группе, а жирафов внутри группы обозначим индексами 1, 2, 3, 4, 5 также в порядке убывания их роста. Составим таблицу роста жирафов.

  Заметим, что жирафы из групп Г и Д не могут быть призёрами, так как рост каждого из них меньше, чем рост жирафов А₁, Б₁ и В₁. Также призерами не могут быть жирафы А₄, Б₄, В₄, А₅, Б₅, В₅. Кроме того, так как  А₁ > Б₁ > В₁ > В₂ > В₃,  то призёрами не могут быть жирафы В₂ и В₃. А так как
А₁ > Б₁ > Б₂ > Б₃,  то и Б₃ – не призер. Таким образом, призёрами могут оказаться только шесть жирафов: А₁, А₂, А₃, Б₁, Б₂, В₁. Но уже известно, что жираф, обозначенный А₁, – самый высокий. Седьмым выходом мы сравним 5 остальных жирафов и тем самым выявим жирафов, занявших 2 и 3 место.

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

олимпиада
Название	Московская устная олимпиада для 6-7 классов
год/номер
Номер	13 (2015 год)
Дата	2015-03-9
класс
Класс	7 класс
задача
Номер	7.6