Number theory problem

This is a discussion on Number theory problem within the A Brief History of Cprogramming.com forums, part of the Community Boards category; Assume you have a string of elements called w and b where w == 1 and b == -1. The ...

  1. #1
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595

    Number theory problem

    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.

  2. #2
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    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.

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  3. #3
    Software Developer jverkoey's Avatar
    Join Date
    Feb 2003
    Location
    University of Waterloo
    Posts
    1,903
    wwbwwbwb==2
    bbwbbwbw==-2

    -edit-
    axon beat me to it, lol

  4. #4
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    @ jeff

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  5. #5
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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.

  6. #6
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    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.
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  7. #7
    Software Developer jverkoey's Avatar
    Join Date
    Feb 2003
    Location
    University of Waterloo
    Posts
    1,903
    ........hmm, good point

  8. #8
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    exactly, the grammar rules are not very explicit...ELAD WE NEED AN EXPLANATION HERE!!!

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  9. #9
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    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*)
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  10. #10
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    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!
    Last edited by elad; 09-02-2004 at 10:39 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. memory issue
    By t014y in forum C Programming
    Replies: 2
    Last Post: 02-20-2009, 11:37 PM
  2. xor linked list
    By adramalech in forum C Programming
    Replies: 23
    Last Post: 10-14-2008, 10:13 AM
  3. Random Number Range Problem.
    By xamlit in forum C Programming
    Replies: 11
    Last Post: 01-26-2006, 11:55 AM
  4. number ouput problem...
    By o0obruceleeo0o in forum C++ Programming
    Replies: 7
    Last Post: 11-17-2002, 05:56 AM
  5. problem with my prime number program
    By datainjector in forum C Programming
    Replies: 4
    Last Post: 07-12-2002, 12:30 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21