ОЛ ВЗМШ при МГУ: Отделение математики

Подсказки

Подсказка к 436 б) - похожая задача. Чётов пишет на доске одно целое число, а затем Нечётов - другое. Если их сумма чётна, то победителем объявляется Чётов, если нечётна, то Нечётов. Может ли  один из них играть так, чтобы непременно выиграть?

Решение. Предположим, что Чётов назвал четное число. Тогда, чтобы  выиграть, Нечётову достаточно назвать нечётное число, например, 1. Если же Чётов назвал нечётное число, то Нечётов выиграет, назвав чётное число, например, 0. Таким образом, алгоритм,  всегда приводящий к выигрышу в этой игре есть у Нечётова.

Подсказка к  задачам 490 и 493 - похожая задача 494.

494. Даны числа 1, 2, 3,4,5,6. Разрешено к любым двум из них прибавить по единице. Можно ли за несколько шагов уравнять эти числа?

Решение. Прибавление к числу единицы меняет его чётность. Прибавление по 1 к двум числам меняет чётность двух чисел. Если это были два чётных числа, то чётных

чисел станет на два меньше, если два нечётных, то чётных станет на два больше. А если одно было чётное, а другое нечётное, то количество чётных чисел не изменится. В любом случае чётность числа чётных чисел не изменится. Другими словами, здесь чётность числа чётных чисел - инвариант. Но если в шестерке все числа станут одинаковые, чётных среди них станет 0 или 6 - чётное число.

Ответ. Нельзя.

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

Подсказка к 448. Найдите инвариант.

450. В забеге участвовали 3 бегуна: Иванов, Петров и Сидоров. Перед забегом 4 болельщика дали такие 4 прогноза:

1. Победит Иванов.
2. Сидоров обгонит Петрова.
3. Петров финиширует следующим после Иванова.
4. Сидоров не  победит.

После забега оказалось, что среди прогнозов было чётное число верных. В каком порядке финишировали бегуны?

Подсказка. Поскольку трудно делать какие-либо выводы, не зная, какие именно прогнозы верны, советую попробовать решить задачу полным перебором, тем более что перебрать придётся всего 6 вариантов (3 варианта победителя комбинируются с двумя вариантами того, кто из остальных участников на втором месте). Заполните самостоятельно таблицу. Варианты будем обозначать тройками, состоящими из первых букв фамилий. Победителя записываем на первом слева месте, прибежавшего последним - на последнем слева.

458. Мышка грызёт куб сыра с ребром 3, разбитый на 27 единичных кубиков. Когда мышка съедает какой-либо кубик, она переходит к кубику, имеющему общую грань с предыдущим. Может ли мышка съесть весь куб, кроме центрального кубика? А если бы куб имел размеры 13*13*13?

Подсказки. Прежде всего , полезно мысленно раскрасить кубики по принципу шахматной доски, то есть так, чтобы все кубики, имеющие общую грань с чёрным кубиком были белыми и наоборот. Чтобы задача стала "плоской", полезно ра зрезать куб (мысленно) на 3 горизонтальных слоя и изобразить их так, как они выглядят на  виде сверху.

.                           

Нижний слой	Средний слой	Верхний слой.

Подсчитайте, сколько всего чёрных и сколько белых кубиков в кубах 3*3 и 13*13  , если не считать центральный кубик. Сделайте выводы. В том случае, если вывод о невозможности делать рано, попытайтесь доказать "Может". Для этого попытайтесь найти и нарисовать на слоях правильный путь мыши. Не забывайте, что когда мышка переходит из слоя в слой, она переходит в кубик, лежащий точно над или точно под исходным.

Задача, похожая на 466. На окружности взяты 4 точки. Можно ли так построить несколько треугольников с вершинами в этих точках, чтобы каждый отрезок с концами в двух из этих точек стал стороной ровно одного из этих треугольников.

Решение. Приведём такой способ решения, который полезен и для большего числа точек, например, для ста точек. Обозначим точки буквами A,B,C,D.Через точку А нужно провести 3 отрезка. (Обратим внимание на то. что это число нечётное.) Но в каждом треугольнике с вершиной А чётное число (две) сторон, выходящих из А. Значит требуемое построение невозможно.

471. Можно ли из пяти фигур

сложить прямоугольник размером 4*5?

Подсказки. Немного переформулируем задачу: можно ли разрезать прямоугольник 4*5 на такие пять фигур?

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

Подсказка к 472. Прочтите подсказки к 458. 476. На какое наименьшее  число прямоугольников можно разрезать данную фигуру?

рис.

Подсказки.

Прежде всего, раскрасьте доску. Обратите внимание, что чёрных квадратиков намного меньше, чем белых (голубых). На сколько именно? Теперь заметим, что в каждом прямоугольнике чёрных квадратиков либо столько же, сколько белых, либо на один меньше или больше. Заметьте, что это верно и для одноклеточных прямоугольников. Значит, число прямоугольников не может быть меньше разности чисел белых и чёрных квадратиков. Поэтому если нам удастся разбить фигуру на  24-9=15 прямоугольников, то задача будет решена.(А если нет, то придётся искать какие-то доводы в пользу того, что прямоугольников не может получиться меньше 16.) Попробуйте это сделать. Чтобы не гадать при этом впустую, подумайте, сколько всего должно получиться прямоугольников, имеющих хоть одну чёрную клетку. Сколько чёрных и сколько белых клеток должно быть в каждом из них? Ввиду симметричности не имеет значения, какой из двух прямоугольников, содержащих нижнюю  левую чёрную клетку выбрать. А после этого каждый раз находим ту чёрную клетку, для которой остался только один вариант.

501.У царя Никиты было 45 сыновей. Он завещал им разделить между собой таким образом, чтобы земли каждого из них граничили с землями ровно 3 или 7 его братьев. Призадумались братья. Смогут ли они выполнить волю отца?

Подсказка. Задача сводится к задаче 500. Допустите, что волю отца выполнить удалось. Поместите на землю каждого брата марсианина, у которого столько рук, со сколькими землями у этого участка есть границы, причём руки достаточно длинные, чтобы он мог взяться за руки с марсианами со всех земель, имеющих с ним общую границу.

502. Не существует выпуклого многогранника, у которого число граней нечётно, а каждая грань имеет нечётное число вершин. Докажите это.

Подсказка. В каждой вершине сходятся несколько граней, поэтому иметь дело с вершинами неудобно. Но у грани столько же вершин, сколько сторон, то есть рёбер. Замените в условии "вершин" на "рёбер". Задача, подобно задаче 501, сразу сводится к задаче 500.

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

Подсказка. Заметьте, что если вершина, отличная от вершин самого квадрата, является вершиной не более трёх прямоугольников, то, так как случаи, когда она является вершиной ровно одного или ровно трёх прямоугольников, невозможны, она является вершиной ровно двух прямоугольников. А теперь подсчитайте двумя способами число всех прямых углов всех прямоугольников, на которые разрезан квадрат. Обратите внимание, что это число должно быть не только чётным, но и кратным 4. (Почему?)

505. В некоей стране города связаны авиалиниями ( с двусторонним движением). Из столицы выходит 1981 линия, из города Дальний -1 авиалиния, а из остальных городов - по 20 авиалиний. Докажите, что из столицы можно долететь до Дальнего (возможно, с пересадками).

Подсказка. Если попытаться свести эту задачу к задаче 500, поместив в каждом городе по марсианину  с таким числом длинных рук, сколько линий выходит из города,  то ничего не получится, так как марсиан с нечётным числом рук будет двое - чётное число. Но что если поместить марсиан только в те города, до которых можно долететь из столицы? Тогда у столичного марсианина будет1981 рука, а  у всех остальных, если только они находятся не в Дальнем - по 20, т.к. если из столицы можно долететь до какого-то города, то можно с пересадками долететь и до всех городов, связанных с ним авиалиниями.