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 Search CTK Buying a book is a commitment to learning Table of content Products to download and subscription Things you can find on CTK Chronology of updates Email to Cut The Knot Recommend this page

CTK Exchange

Subject: "Recreational Combinatorics"     Previous Topic | Next Topic
Printer-friendly copy     Email this topic to a friend    
Conferences The CTK Exchange College math Topic #650
Reading Topic #650
The Mask
guest
Oct-08-07, 09:02 AM (EST)
 
"Recreational Combinatorics"
 
   There is a wire stretching infinitely long in both directions. And there two species of birds - yellow and green- who happen to sit on it.

But they sit according to a certain condition which states that counting onwards from a particular bird the bird at 4th position and at the 7th position need to be of the same color.

Thus, if the 5th bird is green, the 1st one and the ninth one have to be green. And same goes for birds at position 12 and at position -2.
So, if you have at least one bird of each color, find with proof the maximum number of birds that you can manage to accomodate on the wire without breaching the said condition.

In the end i would add, i was able to guess an answer because i could not do any better..but i was unable to prove it.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
alexb
Charter Member
2092 posts
Oct-08-07, 09:31 AM (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  
2. "RE: Recreational Combinatorics"
In response to message #0
 
  

0 1 2 3 4 5 6 7 8
x x y x x x y x x

For index n, birds n+4 and n+7 are of the same color as are birds n-4 and n-7. Hence,

birds 0, 4, 7, 8=4+4, 1=8-7, 3=7-4, 5=1+4 must be of the same color.

Birds 2 and 6 must be of the other kind. Bird 9 would be of both colors, for 9=2+7 and 9=5+4.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
mr_homm
Member since May-22-05
Oct-08-07, 10:08 PM (EST)
Click to EMail mr_homm Click to send private message to mr_homm Click to view user profileClick to add this user to your buddy list  
3. "RE: Recreational Combinatorics"
In response to message #2
 
   An alternative way of stating what is basically the same proof:

Suppose there were 10 birds. Let the first bird be 1; then starting from 0, take4 steps forward, then another 4, then 7 back, and then repeat this pattern. You reach the following birds, which are therefore the same color: 4, 8, 1, 5, 9, 2, 6, 10, 3, 7. But this is all of the birds! Of course, if there are more than 10, you can simply break them into overlapping sets of 10; thus they are all the same color.

Alex's example of 9 birds satisfying the rules then completes the proof. This is not particularly a "better" proof; it is just my perspective on the problem.

--Stuart Anderson



  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
The Mask
guest
Oct-09-07, 10:55 AM (EST)
 
4. "RE: Recreational Combinatorics"
In response to message #3
 
   Hello there,

Nice perspective Mr. Homm and nicely explained solution alex

However, i was trying to go after something stronger. You see, i came up roughly with the same proof sketched by alex. But i believe though it does solve the problem, it does not tell me (who is not a mathematician) how to approach the general case.
I understand that we could have placed an infinite number of birds on the wire if the numbers were 12 and 16 (instead of 4 and 7) or any other pair of numbers , a and b with gcd(a,b) > 1

However, with gcd(a,b)=1; things change. So, i would like to have a general result in this case.

And again in the end i would like to have a proof first for the fact that in the case of gcd(a,b)=1 we have a finite number of birds.

Next i wou;d like to know what that finite number is. (of course the 2 can be combined directly)..


  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.

Copyright © 1996-2018 Alexander Bogomolny

Search:
Keywords:

Google
Web CTK