Решение задачи 410

Условие:

В магазине есть палочки только простых длин, но зато всех: 2 см, 3 см, 5 см, 7 см и т.д. Какое наименьшее число палочек разных длин нужно купить, чтобы сложить из них контур квадрата?

Решение:

Оценка:

Так как длины всех палочек разные, то максимум одна сторона представлена одной палочкой. Это значит, что палочек минимум семь. Покажем, что палочек не может быть семь. Пусть это так, тогда одна сторона представлена одной палочкой, остальные три -- двумя. Отсюда следует, что длина стороны квадрата выражается нечетным числом (очевидно, что сторона больше двух). Но так как палочка длиной 2 максимум одна, то найдется сторона, представленная двумя палочками, каждая из которых имеет нечетную длину. Получается, что эта сторона имеет четную длину, противоречие. Значит, палочек хотя бы восемь.

Пример:

Возьмем восемь палочек: 17, 19, 23, 29, 31, 37, 41, 43. Сложим четыре стороны: 17+43=19+41=23+37=29+31=60.

Ответ: Восемь.