Question

How many different strings of binary length 6 are there such that no two are reversals of each other or add up to 111111?

Answer 1

69

Answer 2

It's not 69.

Answer 3

why?

Answer 4

Wouldn't 111111 be produced by by only two unique combinations? If so, wouldn't that mean 2^6 - 1, because all combinations produce different strings resulting in not 111111 except for that special case? I'm not sure.

Answer 5

In case of adding two binary numbers, is what I mean.

Answer 6

every string has a reverse

Answer 7

so 2^5 (without the 111111 thing).

Right?

Answer 8

So you divided by two because a whole half of the possibilities is reversed strings?

Answer 9

Also, 111111+000000=111111
101010+010101=111111
....

Answer 10

I think....

Answer 11

I don't get the question, is it to be interpreted that we add two binary strings, A and B, and then see the possibility of A + B ending up to be 111111?

Answer 12

yes

Answer 13

https://www.sccollege.edu/Faculty/DDiaz/Documents/sml_sp13.pdf

Answer 14

scroll down for solutions

Answer 15

the number of all possible outputs that can be produced = (2^6)^2 because we can map any possibility with another, much like multiplication, right?
the possibility of the two numbers being inverted then is inversionOccurance/totalPossibility

Answer 16

How could you prove it's 69?

Answer 17

I get 28, but that's not one of the so printed possible answers.

Answer 18

this is 2^6 - 8 possible reversable combos all divided by 2 because each can be inverted. Am I right?

Answer 19

The total number of symmetric \(6\)-digit strings (reversals) is \(2^3=8\) because only the first three digits are needed to determine if a string is symmetric; since this is a manageably small number, I'll list them:
\[\begin{matrix}\color{red}{000\,000}&\color{blue}{100\,001}&\color{green}{010\,010}&001\,100\\
110\,011&\color{green}{101\,101}&\color{blue}{011\,110}&\color{red}{111\,111}\end{matrix}\]Adding the matching-color strings gives \(111\,111\).

Meanwhile, there are \(64\) total ways to add binary strings to add up to \(111\,111\) (how many ways can you add two positive integers to add up to \(n\)?).

The total number of ways to satisfy \(x\) OR \(y\) is given by the inclusion/exclusion principle:
\[n(x\vee y)=n(x)+n(y)-n(x\wedge y)\]