Author |
Topic: favorable 5-tuples (Read 822 times) |
|
balakrishnan
Junior Member
Gender: 
Posts: 92
|
 |
favorable 5-tuples
« on: Jan 1st, 2008, 4:19pm » |
 Quote  Modify
|
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?
|
|
 IP Logged |
|
|
|
Joe Fendel
Full Member
Posts: 158
|
|
Re: favorable 5-tuples
« Reply #1 on: Jan 3rd, 2008, 3:06pm » |
Quote Modify
|
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.
|
| « Last Edit: Jan 3rd, 2008, 3:06pm by Joe Fendel » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: favorable 5-tuples
« Reply #2 on: Jan 4th, 2008, 12:53am » |
Quote Modify
|
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(n5).
|
| « Last Edit: Jan 4th, 2008, 12:54am by Grimbal » |
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: favorable 5-tuples
« Reply #3 on: Jan 4th, 2008, 3:45am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: favorable 5-tuples
« Reply #4 on: Jan 4th, 2008, 7:41am » |
Quote Modify
|
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
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
balakrishnan
Junior Member
Gender:
Posts: 92
|
|
Re: favorable 5-tuples
« Reply #5 on: Jan 4th, 2008, 6:52pm » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: favorable 5-tuples
« Reply #6 on: Jan 5th, 2008, 9:54am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: favorable 5-tuples
« Reply #7 on: Jan 5th, 2008, 11:09am » |
Quote Modify
|
on Jan 5th, 2008, 9:54am, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
balakrishnan
Junior Member
Gender:
Posts: 92
|
|
Re: favorable 5-tuples
« Reply #8 on: Jan 17th, 2008, 7:34am » |
Quote Modify
|
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?
|
| « Last Edit: Jan 17th, 2008, 7:34am by balakrishnan » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print