CTK Exchange
Front Page
Movie shortcuts
Personal info
Awards
Reciprocal links
Terms of use
Privacy Policy

Interactive Activities

Cut The Knot!
MSET99 Talk
Games & Puzzles
Arithmetic/Algebra
Geometry
Probability
Eye Opener
Analog Gadgets
Inventor's Paradox
Did you know?...
Proofs
Math as Language
Things Impossible
My Logo
Math Poll
Other Math sit's
Guest book
News sit's

Recommend this site

Manifesto: what CTK is about |Store| Search CTK Buying a book is a commitment to learning Table of content Things you can find on CTK Chronology of updates Email to Cut The Knot Recommend this page

CTK Exchange

Subject: "pigeonhole sequence problem"     Previous Topic | Next Topic
Printer-friendly copy     Email this topic to a friend    
Conferences The CTK Exchange College math Topic #474
Reading Topic #474
peterash
Member since Sep-19-04
Sep-19-04, 09:44 PM (EST)
Click to EMail peterash Click to send private message to peterash Click to view user profileClick to add this user to your buddy list  
"pigeonhole sequence problem"
 
   I'm looking for applications of the pigeonhole principle that would be good for a freshman-level course in mathematical problem solving that I am teaching. I looked at Item #119 in cut-the-knot|Arithmetic/ 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 Printer-friendly page | Reply | Reply With Quote | Top
alexb
Charter Member
1346 posts
Sep-19-04, 09:50 PM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
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 freshman-level course in
>mathematical problem solving that I am teaching. I looked at
>Item #119 in cut-the-knot|Arithmetic/ 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 Printer-friendly page | Reply | Reply With Quote | Top
peterash
Member since Sep-19-04
Sep-26-04, 06:15 PM (EST)
Click to EMail peterash Click to send private message to peterash Click to view user profileClick to add this user to your buddy list  
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 Printer-friendly page | Reply | Reply With Quote | Top
alexb
Charter Member
1346 posts
Sep-26-04, 10:25 PM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
3. "RE: pigeonhole sequence problem"
In response to message #2
 
   >What do you think?

Thank you for a good idea. Time permitting, I am going to do that.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
alexb
Charter Member
1346 posts
Oct-04-04, 03:31 PM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
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 at

https://www.cut-the-knot.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 Printer-friendly page | Reply | Reply With Quote | Top

Conferences | Forums | Topics | Previous Topic | Next Topic

You may be curious to have a look at the old CTK Exchange archive.
Please do not post there.

|Front page| |Contents|

Copyright © 1996-2018 Alexander Bogomolny

66326334


Google
Web CTK