logoalt Hacker News

bazzargh01/04/20261 replyview on HN

I'm saying it's a tautology because it's just a binary representation of the set. Suppose we have 8 players, with x and y being 2 and 4: set the 2nd and 4th bits (ie 2^2 & 2^4) and you have 00001010.

But to lay it out: every positive integer is a sum of powers of 2. (this is obvious, since every number is a sum of 1s, ie 2^0). But also every number is a sum of _distinct_ powers of 2: if there are 2 identical powers 2^a+2^a in the sum, then they are replaced by 2^(a+1), this happens recursively until there are no more duplicated powers of 2.

It remains to show that each number has a unique binary representation, ie that there are no two numbers x=2^x1+2^x2+... and y=2^y1+2^y2+... that have the same sum, x=y, but from different powers. Suppose we have a smallest such number, and x1 y1 are the largest powers in each set. Then x1 != y1 because then we can subtract it from both numbers and get an _even smaller_ number that has distinct representations, a contradiction. Then either x1 < y1 or y1 < x1. Suppose without loss of generality that it's the first (we can just swap labels). then x<=2^(x1+1)-1 (just summing all powers of 2 from 1..x1) but y>=2^y1>=2^(x1+1)>x, a contradiction.

or, tl;dr just dealing with the case of 2 powers: we want to disprove that there exists a,b,c,d such that

2^a + 2^b = 2^c + 2^d, a>b, c>d, and (a,b) != (c,d).

Suppose a = c, then subtract 2^a from both sides and we have 2^b = 2^d, so b=d, a contradiction.

Suppose a>c; then a >= c+1.

2^c + 2^d < 2^c + 2^c = 2^(c+1).

so

2^c + 2^d <= 2^(c+1) - 1 < 2^(c+1) + 2^b <= 2^a + 2^b

a contradiction.


Replies

noduermelast Monday at 12:46 PM

Thanks for the great response. Honestly, TIL that 2^0 = 1. That was a new one for me and I'm not sure I understand it. I failed pre-Calculus, twice.

Visually I think I can understand the bitwise version now, from reading this. But it wouldn't work for 3 integers, would it?

show 1 reply