14
$\begingroup$

The following 3x4 rectangle can be cut into pieces along grid lines, so that each piece has exactly three neighbors:

Problem: Find the smallest rectangle on the integer grid that can be cut into pieces along grid lines, so that each piece has exactly five neighbors.

Pieces are neighbors, if their boundaries touch; touching in a corner doesn't count.

$\endgroup$
6
  • $\begingroup$ I'm guessing we should use at least 8 colours? Maybe 13, 18... $\endgroup$
    – dmg
    Jan 24, 2015 at 13:23
  • $\begingroup$ @dmg You mean figures? Colours do not matter. Why do you think so? $\endgroup$
    – Somnium
    Jan 24, 2015 at 13:49
  • 3
    $\begingroup$ You need at least 12 figures. Probably 12 figures gives the minimum, but it's annoying to optimize the rectangle size. $\endgroup$
    – Lopsy
    Jan 24, 2015 at 14:07
  • 1
    $\begingroup$ I thought of this as a planar graph, where "points of touch" are edges, which gave 8 figures, but I made a typo in my formulae and it should be 12 as @Lopsy said. I think that this is a bit more constrained than a planar graph, but am not really sure $\endgroup$
    – dmg
    Jan 24, 2015 at 14:10
  • 1
    $\begingroup$ Actually, I thought up this puzzle when was reading about planar graphs. $\endgroup$
    – Somnium
    Jan 24, 2015 at 14:13

2 Answers 2

21
$\begingroup$

How's this?

enter image description here

I got this by square-izing the icosahedron graph:

$\endgroup$
5
  • $\begingroup$ I had solution of the same size and found with same manner. How about proof that this is minimal? $\endgroup$
    – Somnium
    Jan 24, 2015 at 14:24
  • 1
    $\begingroup$ @Lopsy: Could you expand on how you "square-ized" the graph? The graph has 12 nodes, which I guess matches the 12 colours in your rectangle and I can see the "similarity". But I'm not sure about the procedure you've used for "square-izing". $\endgroup$
    – BmyGuest
    Jan 24, 2015 at 15:04
  • 1
    $\begingroup$ No formal procedure, I just tried to squeeze it all into a square grid, starting from the center. Not sure how to approach a proof of minimality. $\endgroup$
    – Lopsy
    Jan 24, 2015 at 15:08
  • 1
    $\begingroup$ Does anybody know the treewidth of the icosahedron graph? If the treewidth is $n$, then a rectangle containing it needs to have height and width at least $n$. I looks like it has treewidth 5 but I'm not sure. $\endgroup$
    – Lopsy
    Jan 24, 2015 at 15:24
  • $\begingroup$ @Lopsy The treewidth is $6$: houseofgraphs.org/graphs/1186 $\endgroup$
    – RobPratt
    Nov 25, 2023 at 15:49
13
$\begingroup$

Here is a proof that $12$ is the smallest possible number of regions in any feasible solution.

Consider an arbitrary division of an arbitrary rectangle into $n$ regions, such that every region has exactly five neighboring regions. We translate this picture into a so-called planar graph: each of the $n$ regions then translates into a vertex/point, and there is a connecting edge between any two vertices/points that correspond to neighboring regions. The total number of edges is denoted $e$.

We only need facts on $e$ and $n$

Fact 1: $~~~~2e=5n$

This can be seen by counting the touching vertex-edge pairs: every edge touches two vertices, and every vertex touches $5$ edges.

Fact 2: $~~~~e\le3n-6$

This fact can be found (for instance) on the wiki-page in the paragraph on maximal planar graphs. If follows from the Euler formula for planar graphs.

Now by combining Facts 1 and 2, we get

$5n/2~=~e~\le~3n-6$,

which implies $0\le n/2-6$ and hence $n\ge12$. Consequently, Lopsy's construction is best possible with respect to the number of used regions.

$\endgroup$

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.