Логические задачи : Шахматный турнир

	"Логические задачи" - это познавательно-развлекательный проект для непрокисших мозгов. Задачи на логику, нестандартное мышление. Не всегда самое очевидное решение - правильное. Но иногда всё оказывается проще, чем кажется на первый взгляд.
Задачи на логику и сообразительность
Главная \| О проекте \| Все задачи-1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C \| Добавить задачу

О сайте
Гостевая книга
ЧаВо

Пользователи
RSS

Поиск на сайте

запомнить меня

Задачи

Переливания и взвешивания

Теорвер, комбинаторика

Задания на наблюдательность

требуется помощь

Чисто поржать

Детские с подковыркой

Данетки

Текущие:

  Мой любимый грех (с)
  Математика в архитектуре
  Не сыпь мне соль на рану
  «Геометрическая»
  Высказывание Ломоносова
  Наверное, не про яблоки
  Комерция
  Везде градусы
  Вагончик тронется, вагончик тронется..
  Спасибо медикам и католикам))
  Специальная купюра
  Студенческая смекалка
  Эллипс vs Круг
  Современные технологии. Немецкий стандарт.
  Спортивная
  философская
  Про газету
  печатная монета
  Купюра евро
  Древние изобретения
  Биометрические паспорта
  Новый глава
  В далеком созвездии тау Кита... 8)))
  Огородное
  Средневековое строительство
  Жестокое наказание
  Их нравы - 4
  Европейский стандарт

Разгаданные недавно:

  этот модный тандыр
  Из Что-Где-Когда
  Может ли такое быть?
  Что изображено?
  Да на тебе пахать надо!

Справочная

Признаки делимости
Площади фигур

Реклама

Версия для смартфонов

задача: Шахматный турнир

Задачу прислал: Админ

В турнире по шахматам участвуют 20 человек. В процессе каждые два шахматиста должны сыграть ровно одну партию между ними. Через какое наименьшее число прошедших игр может оказаться так, что среди любых трёх игроков какие-то два уже сыграли между собой?


+ 0 -

Ответ

Решение задачи

Ваши ответы на задачу

ответов: 11

Gavroche 2014-06-26 00:15:54 пишет:

Если они все играли со всеми, кроме одного (по 18 партий), а один ни с кем не играл, то 19 человек играли по 18 партий, 19*18 = 162.

Вася Пупкин 2014-05-24 03:40:20 пишет:

Админ, да мне лень уже. Для четырех точек -- делаем две пары, вот и обслужили, двумя связями. Теперь по индукции для четных чисел(пример -- как из картинки для четверки получать картинку для тройки): если было у нас два полностью прошитых изолированных кластера равной мощности, красный и белый, добавим еще пару точек. Изолированными они быть не могут. Первый новичок не может быть соединен не со всеми красными и не со всеми белыми, как и раньше говорили -> с какими-то соединен со всеми -> с другими можно не соединять. Вторую точку, так же рассуждая, припишем ко второму цвету, поскольку к первому обойдется теперь дороже, он уже на единичку мощнее. Между собой новичков не соединяем. Вот и сделали плюшку на два большую. На самом деле в этой индукции тоже жульничество есть, но если не заметите -- сами виноваты, а мне все равно лень замазывать.

Вася Пупкин 2014-05-22 06:22:00 пишет:

К2, пес его, действительно не услеживаю я за Вашим ходом -- в смысле, идея понятна, а воплощение как-то не очень. По-хорошему надо б начать, скажем, с с разрыва одной связи, объявить(я перехожу на свой язык) один ее конец красным, другой белым, остальные вершины делаются серыми, и дальше доказывать, что всегда выгодней превращать серые в красные или белые. Или, может(и даже скорее), начинать с двух несоединенных пар, объявив одну красной, другую белой, и дальше тоже всю серятину отгонять туда-сюда. Но, во-первых, что найдутся две такие друг с другом не соединенные пары -- это отдельно доказывать надо, во-вторых, что-то я не вижу монотонного выигрыша на каждом шагу на таком пути. А эти самые два кластера -- ну да, похоже, локальный минимум(для проверки разорвем в одном связь -- чтобы ее компенсировать, придется из ее концов в соседний кластер протянуть энпополам связей, явно невыгодно), но это именно говорит о локальном минимуме, а что путь до него всегда монотонный, это никто не доказал. Короче, спасибо за теплые слова, с тырешилом поглядим, но по-хорошему надо б допилить.

Админ: не буду мешать :)

K2 2014-05-22 00:16:21 пишет:

Все со всеми это 190, 180 - это все со всеми_кроме_Одного. Потому что если ... мм.... Так - да - я ошибся, минимум меньше - будем продолжать подумать. Думаем: Если кто-то (Любой) НЕ Играл больше чем с одним противником (пытаемся улучшить "мой" варинат на 180) то эти двое (или больше) - Обязательно играли между собой... Ну так и посчитаем для двух: каждый с 17-ю = 170, остальные двое Допустим уже посчитаны, в любом случае Меньше 170 - уже не будет... Каждый с каждым Кроме троих = каждый с 16 = 160 - ну и уже очевидно что так мы Дойдём до "каждый с каждым кроме 10" = 90... (минимум) и уже Показано (Вами) как этого минимума достигнуть. Извращаемся и двигаем дальше: каждый с каждым кроме 11 = каждый с восемью, в том числе и из тех 11 - значит минимум 2 найдётся ни с "каждым" ни с "кем-то из 11" ну и те - между собой тоже... Путано наверное? НО... вошем имхо - смело (и заслуженно) ждите "тырешилу" :)

Вася Пупкин 2014-05-21 23:30:36 пишет:

К2 -- так сказал жеж, для одного -- прореженного, не со всеми связями. 180-то -- это Вы по максимуму считаете, все со всеми.

K2 2014-05-21 22:54:47 пишет:

эм... ну для "одного кластера" я посчитал, получилось 180, для двух - 90 - это меньше, что-то надо Ещё доказывать? (или я чего-то не видеть/не понимать...)

Вася Пупкин 2014-05-21 22:32:04 пишет:

К2, спасибо, но грю ж -- это не решение, дырки сплошные. Вернее, одна, но зато какая -- нужно дказать, что два изолированных полностью прошитых кластера выгоднее одного прореженного. Может быть, вертя картинку для шести, можно в этом убедиться, а заодно и путь док-ва нащупать, я не пробовал, в загоне, а сразу не придумывается.

K2 2014-05-21 12:31:37 пишет:

Блин, а красиво, и главное условия НЕ нарушает. Плюс за 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.

евгений 2014-04-05 22:39:41 пишет:

общее количество партий 20*19/2=190, количество партий для трех игроков 3*2/2=3, искомое число партий 190-3=187

K2 2014-04-05 19:13:01 пишет:

Ну давайте подумаем "на ходу"... в "момент-икс" мы берём Любого игрока, и ещё Любых двоих ,и "имеем" что он играл с Одним из них (как минимум) и (ловкость рук) со всеми 17-ю остальными тоже (иначе мы бы взяли того, "другого"). Итак... Мы имеем что Каждый сыграл с другими игроками по 18 партий, а это в целом == 20*18/2 = 180. Ответ - через 180 игр. (верно?)

Добавьте комментарий:

Обсуждаем

Задача Разрезанный треугольник:
http://lprobs.ru/img/yes.gif : [скрыто]
Гостевая книга:
не представился : Это было в 1913 году. Одиннадцатилетняя девочка, пансионерка Московской Ржевской гимназии очень прос...
Задача Гора.:
Xuzke : [скрыто]
Гостевая книга:
не представился : В школе все казалось правильным. Из математики следует физика, из физики следует химия, из химии сле...
R-2 : Ты решил: Ну, и наконец, то решение, которое тут видимо предполагается в идеале, я не буду говори...
Так, по старой памяти заглянул :) : R-2, условие неплохо бы конкретизировать. ;)) А то так вариантов может быть масса, хотя все обладают...
Задача 4 хода:
колд : [скрыто]
Задача Кот и мышка:
Дмитрий : [скрыто]
Задача Черная Жемчужина:
mskfirst : [скрыто]
Задача Квадратный торт:
не представился : [скрыто]
Задача Задача с ведрами: 9 и 4 = 6.:
ИносОйЧанбин : [скрыто]
Дкгк7 : [скрыто]
Задача Геометрическая 3:
не представился : [скрыто]
Алексей : [скрыто]
Гостевая книга:
R-2 : Дано: листочек бумаги и ручка. На листочке написаны три нуля. О О О Задача: «как из трёх нулей...

Реклама

© 2009-201x Логические задачи

Задачи на логику и сообразительность

Поиск на сайте

Задачи

Данетки

Справочная

Реклама

задача: Шахматный турнир

Ответ

Решение задачи

Ваши ответы на задачу

Обсуждаем

Реклама