1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Challenge III: Rational Tangles, solved by pwsnafu

  1. Aug 5, 2013 #1
    The newest challenge is the following:

    As an example, we can easily go from ##0## to ##-1/3##. Indeed, we can apply ##T## to ##0## to go to ##1##, we apply ##T## to go to ##2##, we apply ##T## to go to ##3##, and then we apply ##R## to go to ##-1/3##.
    Last edited by a moderator: Aug 8, 2013
  2. jcsd
  3. Aug 5, 2013 #2


    User Avatar
    Science Advisor

    Might as well start.

    Well ##R^{-1} = R## and ##T^{-1} = RTRTR## so that shows we can invert any combination.
    Secondly, observe
    ##T^c R T^b R T^a (0) = c - \frac{1}{b - \frac{1}{a}},##
    and in general
    ##T^{k_1} R T^{k_2} \ldots T^{k_n}(0) = k_1 - \frac{1}{k_2 - \frac{1}{\ldots - \frac{1}{k_n}}}##
    We get something similar to continued fractions, the only difference being the subtractions instead of additions. But every positive rational number can be written in this form for the same reason that every rational can be written as a continued fraction (just change "integer part" to "integer part + 1" in the algorithm). So we can map 0 to any positive rational. R'ing that means we get every negative rational.

    Hmm, there's probably something left to prove. Oh well.
  4. Aug 5, 2013 #3
    Posting an answer would be kind of cheating, since I've encountered it before. Someone might be interested to know that T and R are generators of the modular group [itex]\Gamma[/itex] of transformations of the upper half-plane. Answering the question amounts to proving that [itex]\Gamma[/itex] acts transitively on [itex]\mathbb{Q}[/itex].
  5. Aug 6, 2013 #4


    User Avatar
    Homework Helper

    Further insight into micro's hatred of Wikipedia and arithmetic. Clearly we have a group whose action on 0 generates Q. As pwsnafu points out we can use continued fractions. It was quite a macro oversight not to provide the reader with
    Don't you like to subtract?
    Last edited: Aug 6, 2013
  6. Aug 6, 2013 #5
    Surely a challenge question would require the reader to derive facts like the above for themselves.
  7. Aug 6, 2013 #6


    User Avatar
    Science Advisor

    I found deriving that equation quite fun. So I'm glad micro didn't write that. :approve:
  8. Aug 6, 2013 #7


    User Avatar
    Homework Helper

    The following algorithm takes any rational number to a natural number:

    1. If a/b is a natural number, stop.
    2. Else if a/b < 0, apply T.
    3. Else if a/b > 0, apply R.
    4. Repeat.

    The only way this could fail to terminate is if it gets stuck in a rule or cycles continuously. Getting stuck in rule 2 is not possible by the Archimedean property of the integers. Getting stuck in rule 3 is not possible because it takes positive numbers to negative numbers. Cycling from rule 2 to 3 and back again is not possible because the first positive number after a chain of rule T's will be < 1, therefore rule R will reduce the size of the denominator. Eventually, it'll reduce it to 1. This is sufficient to show that the algorithm terminates.

    To extend this, given any two rational numbers, apply the algorithm to each giving two natural numbers N < M. Apply T finitely many times to transform N into M. Then, if R and T are invertible, invert the process that generated M and voila.
  9. Aug 6, 2013 #8
    Not sure why you think I should give a partial solution in a challenge question...

    Anyway, very big congratulations to pwsnafu for giving such a short and elegant solution. And of course, a congratulations to verty as well for providing a more elementary solution. I hope you enjoyed it.

    For a cool application of this question to knot theory, anybody interested can go to:

    A new question will be up shortly!!
    Last edited: Aug 6, 2013
  10. Aug 6, 2013 #9
    Challenge V: Sylvester-Gallai Theorem, solved by Mandelbroth

    I didn't get anywhere with it, but I'm pleased to find I was going in this very direction. I just didn't know how to show it.

    Also, micromass, your second link is giving me a 404 Not Found error.
  11. Aug 6, 2013 #10
    Should work now.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Similar Threads for Challenge Rational Tangles
Challenge Intermediate Math Challenge - May 2018
Challenge Basic Math Challenge - May 2018
Challenge Origami Puzzle Challenge
Challenge Math Challenge by QuantumQuest #4
Challenge Math Challenge by mfb #1