Олимпиадные задачи по теме «Логика и теория множеств» для 11 класса - сложность 1-2 с решениями
Петя загадал положительную несократимую дробь $x = \frac{m}{n}$. За один ход Вася называет положительную несократимую дробь $y$, не превосходящую 1, и Петя в ответ сообщает Васе числитель несократимой дроби, равной сумме $x+y$. Как Васе за два хода гарантированно узнать $x$?
На Поле Чудес выросло 8 золотых монет, но стало известно, что ровно три из них фальшивые. Все настоящие монеты весят одинаково, все фальшивые тоже, но они легче настоящих. Лиса Алиса и Буратино собрали монеты и стали их делить. Алиса собирается отдать Буратино три монеты, но он хочет сначала проверить, все ли они настоящие. Сможет ли он сделать это за два взвешивания на чашечных весах без гирь?
Мудрецам $A, B, C, D$ сообщили, что числа 1, 2, ..., 12 написаны по одному на 12 карточках и что эти карточки будут розданы им по три, причём каждый увидит лишь свои карточки. После раздачи мудрецы по очереди сказали следующее.
$A$: "На одной из моих карточек – число 8".
$B$: "Все числа на моих карточках простые".
$C$: "А все числа на моих – составные, причём имеют общий простой делитель".
$D$: "Тогда я знаю, какие карточки у каждого из вас".
Какие карточки у $A$, если все сказали правду?
16 карточек с целыми числами от 1 до 16 разложены лицевой стороной вниз в виде таблицы $4\times4$ так, что карточки, на которых записаны соседние числа, лежат рядом (соприкасаются по стороне). Какое наименьшее число карточек нужно одновременно перевернуть, чтобы наверняка определить местоположение всех чисел (как бы ни были разложены карточки)?
В комнате находится несколько детей и куча из 1000 конфет. Дети по очереди подходят к куче. Каждый подошедший делит количество конфет в куче на количество детей в комнате, округляет (если получилось нецелое), забирает полученное число конфет и выходит из комнаты. При этом мальчики округляют вверх, а девочки – вниз. Докажите, что суммарное количество конфет у мальчиков, когда все выйдут из комнаты, не зависит от порядка детей в очереди.
а) У Тани есть 4 одинаковые с виду гири, массы которых равны 1000, 1002, 1004 и 1005 г (неизвестно, где какая), и чашечные весы (показывающие, какая из двух чаш перевесила или что имеет место равенство). Может ли Таня за 4 взвешивания гарантированно определить, где какая гиря? (Следующее взвешивание выбирается по результатам прошедших.) б) Тот же вопрос, если у весов левая чашка на 1 г легче правой, так что весы показывают равенство, если масса на левой чашке на 1 г больше, чем на правой.
По кругу стоят буквы A и B, всего 41 буква. Можно заменять ABA на B и наоборот, а также BAB на A и наоборот.
Верно ли, что из любого начального расположения можно получить такими операциями круг, на котором стоит ровно одна буква?
На доске 8×8 в клетках a1 и c3 стоят две одинаковые фишки. Петя и Вася ходят по очереди, начинает Петя. В свой ход игрок выбирает любую фишку и сдвигает её либо по вертикали вверх, либо по горизонтали вправо на любое число клеток. Выиграет тот, кто сделает ход в клетку h8. Кто из игроков может действовать так, чтобы всегда выигрывать, как бы ни играл соперник? В одной клетке может стоять только одна фишка, прыгать через фишку нельзя. <div align="center"><img src="/storage/problem-media/66845/problem_66845_img_2.png"></div>
В каждой клетке полоски длины 100 стоит по фишке. Можно за 1 рубль поменять местами любые две соседние фишки, а также можно бесплатно поменять местами любые две фишки, между которыми стоят ровно три фишки. За какое наименьшее количество рублей можно переставить фишки в обратном порядке?
Фокусник выкладывает в ряд колоду из 52 карт и объявляет, что 51 из них будут выкинуты со стола, а останется тройка треф. Зритель на каждом шаге говорит, какую по счёту с края карту надо выкинуть, а фокусник выбирает, с левого или с правого края считать, и выкидывает соответствующую карту. При каких начальных положениях тройки треф можно гарантировать успех фокуса?
Король вызвал двух мудрецов и объявил им задание: первый задумывает семь различных натуральных чисел с суммой 100, тайно сообщает их королю, а второму мудрецу называет лишь четвёртое по величине из этих чисел, после чего второй должен отгадать задуманные числа. У мудрецов нет возможности сговориться. Могут ли мудрецы гарантированно справиться с заданием?
Фокусник с помощником показывают фокус. В ряд стоят 12 закрытых пустых шкатулок. Фокусник уходит, а зритель на виду у помощника прячет по монетке в любые две шкатулки по своему выбору. Затем возвращается фокусник. Помощник открывает одну шкатулку, в которой нет монетки. Далее фокусник указывает на 4 шкатулки, и их одновременно открывают. Цель фокусника – открыть обе шкатулки с монетками. Предложите способ, как договориться фокуснику с помощником, чтобы этот фокус всегда удавался.
По кругу лежит $2n + 1$ монета орлом вверх. Двигаясь по часовой стрелке, делают $2n + 1$ переворот: переворачивают какую-то монету, одну монету пропускают и переворачивают следующую, две монеты пропускают и переворачивают следующую, три монеты пропускают и переворачивают следующую, и т.д., наконец пропускают 2n монет и переворачивают следующую. Докажите, что теперь ровно одна монета лежит решкой вверх.
У Насти есть пять одинаковых с виду монет, среди которых три настоящие – весят одинаково – и две фальшивые: одна тяжелее настоящей, а вторая на столько же легче настоящей. Эксперт по просьбе Насти сделает на двухчашечных весах без гирь три взвешивания, которые она укажет, после чего сообщит Насте результаты. Может ли Настя выбрать взвешивания так, чтобы по их результатам гарантированно определить обе фальшивые монеты и указать, какая из них более тяжёлая, а какая более лёгкая?
В углу шахматной доски 8×8 стоит фишка. Петя и Вася двигают фишку по очереди, начинает Петя. Он делает фишкой один ход как ферзём (пройденной считается только клетка, куда в итоге переместилась фишка), а Вася – два хода как королём (обе клетки считаются пройденными). Нельзя ставить фишку на клетку, где она уже бывала (включая исходную клетку). Кто не сможет сделать ход – проигрывает. Кто из ребят может играть так, чтобы всегда выигрывать, как бы ни играл соперник?
Марина купила тур в Банановую страну с 5 по 22 октября. Ввозить и вывозить бананы через границу запрещено. Банановый король в начале каждого месяца издаёт указ о ценах. Цена одного банана в местной валюте на нужные числа октября приведена в таблице:<table align="center" border="1" text-align="center"> <tr> <td> $,$5 </td><td> $,$6 </td><td> $,$7 </td><td> $,$8 </td><td> $,$9 </td><td> 10 </td><td> 11 </td><td> 12 </td><td> 13 </td><td> 14 </td><td> 15 </td><td> 16 </td><td> 17 </td><td> 18 </td><td> 19 </td><td> 20 </td><td> 21 </td><td>...
Высота каждой из 2019 ступенек «лестницы» (см. рисунок) равна 1, а ширина увеличивается от 1 до 2019. Правда ли, что отрезок, соединяющий левую нижнюю и правую верхнюю точки этой лестницы, не пересекает лестницу? <img src="/storage/problem-media/66631/problem_66631_img_2.png">
<img align="right" hspace="10" width="169.5" src="/storage/problem-media/66587/problem_66587_img_2.png">В узлах сетки клетчатого прямоугольника $4 \times 5$ расположены $30$ лампочек, изначально все они погашены. За ход разрешается провести любую прямую, не задевающую лампочек (размерами лампочек следует пренебречь, считая их точками), такую, что с какой-то одной стороны от нее ни одна лампочка не горит, и зажечь все лампочки по эту сторону от прямой. Каждым ходом нужно зажигать хотя бы одну лампочку. Можно ли зажечь все лампочки ровно за четыре хода?
Клетки бумажного квадрата $8 \times 8$ раскрашены в два цвета. Докажите, что Арсений может вырезать из него по линиям сетки два квадрата $2 \times 2$, не имеющих общих клеток, раскраски которых совпадают. (Раскраски, отличающиеся поворотом, считаются разными.)
Среди зрителей кинофестиваля было поровну мужчин и женщин. Всем зрителям понравилось одинаковое количество фильмов. Каждый фильм понравился восьми зрителям. Докажите, что не менее $3/7$ фильмов обладают следующим свойством: среди зрителей, которым фильм понравился, не менее двух мужчин.
Решите уравнение $$ x^3+(\log_25+\log_32+\log_53) x=(\log_23+\log_35+\log_52) x^2+1. $$
Имеется железная гиря в 6 кг, сахар и невесомые пакеты в неограниченном количестве, а также нестандартные весы с двумя чашами: весы находятся в равновесии, если грузы на левой и правой чашах относятся как 3 : 4. За одно взвешивание можно положить на весы любые уже имеющиеся грузы и добавить на одну из чаш пакет с таким количеством сахара, чтобы чаши уравновесились (такие пакеты с сахаром можно использовать при дальнейших взвешиваниях). Удастся ли отмерить 1 кг сахара?
В ряд лежат 100 внешне одинаковых монет. Среди них ровно 26 фальшивых, причём они лежат подряд. Настоящие монеты весят одинаково, фальшивые – не обязательно одинаково, но они легче настоящих. Как за одно взвешивание на двухчашечных весах без гирь найти хотя бы одну фальшивую монету?
Вася задумал восемь клеток шахматной доски, никакие две из которых не лежат в одной строке или в одном столбце. За ход Петя выставляет на доску восемь ладей, не бьющих друг друга, а затем Вася указывает все ладьи, стоящие на задуманных клетках. Если количество ладей, указанных Васей на этом ходе, чётно (то есть 0, 2, 4, 6 или 8), то Петя выигрывает; иначе все фигуры снимаются с доски и Петя делает следующий ход. За какое наименьшее число ходов Петя сможет гарантированно выиграть?
100 включённых и 100 выключенных фонариков случайным образом разложены по двум коробкам. У каждого фонарика есть кнопка, нажатие которой выключает горящий фонарик и зажигает выключенный. Ваши глаза завязаны, и вы не можете видеть, горит ли фонарик. Но вы можете перекладывать фонарики из коробки в коробку и нажимать на них кнопки. Придумайте способ добиться того, чтобы горящих фонариков в коробках было поровну.