25

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 = ?$

2 Answers2

17

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$.

xnor
  • 26,756
  • 4
  • 85
  • 144
8

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$

JMP
  • 35,612
  • 7
  • 78
  • 151
  • 1
    Isn't the answer be equal to the ROT13(gur guveq grez, nf gur svefg naq frpbaq pnapryf rnpu bgure)? – athin May 30 '19 at 08:21
  • @athin; good spot! fixed. – JMP May 30 '19 at 08:26
  • @athin; which actually is what axiom 2 says! – JMP May 30 '19 at 08:30
  • 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)) – trolley813 May 30 '19 at 08:34
  • I tried using logic like this, but I kept either getting worse and worse expressions, or in loops :) – micsthepick May 31 '19 at 01:05