Таблицы Брадиса

Если п нечетно, то уложить

Если п нечетно, то уложить

Элементы математики в задачах - Г. А. Мерзон

Задача 5. Докажите, что из любого связного графа можно выкинуть вершину и выходящие из нее ребра так, чтобы он остался связным.

Решение. Рассмотрим в этом связном графе максимальное поддерево и выкинем одну из его висячих вершин (то есть вершину, из которой выходит ровно одно ребро этого дерева) вместе со всеми выходящими из нее ребрами. Тогда оставшееся поддерево, а значит, и весь остав­шийся граф, будут связными.

Задача 6*. В кубической коробке п х п х п лежало п3 единичных ку­биков. Кубики высыпали, каждый просверлили по диагонали, затем все плотно нанизали на нить и связали в кольцо (соединили вершину первого кубика с вершиной последнего). При каких п получившееся «ожерелье» можно убрать обратно в коробку?

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

Ответ. Если п нечетно, то уложить нельзя, если п четно — то можно.

Решение. Если п нечетно, то число кубиков также нечетно. Расставим на диагоналях кубиков стрелки так, чтобы они образовывали цикл и предположим, что «ожерелье» из кубиков удалось уложить в коробку. Тогда стрелки на диагоналях кубиков смотрят либо вверх, либо вниз, и число идущих вверх равно числу идущих вниз. Но всего стрелок столько же, сколько кубиков, то есть нечетное число — получаем противоречие.

В случае, если п четно, «ожерелье» из кубиков можно уложить в коробку, что показывается явно.

Задача 7*. Все 28 Петиных одноклассников имеют по различному числу друзей в этом классе. Сколько из них дружат с Петей? А если одноклассников п?

Ответ. Если число одноклассников п четно, то с Петей дружат п/2. Если же п нечетно, то возможны два ответа — (п — 1)/2 или (п +1)/2.