Занимательные задачи по информатике

1.    Илья Муромец и Змей Горыныч
Перед вами фрагмент сказки:

«Срубил Илья Муромец Змею Горынычу голову, а взамен две выросли. Срубил 2 — выросли 4, срубил 4 — выросли 8, срубил 8— выросли 16, сру­бил 16 — выросли 32, срубил 32 — выросли 63, срубил 63 — выросли 128, срубил 128—выросли 256. А как срубил Илья 256 голов, тут и настал Змею Горынычу конец, потому что был Горыныч восьмиразрядный!"
Ответы и решения см. https://info-polozhit.blogspot.com.by/2017/09/blog-post_27.html

Какие три ошибки имеются в приведенном фрагменте

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

Определите, какие слова должны быть записаны во второй строке:

1, 10, 11, 110, 111

…

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

Есть пружинные весы, которые нужно отградуировать. Каким должен быть набор гирь-разновесов, который можно использовать для градуировки весов на интервал масс 1, 2, …, 31 кг, чтобы число гирь в наборе было минимальным?

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

В лавке бедного торговца вместо гирь было всего 4 камня. Однако с помо­щью этих камней он на рычажных чашечных весах совершенно правильно взвешивал предметы массой 1,2,..., 40 кг. Какого веса были камни?

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

Пусть кто-то загадал некоторое целое число из интервала от 500 до 1000 включительно. Беретесь ли вы узнать загаданное число, задав этому человеку не более 10 вопросов, на каждый из которых он будет отвечать только "да" или "нет"? Вопросы типа "Задуманное число больше 800?", в которых фигурируют слова "больше", "больше либо равно", "меньше", "не меньше", "превышает" и т.п., а также вопросы типа "Задуманное число находится в интервале от ... до ... ?" задавать нельзя. Беритесь, задача эта вполне разрешима.

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

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

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

Ночью к мосту подошла семья (папа, мама, малыш, и бабушка). Папа может перейти мост за 1 минуту, мама — за 2, малыш — за 5, бабушка—за 10 минут. Мост выдерживает только двоих.

Какое минимальное время требуется этой семье для перехода через мост? (Есть один фонарик. Двигаться по мосту без фонарика нельзя. Светить издали нельзя. Носить друг друга на руках нельзя. Бросать фонарик друг другу нельзя. Если мост переходят двое, то они идут с меньшей из их скоростей.)

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

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

За какое минимальное время при этих условиях мама может приго­товить:

а) четыре ломтика хлеба?

б) пять ломтиков?

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

В кабине лифта 20-этажного дома есть две кнопки. При нажатии на одну, из них лифт поднимается на 13 этажей, при нажатии на другую—опускается на 8 этажей. Как попасть с 13-го этажа на 8-й?

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

Имеются 10 мешков, набитых монетами. Известно, что все монеты в девяти мешках не фальшивые. Относительно же одного мешка известно, что в нем либо все монеты фальшивые, либо все настоящие. Фальшивая монета весит 11 г, а настоящая — 10 г. Как с помощью одного взвешива­ния на точных (до 1 г) весах выяснить, есть ли среди 10 мешков мешок с фальшивыми монетами, если есть — указать какой.

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

Имеются 11 мешков, набитых монетами. В десяти мешках монеты настоящие, а в каком-то одиннадцатом —г все монеты фальшивые. Все настоящие монеты одинаковы по весу. Все фальшивые монеты тоже оди­наковы, но несколько отличаются по весу от настоящих монет, причем заранее неизвестно, легче они или тяжелее настоящих. Как с помощью двух взвешиваний на точных весах определить, в каком мешке фальшивые монеты, и указать, легче они или тяжелее настоящих.

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

Когда один компьютер посылает сообщения другому, используя услов­ные единицы и нули, мы должны быть уверены в правильности полученной информации. Значит, для выявления редких, но возможных ошибок нам требуются какие-то методы. Один из таких методов — передача каждой цифры трижды, т.е. три раза подряд. Например, вместо 1100111 нужно передать 111 111 000 000 111 111 111. Почему именно так

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

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

К одному богатому купцу как-то пришёл человек с очень странным предложением.

- Давай, — говорит человек купцу, —составим с тобой уговор, по которому я тебе каждый день в течение месяца буду приносить по 50 000 рублей, а ты мне в первый день дашь одну копейку, во второй день — две копейки, в третий день — 4 копейки и далее каждый день будешь давать мне вдвое больше прежнего.

Купец был удивлен такому предложению. "Что хочет этот сума­сшедший, — думал купец, — неужели ему некуда девать деньги? Ведь он мне за месяц уплатит  30•50 000 - 1 500 000 рублей, а я ему какие-то копейки".

Хорошо, — говорит купец, — по рукам, но смотри не обмани. Деньги будешь приносить каждое-утро в 7 часов, а если опоздаешь, то наш уговор теряет силу

- Ладно, купец, будь по-твоему, но смотри и ты не обмани. Если не выдержишь уговора 30 дней, то вернешь все, что я тебе уплачу.

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

И действительно, утром в 7 часов человек уже стучал в дверь дома купца.

Я принес тебе деньги, купец. Давай мне, что причитается по уговору.

Взял купец 50 000 рублей, уплатил человеку 1 копейку и радуется: вот чудак-человек, деньги ему девать некуда.

На следующее утро опять в 7 часов человек постучал в дом купца.

— Вставай, купец, я принес тебе деньги! Плати и ты мне, как полагается по уговору, вдвое больше прежнего, и я пойду. У меня еще дел много.

Взял купец 50 000 рублей, а взамен отдал 2 копейки. С тем и ушел человек.

На третье утро история повторилась: человек, уплатив купцу снова 50 000 рублей, получил взамен 4 копейки.

Радуется купец: деньги к нему так и плывут. Шутка ли, за три дня он получил 150 000 рублей, отдав взамен лишь 7 копеек!

Прошло еще двадцать дней, в течение которых каждое утро приходил человек, приносил 50 000 рублей и, забрав у купца свои деньги, уходил. Задумался вдруг купец, что стал он уже много платить за каждые 50 000 рублей. Ведь в двадцать третий день он, получив 50 000 рублей, уплатил незнакомцу 41 943 рубля 4 копейки, а на следующее утро предстояло платить вдвое больше, т.е. 83 886 рублей 8копеек!

—Ну, ничего, — думал купец, — осталось 7 дней до конца нашего уговора, уплачу я человеку все, что полагается, и еще останусь с прибылью:

Было ли суждено оправдаться надеждам купца? Ответ получите, используя компьютер.

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

Школьники для игры разбились на две "партии": на "серьезных", отве­чающих правильно на любой вопрос, и на "шутников", дающих па любой вопрос только неправильные ответы.

Учитель, узнав об этом, спросил у Иванова, серьезный ли он человек или шутник. Не расслышав ответа Иванова, он спросил у Петрова и Сидорова (сидевших рядом с Ивановым и все слышавших): "Что ответил мне Иванов?". Петров сказал: "Иванов ответил, что он серьезный человек". Сидоров же ска­зал: "Иванов ответил, что он шутник". Кем были Петров и Сидоров?

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

Три приятеля: Андрей, Борис и Вадим сидели друг, за другом без головных уборов (см. рис.1), причем Борису и Вадиму было запрещено оглядываться назад, Борис же видел голову сидящего внизу Вадима, а Андрей головы обоих своих приятелей. v:shapes="_x0000_s1026">

Рисунок 1

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

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

Мог ли Вадим на основании ответов своих приятелей определить цвет своей шапки?

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

А теперь решите задачу о приятелях и их шапках, так сказать, в общем виде.

Каждого из юношей спросили, может ли он определить цвет своей шапки. Сможет ли Борис на основе ответа Андрея определить цвет своей шапки? Сможет ли Вадим на основе ответов Андрея и Бориса определить цвет своей шапки? Рассмотрите все возможные варианты.

17.  Логические парадоксы и софизмы

Вы, конечно, знаете, что логика — это наука о формах и законах мышления. Ее законы отражают в сознании человека свойства, связи и отношения объектов окружающего мира. Свое понимание окружающего мира человек формулирует в форме высказываний (суждений, утверждений). Знаете вы и о том, что работа компьютера основана на электронных логических элементах.

Логика — достаточно сложная наука, а человеческий мозг — не ком­пьютер. Ошибиться очень просто, особенно в запутанных логических формулах. Очень часто люди допускают преднамеренные ошибки в своих рассуждениях с целью запутать или ввести в заблуждение собеседника. Такие ошибки называют софизмами.

Вот некоторые из софизмов.

17.1.  2x2 = 5

"Доказательство"

Имеем числовое тождество: 4 : 4 = 5 : 5

Вынесем за скобки общий множитель: 4(1 : 1) = 5(1 : 1)

Числа в скобках равны — их можно сократить. Получим: 4 = 5 (!?).

17.2.  5 = 1

"Доказательство"

Вычтем из обеих частей число 3:5-3 = 1- 3, получим: 2 = -2. Возведя в квадрат обе части последнего равенства, получим: 4=4. Так как последнее выражение справедливо, то справедливо и исходное (5 = 1).

17.3.  2 = 3

"Доказательство"

Возьмем равенство: 4 -10 = 9 - 15.

Прибавив к обеим частям 6¹/₄, получаем:

4 - 10 + 6¹/₄= 9 -15 + 6¹/_4.

Выполним преобразования:

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

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

Извлекая из обеих частей равенства квадратный корень, получим:

2-⁵/₂ =3-⁵/₂

Прибавляя к обеим частям по ⁵/₂, приходим к равенству 2 = 3.

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

"Доказательство".

Начнем с равенства:

a=b+c,

из которого следует, что а больше b при с 0.

Умножив обе его части на а - b, получим ,

a² – ab = ab + ac – b²- bc

Перенесем ас в левую часть:

a² – ab - ac = ab– b²- bc

и разложим на множители:

a(a-b-c)=b(a-b-c)

Разделив обе части равенства на a-b-c, найдем

a=b,

что и требовалось доказать.

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

"Доказательство" v:shapes="_x0000_s1027">

Обозначим вес слона с, вес комара — k. Запишем равенство с + k= 2ν, (1) Действительно, такое число ν всегда существует. Например, при условных значениях с = 5000 кг и k =0,0000001 кг оно равно 2500,00000005 кг. Из равенства (1) можно получить два других:

с - 2ν = - k ,

c = 2ν - k .

Умножим левые и правые части этих равенств:

Рисунок 2

с² - 2νc = k² - 2νk.

Добавим к обеим частям полученного равенства ν².

с² - 2νc+ ν² = k² - 2νk + ν²

Можем записать:

(с - ν)² = (k - ν)².

Извлекая квадратный корень из обеих частей равенства, получим:

с - ν = k - ν.

Или, с = k ν. т.е., вес слона равен весу комара!

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

В стишке, взятом из одного английского журнала, выходившего в XIX веке, рассказывается о хитром хозяине гостиницы, сумевшем разместить в девяти комнатах десять гостей так, что каждому из них досталось по отдельной комнате:

Их было десять чудаков,

Тех спутников усталых,

Что в дверь решили постучать

Таверны "Славный малый".

— Пусти, хозяин, ночевать,

Не будешь ты в убытке,

Нам только ночку переспать,

Промокли мы до нитки.

Хозяин тем гостям был рад,

Да вот беда некстати: .

Лишь девять комнат у него

И девять лишь кроватей.

– Восьми гостям я предложу .

Постели честь по чести,

А двум придется ночь проспать

В одной кровати вместе.

Лишь он сказал, и сразу крик,

От гнева красны лица:

Никто из всех десятерых .

Не хочет потесниться.

Как охладить страстей тех пыл,

Умерить те волненья?

Но старый плут хозяин был

И разрешил сомненья.

Двух первых путников пока,

Чтоб не судили строго,

Просил пройти он в номер "А"

И подождать немного

Спал третий в "Б", четвертый в "В",

В "Г" спал всю ночь наш пятый,

В "Д","Е", "Ж", "3" нашли ночлег

С шестого по девятый.

Потом, вернувшись снова в "А",

Где ждали его двое,

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

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

Хоть много лет с тех пор прошло,

Неясно никому,

Как смог хозяин разместить

Гостей по одному.

Иль арифметика стара,

Иль чудо перед нам,

Понять, что, как и почему,

Вы постарайтесь сами.

Найдите ошибки во всех приведенных софизмах.

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

Парадокс "Куча"

Разница между кучей и не кучей — не в одной песчинке. Пусть у нас есть куча (например, песка). Начнем брать из нее каждый раз по одной песчинке, и куча останется кучей. Продолжим процесс. Если 100 песчинок — куча, то 99 — тоже куча, …, 10 песчинок —  куча, то 9 — тоже куча, ..., 3 пес­чинки — куча, 2 — куча, 1 —куча(!?).

Суть парадокса в том, что постепенные количественные изменения (убывание на одну песчинку) не приводят к качественным изменениям.

Задание для самостоятельной работы. Сформулируйте парадокс "Лысый", аналогичный парадоксу "Куча"

Парадокс "Мэр города"

Каждый мэр живет или в своем городе, или вне его. Был издан приказ о выделении одного специального города, где жили бы только мэры, не живущие в своем городе. Естественно, у этого города тоже есть мэр. Где должен жить мэр этого города?

Если он хочет жить в отведенном городе, то он не может это сделать, так. как там живут только мэры, не живущие в своем городе.

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

Итак, он не может жить ни в своём городе, ни вне его.

Задание для самостоятельной работы. Закончите два следующих парадокса.

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

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

Если... .          .

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

Книжные каталоги (перечень книг и других каталогов) подразделяются на два рода:

1)      такие, которые в числе перечисляемых каталогов не упоминают себя (нормальные).

2)      такие, которые сами входят в число перечисляемых каталогов (ненор­мальные).

Библиотекарю дается задание составить каталог всех нормальных и только нормальных каталогов. Должен ли он при составлении своего каталога упомянуть составленный им?

Если...           

18.  Невидимая сумма

Подготовьте лист электронной таблицы Microsoft Excel следующего вида (см. табл. 1).

В ячейки D1 и В5 введите формулу =В1, в ячейки D2 и В6 — формулу =В2, в ячейки ВЗ, D3 и В7 соответственно формулы =В1+В2, =D1-D2 и =В5*В6. Затем выполните следующие действия:

1)      установите указатель активной ячейки на ячейку ВЗ;

Таблица 1

	A	B	C
1	Введите первое число		Первое число:
2	Введите второе число		Второе число:
3	Их сумма:		Их разность:
4
5	Первое чмсло:
6	Второе число:
7	Их произведение:

2)      в главном меню программы выберите пункт Формат, а в нем — под­пунктЯчейки;

3)      в появившемся диалоговом окне Форматы ячеек (см. рис. 3) в спискеЧисловые форматы выберите строку (все форматы), в поле Тип введите три символа ";" (;;;), после чего щелкните кнопку ОК.

вил

Теперь, после ввода значений в ячейки В1 и В2, в ячейках С3 и В7 будут выведены соответственно разность и произведение введенных чисел, а ячейка ВЗ будет пустая, хотя в строке формул для нее будет отображаться введенная ранее формула. Это объясняется тем, что для этой ячейки задан так называе­мый "пустой пользовательский формат" (помните три символа ";")

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

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

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

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

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

Почему задача с этой игрой названа задачей-шуткой?

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

Антиквар приобрел 99 одинаковых по виду старинных монет. Ему сообщили, что одна из монет фальшивая и что она легче настоящих (все настоящие весят одинаково).

1.             Как, используя чашечные весы без гирь, не более чем за 5 взвешива­ний выявить фальшивую монету?

2.             Как выявить фальшивую монету за 7 взвешиваний при условии, вы­двинутом антикваром, — не взвешивая никакую монету более двух раз?

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

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

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

Литература:

Д.М. Златопольский. Занимательные задачи по информатике. (Библиотечка "Первого сентября", серия "Информатика". Вып. 22 ). Москва. ООО "Чистые пруды", 2009