Тема Игры

Игры вслепую

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела игры

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

Ошибка.
Попробуйте повторить позже

Задача 1#76066

На бесконечном шоссе находятся полицейская машина (ездит со скоростью до $100$ км/ч) и вор на угнанном мотоцикле (ездит со скоростью до $80$ км/ч). Полицейские не знают, в каком месте шоссе находится вор. Как им действовать, чтобы наверняка догнать вора? (Вор не может съехать с шоссе или спрятаться).

Показать доказательство

Отправим мысленно в обе стороны дороги двух помощников, едущих со скоростью большей, чем скорость вора, но меньшей, чем скорость полицейской машины. Пусть полицейская машина догонит сначала первого помощника, потом — второго, потом — снова первого, потом — снова второго и т. д. Ясно, что когда-нибудь один из помощников перегонит угонщика, а значит, и полицейский когда-то догонит угонщика.

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#76067

Дима загадал целое число, а Петя пытается его угадать. На каждом шаге он выбирает целое число $N$ и задает Диме вопрос: «Верно ли, что загаданное число равно $N$ ?».

(a) Если Петя не угадал, то Дима обязан перезагадать свое число, увеличив его на $N.$

(b) Если Петя не угадал, то Дима сообщает Пете, больше или меньше загаданное число, чем $N,$ а затем обязан перезагадать свое число, либо увеличив его на $N,$ либо уменьшив его на $N$ (Петя не знает, какой из этих двух вариантов выберет Дима).

Может ли Петя действовать так, чтобы через несколько шагов гарантированно угадать текущее загаданное число?

Показать ответ и решение

(a) Пусть Дима загадал значение — $x$ , а Петя задаст вопросы следующего вида: «Верно ли, что загаданное число равно $n+ Sn$ ?», где $n$ — какое-то число, $Sn$ — сумма чисел из предыдущих вопросов. По условию Дима увеличивал свое значение на число из вопроса Пети, если Петя не угадал, поэтому Петин вопрос вида: «Верно ли, что загаданное число равно $n+ Sn$ ?» — по смыслу эквивалентен вопросу: « $Верно ли, что x= n?$ »

Переберем значения $n$ в следующем порядке: $0,1,−1,2,− 2,3,−3,....$

То есть первые несколько вопросов выглядят так:
«Верно ли, что загаданное число равно $0$ ?»
«Верно ли, что загаданное число равно $1+ 0$ ?»
«Верно ли, что загаданное число равно $− 1+ ((1+ 0)+0)$ ?»
«Верно ли, что загаданное число равно $2+ ((−1 +1+ 0)+(1+ 0)+0)$ ?»
$...$

Тогда Петя рано или поздно выберет значение $n$ равное изначально загаданному $x$ и, спросив «Верно ли, что загаданное число равно $x +Sn?$ » угадает текущее число.

(b) Пусть Петя сначала задаст вопрос, который не изменит числа: «Верно ли, что загаданное число равно $0$ ?» Либо он угадает, либо сможет узнать знак загаданного числа. Без ограничения общности далее считаем, что загаданное число положительное, иначе задаем следующие вопросы с противоположным знаком. (И также будем считать - что если Петя угадал число в какой-то момент, то он автоматически выиграл.)

Теперь пусть Петя задает вопросы вида:
«Верно ли, что загаданное число равно $2− 1$ ?»
«Верно ли, что загаданное число равно $2 2 − 1$ ?»
«Верно ли, что загаданное число равно $3 2 − 1$ ?»
«Верно ли, что загаданное число равно $4 2 − 1$ ?»
…
«Верно ли, что загаданное число равно $k 2 − 1$ ?»

Если Дима ответит, что загаданное число в данный момент $k N > 2 − 1,$ то после вычитания или прибавления к $N$ числа $k 2 − 1$ новое число также будет строго положительным.

Петя будет задавать вопросы до тех пор, пока впервые не получит ответ, что в данный момент загаданное число $N < 2k− 1.$ Заметим, что такой момент наступит, потому что $2k− 1= (2− 1)+ (22− 1)+...(2k−1− 1)+ k,$ то есть как минимум на шаг с номером $k0,$ где $k0$ — изначальное загаданное число, Дима ответит отрицательно на этот вопрос, так как каждый раз число увеличивалось максимум — на сумму чисел во всех предыдущих вопросах.

Перед последним вопросом загаданное число будет лежать в границах $0< N <2k− 1,$ то есть после изменения на $2k− 1$ оно не превосходит по модулю числа $2k+1− 2.$

Пусть Петя задаст вопрос: «Верно ли, что загаданное число равно $0$ ?» И тем самым поймет знак загаданного числа в данный момент.

То есть теперь нам известны знак и границы, в которых лежит текущее загаданное число.

После этого, пока не угадаем число, будем задавать вопросы:
«Верно ли, что загаданное число равно $MAXi$ ?», где $MAXi$ — текущее максимальное по модулю значение для загаданного числа (может быть как положительным, так и отрицательным числом)
«Верно ли, что загаданное число равно $0$ ?»

После первого вопроса (про $MAXi$ ) мы либо угадали число, либо "потенциальные числа"теперь изменили знак (то есть Дима вычел $MAXi$ из загаданного), либо сохранили знак (Дима прибавил $MAXi$ к загаданному числу). Следующий вопрос определяет прибавили или вычли $MAXi,$ и тогда мы снова знаем границы для загаданного числа, но теперь "потенциальных значений"на одно меньше. Значит, такими вопросами число рано или поздно будет угадано.

Ответ:

(a) Да

(b) Да

Ошибка.
Попробуйте повторить позже

Задача 3#76068

Иван Царевич хочет выйти из круглой комнаты с $n$ дверями, $n− 1$ из которых заперты на ключ. За одну попытку он может проверить любые три двери, расположенные подряд, и если одна из них не заперта, то он в неё выйдет. После каждой попытки Баба-Яга запирает дверь, которая была открыта, и отпирает одну из соседних дверей. Какую именно, Иван Царевич не знает. Как ему действовать, чтобы наверняка выйти из комнаты?

Показать доказательство

Занумеруем двери числами $1,2,3,...,n,$ например, по часовой стрелке. Пусть он будет рассматривать двери с номерами $2k − 1,2k,2k+ 1$ для $k ∈{1,2,3,...}.$

Первой попыткой Иван Царевич проверяет двери $1,2$ и $3.$ Если после этого он не сумел выйти из комнаты, то двери $1,2$ и $3$ были заперты. Дверь $2$ останется запертой даже после того, как Баба-Яга запрёт открытую и отопрёт одну из соседних.

Второй попыткой Иван Царевич проверяет двери $3,4$ и $5.$ Если после этого он не сумел выйти из комнаты, то двери $3,4,5$ были заперты, а с учетом того, что $2$ тоже заперта, можно утверждать, что двери $3$ и $4$ останутся запертыми и после действий Бабы-Яги.

Пусть на $k$ шаге он открывает двери с номерами $2k +1,2k+ 2,2k+ 3.$ И пусть ему известно, что $k− 1$ дверей с номерами $(k+ 1),(k+2),...,2k$ точно были закрыты перед его ходом. Тогда после проверки дверей Иваном Царевичем и действий Бабы Яги мы будем знать, что $k$ дверей с номерами $(k+ 2),(k +3),...,(2k+ 2)$ точно заперты, потому что перед ходом Бабы Яги были заперты соседние к ним двери.

Тогда не более, чем за $n$ шагов Иван будет знать все запертые двери и сможет выбрать открытую.

Ошибка.
Попробуйте повторить позже

Задача 4#76069

Состав из конечного числа одинаковых вагонов замкнут в кольцо. Вас с куском мела поместили в один из вагонов. Вы можете свободно ходить по составу и делать любые пометки на стенах вагонов. В любой момент вы можете сказать, сколько вагонов в поезде. Если угадаете, то Вас выпустят. Учтите, однако, что до Вас уже многие пытались пройти это испытание. Возможно, они оставляли на стенах какие-то пометки. Опишите алгоритм, который точно поможет спастись.

Показать доказательство

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

Ошибка.
Попробуйте повторить позже

Задача 5#76071

На бесконечной шахматной доске стоят ферзь и невидимый король. Известно, что ферзь дал шах по горизонтали, и король ушел из под шаха. Докажите, что ферзь может ходить так, чтобы король наверняка еще раз попал под шах.

Показать доказательство

Введем нумерацию горизонталей: пусть строка шахматной доски, на которой находится ферзь вначале будет $0$ -ой. Над горизонталью с ферзем - $1,2,...$ горизонтали, а под ней $− 1,−2,....$

Если король ушел из под шаха, то он находится либо на $1$ -ой, либо на $− 1$ -ой горизонтали.

Пусть первым ходом ферзь сходит на одну клетку вверх. Либо король попадет под шах, либо он был на горизонтали с номером $− 1,$ а после своего хода может находиться только на $0$ -ой, $− 1$ -ой, или $− 2$ -ой строчке.

Назовем “шагом вправо” следующие два подряд хода ферзя: $1)$ По диагонали вправо-вниз на три клетки; (после такого хода либо король попадает под шах, либо после своего хода может находиться только на $0$ -ой, $− 1$ -ой, или $1$ -ой строчке.) $2)$ На три клетки вверх; (либо король попадает под шах, либо после своего хода находится только на $0$ -ой, $− 1$ -ой, или $− 2$ -ой строчке.)

Аналогично “шаг влево”: $1)$ По диагонали влево-вниз на три клетки; $2)$ На три клетки вверх;

Заметим, что когда ферзь делает “шаг влево” или “шаг вправо”, он сдвигается на $3$ клетки вправо или влево. Также король всегда должен находится на полосе из $0$ и $− 1$ -ой горизонтали, иначе попадет под шах. И также можно заметить, что за один “шаг” король будет атакован, если он находился между вертикалями начальной и конечной позиции “шага”. То есть задача сводится к тому, что нужно доказать, что ферзь сможет догнать короля “шагами влево и вправо”, если за один “шаг” ферзь перемещается на $3$ клетки по горизонтали, а король максимум на $2$ клетки по горизонтали.

Но это утверждение уже легко доказать: отправим мысленно в обе стороны две вспомогательные фигуры, перемещающиеся со скоростью $2.5$ клетки за “шаг”. Пусть ферзь догонит сначала первого помощника, потом — второго, потом — снова первого, потом — снова второго и т. д. Ясно, что когда-нибудь один из помощников перегонит короля, а значит, и ферзь когда-то догонит короля, то есть король когда-то будет под шахом.

Ошибка.
Попробуйте повторить позже

Задача 6#81576

Петя задумал натуральное число. Вася каждым ходом называет натуральное число. Если он называет текущее Петино число, то Петя говорит «Я проиграл». Иначе Петя меняет текущее число по такому правилу: если его текущее число $n$ делится на названное Васей число $m,$ то он меняет $n$ на $n- m,$ иначе — на $n ⋅m.$ Может ли Вася действовать так, чтобы наверняка выиграть за конечное число ходов?

Показать ответ и решение

Назовём группой чисел размера $k$ группу чисел $1,1,1,1,2,1,2,1,3,1,3,1,...k,1,k,1.$ Пусть Петя сначала последовательно называет все числа из группы размера $1,$ потом все числа из группы размера $2,$ затем из группы размера $3$ и так дальше.

Покажем, что рано или поздно Петя проиграет. Любое число $n$ представимо в виде $2 xy ,$ где $x$ — свободное от квадрата число или $1.$

Давайте поймём, как числа $k,1,k,1$ влияют на $n.$ Если $n$ не делится на $k,$ то после этих четырёх чисел $n$ не изменится. Если $n$ делится на $k,$ но не делится на $2 k ,$ то оно тоже останется без изменений.

Пусть теперь $n$ делится на $2 k .$ Покажем, что тогда $2 y$ делится на $2 k .$ Предположим противное. Понятно, что $x$ не может делиться на $2 k ,$ значит $x$ делится на $k$ и $2 y$ делится на $k,$ но не делится на $2 k .$ Таким образом, $k$ — свободное от квадрата. Следовательно, хотя бы один простой делитель, входящий в разложение $k,$ входит в разложение $2 y$ в первой степени, иначе $2 y$ поделится на $2 k .$ Пришли к противоречию с тем, что $y2$ — квадрат. То есть в этом случае числа $k,1,k,1$ превратят $n= xy2$ в $xm2,$ где $y m = k.$

Таким образом, понятно, что в процессе величина $y2$ равно как и само число $n$ не возрастает. Также $y2$ не может бесконечно не убывать, рано или поздно будут названы числа $k,1,k,$ где $k$ — делитель $y,$ больший $1.$ Далее рано или поздно аналогичная ситуация произойдёт с $2 yk2-$ и так дальше. Когда-нибудь наступит момент, когда $y2$ превратится в $1,$ после этого рано или поздно будут названы числа $x,1.$ После единицы Петя проиграет.

Также заметим, что если $x= 1,$ то Петя также проиграет, поскольку после чисел $k,1,k$ всегда называется единица.

Ответ:

Да

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#76070

Дан граф-дерево, состоящий хотя бы из $3$ вершин. В некоторой вершине $V$ стоит невидимая фишка. За ход мы выбираем любой набор $N$ вершин графа. Нам сообщают количество вершин набора $N,$ в которые можно добраться из $V$ не более, чем за $1$ ход. Затем фишка передвигается по ребру в одну из соседних вершин. Можно ли через некоторое время точно сказать, где была фишка до последнего перемещения?

Показать ответ и решение

Будем действовать по следующему алгоритму, попутно объясняя, почему он сработает. Рассмотрим висячую вершину $X$ дерева и подвесим граф за нее. Сначала назовем только вершину $X.$

$1$ ) Если нам ответили не 0. Тогда нам могли ответить только $1.$ Обозначим смежную с $X$ вершину через $Y$ и спросим про $X$ и $Y.$ Если нам отвечают не $2,$ то это означает, что фишка стоит не в $X,$ этот случай будет подходить под рассматриваемые далее. Если нам все-таки отвечают $2,$ то спросим про $X,Y$ и все вершины, смежные с $Y.$ Причем спросим про это множество дважды. Заметим, что если хоть раз мы услышим ответ $3$ или больше, то сможем определить положение фишки. Если же $3$ нам не ответят, то это означает, что сейчас, после нашего вопроса, фишка находится ни в $X,$ ни в $Y.$ Этот случай будет подходить под рассматриваемые далее, потому что это то же самое, что спросить только про $X$ и услышать ответ $0.$

$2$ ) Итак, можно считать, что мы услышали ответ $0.$ Это означает, что ни в $X,$ ни рядом с $X$ фишка на предыдущем ходу не стояла. Мы будем увеличивать множество вершин, про которые задается вопрос на очередном шаге, добавляя следующую вершину, смежную с последней из добавленных. При этом есть две возможности, при которых мы начинаем действовать по-другому.

Назовем разветвлением вершину, степень которой больше 3.

a) Последняя добавленная к множеству вершина $Z$ не является разветвлением, но при этом мы услышали в ответ не $0.$ Заметим, что так как до этого множество, про которое мы спрашиваем, с фишкой не соседствовало, то мы можем услышать только $1$ или $2,$ причем если мы услышали $1,$ то фишка находилась в соседней с $Z$ вершине и мы ее определяем, а если $2,$ то в самой вершине $Z,$ что мы также определим. Этот подслучай разобран.

б) Последняя добавленная к множеству вершина $Z$ является разветвлением. Если при этом нам ответили $2$ (а больше ответить нам и не могли), то фишка находилась в вершине $Z.$ Если нам ответили $1,$ то спросим про то же самое множество вершин (обозначим его через $A$ ) еще раз. Если нам отвечают не $0,$ то мы можем однозначно определить положение фишки. Итак, мы добились, чтобы нам ответили $0.$ Получается, что фишка находится на одной из ветвей, выходящих из вершины $Z.$

Будем проверять эти ветви по очереди. Сначала спросим про всю первую ветку (без $Z$ ). Пусть мы услышали ответ $0.$ Тогда повторим вопрос про множество $A,$ пока не услышим $0$ (как мы выяснили ранее, либо за $2$ вопроса мы этого добьемся, либо выясним местоположение фишки). Затем проверим следующую ветку, и так далее, пока не найдем ветку, в которой находится фишка. Вновь проверим множество $A,$ пока не услышим $0$ в ответ. За все наши вопросы фишка не может переходить с ветки на ветку, значит, мы точно знаем, на какой ветке сейчас фишка. Все остальные ветви отбрасываем и добавляем к множеству $A$ фишек, про которые мы сейчас будем спрашивать, первую фишку нужно ветви. Далее действуем по тому же алгоритму. Заметим, что рано или поздно он закончится, так как на отбрасываемых ветках фишка оказаться не может. Значит, в итоге мы найдем фишку.

Ответ:

Да, можно

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания