МАЛЫЙ МЕХМАТ МГУ

Кружок 7 класса

Руководитель Степан Львович Кузнецов
2011/2012 учебный год

Занятие 25 (21 апреля 2012 года). Лабиринт

В процессе игры «Лабиринт» школьнику нужно два раза обойти пять аудиторий, в каждой из которых предлагаются задачи на разные темы (геометрия, игры, комбинаторика, «логика», инвариант) — на первом круге попроще, на втором посложнее; предусмотрены также ещё более сложные дополнительные задачи. Если школьник не справился с задачей, он не может двигаться дальше по кругу прежде, чем посетит специальную аудиторию «Реанимация» и решит там простую задачу или головоломку.

Геометрия

1-й круг

1.
Можно ли квадратный лист бумаги 3×3 сложить так, чтобы после одного прямолинейного разреза он распался на квадраты 1×1?
2.
В неравнобедренном треугольнике длины всех сторон выражаются целым числом сантиметров. Каким, самое меньшее, может быть периметр такого треугольника?
3.
Пятиклассник Петя нарисовал 5 рисунков. На каждом рисунке он изобразил несколько прямых и отметил все их точки пересечения друг с другом. В результате на первом рисунке он отметил всего 1 точку, на втором — 2, на третьем — 3, на четвертом — 4 и на пятом — 5.
а)
Приведите примеры таких рисунков.
б)
Про какие из Петиных рисунков можно наверняка сказать, сколько на них проведено прямых?
4.
На середине ребра молочного пакета (в форме правильного тетраэдра, такие пакеты для молока были распространены в СССР) сидит паук, которому необходимо добраться до середины противоположного ребра. Как ему это сделать за наименьшее время?

2-й круг

1.
Точка M лежит внутри треугольника ABC. Сравните углы ABC и AMC.
2.
Квадрат 40×40 разбит на клетки 1×1. Какое наибольшее число клеток может разрезать прямая, пересекающая этот квадрат?
3.
Точка M лежит внутри треугольника ABC. Что больше: AM + MC или AB + BC?
4.
Верно ли, что из любых 10 отрезков найдутся три, из которых можно составить треугольник?
5.
Разрежьте остроугольный треугольник на три трапеции (подразумевается, что нужно уметь резать всякий остроугольный треугольник, а не один конкретный).

Дополнительные задачи

1.
Отрезки AB и CD длины 1 пересекаются в точке O, причем ∠AOC = 60°. Докажите, что AC + BD ≥ 1.
2.
В прямоугольник вписан четырёхугольник (на каждой стороне прямоугольника по одной вершине четырёхугольника). Докажите, что периметр четырёхугольника не меньше удвоенной диагонали прямоугольника.
3.
На окружности радиуса 1 отмечено 100 точек. Докажите, что на окружности найдется такая точка, для которой сумма расстояний от неё до всех отмеченных точек будет не меньше 100.
4.
Дана замкнутая ломаная, причем любая другая замкнутая ломаная с теми же вершинами имеет большую длину. Докажите, что эта ломаная несамопересекающаяся.
5.
На плоскости даны n красных и n синих точек, никакие три из которых не лежат на одной прямой. Докажите, что можно провести n отрезков с разноцветными концами, не имеющих общих точек.

Игры

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

1-й круг

1.
На доске 4×4 в левом нижнем углу стоит король. Его по очереди двигают двое, причем разрешены только ходы вверх, вправо и вверх-вправо. Проигрывает тот, кто не сможет сходить.
2.
Есть 30 камней. Два игрока по очереди берут от 1 до 10 камней. Выигрывает тот, кто берёт последний камень.
3.
Двое по очереди ломают шоколадку 6×8. За ход разрешается сделать прямолинейный разлом любого из кусков вдоль углубления. Проигрывает тот, кто не сможет сделать ход.
4.
Имеется две кучки камней по 7 в каждой. За ход разрешается взять любое количество камней, но только из одной кучки. Проигрывает тот, кому нечего брать.
5.
Числа от 1 до 20 выписаны в строчку. Игроки по очереди расставляют между ними плюсы и минусы. После того, как все места заполнены, подсчитываем результат. Если он чётен, то выигрывает первый игрок, если нечётен, то второй.

2-й круг

1.
Есть две кучки камней: в одной 25, в другой 30 камней. Можно или взять сколько угодно камней из одной кучки, или равное число камней из обеих кучек. Проигрывает тот, кто не может сделать ход.
2.
На окружности есть 20 точек. Два игрока по очереди соединяют две точки отрезком, причём нельзя пересекать уже проведённые отрезки. Проигрывает тот, кто не сможет сделать ход.
3.
Двое по очереди ставят шахматных слонов в клетки доски 8×8 так, чтобы слоны не били друг друга. Проигрывает тот, кто не может сделать ход. Кто выигрывает?
4.
В игре «Кто первым назовёт число 100» участвуют двое. Один называет любое целое число от 1 до 9 включительно. Второй прибавляет к названному числу любое целое число от 1 до 9 и называет сумму. К этой сумме первый снова добавляет любое целое число от 1 до 9, и называет новую сумму. Выигрывает тот, кто назовёт число 100.
5.
Два игрока по очереди проводят прямые на плоскости. Каждый делает по 4 хода. Первый игрок выигрывает, если эти прямые разбивают плоскость на чётное число частей, а второй — если на нечётное.

Дополнительные задачи

1.
Играют двое. В начале игры есть одна палочка. Первый игрок ломает эту палочку на две части. Далее игроки по очереди ломают на две части любую палочку из имеющихся к данному моменту. Если, сломав палочку, игрок может сложить из всех имеющихся палочек один или несколько отдельных треугольников (каждый — ровно из трёх палочек), то он выиграл. Кто из игроков (первый или второй) может обеспечить себе победу независимо от действий другого игрока?
2.
У Коли и Оли есть по верёвке. Сначала Коля разрезает свою верёвку на три части, затем Оля разрезает на три части свою. Если из полученных шести кусков два треугольника (каждый кусок — сторона треугольника), то выигрывает Оля, иначе — Коля.

Комбинаторика

1-й круг

1.
На плоскости дано n точек. Сколько имеется отрезков с концами в этих точках?
2.
На столе лежат 5 яблок и 4 груши. Сколькими способами можно взять два разных фрукта?
3.
Сколькими способами можно раскрасить грани тетраэдра (треугольной пирамиды) в четыре цвета? (Тетраэдр разрешается поворачивать.)
4.
Бусы — это кольцо, на которое нанизаны бусины. Сколько различных бус можно составить из 10 одинаковых красных бусин и двух одинаковых синих бусин?
5.
Сколькими способами можно поселить 7 студентов в три комнаты: одноместную, двухместную и четырехместную?

2-й круг

1.
Каких пятизначных чисел больше: не делящихся на 5 или тех, у которых ни первая, ни вторая цифра слева — не пятёрка?
2.
Сколько существует 10-значных чисел, в которых имеется хотя бы 2 одинаковые цифры?
3.
Сколько существует шестизначных чисел, в записи которых хотя бы одна четная цифра?
4.
Сколькими способами можно раскрасить грани куба в 6 цветов?
5.
Сколькими способами можно разложить 9 орехов по трём карманам? (Карманы разные, а орехи одинаковые.)

Дополнительная задача

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

«Логика»

1-й круг

1.
Пять первоклассников стояли в шеренгу и держали 37 флажков. У всех справа от Таты — 14 флажков, справа от Яши — 32, справа от Веры — 20, справа от Максима — 8. Сколько флажков у Даши?
2.
В корзине лежат 30 грибов — рыжиков и груздей. Известно, что среди любых 12 грибов имеется хотя бы один рыжик, а среди любых 20 грибов — хотя бы один груздь. Сколько рыжиков и сколько груздей в корзине?
3.
Учитель задал замысловатую задачу. В результате количество мальчиков, решивших эту задачу, оказалось равным количеству девочек, ее не решивших. Кого в классе больше — решивших задачу или девочек?
4.
Является ли старейший шахматист среди музыкантов старейшим музыкантом среди шахматистов? Является ли лучший шахматист среди музыкантов лучшим музыкантом среди шахматистов?
5.
Назовём занятие Малого Мехмата лёгким, если в каждой аудитории найдётся человек, который решил все задачи. Сформулируйте определение сложного занятия.
6.
Один из попугаев А, В и С всегда говорит правду, другой всегда врёт, а третий хитрец — иногда говорит правду, иногда врёт. На вопрос «Кто В?» они ответили:
А: — Лжец.
В: — Я хитрец!
С: — Абсолютно честный попугай.
Кто из попугаев лжец, а кто хитрец?
7.
Среди математиков каждый седьмой — философ, а среди философов каждый девятый — математик. Кого больше: философов или математиков?

2-й круг

1.
12 кандидатов в мэры рассказывали о себе. Через некоторое время один сказал: «До меня соврали один раз». Другой сказал: «А теперь — дважды». «А теперь — трижды», — сказал третий, и так далее до 12-го, который сказал: «А теперь соврали 12 раз». Тут ведущий прервал дискуссию. Оказалось, что по крайней мере один кандидат правильно посчитал, сколько раз соврали до него. Так сколько же всего раз соврали кандидаты?
2.
Есть 100 коробок, пронумерованных числами от 1 до 100. В одной коробке лежит приз и ведущий знает, где он находится. Зритель может послать ведущему пачку записок с вопросами, требующими ответа «да» или «нет». Ведущий перемешивает записки в пачке и, не оглашая вслух вопросов, честно отвечает на каждый из них. Какое количество записок нужно послать, чтобы наверняка узнать, где находится приз?
3.
Юра, Лёша и Миша коллекционируют марки. Количество марок, которых нет у Лёши, меньше, чем количество марок, которые есть и у Юры, и у Лёши. Точно так же, число Лёшиных марок, которых нет у Миши, меньше, чем число марок, которые есть и у Лёши и у Миши. А число Мишиных марок, которых нет у Юры, меньше, чем число марок, которые есть и у Юры и у Миши. Докажите, что какая-то марка есть у каждого из трех мальчиков.

Дополнительные задачи

1.
В магазине есть 3 компьютера: американский, который всегда отвечает правду, китайский, который всегда врёт, и русский, который отвечает что попало. Перед покупкой разрешается задать один вопрос любому одному компьютеру. Можно ли задать такой вопрос, чтобы обязательно купить а) не китайский; б) не русский компьютер?
2.
Часть жителей некого острова всегда говорят правду, остальные — всегда лгут. Путешественник, оказавшийся на острове, в совершенстве владеет языком островитян, только не помнит, какое из двух слов «пиш» и «таш» означает «да», а какое — «нет». Путешественник дошёл до места, где дорога раздваивалась, причём одна из дорог ведёт в деревню, а другая — в болото. На распутье он встретил аборигена. Сможет ли путешественник, задав всего один вопрос (предполагающий ответ «да» или «нет», т. е. «пиш» или «таш»), узнать, какая из двух дорог ведёт в деревню?

Инварианты

1-й круг

1.
В языке Древнего Племени алфавит состоит всего из двух букв: «М» и «О». Два слова являются синонимами, если одно из другого можно получить при помощи исключения или добавления буквосочетаний «МО» и «ООММ», повторяемых в любом порядке и любом количестве. Являются ли синонимами в языке Древнего Племени слова «ОММ» и «МОО»?
2.
Можно ли мышкой обойти доску 5×7 без центральной клетки? В каждой клетке доски нужно побывать ровно по одному разу, передвигать мышку можно только в соседнюю по стороне клетку.
3.
На доске написаны числа 1, 2, 3, …, 19, 20. Разрешается стереть любые два числа a и b и вместо них написать число a + b − 1. Какое число может остаться на доске после 19 таких операций?

2-й круг

1.
На столе лежит куча из 637 ракушек. Из нее убирают одну ракушку и кучу делят на две (не обязательно поровну). Затем из какой-нибудь кучи, содержащей больше одной ракушки, снова убирают одну ракушку и снова кучу делят на две. И так далее. Можно ли через несколько ходов оставить на столе только кучи, состоящие из трех ракушек? Если можно, то сколько нужно для этого сделать ходов и сколько куч получится?
2.
На доске написаны числа 30 и 44. За один ход игрок дописывает ещё одно натуральное число — разность (положительную) любых двух, уже написанных, если она ещё не встречалась. Проигрывает тот, кто не может сделать ход.
3.
В 50 коробках лежат 100 конфет. Девочка и мальчик берут поочерёдно по конфете, начинает девочка. Может ли мальчик добиться того, чтобы последние две конфеты лежали в одной коробке?

Дополнительные задачи

1.
В каждой из n стран правит либо партия правых, либо партия левых. Каждый год в одной из стран A может поменяться власть. Это может произойти в том случае, если в большинстве граничащих со страной А стран правит не та партия, которая правит в стране А. Докажите, что смены правительств не могут продолжаться бесконечно.
2.
Можно ли доску размерами 4 × N обойти ходом коня, побывав на каждом поле ровно один раз, и вернуться на исходное поле?
3.
Дан выпуклый 2m-угольник A1...A2m. Внутри его взята точка P, не лежащая ни на одной из диагоналей. Докажите, что точка P принадлежит чётному числу треугольников с вершинами в точках A1,…, A2m.

«Реанимация»

1.
Какие из приведённых слов имеют ось симметрии: ТОПОТ, СОН, СЕНО, ВЕС, ТОН, ЭХО, СОСНА, СОК?
2.
В одном литре воды содержится 0,00001 миллиграммов золота. Сколько килограммов золота содержится в 1 км3 морской воды?
3.
Маша нарисовала на экране компьютера букву Ы, а потом нажала последовательно три кнопки: «повернуть на 90° по часовой стрелке», «заменить на зеркальное изображение» и «повернуть на 180°». Какую картинку она увидит?
4.
Среди четырёх людей нет трёх с одинаковым именем, или с одинаковым отчеством, или с одинаковой фамилией, но у каждых двух совпадает или имя, или отчество, или фамилия. Может ли такое быть?
5.
Пять мальчиков нашли 9 грибов. Докажите, что хотя бы двое из них нашли равное количество грибов.
6.
Докажите, что произведение любых трёх подряд идущих натуральных чисел делится на 6.
7.
Замените в записи 645*485* звёздочки цифрами так, чтобы полученное число делилось на 15.
8.
Дядька Черномор написал на листке бумаги число 20. Тридцать три богатыря передают листок друг другу, и каждый или прибавляет к числу или отнимает от него единицу. Может ли в результате получиться число 10?
9.
За сутки до дождя Петин кот всегда чихает. Сегодня кот чихнул. «Завтра будет дождь», — подумал Петя. Прав ли он?
10.
Что больше: 2010/2011 или 2011/2012?
11.
У Кости есть 10 палочек длиной 50 см. Он хочет распилить их так, чтобы получилось 50 палочек длиной 10 см. Сколько распилов ему придется сделать?
12.
Разрежьте прямоугольник 3×9 на восемь квадратов.