James Tanton asked last week on Twitter: How many subsets S of {1, 2, …, 10} have the property that S and S+2 cover all the numbers from 1 to 12?
(I’ve taken the liberty of expanding some abbreviations here because my blog, unlike Twitter, doesn’t have a 140-character limit. Also, Tanton gave a hint which I’m omitting; you can click through to the link if you want it.)
In case you don’t know the notation, S + 2 means the set that we get from S by adding 2 to each element. So, for example, if S = {3, 5, 9} then S + 2 = {5, 7, 11}.
This is, with a clever trick, a one-liner in R:
sum(bitOr(0:1023, 4*(0:1023)) == 4095)
which outputs 25, the answer to the question.
(bitOr comes from the bitops package.)
Why does this work? We can represent each subset of {1, 2, …, 10} as an integer in 0, 1, …, 1023 = 210 – 1. Namely, we represent the set S by
so, for example, the set {3, 5, 9} is represented by the integer 22 + 24 + 28 = 276, or 100010100 in binary. (Read from right to left, it’ll make more sense.) Multiplying an integer by 4 = 22 then corresponds to adding 2 to each element — so 1104 = 4 × 276 = 24 + 26 + 210 represents the set {5, 7, 11}. 1104 is 10001010000 in binary; we just add two zeroes to the end.
The union of two sets then just becomes bitwise OR. We can line up our two integers (right-aligned, padding the shorter one with zeroes on the left) and then, in a third row, write a 1 in any column that has a 1 in either position above it:
00100010100
10001010000
-----------
10101010100
The result 10101010100 (binary) corresponds to the set {3, 5, 7, 9, 11}, the union of the two original sets. The bitOr command does this for each possible set; 4095 is 212-1 in binary and corresponds to the set of all the numbers from 1 to 12. So we’re just summing up a vector of TRUEs and FALSEs, with a TRUE in positions corresponding to sets S for which S and S+2 cover and FALSEs otherwise; in this context R treats TRUE as 1 and FALSE as 0, so we get the number of TRUEs.
But why is the answer 25? Can we find a general formula? Think about it; I’ll post the solution tomorrow.
I’m going to try to solve this by deductive logic:
The choice of S and S+2 means that (using the bit terminology) odd bits will union with other odd bits and even bits will union with even bits, so effectively we are dealing with two separable sets A subset {1,..,5} and B subset {1,…,5} where (2*A-1 union 2*B) = S.
S+2 can by obvious construction be broken down into A+1 and B+1, and the “how many ways can S and S+2 cover {1,…,12}” become the two independent sub-problems “how many ways can A and A+1 cover {1,…,6}” (and likewise for B).
A must have 1, since A+1 can’t. A+1 must have 6, since A can’t. So A must also have 5.
In doubt are 2,3,4. Let’s look at 2: If A doesn’t have 2, then A+1 doesn’t have 3, so A must have 3. We can also deduce from that that if A doesn’t have 3, then it must have 2. Looking at 3 and applying the same logic, if A doesn’t have 3, A+1 doesn’t have 4, so A must have 4. So if A doesn’t have 3, A must have 2 and 4. However, if A has 3, we learn nothing about 2 or 4. So for A and A+1, there are 5 possibilities: 1245, 135, 1235, 1345, and 12345.
The same argument holds for B, independently, so choosing one from column A and one from column B, we get 5*5 = 25 choices for S.
The generalization I see is to find the number of covers of {1,…,N+m} using S and S+m (where S is a subset of {1,…,N}.
By the above analysis, S can be partitioned into mA, mB-1, …, mE-m+1, where each A, B,…,E is a subset of {1,…,N/m}, plus or minus an element.
So the interesting generalization is covers of {1,…,N+1} with A and A+1.
We have the general condition that if k not in A (1<k<N), then k+1 and k-1 must be in A. In bit terms, this means that there can be no two consecutive 0s in the bitstring. No other restrictions hold.
So another way of phrasing it is "how many strings of M = N-2 bits have no pair of consecutive zero bits?"
This sounds like the job for a recurrence relationship…
A bit string of length n with no consecutive zero bits can be of a few forms: 1x, where x is consecutive-zero-bit free of length n-1, and 01y, where y in consecutive-zero-bit free of length n-2.
So if F(n) is the number of "Free" strings of length n, then F(n) = F(n-1) + F(n-2). All that is necessary is to find the base-case of the regression.
There is 1 bit string of length 0, and it is consecutive-zero-bit free.
There are 2 bit strings of length 1, and both are consecutive-zero-bit free.
So there should be 3 bit strings of length 2 (10, 11, and 01), and 5 bit strings of length 3 (110,111,101,010,011), etc.
So F(n) is the Fibonacci sequence,
Which means that how many covers of {1,…,N+1} are there using A and A+1, the answer is F(N-2). And for how many covers of {1,…,N+m} are there using S and S+m (letting N=am), the result is F(a)^m.
I believe the result for N=am+b (0 <= b < m) is F(a)^(m-b) * F(a+1)^b, which reduces to the above if b = 0.
Reblogged this on lava kafle kathmandu nepal.
[...] week ago I wrote a post on bitwise set trickery in which I asked a question from James Tanton: how many subsets S of {1, 2, …, 10} have the [...]