Seven integers under 127 and their Ratios
Show that among seven distinct positive integers not greater than 126, one could find two of them, say \(x\) and \(y\), satisfying \(1\lt \frac{y}{x}\le 2\). Prove also that 126 could not be replaced by 127.
|Contact| |Front page| |Contents| |Up|
Copyright © 1996-2018 Alexander BogomolnyShow that among seven distinct positive integers not greater than 126, one could find two of them, say \(x\) and \(y\), satisfying \(1\lt \frac{y}{x}\le 2\). Prove also that 126 could not be replaced by 127.
Solution 1
Arrange the seven given integers in ascending order: \(x_{1}\lt x_{2}\lt \ldots x_{6}\lt x_{7}\). Let's assume that the required inequality does not hold, so that never \(\frac{x_{i+1}}{x_{i}}\le 2\), i.e., \(\frac{x_{i+1}}{x_{i}} \gt 2\), for \(i=1,2,\ldots ,6\). This means that
\(1\lt \frac{x_{2}}{x_{1}} \gt 2, \)
\(1\lt \frac{x_{3}}{x_{2}} \gt 2, \)
\(1\lt \frac{x_{4}}{x_{3}} \gt 2, \)
\(1\lt \frac{x_{5}}{x_{4}} \gt 2, \)
\(1\lt \frac{x_{6}}{x_{5}} \gt 2, \)
\(1\lt \frac{x_{7}}{x_{6}} \gt 2\).
Multiplying all six gives \(\frac{x_{7}}{x_{1}} \gt 2^{6}=64\) or \(64x_{1} \lt x_{7}\le 126\), implying that \(x_{1}=1\).
This means that the least value \(x_{2}\) could have is \(3 = 2x_{1}+1\). Similarly, the least \(x_{3}\) could be is \(7=2x_{2}+1\). Continuing this way we get by necessity the sequence \(1, 3, 7, 15, 31, 63, x_{7}=127\). Contradiction. This sequence serves the counterexample sought in the second part of the problem. Anyway, the derivation shows that our assumption that \(\frac{x_{i+1}}{x_{i}} \gt 2\), for \(i=1,2,\ldots ,6\), is false, so for some \(i\) we have the required inequality.
Solution 2
[Barbeau et all] If the integers \(1,2,3,\ldots ,126\) are split into \(6\) sets, then by the Pigeonhole Principle, one of the sets will contain at least two of seven chosen integers. Thus, the problem is to arrange the splitting so that in each of the \(6\) sets the largest integer is at most twice the smallest. Clearly, the following splitting does the trick:
\(\{1,2\}\), \(\{3,4,5,6\}\), \(\{7,8,\ldots ,13,14\}\), \(\{15,16,\ldots ,29,30\}\), \(\{31,32,\ldots ,61,62\}\), \(\{63,64,\ldots ,125,126\}\).
References
- E. J. Barbeau, M. S. Klamkin, W. O. J. Moser, Five Hundred Mathematical Challenges, MAA, 1995, #13
|Contact| |Front page| |Contents| |Up|
Copyright © 1996-2018 Alexander Bogomolny72002979