Олимпиадные задачи по теме «Теория алгоритмов» для 11 класса - сложность 5 с решениями

На плоскости отмечены все точки с целыми координатами (<i>x,y</i>)такие, что<i> x²+y²<img align="absmiddle" src="/storage/problem-media/115399/problem_115399_img_2.gif"> </i>10<i></i>10. Двое играют в игру (ходят по очереди). Первым ходом первый игрок ставит фишку в какую-то отмеченную точку и стирает ее. Затем каждым очередным ходом игрок переносит фишку в какую-то другую отмеченную точку и стирает ее. При этом длины ходов должны все время увеличиваться; кроме того, запрещено делать ход из точки в симметричную ей относительно центра. Проигрывает тот, кто не может сделать ход. Кто из играющих может обеспечить себе победу, как бы ни играл его соперник?

В нашем распоряжении имеются 3^2<i>k</i>неотличимых по виду монет, одна из которых фальшивая– она весит чуть легче настоящей. Кроме того, у нас есть трое двухчашечных весов. Известно, что двое весов исправны, а одни– сломаны (показываемый ими исход взвешивания никак не связан с весом положенных на них монет, т.е. может быть как верным, так и искаженным в любую сторону, причем на разных взвешиваниях– искаженным по-разному). При этом неизвестно, какие именно весы исправны, а какие сломаны. Как определить фальшивую монету за 3<i>k + </i>1 взвешиваний?

Фокусник отгадывает площадь выпуклого 2008-угольника<i>A</i>₁<i>A</i>₂...<i>A</i>₂₀₀₈, находящегося за ширмой. Он называет две точки на периметре многоугольника; зрители отмечают эти точки, проводят через них прямую и сообщают фокуснику меньшую из двух площадей частей, на которые 2008-угольник разбивается этой прямой. При этом в качестве точки фокусник может назвать либо вершину, либо точку, делящую указанную им сторону в указанном им численном отношении. Докажите, что за 2006 вопросов фокусник сможет отгадать площадь многоугольника.

Игрок на компьютере управляет лисой, охотящейся за двумя зайцами. В вершине<i> A </i>квадрата<i> ABCD </i>находится нора: если в нее, в отсутствие лисы, попадает хотя бы один заяц, то игра проиграна. Лиса ловит зайца, как только оказывается с ним в одной точке (возможно, в точке<i> A </i>). Вначале лиса сидит в точке<i> C </i>, а зайцы – в точках<i> B </i>и<i> D </i>. Лиса бегает повсюду со скоростью не больше<i> v </i>, а зайцы – по лучам<i> AB </i>и<i> AD </i>со скоростью не больше 1. При каких значениях<i> v </i>лиса сможет поймать обоих зайцев?

Загадано число от 1 до 144. Разрешается выделить одно подмножество множества чисел от 1 до 144 и спросить, принадлежит ли ему загаданное число. За ответ да надо заплатить 2 рубля, за ответ нет – 1 рубль. Какая наименьшая сумма денег необходима для того, чтобы наверняка угадать число?

По заданному ненулевому<i>x</i>значение<i>x</i>⁸можно найти за три арифметических действия:<nobr><i>x</i>² = <i>x</i> · <i>x</i>,</nobr><nobr><i>x</i>⁴ = <i>x</i>² · <i>x</i>²,</nobr><nobr><i>x</i>⁸ = <i>x</i>⁴ · <i>x</i>⁴,</nobr>а<nobr><i>x</i>¹⁵ —</nobr>за пять действий: первые<nobr>три —</nobr>те же самые, затем<nobr><i>x</i>⁸ · <i>x<...

Двое играют в такую игру. Один задумывает натуральное<nobr>число <i>n</i>,</nobr>а другой задаёт вопросы типа «верно ли, что<i>n</i>не<nobr>меньше <i>x</i>»</nobr><nobr>(число <i>x</i></nobr>он может выбирать по своему усмотрению) и получает ответы «да» или «нет». Каждой возможной<nobr>стратегии <i>T</i></nobr>второго игрока сопоставим функцию<i>f</i>_<i>T</i>(<i>n</i>), равную числу вопросов (до отгадывания), если было задумано<nobr>число <i>n</i>.</nobr>Пусть, например,<nobr>стратегия <i>T</i></nobr>состоит в том, что сначала задают вопросы: «верно ли, что<i>n</i>не...

На острове живут хамелеоны пяти цветов. Когда один хамелеон кусает другого, цвет укушенного хамелеона меняется по некоторому правилу, причём новый цвет зависит только от цвета укусившего и цвета укушенного. Известно, что $2023$ красных хамелеона могут договориться о последовательности укусов, после которой все они станут синими. При каком наименьшем $k$ можно гарантировать, что $k$ красных хамелеонов смогут договориться так, чтобы стать синими? Например, правила могут быть такими: если красный хамелеон кусает зелёного, укушенный меняет цвет на синий; если зелёный кусает красного, укушенный остаётся красным, то есть «меняет цвет на красный»; если красный хамелеон кусает красного, укушенный меняет цвет на жёлтый, и так далее. (Конкретные правила смены цветов могут быть устроены иначе.)

На доске написано несколько чисел. Разрешается стереть любые два числа $a$ и $b$, а затем вместо одного из них написать число $\frac{a+b}{4}$. Какое наименьшее число может остаться на доске после 2018 таких операций, если изначально на ней написано 2019 единиц?

Глеб задумал натуральные числа $N$ и $a$, $a < N$. Число $a$ он написал на доске. Затем он начал выполнять следующую операцию: делить $N$ с остатком на последнее выписанное на доску число, а полученный остаток от деления также записывать на доску. Когда на доске появилось число $0$, он остановился. Мог ли Глеб изначально выбрать такие $N$ и $a$, чтобы сумма выписанных чисел была больше $100 N$?

В доме из $2^n$ комнат сделали евроремонт. При этом выключатели света оказались перепутанными, так что при включении выключателя в одной комнате загорается лампочка, вообще говоря, в какой-то другой комнате. Чтобы узнать, какой выключатель к какой комнате подсоединён, прораб посылает несколько людей в какие-то комнаты, чтобы те, одновременно включив там выключатели, вернулись и сообщили ему, горела лампочка в их комнате или нет. а) Докажите, что за $2n$ таких посылок прораб может установить соответствие между выключателями и комнатами. б) А может ли он обойтись $2n-1$ такими посылками?

Имеется несколько кучек камней. Двое по очереди берут из них камни. За один ход разрешается взять из одной кучки от 1 до 5 камней. Определите выигрышную стратегию в этой игре, если тот, кто взял последний камень а) выигрывает; б) проыигрывает.