Author |
Topic: Student trumps teacher on pigeonhole (Read 908 times) |
|
ecoist
Senior Riddler
Gender: 
Posts: 405
|
 |
Student trumps teacher on pigeonhole
« on: Dec 1st, 2006, 8:50pm » |
 Quote  Modify
|
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.
|
| « Last Edit: Dec 2nd, 2006, 8:14am by ecoist » |
 IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2874
|
|
Re: Student trumps teacher on pigeonhole
« Reply #1 on: Dec 2nd, 2006, 6:52am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Student trumps teacher on pigeonhole
« Reply #2 on: Dec 2nd, 2006, 8:09am » |
Quote Modify
|
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?
|
| « Last Edit: Dec 2nd, 2006, 2:41pm by ecoist » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2874
|
|
Re: Student trumps teacher on pigeonhole
« Reply #3 on: Dec 3rd, 2006, 3:24pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Joe Fendel
Full Member
Posts: 158
|
|
Re: Student trumps teacher on pigeonhole
« Reply #4 on: Dec 5th, 2006, 2:42pm » |
Quote Modify
|
I think I've got a proof for the formula.
| hidden: |
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?
|
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}.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Student trumps teacher on pigeonhole
« Reply #5 on: Dec 5th, 2006, 2:51pm » |
Quote Modify
|
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]
|
| « Last Edit: Dec 6th, 2006, 10:30am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2874
|
|
Re: Student trumps teacher on pigeonhole
« Reply #6 on: Dec 5th, 2006, 3:20pm » |
Quote Modify
|
on Dec 5th, 2006, 2:51pm, 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?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Student trumps teacher on pigeonhole
« Reply #7 on: Dec 6th, 2006, 12:42am » |
Quote Modify
|
on Dec 5th, 2006, 3:20pm, rmsgrey wrote:| Ummm... are you sure you've phrased that correctly? |
|
No
I just realized I didn't this morning..
|
| « Last Edit: Dec 6th, 2006, 12:51am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Student trumps teacher on pigeonhole
« Reply #8 on: Dec 6th, 2006, 9:46am » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
Joe Fendel
Full Member
Posts: 158
|
|
Re: Student trumps teacher on pigeonhole
« Reply #9 on: Dec 6th, 2006, 10:11am » |
Quote Modify
|
on Dec 5th, 2006, 3:20pm, 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".
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Student trumps teacher on pigeonhole
« Reply #10 on: Dec 6th, 2006, 10:34am » |
Quote Modify
|
on Dec 6th, 2006, 9:46am, 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 Dec 6th, 2006, 10:11am, 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.
|
| « Last Edit: Dec 6th, 2006, 10:53am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Student trumps teacher on pigeonhole
« Reply #11 on: Dec 6th, 2006, 11:30am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Student trumps teacher on pigeonhole
« Reply #12 on: Dec 6th, 2006, 11:55am » |
Quote Modify
|
on Dec 6th, 2006, 11:30am, 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.
|
| « Last Edit: Dec 6th, 2006, 11:59am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Student trumps teacher on pigeonhole
« Reply #13 on: Dec 6th, 2006, 12:40pm » |
Quote Modify
|
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.
|
| « Last Edit: Dec 6th, 2006, 6:00pm by ecoist » |
IP Logged |
|
|
|
Joe Fendel
Full Member
Posts: 158
|
|
Re: Student trumps teacher on pigeonhole
« Reply #14 on: Dec 6th, 2006, 1:41pm » |
Quote Modify
|
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)?
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print