2
$\begingroup$

From Putnam and Beyond:

Proofs (Question 10:)

Let $n>1$ be an arbitrary real number and let $k$ be the number of positive prime numbers less than or equal to $n$. Select $k + 1$ positive integers such that none of them divides the product of all the others. Prove that there exists a number among the chosen $k + 1$ that is bigger than $n$.

Assume the contrary. Our chosen numbers $a_1,a_2,\dots,a_{k+1}$ must have a total of at most $k$ distinct prime factors (the primes less than or equal to $n$). Let $o_p(q)$ denote the highest value of $d$ such that $p^d\mid q$. Also, let $a = a_1a_2\dots a_{k+1}$ be the product of the numbers. Then for each prime $p$, $o_p(a) = \sum_{i=1}^{k+1} o_p(a_i)$, and it follows

Here's the part onwards that I do not understand: Specifically, what does it mean by hostile value?

that there can be at most one hostile value of $i$ for which $o_p(a_i)>o_{p}(a)/2$. Because there are at most $k$ primes that divide $a$, there is some $i$ that is not hostile for any such prime. Then $2o_p(a_i)\le o_p(a)$, so $o_p(a_i) \le o_p(a/a_i)$ for each prime $p$ dividing $a$. This implies that $a_i$ divides $a/a_i$, which contradicts the fact that the $a_i$ does not divide the product of the other $a_j$’s. Hence our assumption was false, and the conclusion follows.

Question is page 16 of the pdf while answer is on 367 of the pdf.

Thanks.

PS Can someone help me tag it here https://math.stackexchange.com/questions/tagged/contest-math

When I put 'contest-math' it does not recognize the existing tag and says its new.

  • 0
    Please remove the link to the book. It is not yet freely distributable, legally.2012-05-19

1 Answers 1

3

The sentence in which the term hostile value of i is used is intended to define the term: a hostile value of $i$ is one such that $o_p(a_i)>o_p(a)/2$. If there were distinct $i$ and $j$ such that $o_p(a_i)>o_p(a)/2$ and $o_p(a_j)>o_p(a)/2$, then $o_p(a) = \sum_{i=1}^{k+1} o_p(a_i)>o_p(a)$, so there is at most one such ‘hostile’ $i$. (I usually use the term ‘bad’ as a temporary descriptive term in such situations.) We therefore have $o_p(a_j)\le o_p(a)/2$ for $j\ne i$ and hence $2o_p(a_j)\le o_p(a)$.

  • 0
    Thank you for the clarification.2012-05-23