Conference rusure::math

Let F1 and F2 be the probability functions for the required chain lengths, and
let the length of the available chain be L.

Define F(X, Y) = F1(X) F2(Y).

The problem now is to find (best_x,best_y) such that  the integral over
0..best_x, 0..best_y of F(x,y) is maximized, and best_x+best_y <= L.


If F1(x) = 0    x<0,
	   1/L  0<=x<=L,
	   0    x>L

and F2(y) similarly,


			chop 'er in 'alf


/Bevin

PS: My probability theory is a little rusty, this could all be garbage!

From:	ROLL::USENET       "USENET Newsgroup Distributor" 24-FEB-1984 22:45
To:	HARE::STAN
Subj:	USENET net.math newsgroup articles

Newsgroups: net.puzzle,net.math
Path: decwrl!decvax!harpo!eagle!mhuxl!houxm!ihnp4!inuxc!pur-ee!CS-Mordred!Pucc-H:Pucc-I:ags
Subject: Re: Where to cut the chain?
Posted: Wed Feb 22 09:20:17 1984


>  You get a call to bring two lengths of chain with you to a job. Where to 
>  you cut the chain to maximize your chances of both pieces being long enough?

Let the two required lengths be x and y.  Without loss of generality, x >= y.
Therefore the needed lengths can be represented as the coordinates of a point
in the first octant of the plane:  the area in the first quadrant below the
line y=x.

In order to answer the question, a probability distribution is needed.  There
must be a way to assign the relative probability of different points within
the designated region.  Since the area of the region is infinite and the
probability distribution must have an integral of 1 over the region, it follows
that some areas are more probable than others -- there is no such thing as
a uniform probability distribution over the designated region.

The question as stated cannot be answered.

If you knew an upper bound to the lengths, you could assign a uniform 
probability -- but no upper bound is stated.
-- 

Dave Seaman
..!pur-ee!pucc-i:ags

"Against people who give vent to their loquacity 
by extraneous bombastic circumlocution."

Newsgroups: net.math,net.puzzle
Path: decwrl!decvax!harpo!ulysses!mhuxl!ihnp4!ihuxa!trough
Subject: Re: Chain problem can't be answered
Posted: Thu Feb 23 08:53:42 1984


Dave Seaman claims the chain problem has no answer because there's no limit
given on the space of possible required lengths. But there is a limit:
the length of the chain. All required lengths that are longer than the
length of the uncut chain are unattainable regardless of where the chain
is cut, and are thus irrelevant.

					Chris Scusel
					Bell Labs
					Naperville, Ill

				{AT&T BL}!ihnp4!ihuxa!trough

Cutting the chain anywhere but the middle decreases the chances that the
smaller piece will be long enough although increasing the chances that the
larger piece will be.

Since we want BOTH pieces to be long enough, just cut it in the middle to
maximize both lengths.  Seems "intuitive to me (-&".

If I weren't limited to a given starting length of chain, and someone just
told me to bring any old pieces of chain and maximize the chances that
both lengths I bring would be long enough, I'd try to bring the two longest
ones I could find.  Hence given that I'm limited, I cut in the middle so
both lengths are as long as possible.

Aha!  If we assume the two desired chain lengths are independent variables with
the same distribution, then we can prove that cutting it in half is optimal.

A good answer is 1/3.

Let L be the length of the chain.  The request is assumed to be for two
pieces, with uniformly distributed lengths, and two variants:

	(a) the length of each piece is independently < L, or
	(b) the total requested length < L.

Let c be the length of the smaller piece (after the cut).  The following
diagram shows (with x's) the possible requests that can be satisfied.


		  L +---------------+
		    |\              |
		    |  \            |
		L-c |    \          |
	one	    |xxxx  \        |
	request	    |xxxx    \      |
		  c |xxxx      \    |
		    |xxxxxxxxx   \  |
		    |xxxxxxxxx     \|
		  0 +---------------+
		    0    c   L-c   L

			other
			request

The problem, then is to choose c to maximize:

	(a) ( (L-2c)*c*2 + c*c )/( L*L )
	(b) ( (L-2c)*c*2 + c*c )/( L*L/2 )

Obviously, the same c will maximize both.  So we consider (a).  Let z = c/L,
and (a) becomes:

	( (L-2c)*c*2 + c*c )/( L*L ) = 2*(c/L) - 3*(c/L)^2

which is maximized when c = L/3.  So the chain should be cut into lengths
L/3 and 2L/3.

And the cutter's chance of success?  That's 1/3 for (a), or 2/3 for (b).

> CFSCTC::GILBERT

	Is this a Peter Gilbert?

Welcome back!
Andrew.