Млин, последний раз я решал подобную задачку лет эдак 20 назад, в питерской ФМШ... Даже и не знаю, с чего начинать. :(

От противного у меня не получается пока. База индукции (наборы из 1,2,3 квадратов - очевидна). Но переход!

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

Что-то в этом духе должно проходить и для конечных наборов, но не пойму устно, насколько мешают корни из двух и прочие константы. А писать лень.

Вот что тут получается:
1. упорядочиваем по убыванию площадей набор квадратов.
2. Пусть сторона первого (самого крупного) x, тогда x^2 его площадь.
Вкладываем его в угол
0,5 - x^2 это остаток площади (совокупной набора квадратов)
1 - x это сторона нового квадрата
Далее уменьшаем масштаб задачи на коэффициент alfa, и проверяем удовлетворит ли она поставленным условиям
0,5 - x^2 = 0,5 alfa (совокупность квадратов общей площадью 0,5)
1 - x > alfa условие того, что выделенный квадрат в свободной части единичного квадрата больше единичного квадрата в масштабе alfa.
1 - alfa > SQRT(0,5*(1-alfa))
Это верно для любого alfa из интервала [0;1] - вот и база вот и шаг.
Как видим и для бесконечного случая это остается в силе.
Площадь 0,5 это все-таки слишком мало.
Давно не решал мат. задачки ... может где и поторопился с выводами.
Рад был найти тебя в нете.
Паша (Лаптев)

Да, слегка поторопился ...
площадь в масштабе это 0,5 alfa^2

От этого логика решения пострадала не сильно:
доказательство разбивается на два случая:
1) x > 0,5
тогда хвост упихивается в тот самый выделенный квадрат 1-x (неравенства совместны)
2) 0,25 < x < 0,5 выделяем три квадрата со сторонами 0,5 в всободной части единичного квадрата и делим последовательность оставшегося покрытия на 1,2,3 рассчитайсь. Первый кусок упаковываем в первый 0,5 квадрат
второй во второй третий в третий.
3) 0,125 < x < 0,25 выделяем 15 квадратов стороной 0,25 распределяем монотонную последовательность покрытия в эти квадраты как в 2.
4) ...
индукция выходит двумерная, вложенная.

О, какие люди! Паша, привет!

Не очень я понял, откуда следует совместность неравенств в 2-3-4 (когда квадратов 3-15-63 соответственно); а параллельно задумался - нельзя ли бить исходный квадрат сразу по стороне максимального квадрата в текущем остатке (ну и что, что будет нецелое число, остатки так остатки...)

Апдейт. Все, я поиграл с неравенствами и понял идею и зачем разбивать квадраты по степеням четверки тоже понял (до ума доводить лень, но есть общее ощущение, что все оценки должны получиться как раз какие требуется). Спасибо!

И, клянусь!, последняя, но увы самая ужасная ситуация: сторона первого (n+1 в масштабе) квадрата от 0,5 до 2/3 (в этом случае неравенства все-таки несовместны, а масштабирование задачи идет только в случаях от 2/3 и до SQRT(2)) здесь доказывается, что сторона следующего квадрата не может превышать 1-x и опять имеем возможность делить последовательность на первый второй третий.

У тебя скайп есть?
мой "vugluscr1991" сейчас включен, могу также позвонить с него прямо в США (мне так дешево)
тут фокус в том, что монотонную последовательность делим на 3-15-63 и наполняемость каждой подпоследовательности площадями равномерная (годится для точных и аккуратных оценок, которые надо доказывать, но грубо) сумма площадей в каждой из трех меньше, чем остаток пополам, каждая из 63 меньше, чем остаток на 32 и т.д.

Скайпа у меня нет, и я ж на работе, как тут позвонишь...
Но я более или менее разобрался, спасибо еще раз!

(масштабирование - от 2/3 до sqrt(1/2) конечно :) )

Успехов!
Приветы всем.
будет время - заони (или пиши vugluscr#list.ru)
Я из Е-бурга уехал в Волжский (Волгоград), занимаюсь продажами ПП. Общаюсь мало. На всех кидаюсь :))) Чтоб не как с клиентами, а душевно, вот математика к примеру - вечер удался. Бай!

Ты тоже пиши:
echtykov#gmail#com

Рад был!