Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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

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

share|improve this answer
1  
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 at 20:41
1  
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 at 21:10
2  
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 at 23:00
4  
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 at 0:27
1  
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 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.

enter image description here

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

share|improve this answer

Partial answer:

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

share|improve this answer

Partial answer:

5 <= n <= infinity k = 2
Arranged in a giant circle, all coins would touch 2 coins (This is if table is infinitely large)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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