

Store








CTK Exchange
peterash
Member since Sep1904

Sep1904, 09:44 PM (EST) 

"pigeonhole sequence problem"

I'm looking for applications of the pigeonhole principle that would be good for a freshmanlevel course in mathematical problem solving that I am teaching. I looked at Item #119 in cuttheknotArithmetic/ Algebra, Number sequences and pigeonhole, and was struck by the elegance of the proof that every sequence of length mn + 1 must have a monotone subsequence of length m+1 or n+1. Unfortunately, I don't understand the game that introduces and illustrates the theorem. As I understand it, you are supposed to fill in 4 blanks to complete a permutation of the first 10 positive integers. To me, this means all you have to do is see which 4 numbers are missing, and put them in the blanks in any order. I looked at a few answers, and I see that the hidden numbers are indeed the numbers I expected, placed in ascending or descending order depending on the colors of the visible numbers. So what? Is this an example of killing a fly with a sledgehammer, or am I missing something about the game? 

Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 


alexb
Charter Member
1346 posts 
Sep1904, 09:50 PM (EST) 

1. "RE: pigeonhole sequence problem"
In response to message #0

>I'm looking for applications of the pigeonhole principle >that would be good for a freshmanlevel course in >mathematical problem solving that I am teaching. I looked at >Item #119 in cuttheknotArithmetic/ Algebra, Number >sequences and pigeonhole, and was struck by the elegance of >the proof that every sequence of length mn + 1 must have a >monotone subsequence of length m+1 or n+1. Yes, it is really nice. >Unfortunately, I don't understand the game that introduces >and illustrates the theorem. From what you wrote I gather you have full understanding of the applet. >As I understand it, you are supposed to fill in 4 blanks to >complete a permutation of the first 10 positive integers. To >me, this means all you have to do is see which 4 numbers are >missing, and put them in the blanks in any order. Not quite. The theorem claims existence of either ascending or descending sequence. The blanks are to be filled by one of these. >I looked at a few answers, and I see that the hidden numbers >are indeed the numbers I expected, placed in ascending or >descending order depending on the colors of the visible >numbers. Right. >So what? So you (or your students) can check whether they indeed got the theorem right. >Is this an example of killing a fly with a >sledgehammer, You may call it that, of course. Although I can assure you that the applet is quite simple. I would rather compare it to a, say, 3/8" drill than to a 6" sledgehammer. >or am I missing something about the game? Nope, I believe you got it right.


Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 



peterash
Member since Sep1904

Sep2604, 06:15 PM (EST) 

2. "RE: pigeonhole sequence problem"
In response to message #1

Let me suggest a slightly different game to illustrate the theorem, which I would find more compelling. Present 10 cards with 6 face up, as you do in your game. Make sure that the numbers are generated so that there are no monotone subsequences of length 4. Challenge the student to fill in the remaining 4 numbers so that there will be NO monotone subsequences of length 4. If you wish, you could offer a cash prize for doing so. After filling in the numbers, the student presses a "Test" button. The button causes a monotone subsequence of length 4 (or greater) to be highlighted. What do you think? 

Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 






alexb
Charter Member
1346 posts 
Oct0404, 03:31 PM (EST) 

5. "RE: pigeonhole sequence problem"
In response to message #3

>>What do you think? > >Thank you for a good idea. Time permitting, I am going to do >that. Well, an implementation, perhaps not entirely satisfactory, is now located athttps://www.cuttheknot.org/Curriculum/Combinatorics/UpAndDownGame.shtml There is certainly a difficulty, which I have not resolved yet, as to what part of a permutation should be left over. If it's too long, then the result is virtually predetermined. If it's too short, then it's unclear how to inforce the existence of a, say, increasing sequence. Time permitting, I may return to that problem.


Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 



You may be curious to have a look at the old CTK Exchange archive. Please do not post there.
Front page
Contents
Copyright © 19962018 Alexander Bogomolny
69978510


