wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> favorable 5-tuples
        
(Message started by: balakrishnan on Jan 1^st, 2008, 4:19pm)

Title: favorable 5-tuples
Post by balakrishnan on Jan 1^st, 2008, 4:19pm

you have n sticks of lengths (1,2,3...n)
You will choose 5 sticks from these at random and form a quadrilateral of which one side would be used to form a diagonal of this quadrilateral.
Not any 5 sticks chosen at random can be made to form a quadrilateral.
for instance using 1,2,3,4,5 you cannot form such a quadrilateral.

How many such 5-tuples exists for any given n.

For example if n=6,
you have sticks of lenghts 1,2,3,4,5,6
So the 5-tuple 2,3,4,5,6
can be used to form a quadrilateral of sides
2,3,5,6 and the side of length 4 can be used as a diagonal

So f(6)=1

What is f(n) for any given n?

Title: Re: favorable 5-tuples
Post by Joe Fendel on Jan 3^rd, 2008, 3:06pm

I like this problem.

One approach is figuring out a clever algorithm to identify whether a given 5-tuple is favorable. Essentially, we need to be able to break the 5-tuple into 2 triples (with one of the numbers repeated) such that the triangle inequality is possible - the largest number in the triple isn't more than the sum of the other two. If we had an algorithm that could identify this easily (without brute-force checking all triple-pairs) we might be able to find insight into f(n).

Another approach is to find f(n) for increasingly higher n. f(5) is 0, since if the 1 is in our 5-tuple, the triangle it belongs to collapses. f(6)=1, as balakrishnan points out. What about f(7)? Turns out any 5-tuple in {2,...,7} is favorable, so f(7) = 6. Similarly, any 5-tuple in {2,...,8} is favorable, so f( 8 ) = 21.

When we get to f(9), though, we begin to run into further unfavorable 5-tuples. For example, {2,3,4,5,9} is unfavorable because the 9 can't belong to a triple. Similarly {2,3,5,7,9} is unfavorable because the 2 can't belong to a triple. Also {2,3,5,8,9} is unfavorable because the only triples that work are those that contain both the 8 and 9. There may be more - my search isn't exhaustive.

I don't have any further immediate instinct on this, though.

Title: Re: favorable 5-tuples
Post by Grimbal on Jan 4^th, 2008, 12:53am

Since "favorable" depends only on the ratios between the stick lengths, the proportion of favorable 5-tuples for large n must tend to a value corresponding to the proportion of favorable tuples in the continuous case. So it must be O(n⁵).

Title: Re: favorable 5-tuples
Post by jollytall on Jan 4^th, 2008, 3:45am

Not a big result, but still might help someone. The number of favourable triplets is:

k*(k-1)*(4k-5)/6 for n = 2k and
k*(k-1)*(4k+1)/6 for n=2k+1.

But how many ways can you choose 2 of these triplets on a way that one and only one element is the same???

Title: Re: favorable 5-tuples
Post by towr on Jan 4^th, 2008, 7:41am

Can't we count all the different cases separately and then add them?

for a<b<c<d<e we can have
abc ade
abc bde
abc cde
abd ace
abd bce
abd cde
abe acd
abe bcd
abe cde
acd bce
acd bde
ace bcd
ace bde
ade bcd
ade bce

Title: Re: favorable 5-tuples
Post by balakrishnan on Jan 4^th, 2008, 6:52pm

I obtained a closed form expression for this problem.
I dont have any systematic approach to the problem.
As Grimbal stated, the count is O(n^5) and
if you choose any 5 sticks from 1,2..n at random, the probability that they will form a valid quadrilateral is 29/48 for large n

Title: Re: favorable 5-tuples
Post by jollytall on Jan 5^th, 2008, 9:54am

It would be nice to see the closed form. Even more it would be nice to understand how.

Back to Towr's idea, the problem with that, besides the fact, how to solv the different cases individually, it is also how to avoid duplicates. E.g. n=200, a-e = 100-104 is a solution for all the 15 cases, while others are solution only in somoe or one of the 15. So pure adding up is not a solution.

Title: Re: favorable 5-tuples
Post by towr on Jan 5^th, 2008, 11:09am

on 01/05/08 at 09:54:35, jollytall wrote:

Back to Towr's idea, the problem with that, besides the fact, how to solv the different cases individually, it is also how to avoid duplicates. E.g. n=200, a-e = 100-104 is a solution for all the 15 cases, while others are solution only in somoe or one of the 15. So pure adding up is not a solution.

Ah, yes; it would count (1/4th of) how many quadrilaterals you could make with such a 5-tuples, rather than how many 5-tuples there are which you could make such a quadrilaterals with.

Title: Re: favorable 5-tuples
Post by balakrishnan on Jan 17^th, 2008, 7:34am

Here is my answer:
If f(n) represents the number of favorable ways of choosing,then
f(n)=9n/40-11n^2/32+49n^3/216-15n^4/256+29n^5/5760...if n=12k
f(n)=-485/6912+159n/640-45n^2/128+49n^3/216-15n^4/256+29n^5/5760...if n=12k+1
f(n)=-49/432+9n/40-11n^2/32+49n^3/216-15n^4/256+29n^5/5760...if n=12k+2
f(n)=-47/256+159n/640-45n^2/128+49n^3/216-15n^4/256+29n^5/5760...if n=12k+3
f(n)=-2/27+9n/40-11n^2/32+49n^3/216-15n^4/256+29n^5/5760...if n=12k+4
f(n)=539/6912+159n/640-45n^2/128+49n^3/216-15n^4/256+29n^5/5760...if n=12k+5
f(n)=-3/16+9n/40-11n^2/32+49n^3/216-15n^4/256+29n^5/5760...if n=12k+6
f(n)=-1781/6912+159n/640-45n^2/128+49n^3/216-15n^4/256+29n^5/5760...if n=12k+7
f(n)=2/27+9n/40-11n^2/32+49n^3/216-15n^4/256+29n^5/5760...if n=12k+8
f(n)=1/256+159n/640-45n^2/128+49n^3/216-15n^4/256+29n^5/5760...if n=12k+9
f(n)=-113/432+9n/40-11n^2/32+49n^3/216-15n^4/256+29n^5/5760...if n=12k+10
f(n)=-757/6912++159n/640-45n^2/128+49n^3/216-15n^4/256+29n^5/5760...if n=12k+11

can anyone prove it?