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

Аватар пользователя
Ian
Сообщений: 653
Зарегистрирован: 18 янв 2016, 19:42

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

Сообщение Ian » 14 фев 2021, 07:24

При каком наименьшем [math] в квадрате со стороной [math] можно разместить 5 единичных квадратиков?

ARRY
Сообщений: 82
Зарегистрирован: 30 дек 2015, 09:46

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

Сообщение ARRY » 14 фев 2021, 09:52

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

Аватар пользователя
Ian
Сообщений: 653
Зарегистрирован: 18 янв 2016, 19:42

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

Сообщение Ian » 14 фев 2021, 16:17

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

ARRY
Сообщений: 82
Зарегистрирован: 30 дек 2015, 09:46

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

Сообщение ARRY » 14 фев 2021, 23:44

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

Аватар пользователя
Ian
Сообщений: 653
Зарегистрирован: 18 янв 2016, 19:42

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

Сообщение Ian » 15 фев 2021, 09:42

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

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

zykov
Сообщений: 947
Зарегистрирован: 06 янв 2016, 17:41

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

Сообщение zykov » 15 фев 2021, 14:04

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

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

zykov
Сообщений: 947
Зарегистрирован: 06 янв 2016, 17:41

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

Сообщение zykov » 15 фев 2021, 14:09

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

zykov
Сообщений: 947
Зарегистрирован: 06 янв 2016, 17:41

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

Сообщение zykov » 15 фев 2021, 14:55

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
Сообщений: 947
Зарегистрирован: 06 янв 2016, 17:41

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

Сообщение zykov » 15 фев 2021, 18:19

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$.

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

Аватар пользователя
Ian
Сообщений: 653
Зарегистрирован: 18 янв 2016, 19:42

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

Сообщение Ian » 15 фев 2021, 19:07

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

zykov
Сообщений: 947
Зарегистрирован: 06 янв 2016, 17:41

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

Сообщение zykov » 15 фев 2021, 20:32

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

peregoudov
Сообщений: 500
Зарегистрирован: 29 дек 2015, 13:17

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

Сообщение peregoudov » 21 фев 2021, 22:33

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

zykov
Сообщений: 947
Зарегистрирован: 06 янв 2016, 17:41

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

Сообщение zykov » 22 фев 2021, 00:47

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

zykov
Сообщений: 947
Зарегистрирован: 06 янв 2016, 17:41

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

Сообщение zykov » 22 фев 2021, 00:56

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

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


Вернуться в «Математика»

Кто сейчас на форуме

Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 3 гостей