4
$\begingroup$

Here's a puzzle given me by some folks at Science Olympiad. I haven't been able to solve it yet.

You have 50 disks, each 1 cm in diameter. On the table are four concentric rings: the first with a radius of 2.1 cm, the next with a radius of 4.2 cm, the next of radius 6.3 cm, and the last of radius 8.4 cm.

Disks in the inner circle are worth 30 points, the 2nd circle 20, the 3rd 14, and the outermost 5. Disks must be completely flat on the table, and cannot be on top of each other. Disks in two circles (straddling the line) receive the points of the lower-valued area.

What is the highest possible score? Preference will be given to answers that demonstrate that this score is indeed the highest.

Note: this is NOT tagged lateral-thinking. It's just a close-packing puzzle.

$\endgroup$
0

1 Answer 1

8
$\begingroup$

Here are some statistics as to the diameter of the smallest circle that $n$ diameter-$1$ circles can be packed into:

$$\begin{matrix} 2 & 2 \\ 3 & 2.1547 \\ 12 & 4.0296 \\ 13 & 4.2361 \\ 31 & 6.2915 \\ 32 & 6.4295 \\ 50 & 7.9475\end{matrix}$$

The best-known packing of $31$ puts $1$ in the inner $2.1$-circle, $6$ others in the $4.2$-circle and the other $31-7=24$ in the $6.3$-circle. The other $50-31=19$ fit in the outer ring. This gives a score of $1\cdot30+6\cdot20+24\cdot14+19\cdot5=581$.

If, alternatively, we pack as many as possible into the $4.2$-circle, we pack $12$ there. Of those $12, 3$ are as near to the centre as possible, but fail to fit into the inner $2.1$-circle, so each of the $12$ scores $20$. $16$ more will fit in the $6.3$-circle, though $17$ won't, because doing that entails packing their centres onto a $5.3$-circle, and $5.3\pi\approx16.65<17$. $50-12-16=22$ fit in the outer ring. This gives a score of $12\cdot20+16\cdot14+22\cdot5=574$ so this is worse.

The ratios between the scores are carefully chosen. If circles in the $6.3$-circle scored only $13$ instead of $14$, $581$ and $574$ would be $557$ and $558$, so the formerly worse solution would then be better.

The results for the smallest circle into which $n$ unit circles can be packed come from Graham[1].


I could've sworn that all the dimensions specified were diameters.

12 radius-$1$ circles pack into a circle of radius $4.0296$. Therefore 12 diameter-$1$ circles pack into a circle of radius $2.1$. Now consider the second ring (of radius $r=4.2$). $2\pi (r-\frac12)>23$ and $2\pi (r-1\frac12)>16$, so there is room in the second ring for a ring of $15$ or $16$ and a ring further out of $22$ or $23$. The score would then be $12\cdot30+38\cdot20=1120$. But there is no subtlety here, and the largest two of the four concentric rings are not needed. I think the intended problem must be as I originally thought it was: with circles of diameter $1$ in rings of diameter $2.1, 4.2, 6.3, 8.4$. Or circles of radius $1$ in rings of radius $2.1, 4.2, 6.3, 8.4$.


[1] Graham et al., Dense packings of congruent circles in a circle. Discrete Mathematics 181 (1998), p.139-154.

$\endgroup$
4
  • $\begingroup$ Or, alternatively, if we pack as many disks as possible inside the 2.1 ring we'll get 2 scoring 30 each, which is the same as 3 scoring 20 each. Agree that the scores and radii are too convenient for the first problem not to be intended. With the caveat that this relies on Graham's results which to my knowledge are not all proven to be optimal, so maybe it would be best to refer to the "optimal" packing for 31 as the "best known". $\endgroup$
    – ffao
    Commented Sep 12, 2016 at 8:18
  • $\begingroup$ Please note that the disks have a diameter of 1cm, and the circles have a radius of 2.1 cm, 4.2cm, etc. $\endgroup$
    – dpdt
    Commented Sep 12, 2016 at 19:05
  • $\begingroup$ @dpdt That case is covered under the line, but it's so uninteresting that the solution is really short. $\endgroup$
    – ffao
    Commented Sep 12, 2016 at 20:56
  • $\begingroup$ That's a great website you linked to, it seems invaluable for these types of problems. $\endgroup$ Commented Sep 12, 2016 at 23:38

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.