PDA

View Full Version : Number theory problem

09-01-2004, 09:00 PM
Assume you have a string of elements called w and b where w == 1 and b == -1. The value of the string is the sum total of adding up each w and b in the string. For example: the value of wbw is 1, and the value of wbww is 2, etc.

Rules:
1) The string is developed by adding one element at a time onto the end of the existing string.
2) You can't add more than 2 w or 2 b in a row.
3) If the string consists of an odd number of elements the difference between the number of w and the number of b can't be greater than 1.

Question:
If the string ends in b can the value of the string ever be 2, or visa versa if the string ends in w can the value of the string ever be -2?

Answer: Not that I can figure out. Can anybody develop a string to show otherwise?

Reason for asking--I'm trying to develop an algorithm to pair up players in a chess tournament according to Swiss Tournament rules and came up with this tidbit which I thought was interesting.

axon
09-01-2004, 09:12 PM
bwwbwwbwwb = 2

-1 + 1 = 0 + 1 = 1 - 1 = 0 +1 = 1 + 1 = 2 -1 = 1 + 1 = 2 + 1 = 3 - 1 = 2

this works if I'm following all the exceptions of your grammar - and I think I am. There is an even number of characters (10); no more than two of the same characters in a row.

jverkoey
09-01-2004, 09:12 PM
wwbwwbwb==2
bbwbbwbw==-2

-edit-
axon beat me to it, lol

axon
09-01-2004, 09:13 PM
:p @ jeff

PJYelton
09-01-2004, 09:25 PM
I'm not sure if either of those examples apply since it depends on if the string must follow the rules with the addition of each new character.

If so, then Axon's is invalid since bwwbwwbwwb is impossible to reach since bwwbwwbww goes against rule 3. Same with jverkoeys examples which both break rule 3 at game 5.

XSquared
09-01-2004, 09:27 PM
It depends on your interpretation of the rules. I read number 3 as meaning any substring also (assuming the substring starts at the first letter), because it says that you add a letter onto an existing string (which I assume the same rules apply to), so in that case both of your examples fail.

jverkoey
09-01-2004, 09:27 PM
........hmm, good point

axon
09-01-2004, 10:04 PM
exactly, the grammar rules are not very explicit...ELAD WE NEED AN EXPLANATION HERE!!! ;)

Sang-drax
09-02-2004, 04:51 AM

We have:
w = 1
b = -1

We want a sequence S = 2 that ends in a b

S = Xb = 2 where X is an arbitrary sequence
X = 3 because b = -1

If X has an odd number of elements X cannot equal three because of rule 3).

If X has an even number of elements X can be written:
X = Ya where a is either w or b

Y is odd and can equl max 1 according to rule 3). a can equal max 1 (w). Thus, X can equal maximum 2.

Conclusion: It isn't possible.

The opposite case can be proven in the same way.

(You almost had me miss my math class *hurries away*)