0
$\begingroup$

If we have a sequence from 0 to N in binary format then the number of 0 and number of 1s in the least significant bit have a balance i.e. if N was even then there is one 0 more than how many 1s are there. If it is odd the number of 0s and 1s are the same.
Example:

0000    
0001  
0010  
0011 

There are 2 0s and 2 1s in the first binary column (N = 3 i.e. odd)

0000    
0001  
0010  
0011 
0100  

There are 3 0s and 2 1s in the first binary column (N = 4 i.e. even).

This makes sense since each number is basically the previous +1, so each addition either adds a 1 or a 0 to the last column and since this is about all the numbers from 0 to N this equation is there.
What is not straightforward to me to understand intuitively is that if I split these numbers to 2 sets, i.e. odds (or those with the last bit set to 1) and evens (those with the last bit set to 0) the same equation holds.
The same also holds for all further subdivisions of those with the second column 0 vs second column 1 etc.
Could some give some insight why this further and further subdivision keeps having this condition hold?

$\endgroup$
1
$\begingroup$

The rightmost two bits go through the cycle $00, 01, 10, 11$, which corresponds to counting $0,1,2,3$. If you separate out the even numbers, you select those with $0$ in the ones bit, and they will count $0,2,0,2,0,2$. The twos bit will alternate between $0$ and $1$, just like the ones bit did when you had all the numbers. It works the same however many bits you select and which selection you make. If you just take the numbers that end in $101$ you will get the numbers that are equivalent to $5 \bmod 8$. If you consider the next bit, which is the eights place, you will alternate between $5 \bmod 16$ and $13 \bmod 16$. The first has $0$ in the eights place and the second has $1$ in the eights place, so you get the same alternation.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The first has 0 in the eights place and the second has 1 in the eights place, so you get the same alternation I would get the alteration of 0s and 1s but why would I get the exact same number of 0s and 1s for all possible selections? $\endgroup$ – Jim Apr 14 at 22:15
  • $\begingroup$ If they alternate, you always get the same number or one more $0$ because you start with $0$ $\endgroup$ – Ross Millikan Apr 14 at 22:21
  • $\begingroup$ Yeah I asked the wrong question. So if we select a subset e.g. that ends with 00 the following bit can only be 0 or 1 and from that follows that regardless of the actual total numbers it would always be either same number of 0s and 1s or one more 0 in the third position? But this only holds if the original sequence had all the numbers from 0 to N? $\endgroup$ – Jim Apr 14 at 22:32
  • 1
    $\begingroup$ If it ends with $00$ you are then looking at the preceding bit, but yes. If you started with all the numbers from $0$ to $N$ and extract all the ones that end in $00$ the preceding bit, which is the fours, will alternate. If some of the numbers between $0$ and $N$ are missing, you might upset the pattern. $\endgroup$ – Ross Millikan Apr 14 at 22:35
  • 1
    $\begingroup$ There are the same number of each digit, or perhaps one more. You might have one more $0$ than $9$ and the break can come anywhere in the list, just after the last digit. So if the digits end with $5$ there will be one more $0-5$ than $6-9$ $\endgroup$ – Ross Millikan Apr 15 at 19:07

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.