Can someone please help me with this? Let C=$\{1,2,4,5,8,10,20,31,40,62,124,155,248,310,620,1240\}$ be the set of positive divisors of $1240$. Prove that in any subset of $9$ elements of $C$, there are two elements whose product is $1240$.
I know that multiplying each element from the left with the ones on the right gives $1240$, but how do I use that info to answer this?
On
Consider the eight sets of factor pairs: $$\{1, 1240\}, \{2, 620\}, \{4, 310\}, \{5, 248\}, \{8, 155\}, \{10, 124\}, \{20, 62\}, \{31, 40\}$$ If you choose nine elements from set $C = \{1, 2, 4, 5, 8, 10, 20, 31, 40, 62, 124, 155, 248, 310, 620, 1240\}$, you must choose both elements of at least one of these eight sets of factor pairs. What can you conclude?
Hint: Prime factorize 1240 into $2^3\cdot 5\cdot 31$. Any element of $C$ will be a subset of that prime list. Two elements multiply to get you 1240 if and only if the sum of the count of each prime in each of your two numbers is the same as the amount in 1240. Then use pigeonhole principle
In other words, number A will have $0-3$ copies of 2, $0-1$ copies of 5, and $0-1$ copies of 31. Start splitting the numbers up, for instance, half of them include 31 and half don't, you need one from each half, etc.
Alternatively, use your notion of a number on the left half multiplied by a number on the right half equals 1240 and start working by elimination to figure out the largest subset of $C$ could be to NOT have such a pair. As soon as you pick 1 number, you eliminate another as a possibility. Repeat.