24
$\begingroup$

We are given an operation $\oplus$ that is associative and commutative, has $0$ as a neutral element, and we know:

  • $1/10 \oplus 1/6 = 5/29$
  • $1/6 \oplus 2/3 = 7/10 $
  • $1/5 \oplus 2/5 = 3/7 $
  • $1/4 \oplus 3/4 = 2/3 $
  • $3/5 \oplus 1/3 = 3/4 $
  • $5/8 \oplus 7/8 = 10/27 $
  • $1/7 \oplus 1/7 = 0 $
  • $1/6 \oplus 1/5 = 2/9 $
  • $4/5 \oplus 1/5 = 3/4 $
  • $2/3 \oplus 3/4 = 1/4$
  • $1 \oplus 1/2 = 2$
  • $1 \oplus 2/3 = 3$
  • $2 \oplus 2/5 = 4$
  • $3 \oplus 2/7 = 5$

Question. $4/5 \oplus 5/6 = ?$

Bonus question: $1 \oplus 1/3 \oplus 1/5 \oplus 1/7 \oplus 1/9 \oplus \ldots = ?$

$\endgroup$
5
  • 2
    $\begingroup$ Are the numbers written as X/Y fractions as defined in 'regular' mathemathics or are they just a way to denote number pairs? Will X⊕1/2 be equal to X⊕2/4? $\endgroup$
    – jarnbjo
    May 29, 2019 at 10:30
  • $\begingroup$ @jarnbjo guessing by the fact that some are just the one number, one ought to assume they are regular fractions $\endgroup$ May 29, 2019 at 10:48
  • 2
    $\begingroup$ That's right @micsthepick $\endgroup$ May 29, 2019 at 10:49
  • $\begingroup$ By any chance was this question inspired by this one? $\endgroup$ May 29, 2019 at 19:27
  • $\begingroup$ No, it wasn't, @TheSimpliFire, but that question is interesting, too! $\endgroup$ May 30, 2019 at 4:15

2 Answers 2

16
$\begingroup$

The operation $\oplus$ is bitwise XOR, with non-negative fractions mapped via the Stern-Brocot tree to dyadic rationals from 0 to 1.

https://i.stack.imgur.com/8zKGo.png

For example, take $2 \oplus \frac{2}{5}$. Look at the first few layers of the Stern-Brocot tree drawn above and imagine the bottom line of number as a "ruler" divided into 32 equal sections. The horizontal position of the fraction $2/1$ in the tree maps to the $3/4$-point of the ruler, and $2/5$ to $3/16$-point. The denominators are always powers of 2, so can write them as terminating binary representations $0.11_2$ and $0.0011_2$. If we do bitwise XOR on each place value, we get $0.1111_2$, which is $15/16$.

    3/4  = 0.110000....
^   3/16 = 0.001100....
   --------------------
   15/16 = 0.111100....

The XOR is just adding without carrying. We look at each place value column separately, and write a 1 where the two summands are different and 0 where they are same.

Finally, we need to convert the position on the ruler back to a fraction in the tree. If we look 15/16 of the way on the ruler, we find fraction $4/1$ or $4$. So, $2 \oplus \frac{2}{5} = 4$.

Each successive layer of the Stern-Brocot tree is mapped to finer and finer dyadic rationals with increasingly large power-of-two denominators, like the marks on a ruler can yet finer marks placed at the halfway points.

enter image description here

Whereas each new mark is at a position that's the average of the two on either side, the corresponding fraction in the tree is the mediant of the two surrounding it, where the mediant of $a/b$ and $c/d$ is $(a+b)/(c+d)$. The rationals produced this way in the tree are all in simplified form.

We can answer the puzzle's question by computing $4/5 \oplus 5/6$ and get $1/6$

4/5 -> 15/32 = 0.111110000...
5/6 -> 31/64 = 0.111111000...
-----------------------------
1/6 ->  1/64 = 0.000001000...

Since bitwise XOR is clearly commutative and associative, so is the operation $\oplus$ which has just relabeled the dyadic fractions on $\left|0,1\right)$ as non-negative rationals in simplest form. This is also suggested by the puzzle using the symbol $\oplus$, which is commonly used for XOR. The identity is zero in both cases. Since any number XOR'ed with itself is zero, we too have the identity $x \oplus x = 0$.

For the bonus question $1 \oplus 1/3 \oplus 1/5 \oplus 1/7 \oplus \cdots $, we do:

1/1 -> 1/2   = 0.100000000...
1/3 -> 1/8   = 0.001000000...
1/5 -> 1/32  = 0.000010000...
1/7 -> 1/128 = 0.000000100...
...
-----------------------------
?   -> 2/3   = 0.101010101...

In the end, we're looking for a value in the tree positioned over $2/3$ on the ruler. This clearly can't be a rational, since those map to dyadic fractions. But, we can find a real number with the appropriate limit. To take the path to $2/3$ on the number line, we alternate going right and left down the Stern-Brocot tree, which takes us down the fractions:

$$ \frac{1}{1}, \frac{2}{1}, \frac{3}{2}, \frac{5}{3}, \frac{8}{5}, \frac{13}{8}, \dots $$

These are of course ratios of successive Fibonacci numbers, corresponding to iterating the map $\frac{p}{q} \to \frac{p+q}{p}$, and their limit is the Golden Ratio $\phi \approx 1.618$. So, $1 \oplus 1/3 \oplus 1/5 \oplus 1/7 \oplus \dots = \phi$.

$\endgroup$
4
  • $\begingroup$ I noticed how much this function was like xor, but I had absolutely no knowledge of anything that might work. $\endgroup$ May 30, 2019 at 10:50
  • 8
    $\begingroup$ it's fitting that xnor answer's the question that involves xor :) $\endgroup$ May 30, 2019 at 10:51
  • 1
    $\begingroup$ Damn it. I actually drew a Stern-Brocot tree yesterday while looking at this... $\endgroup$
    – Gareth McCaughan
    May 30, 2019 at 10:52
  • $\begingroup$ Wonderful answer!! $\endgroup$ May 30, 2019 at 15:02
7
$\begingroup$

Firstly, we notice:

$1/4 \oplus 3/4 = 2/3$
$2/3 \oplus 3/4 = 1/4$

So I have interpreted this generally to allow $x \oplus y = z \iff z \oplus y = x$

Also we have:

$1/4 \oplus 3/4 = 2/3$
$4/5 \oplus 1/5 = 3/4$

So again, in general $1/n \oplus (n-1)/n = (n-2)/(n-1)$

Hence $5/6 \oplus 1/6 = 4/5$

And finally:

$1/7 \oplus 1/7 = 0 $

implies $x \oplus x = 0$

And so to the question:

Question. $4/5 \oplus 5/6 = ?$

$4/5 \oplus 5/6$

$= (3/4 \oplus 1/5) \oplus (4/5 \oplus 1/6)$
$= 3/4 \oplus (1/5 \oplus 4/5) \oplus 1/6$
$= 3/4 \oplus 3/4 \oplus 1/6$
$=0 \oplus 1/6$
$=1/6$

$\endgroup$
5
  • 1
    $\begingroup$ Isn't the answer be equal to the ROT13(gur guveq grez, nf gur svefg naq frpbaq pnapryf rnpu bgure)? $\endgroup$
    – athin
    May 30, 2019 at 8:21
  • $\begingroup$ @athin; good spot! fixed. $\endgroup$
    – JMP
    May 30, 2019 at 8:26
  • $\begingroup$ @athin; which actually is what axiom 2 says! $\endgroup$
    – JMP
    May 30, 2019 at 8:30
  • $\begingroup$ The 4/5+5/6 thing can be deduced simpler. If rot13(k cyhf l rdhnyf m vzcyvrf m + l rdhnyf k), then rot13(vs svir fvkguf cyhf bar fvkgu vf sbhe svsguf, fb svir fvkguf cyhf sbhe svsguf vf bar fvkgu (pbzzhgngvivgl)) $\endgroup$
    – trolley813
    May 30, 2019 at 8:34
  • $\begingroup$ I tried using logic like this, but I kept either getting worse and worse expressions, or in loops :) $\endgroup$ May 31, 2019 at 1:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.