В турнире по шахматам участвуют 20 человек. В процессе каждые два шахматиста должны сыграть ровно одну партию между ними. Через какое наименьшее число прошедших игр может оказаться так, что среди любых трёх игроков какие-то два уже сыграли между собой?
Если они все играли со всеми, кроме одного (по 18 партий), а один ни с кем не играл, то 19 человек играли по 18 партий, 19*18 = 162.
Вася Пупкин 2014-05-24 03:40:20 пишет:
Админ, да мне лень уже. Для четырех точек -- делаем две пары, вот и обслужили, двумя связями. Теперь по индукции для четных чисел(пример -- как из картинки для четверки получать картинку для тройки): если было у нас два полностью прошитых изолированных кластера равной мощности, красный и белый, добавим еще пару точек. Изолированными они быть не могут. Первый новичок не может быть соединен не со всеми красными и не со всеми белыми, как и раньше говорили -> с какими-то соединен со всеми -> с другими можно не соединять. Вторую точку, так же рассуждая, припишем ко второму цвету, поскольку к первому обойдется теперь дороже, он уже на единичку мощнее. Между собой новичков не соединяем. Вот и сделали плюшку на два большую. На самом деле в этой индукции тоже жульничество есть, но если не заметите -- сами виноваты, а мне все равно лень замазывать.
Вася Пупкин 2014-05-22 06:22:00 пишет:
К2, пес его, действительно не услеживаю я за Вашим ходом -- в смысле, идея понятна, а воплощение как-то не очень. По-хорошему надо б начать, скажем, с с разрыва одной связи, объявить(я перехожу на свой язык) один ее конец красным, другой белым, остальные вершины делаются серыми, и дальше доказывать, что всегда выгодней превращать серые в красные или белые. Или, может(и даже скорее), начинать с двух несоединенных пар, объявив одну красной, другую белой, и дальше тоже всю серятину отгонять туда-сюда. Но, во-первых, что найдутся две такие друг с другом не соединенные пары -- это отдельно доказывать надо, во-вторых, что-то я не вижу монотонного выигрыша на каждом шагу на таком пути. А эти самые два кластера -- ну да, похоже, локальный минимум(для проверки разорвем в одном связь -- чтобы ее компенсировать, придется из ее концов в соседний кластер протянуть энпополам связей, явно невыгодно), но это именно говорит о локальном минимуме, а что путь до него всегда монотонный, это никто не доказал. Короче, спасибо за теплые слова, с тырешилом поглядим, но по-хорошему надо б допилить.
Все со всеми это 190, 180 - это все со всеми_кроме_Одного. Потому что если ... мм.... Так - да - я ошибся, минимум меньше - будем продолжать подумать. Думаем: Если кто-то (Любой) НЕ Играл больше чем с одним противником (пытаемся улучшить "мой" варинат на 180) то эти двое (или больше) - Обязательно играли между собой... Ну так и посчитаем для двух: каждый с 17-ю = 170, остальные двое Допустим уже посчитаны, в любом случае Меньше 170 - уже не будет... Каждый с каждым Кроме троих = каждый с 16 = 160 - ну и уже очевидно что так мы Дойдём до "каждый с каждым кроме 10" = 90... (минимум) и уже Показано (Вами) как этого минимума достигнуть. Извращаемся и двигаем дальше: каждый с каждым кроме 11 = каждый с восемью, в том числе и из тех 11 - значит минимум 2 найдётся ни с "каждым" ни с "кем-то из 11" ну и те - между собой тоже... Путано наверное? НО... вошем имхо - смело (и заслуженно) ждите "тырешилу" :)
Вася Пупкин 2014-05-21 23:30:36 пишет:
К2 -- так сказал жеж, для одного -- прореженного, не со всеми связями. 180-то -- это Вы по максимуму считаете, все со всеми.
эм... ну для "одного кластера" я посчитал, получилось 180, для двух - 90 - это меньше, что-то надо Ещё доказывать? (или я чего-то не видеть/не понимать...)
Вася Пупкин 2014-05-21 22:32:04 пишет:
К2, спасибо, но грю ж -- это не решение, дырки сплошные. Вернее, одна, но зато какая -- нужно дказать, что два изолированных полностью прошитых кластера выгоднее одного прореженного. Может быть, вертя картинку для шести, можно в этом убедиться, а заодно и путь док-ва нащупать, я не пробовал, в загоне, а сразу не придумывается.
Блин, а красиво, и главное условия НЕ нарушает. Плюс за 90.
Вася Пупкин 2014-05-21 09:01:27 пишет:
Ну, это не очень строгое решение, но строже у меня не получается. Пусть для начала все сыграют со всеми. Это явно избыток. Начнем убирать лишние игры. Раскрасим наших игроков в красный и белый, и разорвем все красно-белые связи. Убавили число игр на ЭнКрасныхНаЭнбелых. Что имеем теперь? Любой красно-белый треугольник должен быть счастлив -> все красные по-прежнему должны сыграть каждый с каждым. Ну, и все белые тоже. Третьего изолированного полностью кластера ввести не получится -- тройка трех цевтов будет несчастна. Теперь поглядим, а стоило ли вообще делать два кластера? Рассмотрим серую вершину, связанную как с красными, так и с белыми -- такой "мостик" между двумя кластерами. Если она связана не со всеми красными, и не со всеми белыми -- мы всегда сможем построить несчатливый треугольник -> придется ее связать со всеми. Но если уж мы ее связали со всеми красными, так зачем нам вообще сохранять ее связи с белыми? Нафиг их все, и серая ушла к красным. Вот это и есть нестрогое место в разборках, мы как бы доказали, что два полностью сыгранных внутри кластера лучше, чем их соединение, но на самом деле это все-таки не доказательство, а соображения. Ну ладно, примем все же за правду. Понятно тогда, что число игр минимизируется при равной мощности обоих кластеров(это строго, m(m-1) + n(n-1) при m+n = K минимизируется при m=n=K/2). Проверим на шести игроках -- две тройки играют по три игры, итого 6 из 6*5/2 -- пятнадцати возможных. Вроде бы прилично. Ну, и для двадцати тогда разбиваем их на две десятки, внутри каждой проводим все возможные игры -- по 10*9/2=45, и всего, значит, 90 игр. Ну, тоже вроде бы ничего, вместо полных 20*19/2=190.
Ну давайте подумаем "на ходу"... в "момент-икс" мы берём Любого игрока, и ещё Любых двоих ,и "имеем" что он играл с Одним из них (как минимум) и (ловкость рук) со всеми 17-ю остальными тоже (иначе мы бы взяли того, "другого"). Итак... Мы имеем что Каждый сыграл с другими игроками по 18 партий, а это в целом == 20*18/2 = 180. Ответ - через 180 игр. (верно?)