## Probability problem

**Moderators:** gmalivuk, Moderators General, Prelates

### Probability problem

Hi,

We have a squared grid 10x10.

We color randomly 50 squares in red and the remaining in blue.

We define a relation of ownership as follows :

A square A(i,j) (red or blue) is owned by the blue player if the number of the adjacent squares (orthogonally and diagonally) colored in blue surrounding A(i,j) is > to the squares colored in red. If the numbers are equal no one own that square A(i,j). Otherwise the red player owns that square.

There are 100 squares on the grid. Let us call :

B the squares owned by the blue player

R the squares owned by the red player

and N the number of squares not owned by any of the players

D=abs(R-B)

Can we find a closed formula for the law distribution of P(D=k) where k>=0 ?

Thank you for any clue

We have a squared grid 10x10.

We color randomly 50 squares in red and the remaining in blue.

We define a relation of ownership as follows :

A square A(i,j) (red or blue) is owned by the blue player if the number of the adjacent squares (orthogonally and diagonally) colored in blue surrounding A(i,j) is > to the squares colored in red. If the numbers are equal no one own that square A(i,j). Otherwise the red player owns that square.

There are 100 squares on the grid. Let us call :

B the squares owned by the blue player

R the squares owned by the red player

and N the number of squares not owned by any of the players

D=abs(R-B)

Can we find a closed formula for the law distribution of P(D=k) where k>=0 ?

Thank you for any clue

### Re: Probability problem

Can you clarify the ownership formula? Does the cell's own colour count, or only the colours of the neighbours? How does it work on the corners, do the neighbours "wrap around", or do the corner cells simply have fewer neighbours?

Am symmetry argument says that P(B=k) = P(R=k), but any further insight seems to be a combinatorial nightmare. Having exactly 50 red and 50 blue cells looks much harder than throwing a coin for each cell, because your cell colors stop being independent, making it much less likely to find a nice closed form.

Unfortunately, there's around 10^29 possibilities (a bit less if you exploit symmetries), which is too much for brute forcing.

Am symmetry argument says that P(B=k) = P(R=k), but any further insight seems to be a combinatorial nightmare. Having exactly 50 red and 50 blue cells looks much harder than throwing a coin for each cell, because your cell colors stop being independent, making it much less likely to find a nice closed form.

Unfortunately, there's around 10^29 possibilities (a bit less if you exploit symmetries), which is too much for brute forcing.

### Re: Probability problem

Tub wrote:Can you clarify the ownership formula? Does the cell's own colour count, or only the colours of the neighbours? How does it work on the corners, do the neighbours "wrap around", or do the corner cells simply have fewer neighbours?

Am symmetry argument says that P(B=k) = P(R=k), but any further insight seems to be a combinatorial nightmare. Having exactly 50 red and 50 blue cells looks much harder than throwing a coin for each cell, because your cell colors stop being independent, making it much less likely to find a nice closed form.

Unfortunately, there's around 10^29 possibilities (a bit less if you exploit symmetries), which is too much for brute forcing.

Only the colors of the neighbors count.

On the corners the edges are considered like occupied squares : the square in the corner up left is surrounded by 3 squares hence one of the players owns it.

Squares have 3, 5 or 8 neighbors.

Maybe simulation could give some results. A close formula using generating function (?)

### Re: Probability problem

There is maybe a way to find some pattern if we start by a grid 2x2 (2 blue 2 red) then 4x4 (8 blue, 8 red) and 2nX2n with n>4.

In 2x2 which easy to analyze B=2, R=2, N=0,D=0 for all the configurations.

Is this method going to lead to some close formula? I do not know for now.

In 2x2 which easy to analyze B=2, R=2, N=0,D=0 for all the configurations.

Is this method going to lead to some close formula? I do not know for now.

### Re: Probability problem

Tub wrote:Am symmetry argument says that P(B=k) = P(R=k), but any further insight seems to be a combinatorial nightmare. Having exactly 50 red and 50 blue cells looks much harder than throwing a coin for each cell, because your cell colors stop being independent, making it much less likely to find a nice closed form.

It's also rather easy to see that 64 is an upper bound for N. In general for a nxm grid N can never exceed (n-2)(m-2) and can always be 0.

-- edit: had D, where it should be N

Last edited by lorb on Thu Mar 02, 2017 7:38 pm UTC, edited 1 time in total.

Please be gracious in judging my english. (I am not a native speaker/writer.)

http://decodedarfur.org/

http://decodedarfur.org/

### Re: Probability problem

Perhaps Goahead52 can clarify the values of B, R, and N for the following situation, because I don't think it follows lorb's bound.

To me, it looks like the red cells all have one more blue neighbor than red neighbors and the blue cells all have two more blue neighbors than red neighbors. This would give B=16, R=0, N=0, D=16.

Did I misinterpret the rules?

Code: Select all

`RRRR`

BBBB

BBBB

RRRR

To me, it looks like the red cells all have one more blue neighbor than red neighbors and the blue cells all have two more blue neighbors than red neighbors. This would give B=16, R=0, N=0, D=16.

Did I misinterpret the rules?

### Re: Probability problem

DavidSh wrote:Perhaps Goahead52 can clarify the values of B, R, and N for the following situation, because I don't think it follows lorb's bound.Code: Select all

`RRRR`

BBBB

BBBB

RRRR

To me, it looks like the red cells all have one more blue neighbor than red neighbors and the blue cells all have two more blue neighbors than red neighbors. This would give B=16, R=0, N=0, D=16.

Did I misinterpret the rules?

No. Your results :

"B=16, R=0, N=0, D=16"

are right.

You understood well the rules.

### Re: Probability problem

DavidSh wrote:Perhaps Goahead52 can clarify the values of B, R, and N for the following situation, because I don't think it follows lorb's bound.

That is because I wrote D where it should have said N. :/

Please be gracious in judging my english. (I am not a native speaker/writer.)

http://decodedarfur.org/

http://decodedarfur.org/

### Re: Probability problem

lorb wrote:DavidSh wrote:Perhaps Goahead52 can clarify the values of B, R, and N for the following situation, because I don't think it follows lorb's bound.

That is because I wrote D where it should have said N. :/

Do you mean that for 10x10 grid that the value D could not reach 100 ?

I`m working on configuration such as D=100. I did not finished yet.

- gmalivuk
- GNU Terry Pratchett
**Posts:**25854**Joined:**Wed Feb 28, 2007 6:02 pm UTC**Location:**Here and There-
**Contact:**

### Re: Probability problem

No, writing D was the mistake. N cannot be 100 because the edges and corners are always owned by someone.

### Re: Probability problem

gmalivuk wrote:No, writing D was the mistake. N cannot be 100 because the edges and corners are always owned by someone.

In grid 4x4 a blue player (or the red player) could own all the squares. Look at the solution given above by DavidSh.

Why not in 10x10?

- WibblyWobbly
- Can't Get No
**Posts:**506**Joined:**Fri Apr 05, 2013 1:03 pm UTC

### Re: Probability problem

Goahead52 wrote:gmalivuk wrote:No, writing D was the mistake. N cannot be 100 because the edges and corners are always owned by someone.

In grid 4x4 a blue player (or the red player) could own all the squares. Look at the solution given above by DavidSh.

Why not in 10x10?

It's quite possible you can have all squares in a 10x10 grid owned by one player. What you can't have is more than 64 of the squares be unowned. Boundary squares must always be owned in a game in which all grid squares are initially assigned a color.

Now, if you don't assign colors to all 100 squares at the beginning, edge squares could become unowned. Not sure how that would affect the limit on N, though.

For the original idea of the upper bound on N: this is apparently true in higher dimensions as well, isn't it? Boundary squares/cubes/hypercubes will always have an odd number of neighbors?

- gmalivuk
- GNU Terry Pratchett
**Posts:**25854**Joined:**Wed Feb 28, 2007 6:02 pm UTC**Location:**Here and There-
**Contact:**

### Re: Probability problem

Why not what?Goahead52 wrote:gmalivuk wrote:No, writing D was the mistake. N cannot be 100 because the edges and corners are always owned by someone.

In grid 4x4 a blue player (or the red player) could own all the squares. Look at the solution given above by DavidSh.

Why not in 10x10?

N cannot be 100. I wasn't saying anything about D, and lorb admitted a mistake, so also wasn't intentionally saying anything about D.

### Re: Probability problem

The upper bound of N is obvious.

I`m interested by the values of D and their probability.

Until now if you put aside the simulation (which is easy to do for someone who is programmer) it is hard if not impossible to have a close formula for those values.

I`m interested by the values of D and their probability.

Until now if you put aside the simulation (which is easy to do for someone who is programmer) it is hard if not impossible to have a close formula for those values.

### Who is online

Users browsing this forum: No registered users and 8 guests