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

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

Листок 1

1.

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

2.

Есть n одинаковых монет, из которых ровно одна фальшивая (легче остальных). Какое наименьшее число взвешиваний на чашечных весах без гирь потребуется, чтобы выделить фальшивую монету, если а) n=3, б) n=9, в) n=27, г) n=3^k (k — натуральное число), д) n — произвольное натуральное число?

3.

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

4.

Имеется 100 мешков по 1000 монет в каждом. Известно, что в 99 мешках монеты настоящие, а в одном — фальшивые. Настоящая монета весит 10 г, а фальшивая — 9 г. За какое наименьшее количество взвешиваний на электронных весах можно определить мешок с фальшивыми монетами? (Электронные весы позволяют определить вес произвольного набора монет)

5.

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

6.

Какое наибольшее число а) ладей, б) королей можно поставить на шахматную доску так, чтобы никакие 2 из них не били друг друга?

7.

На поле а) 8 × 8, б) 9 × 9 для игры в ,,морской бой'' стоит один четырёхпалубный корабль. Какое минимальное число выстрелов надо произвести, чтобы наверняка его ранить?

8.

В каждой клетке доски 5 × 5 сидит жук. По свистку каждый из жуков переползает в одну из соседних (по горизонтали или по вертикали) клеток. Докажите, что при этом хотя бы одна клетка освободится.

9.

В каждой клетке доски 9 × 9 сидит жук. По свистку каждый из жуков переползает в одну из соседних по диагонали клеток. Докажите, что при этом пустых клеток будет не меньше 9.

10.

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