Ссылки по теме:
Подборка статей в журнале "Квант"
Подтемы:
Подборка статей в журнале "Квант"
Подтемы:
-
Теория игр
(278 задач)
Взвешивания
(154 задачи)
Теория алгоритмов (прочее)
(268 задач)
Кооперативные алгоритмы
(29 задач)
Переправы
(1 задача)
Фильтр
Выбрана 1 задача
Версия для печати
Убрать все задачи
В доме из $2^n$ комнат сделали евроремонт. При этом выключатели света оказались перепутанными, так что при включении выключателя в одной комнате загорается лампочка, вообще говоря, в какой-то другой комнате. Чтобы узнать, какой выключатель к какой комнате подсоединён, прораб посылает несколько людей в какие-то комнаты, чтобы те, одновременно включив там выключатели, вернулись и сообщили ему, горела лампочка в их комнате или нет.
а) Докажите, что за $2n$ таких посылок прораб может установить соответствие между выключателями и комнатами.
б) А может ли он обойтись $2n-1$ такими посылками?
Решение
Убрать все задачи
В доме из $2^n$ комнат сделали евроремонт. При этом выключатели света оказались перепутанными, так что при включении выключателя в одной комнате загорается лампочка, вообще говоря, в какой-то другой комнате. Чтобы узнать, какой выключатель к какой комнате подсоединён, прораб посылает несколько людей в какие-то комнаты, чтобы те, одновременно включив там выключатели, вернулись и сообщили ему, горела лампочка в их комнате или нет.
а) Докажите, что за $2n$ таких посылок прораб может установить соответствие между выключателями и комнатами.
б) А может ли он обойтись $2n-1$ такими посылками?
Решение
Задачи
Страница: << 104 105 106 107 108 109 110 >> [Всего задач: 737]
В доме из $2^n$ комнат сделали евроремонт. При этом выключатели света оказались перепутанными, так что при включении выключателя в одной комнате загорается лампочка, вообще говоря, в какой-то другой комнате. Чтобы узнать, какой выключатель к какой комнате подсоединён, прораб посылает несколько людей в какие-то комнаты, чтобы те, одновременно включив там выключатели, вернулись и сообщили ему, горела лампочка в их комнате или нет.
а) Докажите, что за $2n$ таких посылок прораб может установить соответствие между выключателями и комнатами.
б) А может ли он обойтись $2n-1$ такими посылками?
Глеб задумал натуральные числа $N$ и $a$, $a < N$.
Число $a$ он написал на доске.
Затем он начал выполнять следующую операцию: делить $N$ с остатком на последнее выписанное на доску число, а полученный остаток от деления также записывать на доску. Когда на доске появилось число $0$, он остановился. Мог ли Глеб изначально выбрать
такие $N$ и $a$, чтобы сумма выписанных чисел была больше $100 N$?
На доске написано несколько чисел. Разрешается стереть любые два числа $a$ и $b$, а затем вместо одного из них написать число $\frac{a+b}{4}$. Какое наименьшее число может остаться на доске после 2018 таких операций, если изначально на ней написано 2019 единиц?
На острове живут хамелеоны пяти цветов. Когда один хамелеон кусает другого, цвет укушенного хамелеона меняется по некоторому правилу, причём новый цвет зависит только от цвета укусившего и цвета укушенного. Известно, что $2023$ красных хамелеона могут договориться о последовательности укусов, после которой все они станут синими. При каком наименьшем $k$ можно гарантировать, что $k$ красных хамелеонов смогут договориться так, чтобы стать синими?
Двое играют в «крестики–нолики» на бесконечном листе клетчатой бумаги. Начинающий ставит крестик в любую клетку. Каждым следующим своим ходом он должен ставить крестик в свободную клетку, соседнюю с одной из клеток, где уже стоит крестик; соседней с данной клеткой считаем любую, имеющую с ней общую сторону или общую вершину. Второй играющий каждым своим ходом может ставить сразу три нолика в любые три свободные клетки (не обязательно рядом друг с другом или с ранее поставленными ноликами). На рисунке изображена одна из позиций, которые могут возникнуть после третьего хода. Докажите, что как бы ни играл первый игрок, второй может его «запереть»: добиться того, чтобы первому было некуда поставить крестик. Исследуйте аналогичные игры, в которых второму разрешено за один ход ставить не три, а два или даже только один нолик. Каков здесь будет результат при правильной игре партнёров: удастся ли ноликам «запереть» крестики (и можно ли оценить сверху число ходов, которые могут «продержаться» крестики) или же крестики могут играть бесконечно долго?
Страница: << 104 105 106 107 108 109 110 >> [Всего задач: 737]
Задача 66489 |
|
|
а) Докажите, что за $2n$ таких посылок прораб может установить соответствие между выключателями и комнатами.
б) А может ли он обойтись $2n-1$ такими посылками?
|
|
|
Решение |
Задача 66561 |
|
|
|
|
Решение |
Задача 66617 |
|
|
|
|
|
Решение |
Задача 67194 |
|
|
Например, правила могут быть такими: если красный хамелеон кусает зелёного, укушенный меняет цвет на синий; если зелёный кусает красного, укушенный остаётся красным, то есть «меняет цвет на красный»; если красный хамелеон кусает красного, укушенный меняет цвет на жёлтый, и так далее. (Конкретные правила смены цветов могут быть устроены иначе.)
|
|
|
Решение |
Задача 73626 |
|
|
Попробуйте изучить другие варианты этой игры: когда соседними с данной считаем только клетки, имеющие с ней общую сторону; когда плоскость разбита не на квадраты, а на правильные шестиугольники; когда первому разрешено ставить сразу
|
|
|
Решение |
Страница: << 104 105 106 107 108 109 110 >> [Всего задач: 737]
