A sequence of positive integers, a[1], a[2], a[3], . . . , a[n] is called a Special Sequence, if a[1] divides a[2], a[2] divides a[3], and so on until a[n−1] divides a[n], and if all the elements are distinct.
For example, (2, 4, 8, 32) is a Special Sequence. But (4, 2, 8) is not, because 4 does not divide 2. Similarly (2, 4, 4, 8) is also not Special, because the elements are not distinct.
You need to find the number of Special Sequences such that all the elements of the sequence are from the set {1, 2, . . . , K}.
Suppose K = 3. The Special Sequences possible are (1), (2), (3), (1, 2), (1, 3). So
the answer would be 5.
Find the answer for K = 19.
Show the logic and method as well.
Answers
Answer:
.Since we are to choose distinct numbers from {1,2,3…K}, the numbers must be in increasing order because they are all positive. I think that the difficulty of this problem is in the fact that the Special Sequence can be of any length. We can go about choosing say n elements in (Kn) ways but again how do we control that? Talking about a recursive solution, I think that is the way to go but I can't get how to do that (that is get a recursive formula for that).
Answer:
First, let me consider the example given in the question. Here K = 3.
Then the possible special sequences [written as sets by me here] are {1}, {2}, {3}, {1, 2}, {1, 3}.
Here {2, 3} and {1, 2, 3} are not possible, because 2 does not divide 3.
But if 3 was divided by 2, then {2, 3} would be possible, in which 2 is the starting element written in ascending order. And there is already another set having element ending in 2 [written in ascending order], i.e., {1, 2}. So the union of these two sets would also be possible too, i.e., {1, 2, 3}.
This logical concept is being used here to find the answer, that,
if {a, b} and {b, c} are two special sequence sets, then so will be {a, b, c}.
Now come to the question.
Here K is given as 19. So the overall (universal) set will be {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19}.
In the example, since K = 3, then {1}, {2} and {3} were also special sequence sets.
Thus we can make 19 such sets by K = 19.
{1}, {2}, {3}, {4}, {5}, ........., {19}
So there are 19 sets, each having a cardinality of 1.
Now let's find no. of sets having a cardinality of 2.
Since every number is divisible by 1, we can make sets having 2 elements, with first element 1 and each other numbers as the second element. Thus there will be 18 sets.
{1, 2}, {1, 3}, {1, 4}, {1, 5}, ........., {1, 19}
Divide 19 by 2, we get quotient 9. Thus we can make 8 sets starting with 2.
{2, 4}, {2, 6}, {2, 8}, {2, 10}, {2, 12}, {2, 14}, {2, 16}, {2, 18}
Divide 19 by 3, we get quotient 6. Hence there are 5 sets starting with 3.
{3, 6}, {3, 9}, {3, 12}, {3, 15}, {3, 18}
Divide 19 by 4, we get quotient 4. Hence 3 sets can be formed starting with 4.
{4, 8}, {4, 12}, {4, 16}
Divide 19 by 5, we get quotient 3. Hence 2 sets can be formed starting with 5.
{5, 10}, {5, 15}
Divide 19 by 6, we get quotient 3. Hence 2 sets can be formed starting with 6 too.
{6, 12}, {6, 18}
Divide 19 by 7, we get quotient 2. Hence 1 set can be formed starting with 7.
{7, 14}
Divide 19 by 8, we get quotient 2. Hence 1 set can be formed starting with 8.
{8, 16}
Divide 19 by 9, we get quotient 2. Hence 1 set can be formed starting with 9.
{9, 18}
Divide 19 by 10, the quotient is 1. Hence no set is formed starting with 10.
Okay, over!
So there are 41 sets, each having a cardinality of 2.
Now let's find no. of sets having a cardinality of 3. Here the concept with union that was found earlier is considered since.
The union of {1, 2} with each set of 2 elements starting with 2 [found earlier] are also special sequence sets. Hence 8 sets are formed.
{1, 2, 4}, {1, 2, 6}, {1, 2, 8}, {1, 2, 10}, {1, 2, 12}, {1, 2, 14}, {1, 2, 16}, {1, 2, 18}
Likewise,
→ Union of {1, 3} and each set of 2 elements starting with 3, thus 5 new sets.
→ Union of {1, 4} and each set of 2 elements starting with 4, thus 3 new sets.
→ Union of {1, 5} and each set of 2 elements starting with 5, thus 2 new sets.
→ Union of {1, 6} and each set of 2 elements starting with 6, thus 2 new sets.
→ Union of {1, 7} and each set of 2 elements starting with 7, thus 1 new set.
→ Union of {1, 8} and each set of 2 elements starting with 8, thus 1 new set.
→ Union of {1, 9} and each set of 2 elements starting with 9, thus 1 new set.
→ Union of {2, 4} and each set of 2 elements starting with 4, thus 3 new sets.
→ Union of {2, 6} and each set of 2 elements starting with 6, thus 2 new sets.
→ Union of {2, 8} and each set of 2 elements starting with 8, thus 1 new set.
→ Union of {3, 6} and each set of 2 elements starting with 6, thus 2 new sets.
→ Union of {3, 9} and each set of 2 elements starting with 9, thus 1 new set.
→ Union of {4, 8} and each set of 2 elements starting with 8, thus 1 new set.
Over!
So there are 33 sets, each having a cardinality of 3.
Now, sets having a cardinality of 4 each.
→ Union of {1, 2} and each set of 3 elements starting with 2, thus 6 new sets.
{1, 2, 4, 8}, {1, 2, 4, 12}, {1, 2, 4, 16}, {1, 2, 6, 12}, {1, 2, 6, 18}, {1, 2, 8, 16}
→ Union of {1, 3} and each set of 3 elements starting with 3, thus 3 new sets.
→ Union of {1, 4} and each set of 3 elements starting with 4, thus 1 new set.
→ Union of {2, 4} and each set of 3 elements starting with 4, thus 1 new set.
Over!
So there are 11 sets, each having a cardinality of 4.
Now, sets having a cardinality of 5 each.
→ Union of {1, 2} and each set of 4 elements starting with 2, thus 1 new set.
{1, 2, 4, 8, 16}
Only this one! Over!
Now, sets having a cardinality of 6 each. But there's not such a set.
Union of {1, 2} and each set of 5 elements starting with 2 can't be found.
Now we can conclude, and let me calculate the total no. of sequences.
19 + 41 + 33 + 11 + 1 = 105
Hence the answer is 105.