задачка

как предмет называется?

как предмет называется?

а какая разница ?

Определите сколько игр будет сыграно в первом раунде

В первом раунде 500 игр. Т.к каждый сыграет всего с одним оппонентом.

теория графов

1. 1000/2 = кол-во одновременных партий, умножить на 10 - 5000 партий в 1 раунде.
второй вопрос не понял.

вот я тоже не понял :) и еще непонятно к чему там лотерея и «неожиданно большое количество».

2) Организаторы стараются сократить время первого раунда. К счастью, очень большое количество игр могут быть сыграны параллельно, учитывая, что каждый игрок может учавствовать макс в одной игре на каждом этапе раунда (всего 10 игр). Подразумевается, что все игры имеют одинаковое время.

максимальное паросочетание на графе, определенным лотереей.

Граф строим так: Игроки - узлы графа, Если между игроками, которые должны между собой играть по результатам в лотереи, то между узлами ребро

Определите сколько игр будет сыграно в первом раунде

В первом раунде 500 игр. Т.к каждый сыграет всего с одним оппонентом.

Это надо еще доказать.

максимальное паросочетание на графе, определенным лотереей.

надо только доказать (если это действительно так), что в случае с 10-ругулярным графом (а у нас именно такой получается) выполняется теорема Тутта.

Тогда существует идеальное паросочетание => 500 игр может быть сыграно.

да это понятно, и, мол, это число покажет сколько групп параллельных игр нужно сыграть минимум.

я так и не понял, в чем задача, если мы имеем 10 игр и игроки могут учавствовать параллельно.. ну и будет 10 * время игры - минимум время раунда, не?

у нас 1000 игроков и 10 игр на каждого, там 5000 игр получается.

ну или 10 регулярный граф с 500 точками, суммируем градусы, тоже 5000.

или как ты хотел его моделировать?

я так и не понял, в чем задача, если мы имеем 10 игр и игроки могут учавствовать параллельно.. ну и будет 10 * время игры - минимум время раунда, не?

оценка сверху 11*время игры. Так как раз граф 10-регулярный, то его можно с уверенностью раскрасить в 11 цветов.

пишут, по определению vertex-chromatic number (минимальное число цветов) меньше либо равно точке с макс градусом, т.е. <= 10.

пишут, по определению vertex-chromatic number (минимальное число цветов) меньше либо равно точке с макс градусом, т.е. <= 10.

вот тебе контрпример - K₄ (полный граф о четырех вершинах), раз не веришь :)

У каждой точки градус 3, но хроматическое число этого графа очевидно 4.

да это понятно, и, мол, это число покажет сколько групп параллельных игр нужно сыграть минимум.

но вообще я бы через паросочетание на 10-регулярном графе попробовал.

я дико извиняюсь, ест-но:

χ( G ) ≤ ∆( G ) + 1.

блин, бошка уже не работает..

округли количество игроков до 1024 и реши уже задачку устно :(

перепутал я :)

мы же считаем игры (т.е. соединения), а не игроков, поэтому ищем edge-chromatic число, а оно 10. Его можно же представить как bipartite граф, а в нем это число всегда равно макс градусу.

пределите сколько игр будет сыграно в первом раунде.

5000. Потому, что каждый сыграет 10 игр, но каждая игра содержит двух участников.

Организаторы стараются сократить время первого раунда.

Зря стараются. Время первого раунда определяется по времени самого медленного игрока, но поскольку количество и время игра одинаково, а надо сыграть 10 партий последовательно, время составит - 10(игр) * время_одной_игры.

Время в этой задаче не оптимизируется.

1) Определите сколько игр будет сыграно в первом раунде.

СКОЛЬКО ДОСОК СТОЛЬКО И ИГР

Не знаю, как там в теории графов, но любой шахматный судья 1000 человек по швейцарке разрулит с завязанными глазами, так что 500 игр в каждом туре :D