Версия для печати
Убрать все задачи
а) Электрическая схема имеет вид решетки 3×3: всего в схеме 16 узлов (вершины квадратиков решётки), которые соединены проводами (стороны квадратиков решётки). Возможно, часть проводов перегорела. За одно измерение можно выбрать любую пару узлов схемы и проверить, проходит ли между ними ток (то есть, проверить, существует ли цепочка неперегоревших проводов, соединяющая эти узлы). В действительности схема такова, что ток проходит от каждого узла к любому другому. За какое наименьшее число измерений всегда можно в этом удостовериться?
б) Тот же вопрос для решётки 5×5 (всего 36 узлов).

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


Решение
О том, как прыгают
кузнечики. Предположим, что имеется лента, разбитая на клетки и
уходящая вправо до бесконечности. На первой клетке этой ленты
сидит кузнечик. Из любой клетки кузнечик может перепрыгнуть либо
на одну, либо на две клетки вправо. Сколькими способами кузнечик
может добраться до
n-ой от начала ленты клетки?

Решение