Number of ways to choose numbers from a list. While studying, I came upon this question in my book: "How many ways are there to take 7 numbers from 1 to 12 such that none of the chosen numbers is twice the other?"
The solution is shown as 47, but a detailed explanation to why this is the answer is not given.
I would be grateful if someone could provide an explanation for this problem.
 A: I would divide the numbers into the following groups:
Group 1: 1, 2, 4, 8
Group 2: 3, 6, 12
Group 3: 5, 10
Group 4: 7, 9, 11
We know that we need to exclude a total of 5 numbers out of the 12. Because none of the chosen numbers can be twice another, we must exclude at least 2 from Group 1, at least 1 from Group 2, at least 1 from Group 3.
We have the following possibilities (when I say choose 2 from Group 1, I mean choose the ones that we exclude from your set):
Case 1: Choose 2 from Group 1, 1 each from Groups 2, 3, 4. There are 3 ways to choose the 2 to exclude from Group 1 (exclude 1 and 4, 2 and 4, or 2 and 8, so that the numbers we include in our set would be 2 and 8, 1 and 8, or 1 and 4), 1 way to choose the 1 number to exclude from Group 2 (we have to exclude 6 so that 3 and 12 are not double each other), 2 ways to choose from Group 3, and 3 ways to choose from Group 4 (since none of them is double any other in Group 4, we can choose however we want). That means the total number in this case is $3*1*2*3=18$ by the multiplication principle.
Case 2: Choose 2 each from Groups 1 and 3, 1 from Group 2, and none from Group 4. Similar calculation to above: $3*1*1*1=3$ ways.
Case 3: Choose 2 each from Groups 1 and 2, and 1 from Group 3. $3*3*2*1=18$.
Case 4: Choose 3 from Group 1, 1 each from 2 and 3. $4*1*2*1=8$.
Adding them together, you get $18+3+18+8=47$ ways to exclude the 5 numbers. Each of those ways uniquely determines the 7 numbers to include in our set so that none of them is double another.
A: Sketch solution:


*

*Consider choices of $8$ numbers, with the same property of double exclusion.

*Consider the partition of $\{1,...12\}$ into $\{1, 2, 4, 8\} \{3, 6, 12\} \{5, 10\}$ and $\{7, 9, 11\}$. Call the sets $s_1, s_2, s_3, s_4$ respectively.


Now a choice of $8$ is the same as not choosing the other $4$, i.e. excluding the other $4$. We can see that we must exclude $2$ elements from $s_1$, $1$ from $s_2$, and $1$ from $s_3$. There are $3$ ways to do this from $s_1$, while avoiding the doubles $(1, 2), (2, 4)$ and $(4, 8)$. We must choose $6$ in $s_2$. There are $2$ choices from $s_3$. Which gives $3*1*2 = 6$ ways of doing this.
Now, every choice of $7$ is a choice of $8$ with one dropped. There are $8$ ways to drop $1$ from a choice of $8$. So we get $6*8 = 48$. I probably have made a mistake here because the book said $47$ but I hope my approach helps you make a dent in your understanding of the problem.
