|
|
|
|
|
|
|
|
CTK Exchange
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) |
|
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) |
|
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 |
|
|
|
You may be curious to have a look at the old CTK Exchange archive. Please do not post there.
Copyright © 1996-2018 Alexander Bogomolny
|
|