Игра на выбывание

Изображение пользователя Gregory Frenklach.

Ещё одна задача...
Она несложная и её легко можно решить с помощью неполной математической индукции, но ответа на вопрос "Почему?" решение этим методом не даст. Поэтому, после того, как решение будет найдено (в чём я не сомневаюсь) мне хотелось бы получить ответ на этот ворос.

А теперь задача...
Две тысячи команд играют между собой попарно по принципу "Проигравший выбывает". В том случае, когда остаётся нечётное число команд - бросают жребий, и та команда, которой повезло просто переходит на следующую стадию без игры. И так до тех пор, пока не будет победителя.

Например, десять команд играют попарно. Остаётся пять. Бросают жребий. Команда, которой повезло переходит на следующую стадию. Из четырёх команд остаётся две. Вместе с "везунчиками" остаётся три команды. Снова бросают жребий, и снова команда, которой повезло на этот раз переходит на следующую стадию без игры. Из двух команд остаётся одна, которая и играет финальный матч с той командой, которой повезло во второй жеребьёвке.

Сколько всего матчей на выбывание проведут две тысячи команд? Это простая часть.
Объясните решение, ответив на вопос "Почему?" С целью утешить математика и он перестал плакать.:)

Форумы: 

Re: Игра на выбывание

Изображение пользователя Gregory Frenklach.

Ещё раз повторю, что на мой взгляд для этой задачи важнее не найти правильное решение, а скорее дать ему (найденному решению) объяснение.

Re: Игра на выбывание

Изображение пользователя Gregory Frenklach.

Уверен, что почти все определились с количеством матчей на выбывание, но столкнулись с проблемой это дело объяснить:)

Re: Игра на выбывание

В результате останется всего одна команда, остальные 1999 команд "вылетят" - в этом смысл игры  (можно трактовать как ИКР)).

Получается, что одна команда должна "выбить" все остальные. Вот и получаем, что количество матчей 1999, т.е. на 1 меньше, чем общее количество команд.

Re: Игра на выбывание

Изображение пользователя Gregory Frenklach.

Alex wrote:

Получается, что одна команда должна "выбить" все остальные. Вот и получаем, что количество матчей 1999, т.е. на 1 меньше, чем общее количество команд.

Почему 1999?
Т.е. 1999 - это правильный ответ на первый вопрос, вытекающий из неполной математической индукции:
1 - 0;
2 - 1;
3 - 2;
4 - 3;
5 - 4;
и т.д.
Количество игр К =  N - 1
И всё таки... почему?

Re: Игра на выбывание

Поясняю. Задачу можно переформулировать. Из 2000 команд надо тем или иным способом выбрать самую сильную. Это можно сделать, как написано у вас в условии, а можно другим способом, например, произвольно выбрать одну из команд и "сравнивать" с ней все остальные. Сколько тогда сравнений нужно произвести? Правильно, 1999! 

Это и есть ответ на вопрос "почему".

Из этого рассуждения видно, что при любом общем числе команд, число матчей будет на 1 меньше. Чудес не бывает, одну команду выбираем за эталон, а оставшиеся (n-1)  последовательно сравниваем с этим эталоном, значит, число сравнений будет (n-1).

Re: Игра на выбывание

Поясняю. Задачу можно переформулировать. Из 2000 команд надо тем или иным способом выбрать самую сильную. Это можно сделать, как написано у вас в условии, а можно другим способом, например, произвольно выбрать одну из команд и "сравнивать" с ней все остальные. Сколько тогда сравнений нужно произвести? Правильно, 1999! 

Это и есть ответ на вопрос "почему".

Из этого рассуждения видно, что при любом общем числе команд, число матчей будет на 1 меньше. Чудес не бывает, одну команду выбираем за эталон, а оставшиеся (n-1)  последовательно сравниваем с этим эталоном, значит, число сравнений будет (n-1).

Можно еще дать определение матча. Матч, это процедура удаления из дальнейшего сравнения одной команды.

Re: Игра на выбывание

Александр Кудрявцев wrote:

Можно еще дать определение матча. Матч, это процедура удаления из дальнейшего сравнения одной команды.

Так еще проще. Удаляются все, кроме одной, поэтому число матчей (n-1).

Re: Игра на выбывание

Изображение пользователя Gregory Frenklach.

Не проще, а правильно.
В каждом матче всегда проигрывает одна команда.
Поскольку в результате выигрывает только одна - проигравших 1999.
Следовательно и матчей 1999.
Таким образом можно даже не использовать неполную математическую индукцию, чтобы решить эту задачу.

Re: Игра на выбывание

Gregory Frenklach wrote:

Не проще, а правильно.

Спорить про очевидное не стану ;-)

Сложнось в задаче - опять хороший заряд инерции. Всё условие толкает на математическое описание предлагаемого варианта отбора команд, а этого и не требуется. Достаточно сформулировать ИКР процедуры отбора - "после отбора останется только одна команда". А дальше воображение само сделает свое дело.

 

Re: Игра на выбывание

Изображение пользователя Gregory Frenklach.

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

Subscribe to Comments for "Игра на выбывание"