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).

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

a contradiction.

▲

noduerme 3 days ago | parent [-]

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?

	▲	bazzargh 3 days ago \| parent [-]
		it works for any number of integers. The first proof above (before tl;dr) is showing that every positive integer has a unique representation as a sum of distinct powers of 2, ie binary, and that no two integers have the same representation. You can watch a lecture about the representation of sets in binary here https://www.youtube.com/watch?v=Iw21xgyN9To (google representing sets with bits for way more like this) But again it's not useful in practice for very sparse sets: if you have say a million players, with at most 10 at the same poker table, setting 10 bits of a million-bit binary number is super wasteful. Even representing the players as fixed size 20-bit numbers (1 million in binary is 20 bits long), and appending the 10 sorted numbers, means you don't need more than 200 bits to represent this set. And you can go much smaller if all you want is to label a _bucket_ that includes this particular set; just hash the 10 numbers to get a short id. Then to query faster for a specific combination of players you construct the hash of that group, query to get everything in that bucket (which may include false positives), then filter this much smaller set of answers.