14
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ do all the coins have to be touching in one large group, or can there be "islands"? $\endgroup$ – dfperry Jan 26 '16 at 20:02
  • $\begingroup$ Oops. Edited :) $\endgroup$ – rnaylor Jan 26 '16 at 20:05
  • $\begingroup$ How large is the table? Infinitely large? $\endgroup$ – Beastly Gerbil Jan 26 '16 at 20:09
  • 4
    $\begingroup$ Seems like a variant of puzzling.stackexchange.com/questions/25219/neighboring-circles $\endgroup$ – JonTheMon Jan 26 '16 at 20:20
  • 1
    $\begingroup$ 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? $\endgroup$ – Peteris Jan 26 '16 at 21:55
10
$\begingroup$

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)
enter image description here 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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Zandar Jan 26 '16 at 20:41
  • 1
    $\begingroup$ 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. $\endgroup$ – Michael Seifert Jan 26 '16 at 21:10
  • 2
    $\begingroup$ 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. $\endgroup$ – f'' Jan 26 '16 at 23:00
  • 4
    $\begingroup$ 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. $\endgroup$ – f'' Jan 27 '16 at 0:27
  • 1
    $\begingroup$ 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. $\endgroup$ – f'' Jan 27 '16 at 23:01
10
$\begingroup$

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.

enter image description here

$\endgroup$
  • 7
    $\begingroup$ In your figures D2,A3,B3,C3, some coins touch four others. $\endgroup$ – Mike Earnest Jan 27 '16 at 4:43
  • $\begingroup$ k will always be <= n. k = 2, n = 0 doesn't make any sense. $\endgroup$ – cst1992 Jan 27 '16 at 5:46
  • $\begingroup$ @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. $\endgroup$ – Chieron Jan 27 '16 at 10:15
  • $\begingroup$ @Chieron Not really, the coins with n=0, all coins touch 0 others; not more. $\endgroup$ – cst1992 Jan 27 '16 at 10:42
  • 2
    $\begingroup$ @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. $\endgroup$ – Chieron Jan 27 '16 at 10:57
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

Partial answer:

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

$\endgroup$

Your Answer

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

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