NetNews Usenet Archive 1992 #30/NN_1992_30.iso/spool/sci/math/16991

Text File | 1992-12-15 | 1.7 KB | 41 lines

Newsgroups: sci.math
Path: sparky!uunet!elroy.jpl.nasa.gov!usc!venice!gay
From: [e-mail] (Lance Gay)
Subject: Re: Interesting Discrete Math Question
Message-ID: <[e-mail]>
Organization: TRW Systems Engineering & Development Division, Carson, CA
References: <[e-mail]> <[e-mail]>
Date: Wed, 16 Dec 1992 00:07:14 GMT
Lines: 30

>In article <[e-mail]> [e-mail] (Pat Noffke) writes:
>Here's a question we had on one of our last tests in Discrete.
>
>A jar contains 100 chips numbered 1 through 100.  I want to draw a
>subset of chips that satisfies the condition that at least two chips
>have values that differ by exactly 3.  What is the minimum number of
>chips I must draw to guarantee that I satisfy the condition?  Justify
>your response.
>

Partition the integers into 3 sets:

  Set 1) 1, 4, 7, 10, ..., 97, 100  (34 integers)
  Set 2) 2, 5, 8, 11, ..., 95, 98   (33 integers)
  Set 3) 3, 6, 9, 12, ..., 96, 99   (33 integers)

Let us detemine the maximum number of chips which can be selected such
that no two chips differ by exactly three.
You may not choose any two adjacent members of any of the three sets.
The optimal stragtegy is to select every other member from each of the
three sets.  Thus we may choose 17 from the first set, 17 from the second
set and 17 from the third set for a total of 51.  (The numbers from the
first set can be chosen two different ways).

Thus the minimum number of chips to select to satify the condition is 52.


Lance J. Gay                                 Internet: [e-mail]
TRW Systems Engineering & Development Div.   Phone: [phone]
Carson, CA  90746