Задачи на логику

[Тощий ударник]

Условие: 1000 игроков, турнир проходит по олимпийской системе, то есть проигравший выбывает.

Сколько матчей нужно сыграть, чтобы выявить победителя?

[Гарпун]

необходимо провести 999 матчей))

[Велизарий]

Сообщение от Тощий ударник
Для просмотра ссылок или изображений, в данном разделе у вас должно быть 1 сообщение(ий) или более. Сейчас у Вас 0 сообщение(ий).

Условие: 1000 игроков, турнир проходит по олимпийской системе, то есть проигравший выбывает.

Сколько матчей нужно сыграть, чтобы выявить победителя?

Эта задача хорошо представима на графах, вершины игроки, ребра сыгранные матчи, каждый матч соединяет двух игроков, проигравший выбывает, в конце остается один, получается ациклический связный граф, он же дерево со свойствами n вершин, n-1 ребер.
Можно по другому взглянуть на эту задачу, каждый матч это выбор пары и откидывание одного проигравшего, до тех пор пока не остается один, то есть нам нужно посчитать за сколько шагов мы таким образом уменьшим 1000 до 1, то есть 1000->999->998->…->1 , что очевидно тоже дает 999
Можно эту задачу немного варьировать и добавить доп условия (иногда такое даем в курсе дискретной математики/ комбинаторики), например сколько нужно матчей при условии, если игрок выбывает после двух поражений, так же сколько нужно матчей что бы определить ТОП5 при начальных условиях, плюс могут быть условия что число площадок ограничено и количество игр в день и кроче числа матчей найти минималье количество дней/раундов или ограничения первые сто не встречаются с последними ста пока есть другие игроки и т.д.
Еще вариация этой задачи (которую обычно программисты решают быстро) , сколько нужно провести матчей что бы полностью упорядочить всех игроков от сильнейшего к слабейшему, тоже самое при условии двух встреч.

[HANSOKU]

Зашел почитать про срач ватников с либерасней,нацистов, Ержанов и водку с колокольчиком, а тут на тебе первым пунктом(

[Тощий ударник]

Сообщение от Велизарий
Для просмотра ссылок или изображений, в данном разделе у вас должно быть 1 сообщение(ий) или более. Сейчас у Вас 0 сообщение(ий).

Эта задача хорошо представима на графах, вершины игроки, ребра сыгранные матчи, каждый матч соединяет двух игроков, проигравший выбывает, в конце остается один, получается ациклический связный граф, он же дерево со свойствами n вершин, n-1 ребер.
Можно по другому взглянуть на эту задачу, каждый матч это выбор пары и откидывание одного проигравшего, до тех пор пока не остается один, то есть нам нужно посчитать за сколько шагов мы таким образом уменьшим 1000 до 1, то есть 1000->999->998->…->1 , что очевидно тоже дает 999
Можно эту задачу немного варьировать и добавить доп условия (иногда такое даем в курсе дискретной математики/ комбинаторики), например сколько нужно матчей при условии, если игрок выбывает после двух поражений, так же сколько нужно матчей что бы определить ТОП5 при начальных условиях, плюс могут быть условия что число площадок ограничено и количество игр в день и кроче числа матчей найти минималье количество дней/раундов или ограничения первые сто не встречаются с последними ста пока есть другие игроки и т.д.
Еще вариация этой задачи (которую обычно программисты решают быстро) , сколько нужно провести матчей что бы полностью упорядочить всех игроков от сильнейшего к слабейшему, тоже самое при условии двух встреч.

На самом деле условия задачи не совсем корректное

Потому что на четвертой итерации уже будет 125 участников т.е. один участник останется без пары

[Велизарий]

Сообщение от Тощий ударник
Для просмотра ссылок или изображений, в данном разделе у вас должно быть 1 сообщение(ий) или более. Сейчас у Вас 0 сообщение(ий).

Потому что на четвертой итерации уже будет 125 участников т.е. один участник останется без пары

Это разве нам мешает определить количество матчей, один счасливчик пропустит раунд, автоматом проходя в следующий тур на выбывание? В некоторых задачах как например с условием двух проигрышей мы не получим точного числа, но получим оценки сверху и снизу (минимального и максимального), где то просто запутывающие условия, как например ограничение что первые сто не играют с игроками из последней из сотни, пока есть другие игроки и т.д.