22
$\begingroup$

Alice and Bob try to divide a piece of land $D$, shaped in a perfect closed disk of radius 1.

Alice moves first to mark some finite (at least one) number of points in $D$.

Bob then draws any number of circles in $D$ according to the following rules:

  1. each circle must contain (within or on the boundary) exactly one of Alice's points.

  2. circles can touch each other at the boundaries, but their interiors mustn't intersect.

The area covered by his circles goes to Bob, the rest goes to Alice.

Question: how should Alice mark her points to maximize her area?

An update concerning the answers

I strongly believe that Alice's optimal share of the land can be no more than half, as two of the answers suggested. But no matter how favorable the evidence is, there's no proof. I used to think I had such a "proof", which I now find to be lacking. So I unmarked the answer because even the OP himself is no longer 100% sure.

Improve this question
$\endgroup$
14
  • $\begingroup$ What if it is impossible for Alice to mark her points to maximize her area, i.e., for every set of finite points, there is another that achieves a greater area? $\endgroup$
    – noedne
    Mar 27, 2022 at 17:18
  • 1
    $\begingroup$ "Bob then draws any number of circles": Doesn't Bob draw the same number of circles as Alice's points? $\endgroup$
    – RobPratt
    Mar 27, 2022 at 17:51
  • 3
    $\begingroup$ Must the points be distinct? Otherwise, Alice can get 100% of the area by marking the same point twice -- then, Bob cannot place any circles, as any circle he would place would either contain either 0 or 2 points. $\endgroup$
    – tjjfvi
    Mar 27, 2022 at 18:10
  • 1
    $\begingroup$ Technically, a circle is a curve. And the area covered by a curve is zero. (At least the well-behaved ones). So Alice gets 100%. $\endgroup$
    – Florian F
    Mar 27, 2022 at 18:57
  • 2
    $\begingroup$ @RobPratt, assuming Alice isn't allowed to place two points in the same location, it's probably pretty easy to prove that Bob should draw the same number of circles as Alice drew points, but the problem statement doesn't require that he must do that. It's probably worth clarifying the assumption I made, though - that Alice can mark a finite number of unique points - otherwise Alice can just trivially mark the same point twice, meaning Bob can't draw any circles at all. $\endgroup$
    – ymbirtt
    Mar 28, 2022 at 8:20

3 Answers 3

Reset to default
11
$\begingroup$

Alice can maximize her area by

Marking one point at the centre and other infinitesimally close to the centre.

Why?

By doing this, Alice can have just less than half of the area as maximum radius of Bob's circle can never be greater than R/2. Therefore Alice gets almost half of the area. This must be the most limiting case.
ExampleImage

Increasing the number of points will only decrease Alice's area because

increasing the number of points increases Bob's chance of covering more area with more circles. If Alice increases the number of points significantly and distributes them all over the circle symmetrically, then Alice will have just around 21.5% area.

There are a few other things Alice can try:

Restrict Bob's circle into very small circlular arcs by selecting points in the straight lines. In the limiting case, the arc will become a triangular box consisting of many smaller square boxes.
enter image description here
Smaller square boxes of 0.005 units
enter image description here
Bob can insert circles in such a way that each square perfectly fits a circle. Therefore the packing fraction: 0.5×0.5×3.14/1 ~ 0.785. Which is consistent with my above observation.

Since increasing the number of points only result in increasing area for Bob, we can extrapolate this fact and can say: Alice should only plot 2 points to restrict Bob to minimum area.

Reference:

https://en.m.wikipedia.org/wiki/Circle_packing_in_a_circle
https://www.engineeringtoolbox.com/smaller-circles-in-larger-circle-d_1849.html

(I used this site to calculate if there a lot of circle of smaller radii into a very large circle. The amount of area covered by them is almost 78.5%). I know this is not a good proof, but I think it would help.

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ With this method, Alice can make her area arbitrarily close to 50%, but she can never maximize her area $\endgroup$
    – tjjfvi
    Mar 27, 2022 at 18:07
  • $\begingroup$ I fixed the spoilertags for you. $\endgroup$
    – Rand al'Thor
    Mar 27, 2022 at 19:33
  • 1
    $\begingroup$ @tjjfvi I'm not myself sure about the answer either. Just trying to extrapolate some facts. $\endgroup$
    – I'm Nobody
    Mar 27, 2022 at 19:41
  • 4
    $\begingroup$ "Increasing the number of points increases Bob's chance of covering more area with more circles" Can you prove this? This is not a trivial claim. $\endgroup$
    – Eric
    Mar 28, 2022 at 6:30
  • 2
    $\begingroup$ My answer is marked true although I'm still not satisfied with the answer. Maybe the OP can explain in his own words. $\endgroup$
    – I'm Nobody
    Mar 29, 2022 at 5:05
3
$\begingroup$

Disappointing result, but hopefully interesting.

This solution is a fractal.

The first three iterations are pictured at the top, and the 'rewrite rule' is at the bottom. enter image description here

Points shown are approximate; Alice should place her points infinitesimally close to these ideal points, whilst ensuring that the depicted circles are a valid and optimal selection for Bob.

Alice can iterate this fractal as many times as desired, and can place points as close to the ideal points as desired, meaning that Alice can make her share arbitrarily close to that of the limit of the fractal.

Bob's area can be calculated as follows:

In the rewrite rule, there are four black circles of radius $\frac{1}{3}$, and four of radius $\frac{1}{6}$, for a total black area of $$k=4\cdot((\frac{1}{3})^2+(\frac{1}{6})^2)\cdot\pi=\frac{5}{9}\pi$$ There are also four blue circles of radius $\frac{1}{2}$, for a total blue area of $$b=4\cdot(\frac{1}{2})^2\cdot\pi=\pi$$ Thus, the percentage area of the rewrite rule covered when expanded infinitely, is $$r=\frac{k+br}{2\cdot\pi}$$ $$r\cdot(1-\frac{b}{2\pi})=\frac{k}{2\pi}$$ $$r\cdot(1-\frac{1}{2})=\frac{5}{18}$$ $$r\cdot\frac{1}{2}=\frac{5}{18}$$ $$r=\frac{5}{9}$$ We can use this to calculate the area covered by the whole fractal. In the initial state, there are two black circles of radius $\frac{1}{3}$ and two blue circles of radius $\frac{1}{2}$, giving a total area of $$a=\frac{2\cdot(\frac{1}{3})^2\cdot\pi+2\cdot(\frac{1}{2})^2\cdot\pi\cdot r}{\pi}=\frac{2}{9}+\frac{1}{2}\cdot r=\frac{2}{9}+\frac{1}{2}\cdot\frac{5}{9}=\frac{1}{2}$$

So, Alice can make her portion of the circle arbitrarily close to

50%. She's probably better off placing just the two points like in @I'm Nobody's answer. However, the fact that this random fractal satisfying the constraints ends up having an area of $\frac{1}{2}$ lends additional credence to that being the maximum.

Improve this answer
$\endgroup$
2
  • 5
    $\begingroup$ Can Bob do better by using this red circle? $\endgroup$
    – noedne
    Mar 28, 2022 at 0:24
  • $\begingroup$ @noedne Hmm, I guess so. I was pretty sure there was a way to place the points (with the whole 'infinitesimally close' thing) such that that's not possible, though, but I can't seem to think of it now $\endgroup$
    – tjjfvi
    Mar 28, 2022 at 13:50
2
$\begingroup$

Alice should

place a LOT of points really close to and all around the perimeter of D, more points is better.

This works because

a circle from Bob can only contain one of the points. Close proximity ensures either small circles or large circles centered outside of the area. (There's no rule against the centers of Bob's circles being outside of D.) In both cases, intersections between Bob's circles and D would be minimal.

Alice gets almost the whole area!

(I'd draw a picture, but I'm on mobile)

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ 1) If Alice only places points near the perimeter, then Bob will be able to draw a large circle in the center that only touches a point closest to the center. 2) The question does stipulate that Bob's circles are in D. $\endgroup$
    – noedne
    Mar 28, 2022 at 0:37
  • 2
    $\begingroup$ Also, even if all are exactly the same distance from the center, Bob will pick a circle that is tiny little bit off the center so it touches just one point, covering nearly all the space. $\endgroup$
    – Zizy Archer
    Mar 28, 2022 at 10:47
  • 1
    $\begingroup$ Fair points. My first Puzzling answer was less good than I thought. $\endgroup$
    – gregsdennis
    Mar 29, 2022 at 6:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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