login
Minimum number of integer-sided squares needed to tile an n-row staircase (a figure with n unit squares in the n-th row, and the leftmost squares of each row vertically aligned).
1

%I #16 Dec 30 2022 06:35:33

%S 1,3,3,7,6,7,7,11,12,13,12,15,14,15,15,20,20,23,22,23,24,25,24,29,28,

%T 29,28

%N Minimum number of integer-sided squares needed to tile an n-row staircase (a figure with n unit squares in the n-th row, and the leftmost squares of each row vertically aligned).

%C a(n) >= n, since the rightmost squares in each row must be covered by distinct tiles.

%C a(n) = n iff n = 2^k - 1.

%C a(n) = n+1 iff n = 2^k - 2^m - 1.

%C a(2*k) <= 2*a(k) + 1, a(2*k+1) <= 2*a(k) + 1 for k >= 1. - _Jinyuan Wang_, Jul 17 2019

%C a(n) <= A003817(n). - _Austin Shapiro_, Dec 29 2022

%H Canadian Mathematical Society, <a href="http://www.smc.math.ca/Competitions/CMO/exam/cmo2010.pdf">2010 Canadian Mathematical Olympiad, Problem 1</a>

%H C. Zhang, <a href="http://cyrilzhang.com/wp-content/uploads/2010/04/tilings.txt">Diagrams of tilings</a> [BROKEN LINK]

%e See link for diagrams of tilings.

%Y Solutions for a(n) = n: A000225. Solutions for a(n) = n+1: A030130, excluding 0.

%K nonn,more

%O 1,2

%A _Cyril Zhang_, Apr 04 2010