"Логические задачи" - это познавательно-развлекательный проект для непрокисших мозгов. Задачи на логику, нестандартное мышление. Не всегда самое очевидное решение - правильное. Но иногда всё оказывается проще, чем кажется на первый взгляд.

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




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

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

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





запомнить меня
Зарегистрироваться


Задачи



Данетки


Текущие:

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

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

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


Справочная



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


Реклама






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

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


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



Ответ





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





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


ответов: 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 игр. (верно?)

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

Комментарий:

Пожалуйста, введите символы с картинки:
(подтверждение не требуется для зарегистрированных пользователей)



 





Обсуждаем

  Задача Квадрат 4x4:
R-2 : [скрыто]
KoKos : [скрыто]
Задача Дефект масс:
R-2 : [скрыто]
Задача Квадрат 4x4:
R-2 : [скрыто]
Задача Дефект масс:
ivana2000 : [скрыто]
Задача Квадрат 4x4:
ivana2000 : [скрыто]
Задача Два момента:
Vladius : [скрыто]
Задача Расставить знаки математических операций:
Вика : [скрыто]
Задача Вопросительное предложение:
Vladius : [скрыто]
Задача Задача про рабочих:
Vladius : [скрыто]
Vladius : [скрыто]
Задача 1 рубль = 1 копейке:
Vladius : [скрыто]
Задача Вот в полу открылся люк ...:
bobo : [решил задачу]
Задача Квадрат 4x4:
не представился : [скрыто]
Задача Дефект масс:
R-2 : [скрыто]



Реклама



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