Let A = { 1 , 2 , 3 , … , 2 0 } be the set of the first 20 positive integers. For each X that is a 15-element subset of A , let p ( X ) be the product of its elements. What is the maximum integer n such that n divides p ( X ) for all choices of X ?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
And here is a logical answer.. Since 15 elements are to be selected, there must be atleast 5 even numbers. So 2^5 ,that is 32, must be a factor of n. Now we look at the multiples of 3. There are 6 multiples of 3 between 1 to 20, so by pigeon hole principle, atleast one factor of 3 must be selected(since 5 numbers are not to be selected). So, 3 will be also a factor of n. Clearly n is not bound to have any other factors. So, n = 32 x 3 = 96.
The questions asks for the maximum value of n which divides all values of p(X).
In other words it is asking for the worst possible cases or we could say the minimum condition which'll always be satisfied. First of all divide the numbers in odd & even group.
E={2,4,6,8,10,12,14,16,18,20}
O={1,3,5,7,9,11,13,15,17,19}
Let us see the cases.
Case 1 -In the set in which all odd no.s are included which means 10 places in set occupied and 5 are left.The next 5 will be from the set E hence we are sure of having some 2's. Then we have to choose the no.s such that they contain minimum no.s of 2's so we have minimum of 5 2's. So it is divisible by 2 5
Case 2 -if we now see no.s divisible by 3.There are 6 no.s like that hence we are sure that at least 1 no divisible by 3 is their in every possible set. Hence p(X) will be divisible by 3.
For any other prime no. we are not sure it to be there.
Hence as per our worst possible cases we can surely say that it is divisible by -
2 5 × 3 = 9 6
1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 1 0 , 1 1 , 1 2 , 1 3 , 1 4 , 1 5 , 1 6 , 1 7 , 1 8 , 1 9 , 2 0
These are the numbers with which the sets are created. There are ( 1 5 2 0 ) different and possible products of the elements of subsets X, but all these products have a maximum common divisor. At first, note that there are possible subsets X that do not contain any multiple of 5, 6, 7, 8, 9 or 10, so these numbers do not take part in the calculations to find the maximum common divisor. All the numbers of the set A are multiples of 1, and all the subsets X must contain multiples of two (in fact, at least 5 of them), so now it is known that the maximum common divisor of all those products is divisible by 2 and is also a multiple of it. However, the interesting fact is noticed when we think of the numbers 3 and 4.
Firstly, there cannot be any subset X with no multiples of 3: in every subset X, there must be at least one multiple of 3. Secondly, there is no subset X that do not contain any multiple of 4 (considering that there is, at least, one multiple of 3 in the subset). So the maximum common divisor is a multiple of, simultaneously, 2, 3 and 4. Now, to be sure that all the possible products are divisible by 3 and 4, let's consider products that include the numbers 3 and 4, because they are the smallest multiples of 3 and 4, respectively. Now, it is noticeable that there cannot be any subset X that, containing only one multiple of 3 and one of 4 (the 3 and the 4), do not contain any other multiple of 4. Hence, all the possible products contain at least one multiple of 3 and two multiples of 4. Considering the second multiple of 4 the next smallest multiple, we get that this number is 8. It means that all the products p(X) are, simultaneously, divisible by 3,4 and 8. Hence, the maximum common divisor of these products are 3x4x8 = 9 6
This is a nice question, I think you should use L A T E X on the sets and the definition of p(x) to make it slightly more attractive!
Log in to reply
Thanks! Sorry for not using Latex. I still need to learn how to use it better, but thanks for the advice!
Log in to reply
Hi, that's all right, even I didn't know much L A T E X when I joined. You can try this out when you get time.
Log in to reply
@Vishnu Bhagyanath – That's an incredible wiki! Thank you! I'll soon read it and learn about Latex. I'm thankful for this!
Problem Loading...
Note Loading...
Set Loading...
First of all, think of the problem the other way around, where exactly 5 elements are removed from a set of 2 0 elements.
With this, let's first form the base. Note that the product of these 1 5 elements will be divisible by each of the elements, and necessarily their prime factors as well.
Consider the multiples of 5 in the set A . There are 5 , 1 0 , 1 5 and 2 0 . So necessarily, atleast one of the subsets would contain none of these elements, since we're removing 5 elements, and there exist only 4 multiples of 5 .
Similar is the case with 7 , 1 1 , 1 3 , 1 7 , 1 9 . So these will not contribute to the final GCD.
Considering the ones of 2 : 2 , 4 , 6 , 8 , 1 0 , 1 2 , 1 4 , 1 6 , 1 8 , 2 0 . Prime factorize out all 2 's from these. Since we're removing five elements, we'd be left with atleast five of the above multiples of 2 . To get the least number of 2 in the final factorization, there would exist one set where 4 , 8 , 1 2 , 1 6 , 2 0 are removed. These leave 2 , 6 , 1 0 , 1 4 , 1 8 which each contain one and only one 2 in it's prime factorization.
Similar is the case with 3 : There would exist a set where only 1 multiple (of the 6 multiples ) are present, the smallest of which is either 3 , 6 , 1 2 or 1 5 each with only a single 3 in it's prime factorization.
So in essence, each set would contain at minimum one 3 and five 2 in it's prime factorization.
3 × 2 5 = 9 6