Ponder This Challenge - November 2000 - 75 integers in [1,230]

Ponder This Challenge:

We gave you a difficult puzzle last month.
This month's will be easier.

Part A:
Select 75 integers between 1 and 230 (inclusive) such that no
two of them differ by exactly 5, 6, or 11.

Part B:
Show that one cannot select 76 integers satisfying the same requirements.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  Part A:
  1,2,3,4,5, 17,18,19,20,21, 33,34,35,36,37, ..., 225,226,227,228,229.
  The pattern is: Take 5, skip 11, take 5, skip 11.

  Part B:
  First we show that among any 16 consecutive integers we can take at most five.
  Suppose, to the contrary, that our collection included six integers among (1,2,3,...,15,16).

  Consider the following six sets:
  (1,6,12), (2,7,13), (3,8,14), (4,9,15), (5,10,16), (11).
  Within each set, any two elements differ by either 5, 6, or 11.
  So each set can contribute at most one to our collection.
  Since our collection needs six elements, we must take exactly one from each set; in particular, we must take element 11 from the last set.

  Similarly, consider the six sets:
  (1,7,12), (2,8,13), (3,9,14), (4,10,15), (5,11,16), (6).
  The same argument tells us that our collection must contain 6.

  But we cannot take both 6 and 11, since they differ by 5.

  Now the integers from 1 to 240 can be partitioned into 15 sets, each containing 16 consecutive integers. We have just shown that our collection can contain at most 5 from each of these sets, or at most 75 in all. So we have shown that we cannot have 76 integers between 1 and 240 inclusive, an even stronger result than was asked for.

  ---

  If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solvers

• David McKee (11.03.2000 @ 1:03 PM EDT)
• Kevin Bealer (11.03.2000 @ 1:39 PM EDT)
• Ming Song (11.03.2000 @ 1:56 PM EDT)
• Sujith Vijay (11.03.2000 @ 2:15 PM EDT)
• Daniel Li (11.03.2000 @ 2:20 PM EDT)
• Tim Edmonds (11.03.2000 @ 3:15 PM EDT)
• Ashish Kadakia (11.03.2000 @ 3:59 PM EDT)
• Akash Jain (11.03.2000 @ 4:51 PM EDT)
• Ravishankar Arunachalam (11.03.2000 @ 6:55 PM EDT)
• Jack Kennedy (11.03.2000 @ 8:53 PM EDT)
• Ether Jones (11.03.2000 @ 11:01 PM EDT)
• Abd Al-Rahman Said Hammad (11.03.2000 @ 11:22 PM EDT)
• Jonathan Hayward (11.04.2000 @ 11:21 AM EDT)
• Murali Prakash (11.04.2000 @ 12:45 AM EDT)
• Joseph DeVincentis (11.04.2000 @ 11:30 PM EDT)
• Achava Nakhash (11.04.2000 @ 11:51 PM EDT)
• Derek Kisman (11.05.2000 @ 2:47 AM EDT)
• Philip Nanni (11.05.2000 @ 2:49 AM EDT)
• Anand (11.05.2000 @ 3:54 AM EDT)
• Ilan Algor (11.05.2000 @ 8:29 AM EDT)
• Francis Golding (11.05.2000 @ 8:43 AM EDT)
• Olivier Miakinen (11.05.2000 @ 9:55 AM EDT)
• Christie Bolton (11.05.2000 @ 6:31 PM EDT)
• Prithu (11.05.2000 @ 7:02 PM EDT)
• Brian Murphy (11.05.2000 @ 10:45 PM EDT)
• Philip Dawson (11.06.2000 @ 6:27 AM EDT)
• Vladimir Sedach (11.06.2000 @ 12:55 PM EDT)
• Samantha Levin (11.06.2000 @ 12:37 PM EDT)
• Trevor Strohman (11.06.2000 @ 2:38 PM EDT)
• Alexey Vorobyov (11.06.2000 @ 2:45 PM EDT)
• Craig Arnold (11.06.2000 @ 4:47 PM EDT)
• Howard Smith (11.06.2000 @ 5:25 PM EDT)
• John Hamilton (11.06.2000 @ 6:04 PM EDT)
• Imtiaz Hossain (11.07.2000 @ 12:27 AM EDT)
• Zhang Lei (11.07.2000 @ 2:19 AM EDT)
• Kivanc Cefle (11.07.2000 @ 2:34 AM EDT)
• Raul Saavedra (11.07.2000 @ 3:21 AM EDT)
• Ed Lee (11.07.2000 @ 5:29 AM EDT)
• Ashutosh Misra (11.07.2000 @ 7:26 AM EDT)
• Alexis Megas (11.07.2000 @ 8:18 AM EDT)
• Dave Biggar (11.07.2000 @ 10:33 AM EDT)
• Guenter Mair (11.07.2000 @ 1:23 PM EDT)
• Shmuel Spiegel (11.08.2000 @ 11:18 AM EDT)
• Ralf Seliger (11.08.2000 @ 2:46 PM EDT)
• Prashanth H Hande (11.08.2000 @ 3:37 PM EDT)
• Ivan Skytte Jørgensen (11.08.2000 @ 6:28 PM EDT)
• Yiu Ming (11.09.2000 @ 6:49 AM EDT)
• Menka Verma (11.09.2000 @ 12:21 PM EDT)
• Suman Datta (11.10.2000 @ 4:49 AM EDT)
• yengyong (11.10.2000 @ 5:31 AM EDT)
• Phil Strenski (11.10.2000 @ 9:06 AM EDT)
• Ivan Corwin (11.10.2000 @ 1:03 PM EDT)
• Viral Patel (11.10.2000 @ 4:24 PM EDT)
• Imrankhan Pathan (11.11.2000 @ 11:46 AM EDT)
• Amos Guler (11.12.2000 @ 8:54 AM EDT)
• Samir Pawanekar (11.12.2000 @ 9:51 AM EDT)
• Sverre Sand (11.12.2000 @ 7:48 PM EDT)
• Michael Malak (11.13.2000 @ 11:32 AM EDT)
• Catherine Bradshaw (11.13.2000 @ 11:42 AM EDT)
• Kevin Vanderwater (11.13.2000 @ 9:16 PM EDT)
• zakharin (11.13.2000 @ 9:47 PM EDT)
• Scott Ransom (11.14.2000 @ 12:10 AM EDT)
• Morten Ofstad (11.14.2000 @ 6:02 AM EDT)
• Jay Cherski (11.14.2000 @ 1:05 PM EDT)
• Aniket Khera (11.15.2000 @ 4:14 PM EDT)
• Islam Gohar (11.16.2000 @ 8:35 AM EDT)
• Tom Blumer (11.16.2000 @ 2:29 AM EDT)
• Rajiv Shukla (11.17.2000 @ 10:10 AM EDT)
• Cristian Stagarescu (11.17.2000 @ 8:48 AM EDT)
• Michael Moyer (11.18.2000 @ 11:48 PM EDT)
• Tom Kauffman (11.19.2000 @ 8:00 PM EDT)
• María Elena Martínez (11.20.2000 @ 1:16 PM EDT)
• Laura Apostoloiu (11.20.2000 @ 12:53 PM EDT)
• A Braunsdorf (11.21.2000 @ 3:02 PM EDT)
• Sudipta Das (11.23.2000 @ 6:32 AM EDT)
• Maneesh Kumar Ponnath (11.23.2000 @ 6:40 AM EDT)
• Johannes Schindelin (11.24.2000 @ 3:05 AM EDT)
• Ludwig Deruyck (11.24.2000 @ 1:06 PM EDT)
• Frank Jones (11.24.2000 @ 11:18 PM EDT)
• Rocke Verser (11.27.2000 @ 9:22 AM EDT)
• Henry Bottomley (11.27.2000 @ 2:05 PM EDT)
• Mihai Cioc (11.28.2000 @ 1:47 PM EDT)
• Ruth Christie (11.28.2000 @ 2:10 PM EDT)
• Anantha Ramamurti (11.28.2000 @ 2:35 PM EDT)
• Siddharth Rai (11.30.2000 @ 1:54 AM EDT)
• Stephane Higueret (11.30.2000 @ 4:20 AM EDT)
• Easwaran Raman (11.30.2000 @ 7:10 AM EDT)
• Nagendra Gd (11.30.2000 @ 1:43 PM EDT)