## Probability problem

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### 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

Tub
Posts: 372
Joined: Wed Jul 27, 2011 3:13 pm UTC

### 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.

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### 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 (?)

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### 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.

lorb
Posts: 404
Joined: Wed Nov 10, 2010 10:34 am UTC
Location: Austria

### 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/

DavidSh
Posts: 108
Joined: Thu Feb 25, 2016 6:09 pm UTC

### 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.

Code: Select all

`RRRRBBBBBBBBRRRR`

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?

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### 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

`RRRRBBBBBBBBRRRR`

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?

"B=16, R=0, N=0, D=16"
are right.

You understood well the rules.

lorb
Posts: 404
Joined: Wed Nov 10, 2010 10:34 am UTC
Location: Austria

### 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/

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### 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: 26082
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.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### 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

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: 26082
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

### 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?
Why not what?

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.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### 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.