О пользе пива
Oct. 12th, 2009 12:33 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
eugeneboНеделю назад приглашал гостей. Потом убирал посуду и задумался вот над каким вопросом.
В квадратный ящик размером 3x3 составляется 9 пивных бутылок диаметром по 1 единице. Всё просто. А вот, скажем, если диаметр бутылки -- уже не 1 единица, а 1.01? Вроде бы можно запихать шесть. Но можно ли больше? И, самое главное, как доказать, что больше нельзя?
С удивлением понял, что не имею ни малейшего понятия о том, как формализуются задачи о максимально плотной упаковке.
В квадратный ящик размером 3x3 составляется 9 пивных бутылок диаметром по 1 единице. Всё просто. А вот, скажем, если диаметр бутылки -- уже не 1 единица, а 1.01? Вроде бы можно запихать шесть. Но можно ли больше? И, самое главное, как доказать, что больше нельзя?
С удивлением понял, что не имею ни малейшего понятия о том, как формализуются задачи о максимально плотной упаковке.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2009-10-12 07:58 am (UTC)Стекло али полиэтилен?
no subject
Date: 2009-10-12 08:08 am (UTC)no subject
Date: 2009-10-12 08:49 am (UTC)no subject
Date: 2009-10-12 09:30 am (UTC)no subject
Date: 2009-10-12 08:51 am (UTC)Семь бутылок диаметром 1,01 можно запихать в ящик даже несколько меньшего размера:
Вот доказать, что больше нельзя — это интересно. Надо подумать.
Задача о максимально плотной упаковке шаров (предположение Кеплера), так наверняка и не решена. См. http://mathworld.wolfram.com/SpherePacking.html, also Kepler conjecture.
no subject
Date: 2009-10-12 09:44 am (UTC)Я также добавил несколько вспомогательных линий, видно несколько равносторонних треугольников и квадратов, чтобы можно было понять, как решить точно.
no subject
Date: 2009-10-12 08:30 pm (UTC)Правда, я так и не понял, каким методом оно получено.
no subject
Date: 2009-10-12 08:39 pm (UTC)Было использовано решение задачи о максимально плотной упаковке двумерных сфер вообще, взята одна ячейка, а потом вокруг этой ячейки построен квадрат?
no subject
Date: 2009-10-12 09:37 pm (UTC)no subject
Date: 2009-10-12 10:12 am (UTC)теоретический алгоритм
Date: 2009-10-12 10:53 am (UTC)Если же говорить о способах решения, то обычно задачи из этой области (комбинаторная геометрия) являются весьма сложными. В то же время, существует общий алгоритм их решения, хотя про него можно сказать, что он чисто "теоретический".
В данном случае, если мы хотим выяснить, можно ли k бутылок радиусом r вместить в квадрат со стороной L, то можно ввести 2k переменных x_i, y_i и написать несколько неравенств. Прежде всего, при любых i<j имеет место неравенство r^2<=(x_j-x_i)^2+(y_j-y_i)^2. Кроме того, |x_i|, |y_i| не превосходят L/2-r при всех i. То есть вопрос состоит в том, при каких значениях параметров r и L полученная система неравенств имеет решение. А для таких задач возможна процедура "элиминации кванторов" -- это было установлено где-то в 60-х годах. Однако весь этот алгоритм сопряжён с большим объёмом вычислений, и без специальных упрощений они довольно редко бывает осуществимы за реальное время. Кстати говоря, для таких задач есть хоть какой-то алгоритм, а может быть намного хуже -- когда нет вообще никакого. То есть не в смысле того, что он неизвестен, а в смысле того, что его не существует в принципе. Скажем, это относится к вопросу о разрешимости уравнений в целых числах.
Re: теоретический алгоритм
Date: 2009-10-12 08:32 pm (UTC)no subject
Date: 2009-10-12 01:22 pm (UTC)Это опять к тому, у кого что в памяти откладывается... :)
У нас был учебный курс на целый семестр. На четвёртом, кажется, курсе.
Именно про максимально плотную упаковку. Из курса не помню просто абсолютно ничего. Хотя помню, что задачки были прикольные и решать их мне нравилось... Так что могу только с уверенностью сказать, что теории об этом существуют, там всё не совсем просто, но весьма забавно.
no subject
Date: 2009-10-12 01:33 pm (UTC)no subject
Date: 2009-10-12 04:57 pm (UTC)http://mathworld.wolfram.com/KeplerConjecture.html
“Hales' proof proved difficult to verify. In 2003, it was reported that the Annals of Mathematics publication would have an unusual editorial note stating that parts of the paper have not been possible to check, despite the fact that a team of 12 reviewers worked on verifying the proof for more than four years and that the reviewers were 99% certain that it is correct (Holden 2003, Szpiro 2003). However, the actual publication contains no such note (Hales 2005).
“In response to the difficulties in verifying his proof, in January of 2003, Hales launched the "Flyspeck project" ("Formal Proof of Kepler") in an attempt to use computers to automatically verify every step of the proof. Unfortunately, Hales expects the project is likely to take 20 person-years of labor (Holden 2003, Szpiro 2003). ”
Интересно — кто-то придумал новое док-во? Я об этом не слышал.
no subject
Date: 2009-10-12 04:35 pm (UTC)no subject
Date: 2009-10-12 04:48 pm (UTC)no subject
Date: 2009-10-12 08:37 pm (UTC)no subject
Date: 2009-10-12 09:34 pm (UTC)no subject
Date: 2009-10-12 08:37 pm (UTC)Ну и как её решали, интересно? Численным перебором?
no subject
Date: 2009-10-13 06:50 pm (UTC)no subject
Date: 2009-10-14 01:53 pm (UTC)Но в твоём случае, насколько я понимаю, задача сводится к плоской, т.к. бутылки не сферические :)
no subject
Date: 2009-10-14 05:41 pm (UTC)