Тема Игры

Игры вслепую

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

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

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

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

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

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

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

Задача 1#76066

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

Подсказки к задаче

Подсказка 1

Можем ли мы в нашем алгоритме с некоторого момента двигаться лишь в одну сторону?

Подсказка 2

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

Подсказка 3

Помните, что нам будет необходимо доказывать, что предложенный алгоритм работает. Доказательство было бы очевидным, если бы мы показали, что наше движение в некотором смысле "'эквивалентно" движению в одну сторону. Более формально, если бы показали, что умеем догонять объект, который будет двигаться со скоростью больше, чем преступник и меньшей, чем полицейский, скажем 90 км/ч, который в нулевой момент времени находился с нами в одной точке, то это бы решило задачу. Докажите почему, это правда. Как осуществить данный алгоритм?

Подсказка 4

Отправим мысленно в обе стороны дороги двух помощников, едущих со скоростью 90 км/ч. Будем догонять сначала первого, после второго, потом снова первого и т.д. Почему мы сможем реализовать наш алгоритм на каждом шаге?

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

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

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

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

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

Задача 2#76067

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

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

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

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

Подсказки к задаче

Подсказка 1, пункт а

Изначальное число произвольно, следовательно, мы должны научиться проверять каждое целое число на каком-то шаге. Как это можно сделать?

Подсказка 2, пункт а

Давайте научимся проверять последовательно числа 0, 1, -1, 2, -2, .... Как будут выглядеть наши вопросы?

Подсказка 3, пункт а

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

Подсказка 1, пункт б

Как в произвольный момент времени понимать знак числа, не меняя его?

Подсказка 2, пункт б

Спрашивать равно ли наше число 0. Теперь было бы хорошо определять границы, в которых находится наше число, постепенно увеличивая его. Как это можно сделать?

Подсказка 3, пункт б

Подсказка 4, пункт б

Будем считать, что загаданное число положительно. Давайте спрашивать равно ли наше число последовательными степеням двойки. Почему рано или поздно мы услышим, что загаданное число меньше того, которое мы загадали?

Подсказка 5, пункт б

В каких границах находится загаданное число после этого вопроса?

Подсказка 6, пункт б

Пусть на текущий момент мы знаем, что загаданное число не превосходит по модулю некоторого значения M. Как путем задачи нескольких вопросов уменьшить проверяемое M?

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

(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

Занумеруем двери числами 1, 2, 3, ..., n по часовой стрелке. Покажем стратегию игры за Ивана Царевича. Без ограничений общности, первым ходом проверим двери 1, 2, 3. Какие двери могут быть открыты на следующем шаге в случае неудачи?

Подсказка 2

Все, кроме 2. Как может выглядеть наш следующих ход?

Подсказка 3

Если мы при следующем шаге не будем проверять никакую из дверей 1, 3, то мы потеряем информацию о второй двери и начнем наш алгоритм сначала. Без ограничений общности мы хотим проверить так же дверь 3, проверять при этом дверь 2 нет смысла, мы знаем, что она закрыта. Таким образом, следующим ходом имеем смысл проверять лишь двери 3, 4, 5. Какие двери не могут быть открыты после данного хода?

Подсказка 4

Двери 3 и 4. Продолжите данный алгоритм по кругу. Почему он будет конечным?

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

Занумеруем двери числами $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

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

Подсказки к задаче

Подсказка 1

Получится ли обойтись без пометок совсем?

Подсказка 2

Нет. Давайте сделаем пометку. Как бы мы искали количество вагонов, если в них еще не было пометок?

Подсказка 3

Прошлись бы в одном направлении, считая количество пройденных вагонов, до первого, пометка в котором похожа на нашу. Что мешает сделать и при нашем условии? Как можно это исправить?

Подсказка 4

Кто-то до нас уже мог сделать подобную заметку. Как мы можем распознавать является ли эта пометка нашей или нет?

Подсказка 5

Давайте зачеркнем данную пометку и пройдем назад отсчитанное количество вагонов, до первого. Если метка в нем зачеркнута, то мы прошлись по всему вагону и количество вагонов на единицу меньше отсчитанного. Если нет, то повторим предложенный алгоритм.

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

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

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

Задача 5#76071

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

Подсказки к задаче

Подсказка 1

Можем ли мы придумать алгоритм, в котором шах гарантированно будет в позиции, когда король и ферзь находятся в одной горизонтали?

Подсказка 2

Нет, король может менять вертикаль каждый раз в противоположную сторону от той, куда мы должны были попасть на следующем шаге. Что это говорит о нашем алгоритме?

Подсказка 4

Наш алгоритм должен предполагать, что нам можем пригодится делать шах по вертикале или диагонали. Таким образом, мы хотим приблизиться к королю как можно "ближе".

Подсказка 3

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

Подсказка 4

Да, например, если первым ходом сдвинуться на одну клетку вверх по диагонали, а все следующие — последовательно на три вниз (при первом ходе) и три вверх (при втором). Как при этом построить алгоритм таким образом, чтобы а) вне зависимости от направления по вертикале короля мы умели подходить к нему как можно "ближе"; б) в случае, при достаточно близком подходе, гарантированно делать шах?

Подсказка 5

Допустим, что мы уже знаем, что король находится справа от нас по вертикале. Тогда мы можем последовательно делать следующие два шага 1) По диагонали вправо-вниз на три клетки; 2) На три клетки вверх. Почему в таком случае мы гарантированно сделаем шах? Что делать в случае, если мы не знаем в направлении относительно нас по горизонтали находится король?

Подсказка 6

Для этого решения этой проблемы, вам может вам понадобится решить следующую известную задачу

Подсказка 7

Для ее решения нужно запустить двух "помощников" в разные помощники, скорость каждого меньше скорости вора, но больше скорости полицейской. Тогда достаточно последовательно догонять правого и левого помощника. Как эта идея поможет в нашей задаче?

Подсказка 8

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

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

Введем нумерацию горизонталей: пусть строка шахматной доски, на которой находится ферзь вначале будет $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$ ход. Затем фишка передвигается по ребру в одну из соседних вершин. Можно ли через некоторое время точно сказать, где была фишка до последнего перемещения?

Подсказки к задаче

Подсказка 1

Как определять положение вершины для дерева из двух вершин?

Подсказка 2

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

Подсказка 3

Заметим, что так как до этого множество, про которое мы спрашиваем, с фишкой не соседствовало, то мы можем услышать только 1 или 2, причем если мы услышали 1, то фишка находилась в соседней с новой добавленной вершине и мы ее определяем, а если 2, то в самой добавленной вершине, что мы также определим. Осталось понять, как действовать в случае, если смежных к последней добавленной вершине больше 2.

Подсказка 4

В таком случае необходимо определять в каком из поддеревьев относительно последней добавленной вершины находится фишка. Как это сделать?

Подсказка 5

Достаточно в качестве проверяемого множества последовательно брать каждое из поддеревьев последней добавленной вершиной (возможно, с последней добавленной в основное множество вершиной).

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

Будем действовать по следующему алгоритму, попутно объясняя, почему он сработает. Рассмотрим висячую вершину $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$ фишек, про которые мы сейчас будем спрашивать, первую фишку нужно ветви. Далее действуем по тому же алгоритму. Заметим, что рано или поздно он закончится, так как на отбрасываемых ветках фишка оказаться не может. Значит, в итоге мы найдем фишку.

Ответ:

Да, можно

Интенсивы

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

Предыдущий раздел

Следующий раздел