A method for cutting squares into distinct squares Original Research Article

We are interested in dissecting squares into distinct squares. We impose the condition that the squares have integer sizes. This restriction does not reduce the number of solutions since it is always possible to scale a non-integer solution to obtain an integer one. This leads, when the square size n is fixed, to a finite enumeration. We propose an algorithm which enumerates a subset of solutions when n is fixed. In spite of the incompleteness of this algorithm, we find many solutions and, in particular, for each integer p between 21 and 63, we have a solution using p squares. A second algorithm, this time complete, but computationally prohibitive, allows us to find an unexpected result: the smallest decomposition using integer squares has a size of 110. This paper is devoted to the description of the algorithms and to the presentation of an interesting subset of solutions.