A subset $E$ of the set $\{1,2,3,\ldots,50\}$ is said to be special if it does not contain any pair of the form $\{x,3x\}.$ A special set $E$ is superspecial if it contains as many elements as possible. How many element there are in a superspecial set and how many superspecial sets there are?
Problem
Source: Finland 2013, Problem 4
Tags: combinatorics unsolved, combinatorics
professordad
02.05.2013 22:57
Partition into sets such that in each set, we have a number not divisible by 3 and all its multiples by a power of 3:
("1" "3" 9 27)
("2" 6 18)
(4 12 36)
(5 15 45)
Note that 7 other sets will have two elements. These sets start with 7, 8, 10, 11, 13, 14, and 16. For the sets with one term, elements could be (17), (19), (20), ... basically all numbers not divisible by 3 from 17 to "50". There are 23 such numbers, so there are 23 sets with one term.
Now take 2 elements from the first set (with 4 numbers), 2 elements from the second through fourth set (leave out the middle), 1 element from the seven sets with two elements, and 1 from each of the 23 single-element sets. The answer to the first question is $2 + 6 + 7 + 23 = 38$.
For the second question, notice that from the first set we may select 3 different pairs of elements. From the seven two-element sets, we have 2 choices for each. So the answer to the second question is $3 \cdot 2^7 = 384$.
Edited for a small mistake/clarification
Chirantan
30.03.2015 06:21
professordad wrote:
Partition into sets such that in each set, we have a number not divisible by 3 and all its multiples by a power of 3:
("1" "3" 9 27)
("2" 6 18)
(4 12 36)
(5 15 45)
Note that 7 other sets will have two elements. These sets start with 7, 8, 10, 11, 13, 14, and 16. For the sets with one term, elements could be (17), (19), (20), ... basically all numbers not divisible by 3 from 17 to "50". There are 23 such numbers, so there are 23 sets with one term.
Now take 2 elements from the first set (with 4 numbers), 2 elements from the second through fourth set (leave out the middle), 1 element from the seven sets with two elements, and 1 from each of the 23 single-element sets. The answer to the first question is $2 + 6 + 7 + 23 = 38$.
For the second question, notice that from the first set we may select 3 different pairs of elements. From the seven two-element sets, we have 2 choices for each. So the answer to the second question is $3 \cdot 2^7 = 384$.
Edited for a small mistake/clarification Can you please explain your solution in more details I did not understand it