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$.
$\begingroup$
$\endgroup$
5
-
$\begingroup$ do all the coins have to be touching in one large group, or can there be "islands"? $\endgroup$– dfperryJan 26, 2016 at 20:02
-
$\begingroup$ Oops. Edited :) $\endgroup$– rnaylorJan 26, 2016 at 20:05
-
$\begingroup$ How large is the table? Infinitely large? $\endgroup$– Beastly GerbilJan 26, 2016 at 20:09
-
4$\begingroup$ Seems like a variant of puzzling.stackexchange.com/questions/25219/neighboring-circles $\endgroup$– JonTheMonJan 26, 2016 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$– PeterisJan 26, 2016 at 21:55
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
9
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
-
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$– ZandarJan 26, 2016 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$ Jan 26, 2016 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, 2016 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, 2016 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, 2016 at 23:01
$\begingroup$
$\endgroup$
7
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.
-
8$\begingroup$ In your figures D2,A3,B3,C3, some coins touch four others. $\endgroup$ Jan 27, 2016 at 4:43
-
$\begingroup$ k will always be <= n. k = 2, n = 0 doesn't make any sense. $\endgroup$– cst1992Jan 27, 2016 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$– ChieronJan 27, 2016 at 10:15
-
$\begingroup$ @Chieron Not really, the coins with n=0, all coins touch 0 others; not more. $\endgroup$– cst1992Jan 27, 2016 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$– ChieronJan 27, 2016 at 10:57
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
Partial answer:
n = infinity, k = 6. Arranged as a hexagonal pattern.
n = infinity, k = 4. Arranged as a square pattern
