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.

Solution


|Contact| |Front page| |Contents| |Up| |Store|

Copyright © 1996-2017 Alexander Bogomolny

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.

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

  1. E. J. Barbeau, M. S. Klamkin, W. O. J. Moser, Five Hundred Mathematical Challenges, MAA, 1995, #13

Related material
Read more...

  • Six integers out of 10: Pigeonhole Principle
  • Pigeonhole Principle (Same sum)
  • Pigeonhole in a Matrix
  • Pigeonhole in Calendar
  • A nice puzzle modeled on the Petersen graph
  • Proizvolov's identity in a game format
  • Pigeonhole with Disjoint Intervals
  • All antichains
  • Euclid via Pigeonhole
  • Light Bulbs in a Circle (an Interactive Gizmo)
  • |Contact| |Front page| |Contents| |Up| |Store|

    Copyright © 1996-2017 Alexander Bogomolny

     62030634

    Search by google: