# Touching coins flat on a table

On an infinite table are $n$ identical circular coins lying flat. Each coin touches exactly $k$ other coins, and any two coins are connected by a path of touching coins.

Determine all possible pairs of values of $n$ and $k$.

• do all the coins have to be touching in one large group, or can there be "islands"? – dfperry Jan 26 '16 at 20:02
• Oops. Edited :) – rnaylor Jan 26 '16 at 20:05
• How large is the table? Infinitely large? – Beastly Gerbil Jan 26 '16 at 20:09
• Seems like a variant of puzzling.stackexchange.com/questions/25219/neighboring-circles – JonTheMon Jan 26 '16 at 20:20
• As it's worded, it doesn't seem to disallow solutions with coins laying flat but not touching the table - for example, stacking pairs of coins on top of each other, and forming a finite circular chain with k=6. Is this an omission or is it meant this way? – Peteris Jan 26 '16 at 21:55

## 4 Answers

My solution:

$n$ = 1 : $k$ = 0 (single coin can't touch any others)
$n$ = 2 : $k$ = 1 (pair of coins only touch each other)
3 <= $n$ < $\infty$ : $k$ = 2 (finite number of coins greater than 2 can only touch 2 others without making the "edge" coins touch a different number [updated from Zandar])
16 <= $n$ < $\infty$ : $k$ = 3 ($n$ must be a multiple of 4 for the diamond pattern to work, update from Michael Seifert)
$n$ = $\infty$ : $k$ = 2,3,4,6 (without "edge coins" to worry about, you can look at any subset of the grid to see what connections are available. 5 can't be done on a normal 2-d euclidian surface, that would require a dodecahedron) for the above images, assume each group of coins is a smaller selection of the infinite mass of coins, with the exception of the $k$=2 section, that is a piece of a loop

• You can have a finite pattern with $k=3$. Have a diamond of coins where the "inner" two coins are touching all the others and the "outer" two coins only touch the inner two, then link a sufficiently large number of these diamonds together to form a circle. – Zandar Jan 26 '16 at 20:41
• Note that your/@Zandar's finite $k = 3$ solution only works if $n$ is a multiple of 4 that is greater than 12. You need a multiple of 4 to get a whole number of "diamonds", and if there are 8 or 12 of them then you can't close the loop. – Michael Seifert Jan 26 '16 at 21:10
• For $k=3$, you can make 34 (plus any multiple of 4) by taking two copies of the solution for 16, adding a coin to each one, and touching the new coins to each other. An odd number of coins is impossible because $nk$ has to be even. $k>3$ is impossible, as proved in the linked question. – f'' Jan 26 '16 at 23:00
• I think you can get $k=5$ with an infinite number of coins. Divide the $k=6$ lattice into hexagons of 7 coins, then remove the center from each one. – f'' Jan 27 '16 at 0:27
• Actually, any even number larger than 16 is possible for $k=3$ because you can add two coins to a diamond (making it a square with two coins on opposite sides) and it still works. – f'' Jan 27 '16 at 23:01

This is all I can find, there may be more.

k=0, n=0 : an empty table. (Fig A1)

k=0, n=1 : a single coin on the table. (Fig B1)

k=1, n=0 : an empty table. (Fig A1)

k=1, n=2 : two coins touching. (Fig C1)

k=2, n=0 : an empty table. (Fig A1)

k=2, n>=3 : a 'ring' of 3 or more coins, each touching its two neighbors (For example Figs. D1 - three coins, and A2 - 5 coins, )

k=3, n=0 : an empty table (Fig A1)

k=3, n=4(m+4), m>=0 : closed loop of four or more repeated blocks of four coins (For example Fig B2 - m=0, and Fig C2 - m=1)

k=3, n=∞ : infinite double row of coins in squared arrangement (Fig A3)

k=3, n=∞ : infinite hexagonal array with every third coin in each row removed. (Fig D3)

k=4, n=∞ : infinite square array of coins (Fig B4), or infinite hexagonal array with every second coin in every second row removed. (Fig A4)

k=4, n=∞ : infinite double row of coins in hexagonal arrangement (Fig B3)

k=5, n=∞ : infinite hexagonal array with one in seven of the coins removed. (Fig C4)

k=6, n=∞ : infinite hexagonal array with no coins removed. (Fig D4)

k>=7, n=0 : empty table again for all these 'impossible' options. • In your figures D2,A3,B3,C3, some coins touch four others. – Mike Earnest Jan 27 '16 at 4:43
• k will always be <= n. k = 2, n = 0 doesn't make any sense. – cst1992 Jan 27 '16 at 5:46
• @cst1992 k can be any number, there was no restriction specified. Every member of the empty set of n coins touches k others.. OP should have eliminated that trivial solution. – Chieron Jan 27 '16 at 10:15
• @Chieron Not really, the coins with n=0, all coins touch 0 others; not more. – cst1992 Jan 27 '16 at 10:42
• @cst1992 it's an empty set, describing properties of all its members always yields true statements. They all touch an infinite number of coins.. and none at the same time. – Chieron Jan 27 '16 at 10:57

Nothing scientific in my answer, just by first impression and looking for possible symmetric arrangements:

On a finite n: n=1, k=0 n=2, k=1 (two coins next to each other) n>=3, k=2 (loop chain of 3 or more coins)

Seems odd that I cannot find a valid composition where k>3 and n is finite. I definitely have to give this further thought.

For infinite n, since there would have to be a symmetric arrangement, k could have any value from 2 to 6 except 5: 2 (i.e. infinite row of single coins), 3 (i.e. two parallel rows), 4 (i.e. two parallel rows offset by half a coin in "zigzagish" form), and 6 (i.e. infinite arrangement of coins as tightly as possible).

I can't figure out an arrangement where k=5, which is quite interesting. Possibly because its impossible to have a 2 dimensional symmetrical arrangement of 5 vertices.

Partial answer:

n = infinity, k = 6. Arranged as a hexagonal pattern.
n = infinity, k = 4. Arranged as a square pattern