Puzzling Asked by A. Rex on January 6, 2021

Given two non-negative integers $x$ and $y$, let $xoplus y$ denote the *bitwise exclusive or* (XOR) of the numbers $x$ and $y$. This is the result of writing $x$ and $y$ in binary notation, then XORing corresponding bits (also known as "addition without carry"), and finally interpreting the result as a number again. This operation is often represented by the expression `x ^ y`

in programming languages and is also known as nim-addition. This operation is commutative and associative, so one can take the XOR of more than one number in any order and simply write $xoplus yoplus z$.

It’s important to note that we view $xoplus y$ as an operation on *numbers* here, not on strings, which is consistent with its behavior in various programming languages. For example, Python will happily report that `123 ^ 456 ^ 789 == 678`

, which you can see by examining the columns of the following table, where we use a subscript like $123_{10}$ to mean *decimal notation* and $0001111011_2$ to mean *binary notation*:

$$begin{align*}

123_{10} &= 0001111011_2

456_{10} &= 0111001000_2

789_{10} &= 1100010101_2

678_{10} &= 1010100110_2.

end{align*}$$

[*Hint*: check that each column of bits has an even number of $1$s.]

Motivated by a recent challenge on the Code Golf Stack Exchange, "For what block sizes is this checksum valid?" (which was the #1 Hot Network Question for a while!), let us call a collection of numbers *good* if their XOR is zero, and *bad* otherwise. For example, the set ${123_{10}, 456_{10}, 789_{10}, 678_{10}}$ is good. In other words, a collection is *good* if "the checksum is valid".

Given a *bitstring* like $101$, one can interpret the string in binary as $101_2 = 5_{10}$, or in decimal notation as $101_{10} = 1100101_2$. By analog to binary-coded decimal, one might call the latter interpretation *decimal-coded binary* (of $101$), meaning we use an entire decimal *digit* to represent a single binary *bit*.

Given a *collection* of bitstrings, like ${10, 100, 110}$, one can interpret the strings in binary like ${10_2, 100_2, 110_2}$ *or* in decimal notation like ${10_{10}, 100_{10}, 110_{10}}$. Sometimes, like in this case, it happens that both the interpretations are good, meaning $10_2oplus 100_2oplus 110_2 = 0$ and $10_{10} oplus 100_{10} oplus 110_{10} = 0$ as well:

$$begin{align*}

10_{10} &= 0001010_2

100_{10} &= 1100100_2

110_{10} &= 1101110_2.

end{align*}$$

Unfortunately, sometimes the binary interpretation is good but the decimal interpretation is bad, like in the case ${100,1000,1100}$ which is good in binary because $100_2 oplus 1000_2 oplus 1100_2 = 0$ but where unfortunately the decimal interpretation has $100_{10} oplus 1000_{10} oplus 1100_{10} = 1984_{10}$:

$$begin{align*}

100_{10} &= 00001100100_2

1000_{10} &= 01111101000_2

1100_{10} &= 10001001100_2

1984_{10} &= 11111000000_2.

end{align*}$$

Of course, it is very often the case that *both* binary and decimal interpretations are bad; this is the usual situation for a random collection. (Checksums are unlikely to be valid by accident.) Thus we have examples of "binary good and decimal good", "binary good but decimal bad", and "binary bad and decimal bad". That leaves a final possibility: "binary bad but decimal good".

Find a collection of bitstrings that is good when interpreted as *decimal numbers* but is bad when interpreted as *binary numbers*.

That is, find a collection of **bitstrings** (ie, strings of $0$s and $1$s) $${abcdotsc def,quad dotsb,quad uvwdotsc xyz }$$ so that the "decimal-coded binary XOR" vanishes, meaning $$abcdotsc def_{10} oplus dotsb oplus uvwdotsc xyz_{10} = 0$$ but their "usual XOR" doesn’t, meaning $$abcdotsc def_{2} oplus dotsb oplus uvwdotsc xyz_{2} ne 0.$$

One answer is:

This was obtained with a computer search using Magma, with the following code:

```
n:=25;
V:=VectorSpace(GF(2),2*n);
W:=sub<V|{V.i:i in {1..n}}>;
S:={};
A:=[];
for i in {1..200} do
t:=IntegerToSequence(i,2);
s:=IntegerToSequence(SequenceToInteger(t,10),2);
Include(~S,V!(t cat [0:j in {1..n-#t}] cat s cat [0:j in {1..n-#s}]));
if (Dimension(sub<V|S> meet W) ge 1) then print i; break; end if;
end for;
```

This code searches for the set of integers with this property with the smallest maximum element. For each integer ?, we create the binary expansion of this integer as ?, and then ? is the "decimal expansion" of the same string of 0s and 1s, converted back to binary. By appending these strings together in a single vector, we can look for solutions where the last half of the vector (the decimal expansion) XORs to 0, but the first half does not. The first integer for which such a set occurs is 168, which gives us the above set of integers.

**A little more detail**

The code above shows that there is a solution set with largest element 10,101,000, but does not actually produce it. The following code actually produces the solution:

```
n:=25;
lim:=200;
V:=VectorSpace(GF(2),2*n);
W:=sub<V|{V.i:i in {1..n}}>;
A:=[];
S:={};
for i in {1..lim} do
t:=IntegerToSequence(i,2);
s:=IntegerToSequence(SequenceToInteger(t,10),2);
jst:=t cat [0:j in {1..n-#t}] cat s cat [0:j in {1..n-#s}];
Append(~A,jst);
Include(~S,V!jst);
if (Dimension(sub<V|S> meet W) ge 1) then
v:=Basis(sub<V|S> meet W)[1];
M:=KMatrixSpace(GF(2),i,2*n);
B:=M!A;
x:=Solution(B,v);
tt:={j:j in {1..i}|x[j] eq 1};
{SequenceToInteger(IntegerToSequence(i,2),10):i in tt};
break;
end if;
end for;
```

The extra code sets v as the target vector, and then uses linear algebra to find the combination of vectors calculated above that sum to v, and converts them to the appropriate integers.

Answered by Jeremy Dover on January 6, 2021

A friend of mine found another solution but, despite my cajoling, declines to post here.

As we know from the other answer, any solution must

The code below finds a couple solutions achieving this bound and

One such solution is

or in decimal notation,

```
M = 2**8
x = [int(bin(n)[2:]) for n in range(M)]
for a in range(M):
for b in range(a):
for c in range(b):
for d in range(c):
if x[a]^x[b]^x[c]^x[d] == 0 and a^b^c^d != 0:
print(a, b, c, d, x[a], x[b], x[c], x[d])
```

However, this leaves open a possibility: **is there a solution with only three strings?**

Answered by A. Rex on January 6, 2021

Get help from others!

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

Recent Answers

- haakon.io on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- Peter Machado on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP