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

CTK Exchange

Subject: "Birds on a wire puzzle"     Previous Topic | Next Topic
Printer-friendly copy     Email this topic to a friend    
Conferences The CTK Exchange Guest book Topic #453
Reading Topic #453
soler
Member since May-13-05
May-14-05, 07:10 AM (EST)
Click to EMail soler Click to view user profileClick to add this user to your buddy list  
"Birds on a wire puzzle"
 
   I may be a little thick but I could not understand the problem Description. If the birds are wider than points then obviously you cannot fit an infinitely large number of them. If they are just points then the answer is the length of the wire. What am I missing?


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
alexb
Charter Member
1604 posts
May-16-05, 11:49 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  
1. "RE: Birds on a wire puzzle"
In response to message #0
 
   >If the birds are wider than points then
>obviously you cannot fit an infinitely large number of them.

Right. They are just points.

>If they are just points then the answer is the length of the
>wire.

Why?

>What am I missing?

I do not know.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
Mark Huber
guest
May-17-05, 01:32 PM (EST)
 
2. "RE: Birds on a wire puzzle"
In response to message #0
 
   Let the wire be the closed interval from 0 to 1, and suppose that there are three birds on the wire, points a = .1, b = .2, and c = .35.

Then bird a is closest to bird b, so interval (.1, .2) is colored yellow. Bird b is closest to bird c, so interval (.2, .35) is colored yellow. Bird c is closes to bird b, so interval (.2, .35) is colored (of course it already was colored earlier so this interval is redundant.)

So from (.1, .2) and (.2,.35) is colored yellow and the rest of the wire is clear.

Here's another example. If the birds sat at .2, .3, .7, and .8, then
the interval (.2,.3) and (.7,.8) would be colored yellow, and the rest of the wire would be clear.

Hope that helps!
-mark


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
happyusers
Member since Jul-29-05
Jul-29-05, 09:28 AM (EST)
Click to EMail happyusers Click to send private message to happyusers Click to view user profileClick to add this user to your buddy list  
3. "RE: Birds on a wire puzzle"
In response to message #2
 
   I understand the question quite well but am not totally convinced by the solutions proposed. In particular, the 4th solution rely on computation of conditionnal probability without saying it.
When you suppose three consecutive intervals, the intermediate having a length of x, the length of the other two is governed by a conditionnal law. To be convinced of that is very simple, Let us suppose a wire of length 1. f(x) has <0,1> for support. Let us say that x=.5. clearly the probability that it is smaller that its two neighbours is null ; nevertheless, the formulation proposed exhibit a positive probability (F(x)*F(x)*f(x) dx).
Furthermore, I don't clearly visualize what is the F(x) law. Why should all intervals would have the same law? What is easy to speak of is the joint law of the xi intervals F(x1,..xi,..xn+1) if there are n birds. One can asset that sum(xi)=1. Another clue that variables xi are not independant.
Hope that helps.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
Mark Huber
guest
Jul-30-05, 02:47 PM (EST)
 
4. "RE: Birds on a wire puzzle"
In response to message #3
 
   Well, happyusers, none of the 4 solutions proposed are rigorous in the sense that they at the level of mathematical proof needed for a journal article, but each contains the essential idea for what could be turned into a rigorous proof.

In the case of the 4th solution by Stuart Anderson, he begins by essentially considering an infinite length wire where the distance between successive birds are independent random variables each with the same distribution.

As you point out, this is not the actual problem of N birds on the wire from 0 to 1. However, as the number of birds grows to infinity, the wire "looks" like it is growing relative to the distance between any two birds, since that distance is going to zero. So fixed wire length and shrinking distance between birds is the same essentially as infinite wire length and fixed distribution of distance between birds.

You are right that this does not give a formal proof of the result unless these two related problems are shown to be equivalent, although it does contain the essential mathematical intuition needed to write out such a proof.

Mark Huber


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
mr_homm
Member since May-22-05
Jul-31-05, 01:05 AM (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  
5. "RE: Birds on a wire puzzle"
In response to message #4
 
   Mark,

Thank you for your kind comments.

Happyuser,

In regard to your doubts about the proposed solutions, some of this is a matter of context and some a matter of interpretation.

First, about the interpretation of the problem: The original problem did not specify the length L of the wire or the number N of birds, except to say that the number was "large." Now with variable L and N, there is not going to be a single numerical answer such as 7/18, of course, so none of the 4 proposed solutions can really be correct for the problem as stated. However, it is easy to show that L is irrelevant to the answer, because, since the birds are randomly distributed on the wire, scaling up the wire after the N birds land on it produces the same probability as scaling it up before they land.

This leaves N as a variable. However, since the problem is stated for "large" N, we are clearly invited to look for the behavior of the problem in the limit as N tends to infinity. This raises its own troubles, however, since if an infinite number of birds land on a finite wire, the density of birds will clearly be infinite. This can be handled using limits, of course, but in view of the fact that the answer to the problem is independent of L, the trouble can be handled by rescaling the wire, so that the density of birds remains finite. We can pick any density we like, and simply expand L as N increases, so that we are really considering a limit of similar problems as both L and N tend to infinity, while their ratio is held constant.

So trying to interprete the problem so that it has a unique solution rather naturally leads to the consideration of an infinite length of wire with a finite density of birds on it. Now as to the context of the four solutions, these were extracted from this forum, and were part of an ongoing discussion of the problem. By the time I posted my solution, Nathan Bowler had already introduced the idea of expanding the length of the wire to infinity, so I took that as my starting point. If this had been an article for publication, I would have cited him of course, but in a thread it didn't seem necessary. When the four solutions were taken out of the thread, however, this context was lost, and so my solution seems to start with several unstated assumptions.

As to the idea that the probabilities should be conditional, this is fortunately not true for an infinite wire. You are correct that it is true for finite L and N. Consider an interval between two birds, and imagine covering everything to the right of this interval. Looking at birds in the visible part, what can you predict about the position of the first bird in the covered part? Nothing but that the birds are uniformly distributed with the same density as on the whole wire. But you know that already, so the data in the visible part contributes nothing to your knowledge of the covered part. Therefore the probability is not conditional after all. Or more technically, you can formulate the probability as conditional if you want, but it is independent of the length of the given interval, so it reduces to an unconditional probability anyway.

About the probability funcition F(x), this is defined to be the probability that the length of an interval will be less than x. If the distribution of birds is uniform, then F(x) is known to be exponential, i.e. F(x) = 1-d*exp(-x/d), where d is the density of birds. However, the main point I wanted to make was that even if the birds were not uniformly distributed (suppose the wire gets more attractive as we move to the right, warmer, covered with birdseed, or something) then F(x) will be some unknown function, but there will still be exactly 1/3 of the intervals smaller than both their neighbors, 1/3 intermediate, and 1/3 bigger than both their neighbors. The only restriction is that F(x) is a correct probability function, satisfying F(0)=0, F(x-->infinity) = 1, F is monotonically increasing. (Based on this, F(x) is automatically integrable in the Lebesgue theory, so you don't need to check this.)

As I pointed out later in the above referenced thread, there is a non-probablistic reason why the proportion of intervals bigger than both neighbors must be the same as the proportion smaller than both neighbors. It'seems a bit counterintuitive at first, since the small intervals outnumber the big ones in the exponential distribution.

Hope this clears up some of the unstated assumptions in my solution.

--Stuart Anderson


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top

Conferences | Forums | Topics | Previous Topic | Next Topic

You may be curious to visit the old Guest book.
Please do not post there.

|Front page| |Contents|

Copyright © 1996-2018 Alexander Bogomolny

[an error occurred while processing this directive]
Search:
Keywords:

Google
Web CTK