wu :: forums (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
riddles >> medium >> Student trumps teacher on pigeonhole
(Message started by: ecoist on Dec 1st, 2006, 8:50pm)

Title: Student trumps teacher on pigeonhole
Post by ecoist on Dec 1st, 2006, 8:50pm
An exercise asks students to show that, given any 6 numbers from {1,2,...,10}, some two of the given numbers differ by 2 or 3.  A student said she could do better, only 5 numbers need be given.  She was right!

Show that, given any n numbers from {1,2,...,n-1+3|(n-1)/2|}, n>4 and |x| denotes the greatest integer less or equal x, some two of the given numbers differ by 2 or 3.

Title: Re: Student trumps teacher on pigeonhole
Post by rmsgrey on Dec 2nd, 2006, 6:52am
Counter-example (n=5): 1, 2, 6, 11, 16

In fact, choosing from numbers 1 to 16, you can get even more numbers with no two 2 or 3 apart.

With numbers 1 to 100 (n=26) you need 41 numbers to guarantee some pair differ by 2 or 3

Find a correct formula for k, with any appropriate restrictions on n, so that, given any n numbers from {1, 2, ..., k}, some pair must differ by 2 or by 3

Title: Re: Student trumps teacher on pigeonhole
Post by ecoist on Dec 2nd, 2006, 8:09am
Right, rmsgrey!  Noticed the error only after I posted the problem.  Correcting it now.  Hmm.  Just noticed that the correction conforms to your observation, rmsgrey.  If n=41, then

n-1+3|(n-1)/2|=100.

Did you already know this formula?

Title: Re: Student trumps teacher on pigeonhole
Post by rmsgrey on Dec 3rd, 2006, 3:24pm
I didn't have a single formula, instead I had two - one for odd n; the other for even:

For odd n: k=5(n-1)/2

For even n: k=5n/2 - 4

Note that the two expressions are equivalent to your single expression for each of the two cases.

In actual fact, I used slightly different variables, and didn't bother formally expressing the equations - instead understanding the problem so I could find values directly - an understanding that let me write down the equations when I started typing this post, but that's only relevant when it comes to explaining how I got (and proved) my answers, which I don't intend to tonight.

Title: Re: Student trumps teacher on pigeonhole
Post by joefendel on Dec 5th, 2006, 2:42pm
I think I've got a proof for the formula.

[hideb]
Proof by induction.  Let n be the smallest "counterexample" value such that there exists an S where S is less than or equal to 5(n-1)/2 (if n is odd) or 5n/2 - 4 (if n is even) and yet there are n numbers between 1 and S such that no three are 2 or 3 apart.

Suppose n is even.  Then take the first (n-1) numbers in the set, which are thus between 1 and (S-1).  Since S <= 5n/2 - 4, then (S-1) <= 5n/2 - 5 = 5(n-2)/2 = 5([n-1] - 1)/2, and thus (n-1) is a smaller counterexample.  So n is not even.

Thus n is odd, so there are numbers between 1 and 5(n-1)/2 such that no two are 2 or 3 apart.  Call this set C.  We can partition the set of numbers from 1 to 5(n-1)/2 into (n-1)/2 groups of 5 consecutive numbers each.  (E.g. {1,2,3,4,5 }, {6,7,8,9,10}, {11, 12, 13, 14, 15}, etc.)  If all of these subsets only had two or fewer members of C, then the total would be <= 2*(n-1)/2 = n-1.  Thus at least one of these subsets has three members of C.  (SEE THREAD TITLE.)  But then we would have 3 numbers picked from 5 consecutive numbers such that none are 2 or 3 apart.  Thus n is not odd.

Thus n doesn't exist, which proves "sufficiency".  I.e. there is no subset of n numbers from 1 to k (as given by the formula) such that no two are 2 or 3 apart.

To prove "necessity", simply note that we can use the subset of N consisting of all numbers congruent to 1 or 2 (mod 5).  Clearly none of these are 2 or 3 apart, since there differences are all 0, 1, or 4 mod 5.  The nth number in this sequence is exactly 1 more than our formula.

QED?
[/hideb]

By the way, I think it's interesting that this formula "works" (trivially) even for n=1, 2.  I.e. there are no single number subsets of an empty set (for n = 1) and no doubleton subsets in {1}.

Title: Re: Student trumps teacher on pigeonhole
Post by towr on Dec 5th, 2006, 2:51pm
How about we generalise it.

Given any n distinct numbers from {1, ..., k} What is the minimum k such that the difference between any of the n numbers is always greater or equal to a, and smaller or equal to b.

[edit v2.0]
Given any n distinct numbers from {1, ..., k}, what is the minimum k such that the there is always a pair of numbers in n with difference greater than or equal to a, and smaller than or equal to b?
Given n > a.
[/edit]

Title: Re: Student trumps teacher on pigeonhole
Post by rmsgrey on Dec 5th, 2006, 3:20pm

on 12/05/06 at 14:51:19, towr wrote:
How about we generalise it.

Given any n distinct numbers from {1, ..., k} What is the minimum k such that the difference between any of the n numbers is always greater or equal to a, and smaller or equal to b.

Ummm... are you sure you've phrased that correctly?

I'd have thought that the following was a better generalisation:

Given any n distinct numbers from {1, ..., k}, what is the maximum k such that the there is always a pair of numbers in n with difference greater than or equal to a, and smaller than or equal to b?

Title: Re: Student trumps teacher on pigeonhole
Post by towr on Dec 6th, 2006, 12:42am

on 12/05/06 at 15:20:36, rmsgrey wrote:
Ummm... are you sure you've phrased that correctly?
No
I just realized I didn't this morning..

Title: Re: Student trumps teacher on pigeonhole
Post by ecoist on Dec 6th, 2006, 9:46am
Don't you guys mean "minimum" instead of "maximum"?  Recall rmsgrey's observation

Quote:
Counter-example (n=5): 1, 2, 6, 11, 16

In fact, choosing from numbers 1 to 16, you can get even more numbers with no two 2 or 3 apart.


I don't know how to solve this generalization.  However, I can handle this one:

Find the least integer k such that, given any n numbers from {1,2,...,k}, some two of them differ by a or b, a>b>0.

But even this problem needs special handling for the case a=2b.

For example, for both generalizations, what answers do you guys get for k when n=4, a=5, b=2 and when n=4, a=6, b=3?

Title: Re: Student trumps teacher on pigeonhole
Post by joefendel on Dec 6th, 2006, 10:11am

on 12/05/06 at 15:20:36, rmsgrey wrote:
Given any n distinct numbers from {1, ..., k}, what is the maximum k such that the there is always a pair of numbers in n with difference greater than or equal to a, and smaller than or equal to b?


Seems to me you just use ecoist's formula, but replace "3" with "b" and "2" with "a".

Title: Re: Student trumps teacher on pigeonhole
Post by towr on Dec 6th, 2006, 10:34am

on 12/06/06 at 09:46:07, ecoist wrote:
Don't you guys mean "minimum" instead of "maximum"?  Recall rmsgrey's observation
Actual, I'm more sure of the answer I want, than the question that goes with it.
I'm swinging a bit on the issue. I do feel it has to be maximum.

To answer the original question, I just thought of the densest way to pack the numbers such that none are 2 or 3 apart, and you get something like xx...xx...xx...x etc
The same works for any [a,b]. Subtract one from the length, and you have the maximum for which at least one pair of numbers must have a difference in that range.

So for any greater k, there needn't be such a pair, hence why it's the maximum. Which I guess settles that.


Quote:
Find the least integer k such that, given any n numbers from {1,2,...,k}, some two of them differ by a or b, a>b>0.
This is a much harder problem imo.


Quote:
For example, for both generalizations, what answers do you guys get for k when n=4, a=5, b=2 and when n=4, a=6, b=3?
For my (intended) generalization, I get 8 and 9 respectively.
For your version I'd probably resort to programming to find out.


on 12/06/06 at 10:11:34, joefendel wrote:
Seems to me you just use ecoist's formula, but replace "3" with "b" and "2" with "a".
After (re)writing the formulas a bit, that's also what I get.

Title: Re: Student trumps teacher on pigeonhole
Post by ecoist on Dec 6th, 2006, 11:30am
For n=4, a=6, and b=3, I get k=12 for towr's generalization.  That is, given any 4 from {1,...,12}, some two differ by 3 or less or 6 or more.  For k=13 (or larger), the four numbers 1, 5, 9, 13 form a counterexample.

Funny, towr, I think your generalization is harder than mine.

Title: Re: Student trumps teacher on pigeonhole
Post by towr on Dec 6th, 2006, 11:55am

on 12/06/06 at 11:30:55, ecoist wrote:
For n=4, a=6, and b=3, I get k=12 for towr's generalization.  That is, given any 4 from {1,...,12}, some two differ by 3 or less or 6 or more.
Ah, I see now, you switched a and b. I intended a <= diff <= b Which is what I wrote, I'm sure.. There couldn't be an and there otherwise.

Your interpretation would make it considerably harder. That wouldn't be a generalization though, as it can't be specialized to the case in the opening post. It'd be an all new and exciting puzzle.

Title: Re: Student trumps teacher on pigeonhole
Post by ecoist on Dec 6th, 2006, 12:40pm
Wow!  I missread your generalization.  Sorry about that.  Your problem is indeed easier than mine.  But my generalization (not my missread) is not so hard, if a short proof is any measure.

Not!  You guys are right, my idea doesn't generalize well.  I was trying to sneak in the following two problems.

Let a and b be integers with 0<a<b, b=/=2a.  Show that, given any n>(a+b)/2 numbers from {1,2,...,a+b}, some two differ by a or b.

Let a be a positive integer.  Show that, given any n>a numbers from {1,2,...,3a}, some two differ by a or 2a.

Title: Re: Student trumps teacher on pigeonhole
Post by joefendel on Dec 6th, 2006, 1:41pm
Here's an expanded generalization, phrased slightly differently:

Let S be a subset of natural numbers.  For any n, find the minimum value of k such that there exists a set, T(n) of n numbers in {1,...,k} such that the difference for every pair of these numbers is in S.

For example, looking at the original problem, S is all natural numbers except 2 or 3.  Then for n=5, k=11, because {1, 2, 6, 7, 11} is an example of a set of 5 numbers in {1,...,11} where the difference for each pair is in S, but there is no such set of 5 numbers in {1,...,10}, as the student pointed out.

For many (S, n), no such k will exist.  For example, if S is a singleton set and n = 3.  Or if S consists of all odd numbers and n = 3.

Here's my question with the generalization - does a greedy algorithm work?  Specifically, suppose we know k(S, n) and furthermore, we know of a particular set, T(n), of n numbers in {1,..,k} that satisfies the "all differences in S" requirement.  Suppose k' is the k-value for n+1.  Then does it follow that there is a set T(n+1) of (n+1) numbers in {1,...,k'} that also satisfies the "all differences in S" requirement AND contains T(n)?

If so, then we can let T(S) to be the union of all T(n), and thus k(n) is just the nth value of T(S) and T(n) is the subset of T(S) consisting of the first n members of T(S).

In our original example, trying to find sets of numbers such that there are no differences of 2 or 3, we basically take T(S) to be the set of all numbers congruent to 1 or  2 (mod 5).  Then k(n) is the nth number in T, and T(n) is the set of the first n numbers of T(S).

But for any S, will this be the case, that there is a T(S) which works?

Some examples:
S is empty: T = {1}
S is all numbers: T is all numbers
S is a singleton, a: T = {1,a+1}.
S is all odd numbers: T = {1,2}
S is all even numbers: T is all odd numbers.
S is all numbers except a: T = {1,...,a,2a+1,2a+2,...,3a,4a+1,4a+2,...}

Is there an S out there for which there is no such T(S)?



Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board