|
|
Устная олимпиада "Открытие"
5-7 класс (май 2014 года)
Задачи
Задача 1. Столбовые шашки
- Первоначально на каждом поле доски стоит шашка (иначе говоря, столбик из одной шашки).
Очередным ходом можно взять любой столбик и прыгнуть им (в пределах доски) по горизонтали
или вертикали на столько клеток, сколько в нём шашек. Например, столбик из одной шашки
может прыгнуть только на соседнюю клетку. Если при этом столбик попадёт на непустую клетку,
он становится на стоящий там столбик и объединяется с ним.
- Цель — собрать все шашки в одной клетке доски.
- 1.1. Соберите на доске 1×6 все шашки в один столбик.
- 1.2. Соберите на доске 1×6 все шашки в один столбик на крайней клетке.
- 1.3. Соберите на доске 1×20 все шашки в один столбик на крайней клетке за 19 ходов.
- 1.4. Докажите, что на доске 1×20 все шашки можно собрать в один столбик на любой клетке доски за 19 ходов.
- 1.5. Докажите, что на доске 5×5 цель достижима не менее чем за 24 хода.
- 1.6. Докажите, что на доске 5×5 цель достижима не менее чем за 25 ходов.
- 1.7. За какое наименьшее число ходов можно достигнуть цели на доске 5×5?
Задача 2. Выстроить ладьи
- На доске n×n стоит n ладей. За один ход любую ладью можно переместить на любую свободную клетку
в ее столбце или строке, не перепрыгивая при этом через другие ладьи.
- Цель — расставить ладьи так, чтобы они не били друг друга. Будем выяснять, какого наименьшего количества ходов достаточно для достижения этой цели.
- 2.1. На доске 6×6 стоят 6 ладей, образуя в углу прямоугольник 2×3. Как достигнуть цели за 7 ходов?
- 2.2. На доске 9×9 стоят 9 ладей. Как достигнуть поставленной цели, сделав не более 36-ти ходов?
- Пару ладей назовём соседними, если они бьют друг друга, а «сложностью» расстановки ладей — количество пар соседних ладей.
- 2.3. Докажите, что за один ход сложность расстановки либо не меняется, либо меняется не более чем на 1.
- 2.4. За какое наименьшее количество ходов из расстановки, показанной на рисунке справа, можно достигнуть цели?
- 2.5. На доске n×n ладьи стоят так, что есть свободная строка и есть свободный столбец. Как выбрать такую ладью, что её ход на свободную линию уменьшит сложность расстановки?
- 2.6. На доске n×n стоят n ладей так, что есть свободная строка, но нет свободных столбцов. Докажите, что на свободную строку можно сдвинуть ладью так, что уменьшится сложность расстановки.
- 2.7. Докажите, что если сложность расстановки ладей равна S, то минимальное число ходов для достижения цели равно S.
Задача 3. Решить тест
- Тестовый тур олимпиады состоит из нескольких вопросов, на каждый надо ответить «да» или «нет». За одну попытку можно ответить на все вопросы, после чего сообщают, на сколько вопросов отвечено верно.
- Цель — правильно ответить на все вопросы после нескольких попыток.
- 3.1. Пусть в олимпиаде 5 вопросов, причём известно, что среди них ровно два верных ответа «нет». Как достигнуть цели за 10 попыток?
- 3.2. Пусть в олимпиаде 5 вопросов, но про верные ответы ничего не известно. Как достигнуть цели за 11 попыток?
- 3.3. Пусть в олимпиаде 10 вопросов, причём известно, что среди верных ответов ровно три ответа «нет». Как достигнуть цели за 11 попыток?
- 3.4. Пусть в олимпиаде 10 вопросов, причём известно, что среди верных ответов ровно три ответа «нет». Как достигнуть цели за 10 попыток?
- 3.5. Пусть в олимпиаде 5 вопросов. Как достигнуть цели за 5 попыток?
- 3.6. Пусть в олимпиаде 30 вопросов. Как за 5 попыток узнать верные ответы в первых пяти вопросах?
- 3.7. Пусть в олимпиаде 30 вопросов, но про верные ответы ничего не известно. Как достигнуть цели за 25 попыток?
|
