[Puzzler] Robin & Marian

[Mike]

(Copied from 538. This is the one I got really excited about. I rarely solve their "hard" puzzle, but I got this one, and the final answer just tickled the crap out of me when I realized what it was.)

Robin of Foxley has entered the FiveThirtyEight archery tournament. Her aim is excellent (relatively speaking), as she is guaranteed to hit the circular target, which has no subdivisions — it’s just one big circle. However, her arrows are equally likely to hit each location within the target.

Her true love, Marian, has issued a challenge. Robin must fire as many arrows as she can, such that each arrow is closer to the center of the target than the previous arrow. For example, if Robin fires three arrows, each closer to the center than the previous, but the fourth arrow is farther than the third, then she is done with the challenge and her score is four.

On average, what score can Robin expect to achieve in this archery challenge?

Note that Robin stops firing arrows as soon as she shoots one that isn't closer than all the ones before it, and her score is the total number of arrows fired. Therefore, her minimum score is 2, because the first one is always closest (it's the only one), then if the second shot is further away, she stops firing and has a score of 2.

[FlameBlade]

I want to recheck my assumptions, but it looks like infinite sum of k/2^k. Which is neat on own.

However, that is assuming that the expectation is that the area would be halved with each shot. I am not convinced on that front. The ratio of radius is something like square root of 2. I just need to think about the question. My current expectation is 4. I just hate computing with circles. I want to program this up and make sure that it's indeed around 4, and if not, get a hint of why not.

[Mike]

To be fair, the answers won't be up til next week, so I'm not sure that my answer is right, but it's so elegant that I feel like it has to be... Like the odd scoring system is specifically to produce this result.

If you want my assumption: I assumed that at any point, you will have X arrows. The chance that any given arrow will be the closest will be 1/X. So the first arrow is by definition closet. The 2nd has a 50-50 chance of being closest. If you get a third arrow, it has a 1 in 3 shot at being closest. Etc. Again, no matter what stage you're at, you just have X randomly placed arrows, and all you care about is the last one.

[FlameBlade]

I think the flaw with that the assumption is that the probability is not distributed uniformly across the distance from the center. When I say that and seeing your work, I think I have a new idea. Going to be tricky to work it out.

[FlameBlade]

I was going by the area. The expectation is half the area each shot. Then the expectation of the next half, but I think that's wrong.

[FlameBlade]

my monte carlo simulation shows me that we're wrong. The answer is approximately e.

Discussion: I figured out that it's best to select a point along the line of radius, and project it around the circle. So, effectively, sqrt(random) where random is (0,1), to generate a distribution that is more akin to an area of circle, but the point on the radius represents ever-growing circle.

Let us step away for a bit. A point on a circle can be represented by:

x = sqrt(r)*cos(theta)
y = sqrt(r)*sin(theta)

we're interested in an unit circle, where the radius is 1. If radius is 1...and no matter what theta, we have the
equation of x**2 + y**2 = 1.

But we are interested in selecting a point on the circle, so we have x**2 + y**2 <= 1.

So we randomize r = [0,1], and do monte carlo. In this sense, it is sufficient to say r <= 1. But to get a point, we need to use sqrt(r), so that's what
we are randomizing for monte carlo method.

And the answer is e.

I basically ran trials, then summed up probability distribution along with its score, and bam, the answer is e.

Now when I think about it, I see my flaw in the arguments, and I bet that there's an infinite series that may help...

https://en.wikipedia.org/wiki/List_of_r ... tions_of_e

I want to say k+1 / k! might be the way to go. Will ahve to think more, and this is way too late for me at the moment.

[Mike]

I also came up with the answer e.

If two arrows both hit the target at completely random points, then it makes sense that they both have an equal likelihood of being closest to the center. So the second shot has a 50% chance of being farther away. So half of all attempts will end with a score of 2.

If you shoot 3 random arrows, then all three have an equal chance of being the closest. So if you get a third shot, there is a 2/3 chance that it will not be closest and you end with a score of 3. But a 1/3 chance it IS closest and you get another shot.

Next shot has a 1/4 chance of being closest... and so on.

I strung together all of these probabilities times the score achieved at each level and it simplified to the sum 1/k! from 0 to . I did not recognize it, so I ran the summation and recognized 2.718 as e. Only when I googled Euler's number did I see this:


And realized someone had deliberately constructed this to walk us down this path. How very nice.

[FlameBlade]

Yep, came baxk to say you were correct in the first place after thinking overnight. When I have so many different tools, I get a bit flustered at times. Probability distribution isn't important, but rather, it can be projected as a random distribution between 0 and 1.

Other way of viewing. Number of shots is a sequence, and only that sequence would get that exact correct ordering. Thats 1 over n! for that ordering, then you sum it up. Getting the equation in the picture you posted.

[Mike]

Other way of viewing. Number of shots is a sequence, and only that sequence would get that exact correct ordering. Thats 1 over n! for that ordering, then you sum it up. Getting the equation in the picture you posted.

Oh damn... that would have been way simpler than all the probability trees I was drawing. Cool!

[FlameBlade]

however, the problem doesn't end there -- we need to compute expectation as well, now that we have probability distribution.

Thankfully, terms cancel out nicely to get us that summation exactly.

[Mike]

The bonus question for this one is: What if the target was divided into 10 concentric circles, numbered 1-10 with 1 at the center. Arrows still land randomly, but each shot has to land in a lower number ring than the last. What is the average expected score in this case?

This one got away from me and I gave up.

[Mike]

The bonus question for this one is: What if the target was divided into 10 concentric circles, numbered 1-10 with 1 at the center. Arrows still land randomly, but each shot has to land in a lower number ring than the last. What is the average expected score in this case?

This one got away from me and I gave up.

Starting from the beginning...
1 circle - 2
2 circles - 35/16 = 2.1875
3 circles - 578/243 ~ 2.3786
4 circles - uh... crap... this'll take me a while

I'm not seeing the pattern yet. It's something to do with combinatorics, but I don't have enough background knowledge. So even though I can brute force calculate 4 circles and maybe even 5, 10 is going to be impossible. I know infinity circles is e, but that's no help.

[Mike]

The bonus question for this one is: What if the target was divided into 10 concentric circles, numbered 1-10 with 1 at the center. Arrows still land randomly, but each shot has to land in a lower number ring than the last. What is the average expected score in this case?

This one got away from me and I gave up.

Starting from the beginning...
1 circle - 2
2 circles - 35/16 = 2.1875
3 circles - 578/243 ~ 2.3786
4 circles - uh... crap... this'll take me a while

I'm not seeing the pattern yet. It's something to do with combinatorics, but I don't have enough background knowledge. So even though I can brute force calculate 4 circles and maybe even 5, 10 is going to be impossible. I know infinity circles is e, but that's no help.

4 circles - 156,009/65,536 ~ 2.3805

Yeah, no way. The next one has a denominator of almost 10 million, and I can't wrap my head around any way to shortcut this yet.

[Eliahad]

Can't you do the same idea you had before?

You really only get 10 shots at the most, right?

Which gives you !10 possible combinations.

The perfect score is only 1 of those possible outcomes. The 2nd most perfect has 9 combinations. The third most perfect has... Etc? So yeah, combinatorics.

But the thing is, you would stop shooting after 2 arrows on some of those combinations...okay fine, it's trickier than I thought. I have to work on other things, but my heart will be here.

[Eliahad]

Also, why do I feel like it's going to head toward the golden ratio?

[Mike]

Can't you do the same idea you had before?

You really only get 10 shots at the most, right?

Which gives you !10 possible combinations.

The perfect score is only 1 of those possible outcomes. The 2nd most perfect has 9 combinations. The third most perfect has... Etc? So yeah, combinatorics.

But the thing is, you would stop shooting after 2 arrows on some of those combinations...okay fine, it's trickier than I thought. I have to work on other things, but my heart will be here.

I started here, but realized that the sectioning complicates it. Each arrow will land randomly in one out of 10 areas, so you are basically generating a random 10-digit number with each volley of 10. But because the larger numbers take up more area on the target, larger digits are more likely in all cases (you have a 1 in 100 chance of getting a 1, but a 19 in 100 chance of getting a 10).

Like I say, if I just follow those guidelines, I can brute force it, but that quickly becomes prohibitive. If I were better at programming, I could maybe figure out a way for a computer to do all of this and get a final result, but I'm not that good. So I'm hoping to have some sort of insight that lets me do slightly less complicated work, but I'm not seeing it yet. I'm really locked in on this and can't see past it.