its very difficult. try out a challenge

Question

Let’s try a math puzzle entirely in binary. Suppose that there are 1111011101 dolphins in a pod. Let S be the set of all positive integers k such that the number of subsets of exactly k dolphins which can be formed from this pod is an odd number. What is the 101010-th smallest number in S, written in binary with no leading zeros?

Answer 1

“Difficult” is not the right word; how about “unusual?” That’s what makes this problem fun as well as challenging. We need to know definitions and procedures.

First, we observe that computers “think” in binary, but for convenience and accuracy, people convert binary to hexadecimal (at first, historically, it was octal) and then to decimal, perform the math operations, and then convert the answer back to hexadecimal/octal/binary. It’s like learning a foreign language such as Spanish or French – we translate because it takes a while to learn to think in that language.

So, there are “1111011101 dolphins in a pod.” That’s “0011 1101 1101 dolphins in a pod” or “3DD dolphins in a pod” or “989 dolphins in a pod.” (note: computer apps and calculators do this conversion quickly).

“Suppose that there are 989 dolphins in a pod. Let S be the set of all positive integers k such that the number of subsets of exactly k dolphins which can be formed from this pod is an odd number. What is the 42-nd (you should have gotten the idea) smallest number in S?"

Now, we need to review “positive integers,” “odd number,” “set” and “subset.” Oh – and “combinations.”
  Zero is neither positive nor negative. Positive, odd integers are “1, 3, 5, …”

  Definition:  Set B is a subset of a set A if and only if every object of B is also an object of A.

  The first element in Set S is 1 because there are 989 subsets of the dolphin pod with exactly 1 (k=1) dolphin and 989 is odd. In term of Combinations, this is the number of combinations (subsets) of size k=1 that can be created from the pod of 989 dolphins. One way of writing this is: C(989,1).  [note: PLZ refer to formula with factorials]

Other elements of S are k where the number of subsets with k elements is odd. The number of subsets with k elements is the number of combinations of 989 choose k, written as C(989,k) and C(989,k) must be odd.
C(989,1) = 989   odd-01
C(989,2) = 488566
C(989,3) = 160738214
C(989,4) = 39621969751   odd-02
C(989,5) = 7805528040947   odd-03
C(989,6) = 1280106598715308
C(989,7) = 179763540933878252
C(989,8) = 22065974649633555433   odd-04
C(989,9) = 2405191236810057542197   odd-05
C(989,10) = 235708741207385639135306
C(989,11) = 20978077967457321883042234
C(989,12) = 1709713354347771733467942071   odd-06
C(989,13) = 128491534399828691046013800259   odd-07
C(989,14) = 8957695541016628747207819218056
C(989,15) = 582250210166080868568508249173640
C(989,16) = 35444481543860172874107939668445335   odd-08
C(989,17) = 2028675326010349894500413252788077115   odd-09
C(989,18) = 109548467604558894303022315650556164210
C(989,19) = 5598503265475088756222877289299475549890
C(989,20) = 271527408375541804676809548531024564169665   odd-10
C(989,21) = 12529050415042857558658497739360133460971685   odd-11
C(989,22) = 551278218261885732580973900531845872282754140
C(989,23) = 23177653785184500148078337470186737325974924060
. . .

C(989,989) = 1  odd-xx   [for fun, determine xx]

By now, you might have seen a pattern. But, don’t just assume that it holds; look at the formula for Combinations and consider factorials and what makes them even or odd. This is what math knowledge does – it greatly shortens problem solving.

[Full Disclosure: I did not calculate factorials in either binary or decimal; I used an online Combinations Calculator.]

So, S is the set (1, 4, 5, 8, 9, 12, 13, … 989)

Now, what is the K for “odd-42?” (the 42-nd element of S? [note: you don’t need a formula if you have the patience to write 42 numbers or know how to put this into MS Excel.]

I’d say the answer is S₄₂=84 [but you should check that carefully, because I often make typos and miscalculations]. Converting that back to binary: S₄₂ = 1010100 (with no leading zeros).