PDA

View Full Version : Number theory problem



elad
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
The answer is no.

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*)

elad
09-02-2004, 10:02 AM
Rule 1 was meant to mean that you add each new element to the back of an existing string to create a new valid string. Sorry if that was unclear.

I interpret Rule 3 to mean that if a string has an odd number of elements then it must be of value 1 or -1. Therefore, for a string to have a value of 2 or -2, the string must have an even number of elements. However, by Rule 1 each string with an even number of elements is built from a shorter string of odd numbered elements, so each sub-string of the string starting with the first element must also be legal. Therefore, I agree with PJYelton and Xsquared in their opinion regarding the strings submitted by Axon and Jverkoey---because if a substring with an odd number of elements fails, the whole string fails.

My summary answer is that if the last value added to a string is -1, for the result to be 2, then the initial value had to be 3. But this is not possible because as a result of Rule 3 each substring with an odd number of elements has to have a value 1 or -1. Therefore, adding a 1 or a -1 to either value will not get to 3. The converse (inverse?) happens if the string ends in 1 (or w). Therefore, the answer is no.


It was nice to see the strings developed by jverkoey and Axon because I had developed a large number of similar strings until I came to my conclussion. It was nice to see the response from PJYelton and Xsqaured because I ruled out those strings by the same logic. It was nice to see Sang-drax's response, because it seems a little more rigorous than my summary, eventhough I think they say the same thing.

Overall, thanks everyone for input!