Занимательные задачи по информатике (Ответы и решения)

1.      Илья Муромец и Змей Горыныч

Ошибка1. После срубания у Змея Горыныча какого-то количества голов у него вырастало вдвое больше голов, поэтому если срубить 32 головы, то должно отрасти 64, а не 63.

Ошибка 2. По той же причине, если срублено 63 головы, то должно отрасти 126, а не 128. Если же выросли 128 голов, то было срублено 64, а не 63.
См.https://info-polozhit.blogspot.com.by/2017/06/blog-post_22.html

Ошибка 3. Восьмиразрядный Горыныч должен умереть после срубания 128 (а не 256) голов, потому что число 256 в двоичном виде уже не помес­тится в разрядную сетку, и все восемь младших разрядов будут нулевые. Если же Змей Горыныч все-таки умер после отрубания 256 голов, он был девятиразрядным, потому что в девяти разрядах число 256 в двоичном виде размещается, а 512 — нет.

2.        Слова после чисел

«Вышел зайчик погулять» (в первой строке записаны числа от 1 до 5 в двоичной системе счисления).

3.      Градуировка весов

Здесь рассуждения такие.

1.               Десятичное число 31 в двоичной системе счисления выглядит так: 11111, а все числа, меньшие 31, в этой системе состоят (естественно) из единиц и нулей.

2.               Любое двоичное число от 1 до 11111 можно получить, складывая двоичные числа 1,10,100,1000 и 10 000 (убедитесь в этом!). Эти числа есть двойка в степени 0, 1, 2, 3 и 4, т.е. десятичные цифры 1, 2, 4, 8 и 16.

Значит, минимальный набор гирь-разновесов, который можно исполь­зовать для градуировки весов на интервал масс 1-31 кг, это гири массой 1, 2, 4, 8 и 16 кг. Например, чтобы отградуировать весы на 3 кг (3₁₀= 11₂), можно использовать гири массой 1 и 2 кг (этим значениям соответствуют двоичные числа 1 и 10), на 13 кг (13₁₀= 1101₂) — гири массой 1,4 и 8 кг (1₂, 100₂ и 1000₂).

4.      Бедный торговец (старинная задача)

Прежде всего вспомним задачу 3. При ее решении использовалась запись чисел в двоичной системе счисления.

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

Следовательно, в нашей задаче надо найти такой набор чисел, которые можно не только складывать, но и вычитать. Если здесь также рас­сматривать представление десятичных чисел 1, 2, ..., 40 в двоичной системе счисления, то выяснится, что для взвешивания понадобится 6 разных камней — массой 1, 2, 4, 8, 16 и 32 кг (убедитесь, что с их помощью можно определить все нужные значения!). В условии же задачи говорится только о четырех камнях. Значит, надо попробовать использовать другие системы счисления.

Чтобы найти, какую именно, рассмотрим более простую задачу: "С помощью какого минимального набора камней разной массы можно взвешивать предметы массой 1, 2, 3 и 4 кг?".

Ответ здесь такой: с помощью двух камней—- массой 1 и 3 кг. Это должно навести на мысль о том, что нужно использовать троичную систему счисления. Действительно, любое троичное число от 1 до 1111 (40₁₀= 1111₃) можно получить, складывая или вычитая числа 1₃, 10₃, 100₃ и 1000₃  (убедитесь в этом!). Эти числа есть тройка в степени 0,1,2 и 3, т.е. десятичные числа 1, 3, 9 и 27, — именно такой массы и были камни в лавке бедного торговца. 

Задание для самостоятельной работы

Подумайте, как определить, какие камни (или гири такого же веса) надо класть вместе с грузом, а какие — на свободную чашку, чтобы при грузе массой А кг весы были в равновесии.

5.      Как отгадать число?

Одна из возможных серий вопросов, заведомо приводящая к успеху, такова.        

1-й вопрос: "Разделите задуманное число на 2. Является ли еди­ница остатком при таком делении?". Если ответ да, то запишем 1, если нет — 0 (иначе говоря, мы запишем остаток от деления заду­манного числа на 2).   

2-й вопрос: "Разделите на 2 то частное, которое получилось при первом делении. Является ли единица остатком при таком делении? Снова при ответе да запишем единицу, а при ответе нет — ноль".

Каждый следующий вопрос будем составлять по тому же самому образцу, т.е. так: "Разделите на 2 то частное, которое получилось при пре­дыдущем делении. Является ли единица остатком при таком делении?" Всякий раз мы пишем единицу при положительном ответе и ноль при отрицательном.

Повторив эту процедуру 10 раз, мы получим 10 цифр, каждая из которых есть нуль или единица.

После ответов на все вопросы записанные цифры надо расположить в обратном порядке — получится двоичное число, соответствующее задуманному десятичному (оно будет 10-значным), Действительно, система наших вопросов воспроизводит ту самую процедуру, с помо­щью которой делается перевод некоторого числа в двоичную систему. При этом десяти вопросов достаточно потому, что каждое число от 500 до 1000 записывается в двоичной системе с помощью не более чем десяти знаков.

Переведя полученное число в десятичную систему счисления, получим задуманное число.

Если считать, что задуманное число уже заранее переведено в двоич­ную систему, то система вопросов, с помощью которой его можно узнать, будет следующей. Нужно о каждой его цифре спросить, равна она нулю или нет. Для этого можно задать такие вопросы:

1.      "Является ли единица крайней справа цифрой двоичного числа, соответствующего задуманному десятичному числу?"

2.      "Является ли единица второй справа цифрой двоичного числа, со­ответствующего задуманному десятичному числу?"

...

10. "Является ли единица десятой справа цифрой двоичного числа, соответствующего задуманному десятичному числу?" , "

6.      Часы остановились

"Изюминка" решения заключается в том, что, уходя из дома, надо пустить в ход свои стенные часы (которые остановились, но не сломались) и заметить по ним, в котором часу вы вышли, а затем — в котором часу вернулись. Так по своим часам можно определить, сколько времени вы отсутствовали. Придя к знакомому и уходя от него, вы узнаете показания его часов. Это даст вам возможность определить продолжительность пребывания у знакомого.   

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

В соответствии с этим алгоритм решения задачи следующий:

1.      Пустить в ход свои стенные часы.

2.      Отметить время ухода из дома по этим часам.

3.      Пойти к знакомому.,

4.      Отметить время прихода к знакомому по его часам.

5.      Определить время ухода от знакомого (также по его часам).

6.      Рассчитать время пребывания у знакомого (разность значений вре­мени по пунктам 5 и 4).

7.      Вернуться домой.

8.      Установить время возвращения домой по своим настенным часам.

9.      Рассчитать время, которое вы отсутствовали дома (разность значений времени по пунктам 8 и 2).,

10.  Вычесть из значения времени, рассчитанного в пункте 9, значение, вычисленное в пункте 6.          

11.  Разделить полученное в предыдущем пункте значение на 2.

12.  Прибавить значение, рассчитанное в пункте 11, ко времени, уста­новленному, в пункте 5.

13.  Поставить стрелки стенных часов на время, вычисленное в пункте 12

7.      Ночной переход на мосту

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

Таблица 1

1.	Переходят пана и мама	2 минуты
2.	Папа с фонариком возвращается	1 минута
3.	Переходят бабушка и малыш	10 минут
4.	Мама с фонариком возвращается	2 минуты
5.	Переходят папа и мама	2 минуты
ИТОГО:		17 минут

8.      Вкусные ломтики

Если пронумеровать ломтики, то задача поджаривания четырех лом­тиков за минимально возможное время решается за четыре шага (этапа), представленных в табл. 2, а пяти ломтиков – за пять шагов, показанных в табл. 3.

Таблица 2

№ этапа	На сковородке находятся:		Продолжительность поджаривания, сек	Готов ломтик
	Ломтик	Сторона
1	№1	Первая	30
	№2	Первая
2	№1	Вторая	30	№1
	№2	Вторая		№2
3	№3	Первая	30
	№4	Первая
4	№3	Вторая	30	№3
	№4	Вторая		№4
Всего:			2 минуты

Таблица 3

№ этапа	На сковородке находятся:		Продолжительность поджаривания, сек	Готов ломтик
	Ломтик	Сторона
1	№1	Первая	30
	№2	Первая
2	№1	Вторая	30	№1
	№3	Первая
3	№2	Вторая	30	№2
	№3	Вторая		№3
4	№3	Первая	30
	№4	Первая
5	№3	Вторая	30	№4
	№4	Вторая		№5
Всего:			2,5 минуты

9.      Задача о лифте

Решение представлено в табл.4

Таблица 4

	Этаж, на котором находимся	Нажимаем на кнопку	Этаж, на котором оказываемся
1	13	-8	5
2	5	+13	18
3	18	-8	10
4	10	-8	2
5	2	+13	15
6	15	-8	7
7	7	+13	20
8	20	-8	12
9	12	-8	4
10	4	+13	17
11	17	-8	9
12	9	-8	1
13	1	+13	14
14	14	-8	6
15	6	+13	19
16	19	-8	11
17	11	-8	3
18	3	+13	16
19	16	-8	8

Примечание. Кнопки с условными обозначениями «-8» и «+13» - те кнопки, при нажатии на которые лифт опускается на 8 этажей и понимается на 13 этажей соответственно.

10.  Мешок с фальшивыми монетами

Выяснить требуемое можно, пользуясь такой системой указаний:

1.      Пронумеровать мешки числами от 1 до 10.

2.      Из каждого мешка извлечь столько монет, каков его номер.

3.      Определить на весах суммарную массу М всех извлеченных монет.

4.      Проверить условие М = 550. Если да, то перейти к указанию 7, иначе — к следующему указанию.

5.      Определить разность R, равную М - 550.

6.      Объявить, что в мешке с номером R монеты фальшивые. Перейти к указанию 8.

7.      Объявить, что мешка с фальшивыми монетами нет.

8.      Конец.

11.  Еще один мешок с фальшивыми монетами

1-е взвешивание. Взять по одной монете из каждого мешка и определить их общий вес V₁. В результате можно определить:

1)      вес настоящих монет т: он равен округленному до целого частному отделения V₁, на 11;

2)      на сколько вес фальшивых монет отличается от веса настоящих, эта величина равна V₁-11 т и позволяет сказать, легче или тяжелее настоящих фальшивые монеты.

2-е взвешивание. Взять, как в предыдущей задаче, из каждого мешка столько монет, каков его номер (общее число взятых монет—66). Если их общий вес V₂,то номер с фальшивыми монетами равен | V₂ - V₁,|/ |V₁-11т|, где символы || означают абсолютную величину числа, представленного между ними.

12.  Почему трижды?

Трехкратное повторение каждой двоичной цифры позволяет в случае ошибки выявить ее. Так, для примера, приведенного в статье, если будет при­нято число 111 101 000 000 111 111 111,то это означает, что при передаче второй цифры была допущена ошибка, и принявший ее (человек или компьютер по специальной программе проверки) сможет прочесть правильный вариант. Если передавать каждую цифру только два раза, то этого достаточно, чтобы выявить, была допущена ошибка при передаче или нет. Но для того, чтобы определить, какова ошибка, двойного повторения мало.

13.  Необычная сделка

          Надеждам купца на то, что в результате сделки он окажется в прибыли, не суждено было сбыться. Это доказывают расчеты, представленные в таблице, которую можно получить, например, средствами программы Mi­crosoft Excel или подобной (см. табл. 5).

Таблица 5

День	Сумма, уплаченная купцу	Сумма, уплаченная купцу с начала месяца	Сумма, уплаченная купцом	Сумма, уплаченная купцом с начала месяца
1-й	50 000	50 000	0,01	0,01
2-й	50 000	100 000	0,02	0,03
3-й	50 000	150 000	0,04	0,07
….	…	…	…	…
29-й	50 000	1 450 000	2 684 354,56	5 368 709,11
30-й	50 000	1 500 000	5 368 709,12	10 737 418,23

Из табл. 5 видно, что в итоге купец отдал на 9 237 418 рублей (!) больше, чем получил.

Можно также разработать компьютерную программу, которая на школьном алгоритмическом языке имеет вид:

алг Необычная _ сделка 

нач цел день, вещ отдал, всего_отдал, всего_получил, прибыль

 |Первый день

отдал := 0.01

всего _ отдал := 0.01

вывод нс, "В первый день .купец отдал ", отдал, "руб."

| Остальные дни

нц для день от 2 до 30

отдал := отдал * 2

всего_отдал := всего _ отдал + отдал

| вывод нс, "В", день, "-й день купец отдал ", отдал, "руб."

кц

вывод нс, "Всего купец отдал", всего_отдал, " руб."

всего __ получил :=30 *-50

вывод нс, "Всего купец получил ", всего-_ получил, " руб."

прибыль := всего _ получил — всего _ отдал

если  прибыль >0

    то

вывод нс, "То есть купец получил прибыль " "

вывод, "в размере '', прибыль,  " руб."

    иначе

            вывод нс, "То есть купец остался в убытке "

            вывод "и потерял ", аbs(прибыль), " руб."

все     

кон

Смысл использованных в ней переменных величин ясен из их имен (функция abs возвращает абсолютное значение числа, указанного в виде ее аргумента в скобках).

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

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

14.  Шутники и серьезные

14. Прежде всего можно установить, что так как Петров и Сидоров на заданный вопрос ответили по-разному, то они относятся к разным "пар­тиям" (один — "шутников", другой — "серьезных").

Рассмотрим возможные ответы Иванова. Если он —- серьезный, то на вопрос учителя он так и ответит (что он серьезный). Если же он шутник — то тогда он ответит, что он якобы серьезный. Получается, что в любом случае Иванов должен ответить: "Я — серьезный человек".

Так как Петров сказал учителю то же, что ответил Иванов, то он отно­сится к "партии серьезных". Тогда Сидоров— шутник.

Можно также решить задачу методом допущений. Если допустить, что Петров — шутник, а Сидоров — серьезный человек, то из ответа первого следует, что Иванов на самом деле — шутник, а из ответов второго — что серьезный человек, чего быть не может.

Если же, наоборот, предположить, что Петров — серьезный человек, а Сидоров — шутник, то из ответа каждого из них следует одно и то же (что Иванов — серьезный).

Следовательно, Петров относится к "партии серьезных", а Сидоров — шутник.

15. Приятели и их шапки

На основании ответов своих приятелей Вадим может определить цвет своей шапки. Действительно, из ответа Андрея его друзьям должно быть ясно, что на них не может быть двух белых шапок (иначе Андрей определил бы, что на нем— черная шапка). Значит, на них либо одна белая и одна черная шапка, либо обе черных.

Если бы на Вадиме была белая шапка, то Борис легко определил бы цвет своей шапки (черный), а так как он этого сделать не смог, то Вадим должен понять, что его шапка черная.

16.  Те же приятели и те же шапки

Ответы на все вопросы, заданные в задаче, для всех возможных вариантов реплик Андрея, Бориса и Вадима приведены в табл. 6:

Таблица 6

Ответ Андрея	Перед Андреем	Ответ Бориса	Ответ Вадима
1. "Могу определить цвет своей шапки"	Две черные или две белые шап­ки	1. "Могу опреде­лить цвет своей шапки"	"Не могу определить цвет своей шапки"
		2. "Могу опреде­лить цвет своей шапки" и назовет цвет	"Могу определить цвет своей шапки" и повторит назван­ный Борисом цвет
2. "Не могу оп­ределить цвет своей шапки"	Одна черная и одна белая шап­ка .	1. "Могу опреде­лить цвет своей шапки"	"Не могу опреде­лить цвет своей шапки"
		2. "Могу опреде­лить цвет своей шапки" и назовет цвет .	"Могу определить цвет своей шапки" и назовет цвет, "противополож­ный" названному Борисом

17.1. 2x2 = 5 

Числа 4 и 5 не являются общими множителями тождества 4 : 4 = 5 : 5, и выносить их за скобки: 4(1:1) = 5(1:1) - нельзя.

17.2. 5 = 1

Проанализируем рассуждения, идя от полученного равенства 4 = 4 "назад".

Если квадраты чисел равны, то это еще не означает, что и сами числа равны. Из равенства квадратов двух чисел вытекает лишь, что равны аб­солютные величины этих чисел.

Поэтому если 4 = 4, то извлечение квадратного корня из обеих частей означает, что 2 = 2 либо -2 = -2, но не означает, что 2 = -2.

17.3. 2 = 3

После извлечения квадратного корня из обеих частей равенства

(2-⁵/₂)² =(3-⁵/₂ )²

записывать 2-⁵/₂ =3-⁵/₂ нельзя (см. объяснения к пре­дыдущему софизму).

17.4. Любое число а равно меньшему числу b

Причиной "странного" результата является то, что в равенстве a(a-b-c)=b(a-b-c)  делить обе части на а -b- с нельзя, так как a-b-c=0 (поскольку было принято, что a=b+c).

17.5. Вес слона равен весу комара

В этой софизме неправильным также является переход от равен­ства

(с - v)2= (к— v)² к равенству c - v = k – v

17.6. Хитрый хозяин гостиницы

            Дело в том, что первоначально хитрый хозяин гостиницы разместил в восьми номерах не десять, а девять гостей (см. табл.7)

Таблица 7

Обозначение комнаты (номера гостиницы)	А	Б	В	…	Ж	З	И
Порядковый номер комнаты	1	2	3		7	8
Порядковый номер гостя	1,2	3	4		8	9

Потом он пригласил в девятый номер гостиницы, обозначенный буквой “И”, одного из двух гостей, находящихся в номере “А”. Так что десятый гость так и остался без гостиничного номера, т.е в приведенном стишке ошибка заключалась во фразе:

Он ключ от “И” вручить был рад

Десятому герою.

Продолжение парадоксов

"Генерал и брадобрей"

… Если он должен брить себя сам, то он не может быть брадобреем, так как у него должны бриться только те солдаты, которые сами себя не бреют.

Если у другого солдата, то он уже не будет специально выделенным брадобреем.

Следовательно, специально выделенный солдат не может ни сам себя брить, ни бриться у другого солдата.

"Каталог всех нормальных каталогов"

… Если должен, то это будет уже ненормальный каталог, а значит, такой каталог не должен составляться.

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

Итак, библиотекарь не может ни упомянуть составленный им каталог, ни не сделать этого.

19.  10 единиц и 10 двоек

Для каждого из двух участников игры возможны три варианта хода:

1)     зачеркнуть две единицы;

2)     зачеркнуть две двойки;

3)     зачеркнуть одну единицу и одну двойку.

Ситуация на доске после каждого из этих вариантов приведена в табл. 8

Таблица 8

Вариант	Исчезнут цифры	Добавится цифра	Количество единиц	Количество двоек
1	1 1	2	Уменьшится на 2	Увеличится на 1
2	2 2	2	Не измениться	Уменьшится на 1
3	1 2	1	Не изменится	Уменьшится на 1

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

Задание для самостоятельной работы .

Подумайте над такой игрой: "На доске написаны 11 единиц и 11 двоек. За ход разрешается стереть две любые цифры и, если они были одинако­выми, написать двойку, а если разными: —  единицу. Если оставшаяся на доске цифра — единица, то выиграл первый игрок, если двойка —  второй". Кто выиграет в этой игре?

20.  "Шоколадка" (задача-шутка)

Если проанализировать зависимость числа разломов R от количества долек шоколадки D (см. рис. 1), то можно установить, что R= D-1

Рисунок 1

Следовательно, в шоколадке 8 х 6 придется сделать 47 разломов, т.е., как бы не действовали участники игры, при 48 дольках шоколадки последний разлом всегда сделает тот, кто начал (поэтому задача и названа шуткой).

Ответ на дополнительное задание к задаче 4 "Бедный торговец"

Пусть груз, который надо взвесить, весит А кг. Это число можно пред­ставить в троичной системе:           

А = (а_n а_n-1...a₁a₀)₃

т.е.

А = а_n  3ⁿ+a_n-1  3^n-1+ ... +а₁ 3+а₀,

- где коэффициенты а_0, a_{1, …,}  а_n  могут принимать значения 0, 1 или 2 (как вы, очевидно, знаете, это так называемая "развернутая" запись числа А).

Можно доказать, что 2   3^m = 3^m+1 – 3^m. Введем "отрицательную цифру" 1 и обозначим ее 1. Тогда последнее равенство можно записать в виде: 2   3^m = 3^m+1 +1 – 3^m . А это означает, что любое целое число А можно изобразить в троичной системе счисления с помощью цифр 0,1 и 1 (заме­нив в его развернутой записи цифры 2 на соответствующую разность):

А = b_m  3^m+b_m-1  3^m-1+ ... +b₁ 3+b₀,

- где каждый из коэффициентов b_m, b_{m-1, …,}  b₀  может быть равным 0, 1 или 1

Например, число 100, которое обычным образом записывается в троичной системе как 10201, во втором варианте будет иметь вид 11101, поскольку 100 =3⁴ + 3³ -3²+1.

Следовательно, чтобы уравновесить груз в А граммов, нужно положить его на первую чашу весов, а гирю в 1 грамм поставить на вторую чашу, если b₀ =1, и на первую чашу, если b₀= 1 (если b₀= 0, то гирю в 1 грамм мы вообще не используем); далее, гиря весом в 3 грамма ставится на вто­рую чашу, если b₁ = 1, и на первую, если b₁=1, и т.д. Легко понять, что, расставив гири по такому принципу, мы уравновесим груз А.

Поясним сказанное на примере. Предположим, что у нас имеется груз в 200 граммов. Переводя 200 в троичную запись, мы получим:

Следовательно, 200₁₀= 21102₃, или в развернутой записи — 200 = 2   3⁴+ + 1   3³ + 1   3² + 0   3 + 2   1.

Таким образом, чтобы уравновесить груз в 200 граммов, положенный на чашу весов, нужно на ту же чашу положить гири в 1 грамм и 81 грамм, а на противоположную — гири в 3, 9, 27 и 243 грамма.

21.  Антиквар и 99 монет

Задача 2. Сначала положим на две чашки весов по 13 монет, затем (если весы находятся в равновесии) уберем их и положим по 11 из еще не брав­шихся монет, затем по 9, 7, 5, 3 и 1 до тех пор, пока одна из чашек не пере­весит. Если такого не произойдет, то после седьмого взвешивания (когда на чашках весов будет по одной монете) останется одна, 99-я по счету, моне­та, которая во взвешиваниях не участвовала. Она и является фальшивой.

Сложнее, если при каком-то взвешивании какая-то чашка весов пере­весила. Прежде всего ясно, что в этот момент фальшивая монета лежит в другой чашке. Составим табличку (см. табл. 9):

Таблица 9

Номер взвешивания	1	2	3	4	5	6	7
Число монет на одной чашке n	13	11	9	7	5	3	1

Итак, при каком-то, k-м, взвешивании мы можем выявить n монет, среди ко­торых находится искомая фальшивая. Можно записать, что п =(7 - k)* 2 + 1. Получается, что мы пришли к задаче нахождения среди (7 - k)* 2 + 1 монет фальшивой монеты за (7 - k) взвешиваний (так как k взвешиваний уже проведе­но, причем каждая монета в рассматриваемой группе взвешивалась один раз).

Введем новую величину m = 7- k. Тогда только что сформулированная задача сводится к следующей: среди (2m + 1) монет найти фальшивую монету за m взвешиваний (среди трех монет за одно взвешивание, среди пяти монет — за два, … среди тринадцати — за 6). При этом никакую мо­нету нельзя взвешивать более одного раза. Такую задачу мы уже решали (см. решение предыдущей задачи).

Ее можно решить так. Надо все монеты, кроме одной; разбить на m пар и последовательно сравнивать веса монет каждой пары — для этого пона­добится m взвешиваний. Если при каком-то взвешивании равновесие нарушится, то более легкая монета и является фальшивой. В противном случае фальшивая монета — оставшаяся "без пары".

22.  Умная обезьяна

Может. Первый раз обезьяна должна уронить один из двух уцелев­ших орехов с 4-го "яруса". Если он разбился, она, используя оставшийся орех, проверит 2-й и, при необходимости, 3-й "ярусы".

Если орех, брошенный с 4-го яруса, не разбился, то второй раз она уронит его с 7-го "яруса". Если он разбился, то проверит 5-й и 6-й "ярусы". Если орех не разбился, то третий раз уронит орех с 9-го "яруса". Если орех разбился, то проверит 8-й "ярус". Если орех не разбился, то проверит 10-й "ярус". Вся схема испытаний следующая:      

Первое испытание — бросить один из двух орехов с 4-г "яруса"

если орех, разбился

 то

  Второе испытание - бросить оставшийся орех с 2-го "яруса"

   если орех разбился

     то

      ярус:=1 номер искомого "яруса"

     иначе

      Третье испытание – бросить орех с 3-го "яруса"

     если орех разбился

 то ярус:=2

 иначе ярус:=3

все

        все

       иначе При первом испытании орех не разбился

        Второе испытание – бросить орех с 7-го "яруса"

        если орех разбился

         то

           Третье испытание – бросить оставшийся орех с 5-го   "яруса"

         если орех разбился

          то ярус:=4

          иначе

            Четвертое испытание – бросить орех с 6-го "яруса"

           если орех разбился

             то ярус:=5

             иначе ярус:=6

           все

         все

    иначе При втором испытании (с 7-го "яруса")орех не разбился

          Третье испытание – бросить орех с 9-го "яруса"

        если орех разбился

         то

          Четвертое испытание – бросить оставшийся орех с 8-го "яруса"

          если орех разбился

           то ярус:=4

           иначе

             Четвертое испытание – бросить орех с 6-го "яруса"

           если орех разбился

             то ярус:=7

             иначе ярус:=8

           все

          иначе При третьем испытании (с 9-го "яруса" орех не разбился

          Четвертое испытание – бросить орех с 10-го "яруса"

  если орех разбился

   то ярус:=9

   иначе ярус:=10

  все

    все

  все

 все

Можно также первое испытание провести на 5-м "ярусе". Если орех разбился, обезьяна, используя оставшийся орех, проверит 2-й и, при необходимости, 3-й и 4-й "ярусы". В противном случае второй раз она уронит его с 7-го "яруса". Если он разбился, то проверит 6-й "ярус''. Если же при втором испытании (на 7-м "ярусе") орех не разбился, то дальнейшие действия умного животного должны быть аналогичными первому варианту решения задачи.

Возможна также модификация только что рассмотренного варианту, в котором второе испытание проводится на 8-м "ярусе".

Задание для самостоятельной работы

1. Составьте полную схему испытаний для второго варианта решения, аналогичную приведенной чуть выше.     -

2. Сравните рассмотренные варианты (см. табл. 10)

Таблица 10

Искомый "ярус''	Число испытаний до нахождения искомого "яруса''
	1-й вариант решения	2-й вариант решения	2-й вариант решения (модификация)
1	2	2	2
2
…
10

Литература

1.      Гарднер М. Математические головоломки и развлечения. М.: Мир, 1999.

2.      Заславская О.Ю. Логические парадоксы и софизмы // Информатика, № 8/2004.

3.      "Квант": научно-популярный физико-математический журнал, 1970-1995.

4.      Кордёмский Б. А. Математическая смекалка. М.: Юнисам, МДС, 1994.

5.      Перельман Я.И. Занимательная математика.  М.: Издательство Руса­нова, 1994.