Портал Естественных Наук, версия 1.1

При каком наименьшем

a в квадрате со стороной

a можно разместить 5 единичных квадратиков?

Без незаполненного пространства, естественно, не получится (только если

n - полный квадрат).
А с незаполненным пространством эта задача рассматривалась, если память не изменяет, в одном из древних "Квантов".
Некоторые результаты есть здесь.

Спасибо, интернет-олимпиада, решение одной из задач которой есть в википедии, это недоработка конечно

Ian писал(а):Source of the post решение одной из задач которой есть в википедии

Да это ещё полбеды, в Википедии, особенно русской, немало ляпов, а то и грубых ошибок.
Гораздо хуже, что организаторы олимпиады вместо составления новых задач берут уже известные из олимпиад 30-40-50-летней давности. А опытные олимпиадники с этими задачами обязаны быть знакомы.

С другой стороны, двадцатилетние не знакомы ни с чем, что было общеизвестно и популярно 20 лет назад. Видимо потому что на них катится такой объем свежей информации, что просто некогда о старом почитать. Пусть хоть так, но чтобы решение не находилось поиском в гугле.
А надо отметить что у этой олимпиады задачи были со вкусом(не знаю кто проводил): соседняя тема про сумму ряда, или вот

: circ.png (82.37 KiB) 14826 просмотра

Тут уж не все догадаются, что поиском надо искать слово "циркулянт"

Ian писал(а):Source of the post соседняя тема про сумму ряда

Если там не требовалось доказательства, а только нужно было ввести целое число в веб-форму, то там думать вообще не надо - просто на компьютере просуммировал несколько первых слагаемых и округлил до целого. Можно за одну минуту уложиться.

Про 5 квадратов, то глядя на картинку - довольно очевидно, что меньше нельзя. Но вот как это строго доказать? Как-то не просто...

Ian писал(а):Source of the post Тут уж не все догадаются, что поиском надо искать слово "циркулянт"

Тут какая-то глубокая теория про циркулянт не требуется. Даже школьник знакомый с системами линейных уравнений может решить (учитывая симметрию в этой системе).
Наприме вычитая из второго равенства первое получаем $(n-1)x_1-x_2-x_3-...-x_n = 1$

.
Аналогично можно сделать для $x_2$

и $x_{n-1}$ .
Для $x_n$

похожим образом из первого нужно вычесть последнее. Получиться $-x_1-x_2-x_3-...+(n-1)x_n = 1-n$

.
Если сложить эти 4 новых равенства, то будет $(n-4)(x_1+x_2+x_{n-1}+x_n) - 4(x_3+x_4+...+x_{n-2}) = 4-n$ .
С другой стороны, если сложить все равенства вместе, то будет $(\sum_{k=1}^n k) (x_1+...+x_n) = \sum_{k=1}^n k$ .
Т.е. $x_1+...+x_n = 1$

.
Подставляя это в предыдущее равенство получаем $n(x_1+x_2+x_{n-1}+x_n) - 4\cdot1 = 4-n$ .
В итоге $n(x_1+x_2+x_{n-1}+x_n) = 8-n$ .

zykov писал(а):Source of the post Если сложить эти 4 новых равенства, то будет $(n-4)(x_1+x_2+x_{n-1}+x_n) - 4(x_3+x_4+...+x_{n-2}) = 4-n$ .

Это можно получить короче, если сразу вычесть из тертьего равенства предпоследнее равенство.
Но выделять по одному слагаемому за раз - более интуитивно.

Я решил систему, но теория про циркулянт использована только в том смысле что он отличен от 0, и значит подобранное решение единственно. Ясно что если в правой части столбец перевернутый; n,n-1,...1, то

x_n=1, остальные нули. А если в правой части столбец из равных чисел, например чисел

(n+1), то и

x_i все равны и легко найти какие. Вычитая из второго решения первое, получим решение всей данной системы.

Да, найти все $x$

тоже можно.
(Достаточно найти $x$

для нескольких небольших $n$

, а там тенденция уже видна - все кроме последнего равны друг другу, а сумма всех равна 1.)
Но думаю, имелось ввиду найти эту сумму не находя сами $x$

.

А к какой-нибудь задаче линейного программирования "пять квадратиков" не сводятся? Задать неравенствами пять квадратиков и большой квадрат, попадание маленького квадратика внутрь большого и во внешность остальных маленьких --- какие-то логические конструкции из неравенств...

"Сложный" путь доказательства оптимальности в лоб там конечно есть. Но это уже скорее дело для компьютера.
Правда чисто линейное програмирование наверно не пройдёт из-за поворотов.
Я имел ввиду, есть ли сравнительно несложный метод руками в тетрадке?

Кстати, насчёт поворотов.
У меня тут есть парочка металлических пазлов Hanayama.
Там нужно сцеплять/расцеплять твёрдые фигуры. Довольно сложно - рекомендую, если такое интересно.
Всё думал, как программу написать, чтобы решала такой пазл. Честно говоря, оно не просто. Пока даже не знаю как, хотя должно быть решаемо.
Там тоже 3D повороты усложняют дело.

Если фигуры имеют форму многогранников, то должно быть попроще. Но есть фигуры и кривой формы, причём не всегда часть окружности (шара или цилиндра).

Портал Естественных Наук, версия 1.1

Пять квадратиков

Пять квадратиков

Пять квадратиков

Пять квадратиков

Пять квадратиков

Пять квадратиков

Пять квадратиков

Пять квадратиков

Пять квадратиков

Пять квадратиков

Пять квадратиков

Пять квадратиков

Пять квадратиков

Пять квадратиков

Пять квадратиков