Oxflip: Patterns and Sequences..

You need to find an invariant. That is, a function of the board position that doesn't change when you flip a row or column. Then show that the value of this invariant is different for the board with a single white counter.

I would have expected you would have been shown some other problems involving invariants. The classic one is http://en.wikipedia.org/wiki/Fifteen_puzzle

Reply 2

OP

DFranklin

You need to find an invariant. That is, a function of the board position that doesn't change when you flip a row or column. Then show that the value of this invariant is different for the board with a single white counter.

I would have expected you would have been shown some other problems involving invariants. The classic one is http://en.wikipedia.org/wiki/Fifteen_puzzle

Can you help me start it off, I still dont understand.

Reply 3

OP

Any Idea's?

Reply 4

fusionskd

Any Idea's?

Try making some moves, and make a note of how many black squares and how many white squares there are before and after each move.

Can you see a pattern? Can you prove it?

Reply 5

OP

DFranklin

Try making some moves, and make a note of how many black squares and how many white squares there are before and after each move.

Can you see a pattern? Can you prove it?

w->1 white
b->1 black

In a 2x2 square:

2b+2w

when theres just one w:

w+3b

(2w+2b)-(w+3b)=1(w-b)

for 3x3

5w+4b

when theres just one w:

w+8b

(5w+4b)-(w+8b)=4(w-b)

4x4

8w+8b

when theres just one w:

w+15b

(8w+8b)-(w+15b)=7(w-b)

5x5

13w+12b

when theres just one w:

(13w+12b)-(w+24b)=12(w-b)

The difference always has a factor of

(w-b)

and

3n+1

where n=0 for the 2x2 table. But what does this mean and can it help me? I'll try now just making different moves on the 4x4 and noting the pattern, but what can be deduced from above, and how can the pattern help me?

Reply 6

You've been asked a question about the 4x4 game - so just look at that, not the other cases.

What can you say about (w-b) (using your notation)?

Reply 7

OP

Ermm....isit that (w-b)=0...? Also the factor thats multiplying it is an even number of the sequence 3n+1....

Reply 8

fusionskd

Ermm....isit that (w-b)=0...?No. To repeat myself:

Start from some random positions (on the 4x4 grid), and make a few random moves. Write down the number of black and white pieces before and after each move.

Reply 9

OP

DFranklin

No. To repeat myself:

Start from some random positions (on the 4x4 grid), and make a few random moves. Write down the number of black and white pieces before and after each move.

Starting from:
8W+8B

Move made
8W+8B
Move made
10W+6B
Move made
12W+4B

I've Noticed that the whites tend to increase by 2 and the blacks are decreasing by 2. [Both being factors of 2]

So it can be gen as;
(W+2n)+(B-2n) = W+B

but the function of just one W and the rest B is W+15B....and niether '1' nor '15' is a factor of 2...

Does the above result suggest anything??

Reply 10

fusionskd

Starting from:
8W+8B

Move made
8W+8B
Move made
10W+6B
Move made
12W+4B

I've Noticed that the whites tend to increase by 2 and the blacks are decreasing by 2. [Both being factors of 2]From

WWWW
WWWW
BBBB
BBBB

I flip row 1 to get

BBBB
WWWW
BBBB
BBBB

So the whites have decreased by 4 and the blacks have increased by 4.

What does this do for your theory?

Reply 11

OP

DFranklin

From

WWWW
WWWW
BBBB
BBBB

I flip row 1 to get

BBBB
WWWW
BBBB
BBBB

So the whites have decreased by 4 and the blacks have increased by 4.

What does this do for your theory?

It can also be:
BBBB
BBBB
WWWW
WWWW

I flip row 1 to get

WWWW
BBBB
WWWW
WWWW

Here the whites have increased by 4 and blacks have decreased by 4...this erm suggests that they can increase or decrease by 2n? OR It could mean erm the increase/decrease is always an even number..? but W+15B are odd [1,15]..If none of the above are even close could you give me another clue. Im really annoyed I cant get this and I cant thank you enough for helping me! Thank you

Reply 12

fusionskd

Here the whites have increased by 4 and blacks have decreased by 4...this erm suggests that they can increase or decrease by 2n?I've no idea! Because you've not explained what n is.

OR It could mean erm the increase/decrease is always an even number..? but W+15B are odd [1,15]..If none of the above are even close could you give me another clue.

No, you're close.

So, you need to form a hypothesis about the increase/decrease.
Then you need to prove it.
Then you need to deduce that [1,15] isn't possible, because of your hypothesis.

Reply 13

OP

DFranklin

I've no idea! Because you've not explained what n is.

No, you're close.

So, you need to form a hypothesis about the increase/decrease.
Then you need to prove it.
Then you need to deduce that [1,15] isn't possible, because of your hypothesis.

The increase/decrease depends on how many blacks [or whites] you change in that specific row or column, which is common sense really. The increase of whites leads to a decrease of blacks. The increase/decrease is given by (nW-pB) where n is the amount of whites to be changed and p is the amount of blacks to be changed.

WWBW [n]
BBWB
BBWB
BBWB

3W-1B=2
The increase of B will be 2, the decrease of white will also be 2.

In another situation;

WWWW
WWWW
BBBB
BBBB [n]

0W-4B=-4
The increase of B will be -4 [Hence a decrease], The decrease of W will be -4 [Hence an increase]

???
I Really hope im going somewhere with this.

So the increase/decrease is determined by nW-pB

in the situation of the one white;
8W+8B
to
W+15B
difference=
7W-7B

Its obvious that it cant be achieved...but how can i explain it....I must be waffling....

Reply 14

Maybe I should have said you were very close.

Here's another suggestion:

When you flip a row, obviously it's only the contents of that row that matter.

So, for example, when you flip a row that is WWWB, you get BBBW, for a net increase of 2 black.

There are only 16 possible arrangements of 4 pieces, so if you calculate the change for each of the 16, you will have found all the possible ways the totals can change.

Reply 15

OP

DFranklin

Maybe I should have said you were very close.

Here's another suggestion:

When you flip a row, obviously it's only the contents of that row that matter.

So, for example, when you flip a row that is WWWB, you get BBBW, for a net increase of 2 black.

There are only 16 possible arrangements of 4 pieces, so if you calculate the change for each of the 16, you will have found all the possible ways the totals can change.

The question say, Don't try and write out every possible combination of moves, So surely there is another way?

But lets see....Has it got to do with the fact that the increase/decrease is always an even number?

p.s I havent been taught this stuff, I'm learning as I go with this, I just thought i'd take a look at the oxford paper and It included that problem. I'm an A-level student looking to do Mathematics at uni

Reply 16

fusionskd

The question say, Don't try and write out every possible combination of moves, So surely there is another way?There are a lot more than 16 possible combinations of moves. Yes, there are other ways, but you don't seem to be spotting them. So what I was pointing out is one way that will let you get to a solution: not the neatest way, or the shortest way, but a way.

But lets see....Has it got to do with the fact that the increase/decrease is always an even number?

Well, yes, it does. But you are calling it a fact. Why is it a fact? You haven't proved it.

Edit: I've realised you don't know this stuff. I read the "for applicants in computer science" and for some silly reason thought it meant for people already studying computer science.

Reply 17

OP

DFranklin

There are a lot more than 16 possible combinations of moves. Yes, there are other ways, but you don't seem to be spotting them. So what I was pointing out is one way that will let you get to a solution: not the neatest way, or the shortest way, but a way.

Well, yes, it does. But you are calling it a fact. Why is it a fact? You haven't proved it.

Edit: I've realised you don't know this stuff. I read the "for applicants in computer science" and for some silly reason thought it meant for people already studying computer science.

This is infact the first time i've tried to solve a problem like this {apart from trying to figure out tic-tac-toe} lol, and i'm doing badly already :frown:

. I really want to solve this now..lol.

So my goal is to try and prove, somehow, that the increasing/decreasing is always an even number.

Btw I'm sorry for taking up a lot of your time...If I end up giving up, would you mind showing me how its done, step by step :biggrin:

Reply 18

fusionskd

So my goal is to try and prove, somehow, that the increasing/decreasing is always an even number.

Yes.

What I would suggest is that however you try to prove it, you need to be methodical. You need to persuade the reader that what you are saying really is true in all cases.

Btw I'm sorry for taking up a lot of your time...If I end up giving up, would you mind showing me how its done, step by step :biggrin:

No problem.

Reply 19

OP