23
$\begingroup$

When I was too young one of my problems was in the list of problems of All-Russian Olympiad. The problem is the following:

Problem. We have a surface of a cube $n\times n \times n$ such that each face is divided in $n^2$ unit squares. Then this surface was covered (once) by $3n^2$ pieces of paper $1\times 2$ (domino) without overlapping. Prove that if $n$ is odd than the number of bent "dominos" is also odd.

Comment. This problem is not very difficult therefore it was solved by 90% participants in 10th grade (about 63 of 70). The solution you can find here. You really need it?)


"Hm..." - I thought - "What will be with $1\times 6$?". It was obvious for myself that it is impossible to cover the surface for $n=1$, but possible for $n=2, 3, 4$... $n=6$...

Aga, if $n$ is even than we can divide faces in two groups (in each group $3$ faces) in such way that faces in one group forms on surface of the cube rectangle $3n\times n$ with $2$ "bends". Each rectangle can be easily divided in pieces of paper $1\times 6$.

The case when $3$ is a divisor of $n$ I am leaving for a reader.

After that I conjectured the following.

Conjecture. For $n$ such that $(n, 6)=1$ there is no such covering of the surface of the cube $n\times n \times n$ by $n^2$ pieces of paper $1\times 6$ without overlapping.

Then I prove that it is true for $n=5$ and some my friends found a more or less suitable proof but it does not work in general case (they understood that vertices of this cube are weak points in this problem).


Finally, this conjecture was disproved (for $n=11$) by Peter Mueller(see his answer below)!

Also I like to add one problem (Russian olympiad folklore):

Problem. Let $n$ be such natural number that $(n,3)=1$, then there is no covering of three faces of a cube $n\times n \times n$ with a common vertex (of this cube) by strips $1\times 3$.

$\endgroup$
9
  • $\begingroup$ This doesn't feel like the right place for this question. Maybe artofproblemsolving.com? $\endgroup$ Oct 23, 2015 at 22:08
  • 14
    $\begingroup$ I think just the opposite! Serious research is fun! $\endgroup$ Oct 24, 2015 at 0:52
  • 5
    $\begingroup$ Later I will add some information to my text and maybe it will become much more serious. Today I cann't even use my computer. Shabbat! Tsss.... please, don't tell in my synagogue that I added a comment here. $\endgroup$
    – polyanom
    Oct 24, 2015 at 7:50
  • 12
    $\begingroup$ If questions of tiling two-dimensional shapes by polyforms were mathematical enough to be studied by Conway and Thurston (dx.doi.org/10.2307/2324578) they should be mathematical enough even for the most snobbish on this board. $\endgroup$ Oct 24, 2015 at 18:22
  • 1
    $\begingroup$ @NoamD.Elkies: It is a solved olympiad problem. I put it here just to give other mathematicians an opportunity to solve that elegant problem. $\endgroup$
    – polyanom
    May 1, 2017 at 7:13

1 Answer 1

33
$\begingroup$

Indeed, there is no solution for $n=5$, and also none for $n=7$. However, for $n=11$ there is a tiling of the requested form. I found it using a straightforward exact cover formulation and Knuth's original exact cover solver. I'm not sure how to best visualize a solution, here is an attempt using random colors for the tiles. It is a little hard to check that all tiles continue correctly across the cut edges of the cube: enter image description here

Added later: Fedja suggested in his comment to more generally look at $1\times 6$ tilings of a $m\times n\times k$ cuboid, for it is easy to see that such a tiling yields a tiling of a $(m+6)\times n\times k$ cuboid.

Indeed, the covering of the $11\times11\times11$ cuboid can be obtained from the way faster to compute covering of the $5\times11\times11$ cuboid: enter image description here

As to the $13\times13\times13$ case, the programs (Knuth's cover and alternatively integer linear program solvers) are still running. There are no solutions for $13\times7\times7$ and $13\times13\times1$. I don't know yet about $13\times13\times7$ and $13\times13\times13$.

$\endgroup$
12
  • $\begingroup$ How do you prove that there are no tilings for $n=7$? $\endgroup$ Oct 26, 2015 at 12:02
  • $\begingroup$ @Fedor Petrov: Just by brute force checking whether there is an exact cover. For $n=7$ Knuth's program took 8 seconds, while it took several hours for $n=11$ until it started to through out some solutions. $\endgroup$ Oct 26, 2015 at 12:18
  • 3
    $\begingroup$ Actually, it is easy to show that if $m\times n\times k$ is coverable, then so is $(m+6)\times n\times k$ (just think of all strips crossing the edges of the face to move and elongate them by 6 units inserting formal $0\times 1$ strips along the edge where nothing is really bent; then split each $12\times 1$ into two $6\times 1$). Thus, to finish off the cube problem for good, it would be nice to do the $n=13$ case as well. I don't think it should be much harder for the computer than $n=11$ and I'll be quite surprised if nothing shows up. :) $\endgroup$
    – fedja
    Oct 31, 2015 at 2:06
  • 1
    $\begingroup$ Also, since we can cover $11\times 11\times 11$ by $6\times 1$, we can cover $55\times 55\times 55$ by $30\times 5$ and, thereby, by $6\times 1$, which takes care of $n=6m+1$ for $m\ge 9$. Thus, the number of exceptional cubes is finite. $\endgroup$
    – fedja
    Nov 2, 2015 at 21:25
  • 1
    $\begingroup$ @fedja: Oh, I had stopped the programs after a few days :-( $\endgroup$ Jan 2, 2016 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.