17
$\begingroup$

I'm an active member and challenge writer on Code Golf SE. Here is a challenge of mine, titled Make a rectangle from a collection of (sliced) squares:

Task

There is a famous formula on the sum of first $n$ squares:

$$ 1^2 + 2^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6} $$

It is known that this number is composite for any $n \ge 3$.

Now, imagine a collection of row tiles (a tile of shape $1 \times k$ with the number $k$ written on each cell), and you have 1 copy of size-1 tile, 2 copies of size-2 tiles, ... and $n$ copies of size-$n$ tiles.

[1]  [2 2]  [2 2]  [3 3 3]  [3 3 3]  [3 3 3] ...

Then arrange them into a rectangle whose width and height are both $\ge 2$. You can place each tile horizontally or vertically.

+-----+---+-+-+
|3 3 3|2 2|1|2|
+-----+---+-+ |
|3 3 3|3 3 3|2|
+-----+-----+-+

Output such a matrix if it exists. [...]

I added a conjecture on the task:

I believe there exists a solution for any $n \ge 3$.

Then an answerer came up with a constructive proof that it is possible to form a nontrivial rectangle using only horizontal tiles:

It's an incremental construction. Consider $n \bmod 6$, we can have these values for height and width of rectangles:

  • $n/6\times (n+1)(2n+1)~(n\bmod 6=0)$

  • $(2n+1)/3\times n(n+1)/2~(n\bmod 6=1)$

  • $(n+1)/3\times n(2n+1)/2~(n\bmod 6=2)$

  • $n/3\times (n+1)(2n+1)/2~(n\bmod 6=3)$

  • $(2n+1)/3\times (n+1)n/2~(n\bmod 6=4)$

  • $(n+1)/6\times n(2n+1)~(n\bmod 6=5)$

(dimensions might be $1$ for $n\leq 6$ so these small cases are handled manually)

So the main idea of my construction is:

  • We construct rectangles with the heights and widths as in above list.

  • If $n\bmod 3 \neq 1$, construct the solution for $n-6$ recursively, add in $n-5,n-4\cdots n$. The height of the rectangle will only increase 1 or 2.

  • If $n\bmod 3=1$, construct the solution for $n-3$ recursively and add in $n-2,n-1,n$. The height of the rectangle will only increase 2.

  • We first carefully assign the new numbers to the added columns, and then put rest of the numbers into one or two added rows.

The rest of the job is some careful casework to pick the numbers. [...]

While this proof solves the question at hand, it isn't as elegant as we expected. So here is the question: Can we find a more mathematical (and less case analysis based) proof that such a solution exists for any $n \ge 3$? It doesn't need to be restricted to horizontal tiles.

Edit: As the question isn't getting any sign of progress, I'm also open to any proof (not necessarily elegant) that is distinct from the one above.

$\endgroup$
  • 2
    $\begingroup$ Given the fact that which factors in $n(n+1)(2n+1)$ could possibly absorb the factors of the denominator $6$ depends on $n$ modulo $6$, in some sense all solutions whose rectangle dimensions have simple formulas in terms of $n$ must look something like the solution you described. $\endgroup$ – Mark S. May 18 at 0:23
  • 3
    $\begingroup$ It's interesting that the other solutions on CodeGolf tend towards random/greedy. As I was thinking about this (and eventually agreeing with @MarkS.), I found that $\sum_{k=1}^{24} k^2 = 4900 = 70^2$ but the 24 squares $1 \times 1$, $2 \times 2$, $\ldots$, $24 \times 24$ cannot tile a $70 \times 70$ square. See this MathOverflow question. $\endgroup$ – Brian Hopkins May 18 at 2:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.