упаковка в квадрате

[avva]

Comments

[tekila_jazz_out]

так это аналог задачи про черепаху которую никогда не догонит тигр. но мы то понимаем без высшей математики что тигр оябязательно догонит черепаху. В данной задаче каждый шаг не добавляет 1/2 к заполнению квадрата а отнимает 1/2 от квадрата (и последующего сегмента). и даже если включить процесс бесконечной операции, то есть область которая не будет заполнена никогда.

другими словами - сколько операций не производи. всегда остается не заполненная область равная 1/2 последнего сегмента.

[lx_photos]

Журналист: "Учёные играют в тетрис!"

[edd_l]

Лучший результат здесь в некотором смысле принадлежит Теренсу Тао https://arxiv.org/abs/2202.03594... )

[avva]

>И такой алгоритм тоже есть. Но об этом месяца через 3-4.
>PS. В общем, вероятно Кнут прав, а Грэм ошибся.

Удачи! :)

[ext_5867341]

Ну здесь Скотт Ааронсон выдает желаемое за действительное. Чтобы значение было практическое, нужно чтобы на еще не созданном квантовом компьютере этот алгоритм запустился, проработал нужное время и выдал результат с разумным success rate. За последние 30 лет веры в то, что квантовый компьютер будет работать по старой модели, сильно поубавилось.

[spamsink]

Напомнило https://mathworld.wolfram.com/18-PointProblem.html

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