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$
  • 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 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$ – micsthepick May 29 at 10:48
  • 2
    $\begingroup$ That's right @micsthepick $\endgroup$ – Dominic van der Zypen May 29 at 10:49
  • $\begingroup$ By any chance was this question inspired by this one? $\endgroup$ – TheSimpliFire May 29 at 19:27
  • $\begingroup$ No, it wasn't, @TheSimpliFire, but that question is interesting, too! $\endgroup$ – Dominic van der Zypen May 30 at 4:15
15
$\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$
  • $\begingroup$ I noticed how much this function was like xor, but I had absolutely no knowledge of anything that might work. $\endgroup$ – micsthepick May 30 at 10:50
  • 8
    $\begingroup$ it's fitting that xnor answer's the question that involves xor :) $\endgroup$ – micsthepick May 30 at 10:51
  • $\begingroup$ Damn it. I actually drew a Stern-Brocot tree yesterday while looking at this... $\endgroup$ – Gareth McCaughan May 30 at 10:52
  • $\begingroup$ Wonderful answer!! $\endgroup$ – Dominic van der Zypen May 30 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$
  • 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 at 8:21
  • $\begingroup$ @athin; good spot! fixed. $\endgroup$ – JMP May 30 at 8:26
  • $\begingroup$ @athin; which actually is what axiom 2 says! $\endgroup$ – JMP May 30 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 at 8:34
  • $\begingroup$ I tried using logic like this, but I kept either getting worse and worse expressions, or in loops :) $\endgroup$ – micsthepick May 31 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.