Is it possible to cover a $70\times70$ square with $24$ squares with side length $1,2,3\ldots24$?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ When I encountered this problem in the past, the first thing that came to my mind was: How do you use the $1$x$1$ square in such a way that you don't require an additional $1$x$1$ to 'fill in the hole' created by that $1$x$1$. I'm not sure if the way in which I described it makes sense through text. There may be a counterexample to that as well. $\endgroup$– VincentCommented Jul 23, 2014 at 6:25
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
This problem was posed by Martin Gardner himself in 1966 (Scientific American, Sept. 1996). As far as I know, it remained unsolved until it was manually checked by a computer program in 2002 (link). It is impossible.
Further notes: Consider the general problem: is it possible to tile an $L\times L$ square with $k$ squares of side length $1,2,3\ldots k$? It turns out, the only solution to $$1^2+2^2+3^2+\cdots+k^2=L^2$$ is $k=24,L=70$ (besides the obvious $k=L=1$). Here is a link to the proof by Watson in 1918 (it's in the first few pages) So this problem is unique, in a way.
Additionally, the general idea of tiling a square completely with other squares is called "squaring the square" and is extensively studied (link).
-
$\begingroup$ $1^2+2^2+3^2+...+24^2=70^2$ its true :) $\endgroup$– piteerCommented Jul 23, 2014 at 6:30
-
$\begingroup$ The first reference you quote is somewhat weird. Firstly, the author of the webpage keeps saying that this particular instance is NP-complete, which doesn't mean anything (because this problem has an algorithmic solution in constant time). Secondly, in this page the author admits that his algorithm didn't find a solution, but it his only a heuristic. Finally, I couldn't download the article which is referenced at the very end. But the quote of the result is stunning. [conti $\endgroup$ Commented Jul 23, 2014 at 6:48
-
$\begingroup$ nued] "In order to check the program, it was run on a set of tiles for which a solution is known to exist; the program found the solution. The program was then run on 24 tiles of sides 1, 2, ..., 24 and found, after a 16-minute search, that no such tiling of the 70 x 70 square is possible." So apparently, the only check of the algorithm was to test it against a YES-instance! Did you find any other reference for this fact? $\endgroup$ Commented Jul 23, 2014 at 6:49
-
1$\begingroup$ The best I can do is a previous post from MathOverflow: mathoverflow.net/questions/133348/… $\endgroup$– ant11Commented Jul 23, 2014 at 6:53
-
1$\begingroup$ A better reference is given there: Annals of Operations Research September 2010, Volume 179, Issue 1, pp 261-295 Optimal rectangle packing Richard E. Korf, Michael D. Moffitt, Martha E. Pollack, which is accessible online. Thanks for the link! $\endgroup$ Commented Jul 23, 2014 at 7:02