SERVING THE QUANTITATIVE FINANCE COMMUNITY

mikebell
Topic Author
Posts: 1698
Joined: July 1st, 2003, 5:23 am

The Matchstick Problem

I heard about this problem last week while vacationing. I didn't have a computer on me so I couldn't test some of my theories but there are a few 'back-of-the-napkin' methods you can utilize. As soon as I got home last night, I ran a few sims in MatLab to see whether my answer was anywhere close. Before I go into how I solved this, you should try it yourself. Problem is deceptively simple and goes something like this.Let's say you have 100,000 matches. If you take each matchstick and snap it in two pieces at random, what is the average ratio of the length of the longer piece to the length of a shorter piece?Simple? PS: Apologies if this has been posted/discussed before (I did a search but didn't find anything and this problem might be filed under a few different names).
Last edited by mikebell on July 25th, 2004, 10:00 pm, edited 1 time in total.

genieman17
Posts: 27
Joined: July 16th, 2004, 4:26 pm

The Matchstick Problem

QuoteOriginally posted by: mikebellI heard about this problem last week while vacationing. I didn't have a computer on me so I couldn't test some of my theories but there are a few 'back-of-the-napkin' methods you can utilize. As soon as I got home last night, I ran a few sims in MatLab to see whether my answer was anywhere close. Before I go into how I solved this, you should try it yourself. Problem is deceptively simple and goes something like this.Let's say you have 100,000 matches. If you take each matchstick and snap it in half at random, what is the average ratio of the length of the longer piece to the length of a shorter piece?Simple? PS: Apologies if this has been posted/discussed before (I did a search but didn't find anything and this problem might be filed under a few different names).Well if you snap them all "in half" then the ratio will be 1-1 for all of them...all the time...assuming you meant break into 2 pieces, then i would say the ratio will be 1.2-1 just guessing though...

mikebell
Topic Author
Posts: 1698
Joined: July 1st, 2003, 5:23 am

The Matchstick Problem

Opps, of course... by "half" I meant in two pieces Fixed in the initial post.

alexandreC
Posts: 678
Joined: June 9th, 2004, 11:35 pm

The Matchstick Problem

without any computer, and giving it a 1 minute though, I would say that the ratio you are looking for is 100 000 / 1.Alex

alexandreC
Posts: 678
Joined: June 9th, 2004, 11:35 pm

The Matchstick Problem

I have assumed that the position where you make the cut is a random variable.(This is obviously not the case in real life, given that if one is asked to cut a match in two pieces, one tends to cut it roughly in two equal pieces.)Alex
Last edited by alexandreC on July 25th, 2004, 10:00 pm, edited 1 time in total.

mikebell
Topic Author
Posts: 1698
Joined: July 1st, 2003, 5:23 am

The Matchstick Problem

QuoteOriginally posted by: alexandreCI have assumed that the position where you make the cut is a random variable.(This is obviously not the case in real life, given that if one is asked to cut a match in two pieces, one tends to cut it roughly in two equal pieces.)AlexCorrect. The way I started, I assumed you're given a precision in terms of the length of the sticks (i.e. 1/10th of the length etc). I solved it for infinite precision, however. Anything over 1/14,500 (or so if I remember correctly) is close to the infinite precision solution.

genieman17
Posts: 27
Joined: July 16th, 2004, 4:26 pm

The Matchstick Problem

ok i take back my 1.2-1 estimate...that estimate is from the assumption that a person is breaking them and people tend to try to break down the middle, since it is broken at random i will guess 3 to 1 average ratio if anyone works this out in some sort of program i wanna see how close my intuition comes to actual results

alexandreC
Posts: 678
Joined: June 9th, 2004, 11:35 pm

The Matchstick Problem

QuoteOriginally posted by: mikebellQuoteOriginally posted by: alexandreCI have assumed that the position where you make the cut is a random variable.(This is obviously not the case in real life, given that if one is asked to cut a match in two pieces, one tends to cut it roughly in two equal pieces.)AlexCorrect. The way I started, I assumed you're given a precision in terms of the length of the sticks (i.e. 1/10th of the length etc). I solved it for infinite precision, however. Anything over 1/14,500 (or so if I remember correctly) is close to the infinite precision solution.well, you didnt mention these precision factor in the problem...Alex
Last edited by alexandreC on July 26th, 2004, 10:00 pm, edited 1 time in total.

alexandreC
Posts: 678
Joined: June 9th, 2004, 11:35 pm

The Matchstick Problem

QuoteOriginally posted by: mikebell Anything over 1/14,500 (or so if I remember correctly) is close to the infinite precision solution.you meant "under" not "over" <wink>Alex
Last edited by alexandreC on July 27th, 2004, 10:00 pm, edited 1 time in total.

zerdna
Posts: 3856
Joined: July 14th, 2002, 3:00 am

The Matchstick Problem

QuoteOriginally posted by: alexandreCwithout any computer, and giving it a 1 minute though, I would say that the ratio you are looking for is 100 000 / 1.Alexi dunno. Without any computer, and giving it about 5 secs thought, it should be smaller. What you are saying is that there are a lot of matches that broke with a break point less than 1/100,000 from one end. That is pretty hard to believe, i would believe it if you said that there is approximately one match like that in a typical situation. If i understood the question it is about a value of sample average. A sample average is a random variable, so there is nothing literally like its fixed value that mikebell asked for. There is, however, a distribution for that sample average, for which mean value and other moments could be found. Mean value if you ask me should be somethig scaling like log, an answer like 2*lnN~20 for N=100000, or at least that order of manitude would be something that'd make sense to me.

mikebell
Topic Author
Posts: 1698
Joined: July 1st, 2003, 5:23 am

The Matchstick Problem

The way the problem was described to me was exactly as I stated it above. After giving it some thought, my initial reaction was "what exactly is average?" (and I've emphasized that word above). Average, in this context can mean a few different things: mean, mode, or median. Quickly looking at it, you can see that mode gives no possible solution (every ratio is different due to distribution - try to convince yourself), median gives an obvious answer (3) so the 'average' must stand for 'mean.' I'll post another hint/my thinking pattern tomorrow.

rblaser
Posts: 61
Joined: July 14th, 2002, 3:00 am

The Matchstick Problem

Without loss of generality, we can assume that the left piece L is smaller or equal to the right piece R. Hence, we are looking for the average X = R/L. Clearly, if we break a match in the middle, the ratio is 1/1. However, as our break point moves further to the left, the ratio changes (but it is equally likely that we will break the match there). For example, R/L is 3/1, 7/1, and 15/1 if we break the match at 3/4, 7/8, and 15/16 respectively. In other words, the ratios get large very quickly as we get closer to the edge, i.e. where L<<R. We can create two series that bound our desired value X from above and below. For the lower sum, we can keep going with the sequence mentioned above to infinity. However, in each interval we assume that the ratio is the same as the previous discrete point we encountered. In other words, between the middle of the match and 3/4 of the match, we approximate the ratio as 1/1. From 3/4 to 7/8, we approximate the ratio as 3/1, etc. The result is obviously smaller than our desired average ratio X. Similarly, we can form an upper sum by assuming that the ratio between the discrete points of the series is the next higher ratio. For example, we approximate the ratio between the middle of the match and 3/4 of the match to be 3/1. From 3/4 to 7/8 it's 7/1, and so on. These two series bound the average ratio from above and below:We can simplify the left hand side (lower bound) as follows:The second sum converges to 1 but the the first sum diverges. However, since our lower bound of X diverges, X iself, i.e the average ratio of the length of the longer piece to the length of a shorter piece diverges as well (is infinity). In particular, this means that a monte carlo simulation would yield wildly different results with every run.

Tripitaka
Posts: 166
Joined: January 30th, 2004, 3:51 pm

The Matchstick Problem

my reasoning was similarish- you snap the match somewhere on the interval (0,1/2] and then the ratio of longest to shortest is L-1/(L) for some L in (0,1/2].the expected ratio would thus be: (err, can't do latex)int (2*(1+1/L)dL on (0,1/2)or something similar, which is an integral that doesn't have a solution so there is no expectation of the ratio, therefore it's an ill posed problem...
Last edited by Tripitaka on July 26th, 2004, 10:00 pm, edited 1 time in total.

MikeM
Posts: 281
Joined: March 12th, 2003, 2:23 pm

The Matchstick Problem

Are we doing longer/shorter or shorter/longer? ...Is it possible that the first one doesn't converge / is infinite (since nobody asked yet)?

Mircea
Posts: 19
Joined: July 9th, 2004, 6:04 pm

The Matchstick Problem

I agree with Triptaka,In LaTexMay be the author meant shorter over longer. In that case there is a finite solution

Wilmott.com has been "Serving the Quantitative Finance Community" since 2001. Continued...

 JOBS BOARD

Looking for a quant job, risk, algo trading,...? Browse jobs here...

GZIP: On