login
Minimal number of horizontal and vertical lines needed to partition a square into rectangles which can be reassembled into n distinct squares.
1

%I #26 Oct 11 2021 18:33:55

%S 3,4,5,5,6,7,7

%N Minimal number of horizontal and vertical lines needed to partition a square into rectangles which can be reassembled into n distinct squares.

%C For n > 2 the values may only be upper bounds.

%H Anonymous, <a href="https://bbs.emath.ac.cn/thread-18080-1-1.html">Divide a square into several small squares.</a> [A Chinese web site where the problem originated]

%F a(n) <= a(n-2) + 2.

%F a(k + m - 1) <= a(k) + a(m).

%e For example, we could use one horizontal line to cut one side of the square in the ratio 2:3 and then two vertical lines to cut another side in the ratio 1:1:3 to form 6 rectangles 1*3, 1*3, 3*3, 1*2, 1*2, 3*2. Then we can reassemble the rectangles into a 3*3 square and a 4*4 square. So a(2) = 3.

%K nonn,hard,more

%O 2,1

%A _Zhao Hui Du_, Oct 01 2021

%E Thanks to _Jinyuan Wang_ for additional comments.