Problem 213

[Harleqin]

Regarding Problem 213, is it correct that a single ring of bell for a 4x4 grid would produce 5.037 empty fields? I hope that I do not give away too many hints with this question.

[stijn263]

I get 4.77777..

[Harleqin]

Yes, I discovered that too. I made a mistake at the end. I get 4.(7) now, too. Strangely, my answer for the problem is still wrong.

[Harleqin]

OK, i check and double check but find no fault.

Can someone verify the following numbers?

grid   bells     empty fields
4x4    1         4.7
4x4    2         4.832873369857695
4x4    3         4.879353255023087
6x6    1         10.9600694
6x6    2         11.012615125394921
6x6    3         11.091047817241131

Do I perhaps have a precision problem?

[stijn263]

You only got the ones with one bell ring correct, the others are too far off to be a precision problem

[Harleqin]

Thank you. That points me directly to the part where the problem should be. However, I am quite sure that the way I'm doing that is correct.

[David F]

I hope this isn't regarded as giving too much away:

You might want to do the following conceptual check:

After a large number of iterations (>900, say), Is it possible for your algorithm to decide the probability of a cell containing over 900 fleas is greater than 0?

(If so, there's a problem, obviously).

[bearface]

While I believe I understand the problem, my inability to produce the correct answer to the original problem and the simpler 4x4 problem lead me to conclude I am fundamentally misinterpreting the problem.

For the 4x4 problem, I get the following distribution of fleas after one bell:

0.666666667 1.083333333 1.083333333 0.666666667
1.083333333 1.166666667 1.166666667 1.083333333
1.083333333 1.166666667 1.166666667 1.083333333
0.666666667 1.083333333 1.083333333 0.666666667

There are no empty cells, and even if you allow for the possibility of fleas in the corner cells and on the edge of the field jumping off of the field, there wouldn't be any empty cells after one bell.

I'm hoping somebody can nudge me towards the correct understanding of the problem. Thank you.

[stijn263]

The problem does not ask for the expected number of fleas on each square (which you computed), but the average number of empty squares on the entire grid.

Let me write out the 2x2 problem. All fleas can jump to one of the 2 adjacent squares, giving the following 16 possible outcomes:

22  21  21  20
00  10  10  20

12  11  11  10
01  11  11  21

12  11  11  10
01  11  11  21

02  01  01  00
02  12  12  22

Giving an expected number of empty squares:
[frac]2,16[/frac]+[frac]1,16[/frac]+[frac]1,16[/frac]+...+[frac]2,16[/frac] = [frac]6,16[/frac]+[frac]2,16[/frac]+[frac]2,16[/frac]+[frac]6,16[/frac] = 1

Thus after 1 bell ring, the expected number of empty squares is 1.

[Harleqin]

I hope this isn't regarded as giving too much away:

After a large number of iterations (>900, say), Is it possible for your algorithm to decide the probability of a cell containing over 900 fleas is greater than 0?

No. In fact, I check that the overall number of fleas remains constant over all iterations.

[bearface]

Thank you stijn263.

[quilan]

Problem 213 (View Problem)

So, this is the first PE problem in a long long long time that has me completely & utterly flummoxed. I've spent long hours each day thinking of methods to solve this, and each ended up being O(a^{x^2}) or something silly like that. That being said, it turns out even my methods of testing random iterations is off. Can anyone confirm on which of the two a 20x20 grid with 50 bell rings is closer to: ~147, or ~166? I'm inclined to believe ~147.

Also, can this problem be done just based on self-knowledge & inference, or does it need (like for example Problem 199 (View Problem)) a bit of outside information / background knowledge to easily do it?

[hk]

Closer to 147.
No outside information needed.

[David F]

Without giving much away, this is one of those problems where finding the right approach is pretty much the entire battle. Almost every solution posted has been essentially the same.

With the right approach, it's not a particularly hard problem. (Nowhere near the difficulty of, say, P198).

[JohnMorris]

You're not alone: it took me a while to get my head round Problem 213 (View Problem) too.

What helped me was writing a Monte-Carlo simulation and running it a few hundred thousand times. It was never (in my lifetime) going to give the right answer to the precision needed, but it did give me a feel for the magnitude of the answer and let me sanity check some of my calculated intermediate results.

(I shall gloss over the fact that I lost two days searching for a bug in my calculation which gave answers about 5% different from the simulation, then to find that the error was in the simulation itself...)

[stijn263]

Even closer to 147.1

Also, can this problem be done just based on self-knowledge & inference, or does it need (like for example Problem 199 (View Problem)) a bit of outside information / background knowledge to easily do it?

Well you do need to know something about expected values

[albert]

The flea problem request "6 decimal places".
Do the numbers before the decimal point count?
i.e. ##.####
or is it
##.######

Thanks

[Tommy137]

wikipedia:

decimal places (the number of digits following the point)

[tjgillies]

skip

Edit by hk:
all code skipped. (nothing remains)
If you want to make a contribution you can do so in the problem forum

[LarryC]

Hi!

I'm finding Problem 213 awfully tough to get round but I think I have a correct method now... except I get the answer wrong! Below are a list of expected values with bell rings and grid size:

Grid Size	Bell Rings	Expected Value
	4		1		4.778
	4		2		5.338
	4		3		5.639

Would it be possible to have them checked?

Thanks,
Lster