Author |
Topic: Trees and Birds (Read 802 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Trees and Birds
« on: Dec 21st, 2003, 12:00pm » |
 Quote  Modify
|
44 trees are arranged in a circle. Originally, every tree is occupied by a single bird. Then, birds start to move in the following manner: 2 birds simultaneously fly to the next tree in opposite directions (every bird may move more than once).
Is it possible that eventually all the birds gather on one tree?
|
|
 IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Trees and Birds
« Reply #1 on: Dec 21st, 2003, 10:08pm » |
Quote Modify
|
i don't think they would
::
(ofcourse i do assume that when you mention that birds move in opposite direction then it means one move clockwise and the other moves anticlockwise)
if two adjacent birds move towards each other,then it would be a simple exchange.Hence no clustering of birds.
However if they move away from each other then we see that the birds start clustering on the trees.
Now think of the circle of trees as a vertical circle with 44 points.draw a diameter such that there are 22 points on one side and 22 on the other.Start moving the birds from the bottom to the top. A simple run would show that at the end we will have two trees with 22 birds on each.
2 birds on the same tree cannot move in the same direction and 2 birds of the adjacent tree ,if they move towards each other then as i mentioned it will be a simple exchange.
In other words, the max we can have on one tree is 22.
However if you had just one more blank tree then we can have all 44 birds on that tree.
::
|
| « Last Edit: Dec 21st, 2003, 10:10pm by TenaliRaman » |
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Trees and Birds
« Reply #2 on: Dec 22nd, 2003, 1:02am » |
Quote Modify
|
TenaliRaman, although your answer is correct, I am not sure the argument is perfectly convincing: in particular, your assertion that the maximum number of birds at one tree is 22? Assume there are already 22 at a certain tree. Then, if only birds from other trees move, some of them can certainly move to that tree, making it more than 22. Am I missing something?
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Trees and Birds
« Reply #3 on: Dec 22nd, 2003, 6:04am » |
Quote Modify
|
Actually ,
i never put that up as an argument , it was more of "a run of thought".I hid basically for the reason that my post doesn't put wrong thought on a mind which might be on a right track. 
Also you are right, i was feeling drowsy and hungry and ate up a few words there,
::
the max 22 i meant was max possible value for which the birds are symmetrically distributed.
Any further movement would make the distribution asymmetric.
2 points i forgot to add in my last post,
1>the birds must be symmetrically distributed if they have anyhope of reaching a common tree.why? since 2 birds were moving simultaneously.
2>if they are to be on a common branch, they would need to move odd number of times.
::
I am angry with myself for the reason that i am not able to put the entire reasoning above into a rigorous set of conclusive arguments.
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Trees and Birds
« Reply #4 on: Dec 22nd, 2003, 11:46am » |
Quote Modify
|
I found an invariant (hint): number the trees in order from 1 to 44, and consider the sum of the positions of each bird.
Solution: The sum changes by either 0 or 44 every move. It starts at 1+...+44 = 22(45) == 22 (mod 44), but if all the birds were on the same tree, the sum would be 44k == 0 for some k.
In general, it's possible iff the number of trees is odd.
|
| « Last Edit: Dec 22nd, 2003, 11:48am by Eigenray » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Trees and Birds
« Reply #5 on: Dec 23rd, 2003, 1:56am » |
Quote Modify
|
Nice solution, Eigenray  ! (For me, this approach is very suitable for such kind of problems).
What about some generalizations?
Consider all possible arrangments of M birds on N trees. Call two arrangments equivalent if one may be reached from another by the rules of the original puzzle. Questions:
Q1. What are the equivalence conditions?
Q2. How many equivalence classes there are?
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Trees and Birds
« Reply #6 on: Dec 23rd, 2003, 5:04am » |
Quote Modify
|
Suppose that birdi is at xi in state X, and at yi in state Y. The two states are equivalent iff S:= [sum](yi - xi) == 0 mod N.
Proof: Let di denote the net movement of birdi in the positive direction, so that di == yi - xi mod N. After any set of legal moves, [sum]di = 0, so S == 0 is necessary.
Conversely, suppose S = kN. Then we can let d1 = y1-x1 - kN, while for i>1, di = yi - xi, so that [sum]di=0. Now we can take any bird i with di > 0, and a bird j with dj < 0, and have each move one space in opposite directions, and repeat until all birds are in position, after a total of [sum]|di|/2 simultaneous moves.
Then the answer to Q2 would be that there are N equivalence classes, since any state is equivalent to having, for some k, one bird at treek, and the others at treeN = tree0.
This has an interesting physical interpretation. Consider M people standing at some vertices of a regular N-gon on a disc which is free to rotate about a fixed axis, but not translate. Then during each move, there is no net torque, though the center of mass can change. Then two states are equivalent if the people can walk from one to the other without the disc rotating.
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Trees and Birds
« Reply #7 on: Dec 23rd, 2003, 11:42am » |
Quote Modify
|
Wowee Eigenray!! very nice 
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print