Тема: Построение простейших алгоритмов.

Раздаточный материал

Задача  №1

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

Задача №2

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

Задача №3

Дана клетчатая таблица 99*99, каждая клетка которой окрашена в черный или в белый цвет. Разрешается одновременно перекрасить все клетки некоторого столбца или некоторой строки в тот цвет, клеток которого в этом столбце или в этой строке до перекрашивания было больше. Всегда ли можно добиться того, чтобы все клетки таблицы стали покрашены в один цвет?

Задача №4

Каждую из трех котлет нужно пожарить на сковороде с двух сторон в течение пяти минут каждую сторону. На сковороде умещается только две котлеты. Можно ли сжарить все три котлеты быстрее, чем за 20 минут (временем на переворачивание и перекладывание котлет пренебрегаем)?

Задача №5

Как отмерить 15 минут, пользуясь песочными часами на 7 минут и на 11 минут?

Задача №6

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

Задача №7

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

Задача №8

Шоколадка имеет размер 4*10 плиток. За один ход разрешается разломать один из уже имеющихся кусочков на два вдоль прямолинейного разлома. За какое наименьшее число ходов можно разбить всю шоколадку на кусочки размером в одну плитку?

Задача №9

Нужно узнать пятизначный номер телефона, задавая вопросы, на которые возможен ответ "да" или "нет". За какое наименьшее число вопросов это гарантированно можно сделать (при условии, что на вопросы даются правильные ответы)?

Задача №10

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

Задача №11

В одной урне лежат два белых шара, в другой два черных, в третьей - один белый и один черный. На каждой урне висела табличка, указывающее ее содержимое: ББ, ЧЧ, БЧ. Некто перевесил таблички так, что теперь каждая табличка указывает содержимое урны неправильно. Разрешается вынуть шар из любой урны, не заглядывая в нее. Какое наименьшее число извлечений потребуется, чтобы определить состав всех трех урн?

Задача №12

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

Задача №13

Вычислительная машина умеет выполнять только одну операцию: a*b=1-a/b. Как выполнить с помощью этой машины все четыре арифметических действия?

Задача №14

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

Задача №15

Есть три бидона емкостью 14 л, 9 л и 5 л. В большем бидоне 14 литров молока, остальные бидоны пусты. Как с помощью этих сосудов разлить молоко пополам?

Задача №16

Неуловимый Джо никогда не проигрывает на рулетке больше четырех раз подряд и никогда не ставит больше 10 долларов. Как ему выиграть 1000 долларов? (В случае выигрыша на рулетке возвращается удвоенная ставка; вначале Джо имеет 100 долларов.)

Задача №17

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

Задача №18

Несколько камней весят вместе 10 т, при этом каждый из них весит не более 1 т. 1) Докажите, что этот груз можно за один раз увезти на пяти трехтонках. 2) Приведите пример набора камней, удовлетворяющих условию, для которых четырех трехтонок может не хватить, чтобы увезти груз за один раз.

Задача №19

Семья ночью подошла к мосту. Папа может перейти его за 1 минуту, мама за 2, малыш - за 5, а бабушка - за 10 минут. У них есть один фонарик. Мост выдерживает только двоих. Как им перейти мост за 17 минут? (Если переходят двое, то они идут с меньшей из их скоростей. Двигаться по мосту без фонарика нельзя. Светить издали нельзя. Носить друг друга на руках нельзя. Кидаться фонариком нельзя.)

Задача №20

На международный конгресс приехало 578 делегатов из разных стран. Любые три делегата могут поговорить между собой без помощи остальных (при этом, возможно, одному из них придется переводить разговор двух других). Докажите, что всех делегатов можно поселить в двухместных номерах гостиницы таким образом, чтобы любые двое, живущие в одном номере, могли поговорить без посторонней помощи.

Задача №21

На столе - куча из 1001 камня. Ход состоит в том, что из какой-либо кучи, содержащей более одного камня, выкидывают камень, а затем одну из куч делят на две. Можно ли через несколько ходов оставить на столе только кучки, состоящие из трех камней?

Задача №22

Один человек задумал 10 натуральных чисел - x₁, x₂, ... , x₁₀. Другой отгадывает их. Разрешается задавать вопросы вида: "чему равна сумма a₁x₁+a₂x₂+...+a₁₀x₁₀?", где a₁, a₂, ... , a₁₀ - некоторые натуральные числа. Как за 2 вопроса узнать все загаданные числа?

Задача №23

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

Задача №24

Переаттестация Совета Мудрецов из n мудрецов происходит так: король выстраивает их в колонну по одному и надевает на голову каждому колпак белого или черного цвета. Каждый мудрец видит цвета колпаков всех впереди стоящих мудрецов, но не видит цвет своего колпака и цвета колпаков мудрецов, стоящих сзади него. Затем мудрецы по одному называют какой-нибудь цвет (каждому разрешается говорить ровно один раз; то, что говорит один мудрец, слышат все). После этого король казнит всех мудрецов, назвавших цвет, отличный от цвета своего колпака. Накануне переаттестации все члены Совета договорились между собой и придумали, как минимизировать число казненных. Скольким из них гарантированно удастся избежать казни?

Задача №25

На табло горят несколько лампочек. Имеется несколько кнопок. Кнопка меняет состояние лампочек, с которыми она соединена. Известно, что, для любого набора лампочек найдется кнопка, соединенная с нечетным числом лампочек из этого набора. Докажите, что нажимая на кнопки можно погасить все лампочки.

Задача №26

Лабиринтом называется клетчатый квадрат 10*10, некоторые пары соседних узлов в котором соединены отрезком - "стеной" таким образом, что переходя из клетки в соседнюю по стороне клетку и не проходя через стены, можно посетить все клетки квадрата. Границу квадрата будем также считать обнесенной стеной. В некоторой клетке некоторого лабиринта стоит робот. Он понимает 4 команды - Л, П, В, Н, по которым соответственно идет влево, вправо, вверх и вниз, а если перед ним "стена", то стоит на месте. Как написать программу для робота, выполняя которую он обойдет все клетки независимо от лабиринта и от своего начального положения?

Задача №27

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

Задача №28

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

Задача №29

Написанное на доске четырехзначное число можно заменить на другое, прибавив к двум его соседним цифрам по единице, если ни одна из этих цифр не равна 9; либо, вычтя из соседних двух цифр по единице, если ни одна из них не равна 0. Можно ли с помощью таких операций из числа 1234 получить число 2002?

Задача №30

На экране терминала с доступом к "Матрице" горит число, которое каждую минуту увеличивается на 102. Начальное значение числа 123. Хакер Нео имеет возможность в любой момент изменять порядок цифр числа, находящегося на экране. Может ли он добиться того, чтобы число никогда не стало четырехзначным? Добившись этого, он зациклит действия агентов и спасет своих друзей.