Ещё одна задача...
Она несложная и её легко можно решить с помощью неполной математической индукции, но ответа на вопрос "Почему?" решение этим методом не даст. Поэтому, после того, как решение будет найдено (в чём я не сомневаюсь) мне хотелось бы получить ответ на этот ворос.
А теперь задача...
Две тысячи команд играют между собой попарно по принципу "Проигравший выбывает". В том случае, когда остаётся нечётное число команд - бросают жребий, и та команда, которой повезло просто переходит на следующую стадию без игры. И так до тех пор, пока не будет победителя.
Например, десять команд играют попарно. Остаётся пять. Бросают жребий. Команда, которой повезло переходит на следующую стадию. Из четырёх команд остаётся две. Вместе с "везунчиками" остаётся три команды. Снова бросают жребий, и снова команда, которой повезло на этот раз переходит на следующую стадию без игры. Из двух команд остаётся одна, которая и играет финальный матч с той командой, которой повезло во второй жеребьёвке.
Сколько всего матчей на выбывание проведут две тысячи команд? Это простая часть.
Объясните решение, ответив на вопос "Почему?" С целью утешить математика и он перестал плакать.:)
Re: Игра на выбывание
Ещё раз повторю, что на мой взгляд для этой задачи важнее не найти правильное решение, а скорее дать ему (найденному решению) объяснение.
Re: Игра на выбывание
Уверен, что почти все определились с количеством матчей на выбывание, но столкнулись с проблемой это дело объяснить:)
Re: Игра на выбывание
В результате останется всего одна команда, остальные 1999 команд "вылетят" - в этом смысл игры (можно трактовать как ИКР)).
Получается, что одна команда должна "выбить" все остальные. Вот и получаем, что количество матчей 1999, т.е. на 1 меньше, чем общее количество команд.
Re: Игра на выбывание
Почему 1999?
Т.е. 1999 - это правильный ответ на первый вопрос, вытекающий из неполной математической индукции:
1 - 0;
2 - 1;
3 - 2;
4 - 3;
5 - 4;
и т.д.
Количество игр К = N - 1
И всё таки... почему?
Re: Игра на выбывание
Поясняю. Задачу можно переформулировать. Из 2000 команд надо тем или иным способом выбрать самую сильную. Это можно сделать, как написано у вас в условии, а можно другим способом, например, произвольно выбрать одну из команд и "сравнивать" с ней все остальные. Сколько тогда сравнений нужно произвести? Правильно, 1999!
Это и есть ответ на вопрос "почему".
Из этого рассуждения видно, что при любом общем числе команд, число матчей будет на 1 меньше. Чудес не бывает, одну команду выбираем за эталон, а оставшиеся (n-1) последовательно сравниваем с этим эталоном, значит, число сравнений будет (n-1).
Re: Игра на выбывание
Можно еще дать определение матча. Матч, это процедура удаления из дальнейшего сравнения одной команды.
Re: Игра на выбывание
Так еще проще. Удаляются все, кроме одной, поэтому число матчей (n-1).
Re: Игра на выбывание
Не проще, а правильно.
В каждом матче всегда проигрывает одна команда.
Поскольку в результате выигрывает только одна - проигравших 1999.
Следовательно и матчей 1999.
Таким образом можно даже не использовать неполную математическую индукцию, чтобы решить эту задачу.
Re: Игра на выбывание
Спорить про очевидное не стану ;-)
Сложнось в задаче - опять хороший заряд инерции. Всё условие толкает на математическое описание предлагаемого варианта отбора команд, а этого и не требуется. Достаточно сформулировать ИКР процедуры отбора - "после отбора останется только одна команда". А дальше воображение само сделает свое дело.
Re: Игра на выбывание
Главная сложность в том, что надо связать каждую игру с проигрышем команды и, следовательно, количество игр с количеством проигравших команд.