January 2001
<<December January February>>
| This month's puzzle comes from Raul Saavedra.
Imagine you have N events of non-zero duration, in how many different ways could those events overlap in time? (This combinatorial problem shows up within the context of temporal reasoning). Let’s formulate the problem more precisely. Imagine you have two non-null segments, AB and XY (A < B and X < Y always). If you wanted to put them on a line, you could arrange those 2 segments in exactly 13 different ways: Graphical representation Constraints
Part A) Derive a method for computing the function F(N) which given the number of segments N returns the total number of ways in which those N segments can be arranged on a line:
F(2) = 13 : F(N) = ??? Part B) Find F(N) for N=3,4,… up to 10. Bonus question: Lyle Ramshaw remarks that, if we allow zero-length intervals (left endpoint = right endpoint), the number of allowable configurations becomes exactly twice as large. (For n=2 there would be 26 possibilities instead of 13.) Can you find a simple combinatorial explanation for that? |
We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!
We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com
Challenge:
01/02/01 @ 09:00 AM EST
Solution:
02/01/01 @ 10:00 AM EST
List Updated:
02/01/01 @ 7:00 PM EST
People who answered correctly:
Henry Bottomley (01.02.2001 @ 1:18 PM EDT)
Samantha Levin (01.02.2001 @ 3:25 PM EDT)
Jack Kennedy (01.02.2001 @ 6:21 PM EDT)
Francis Golding (01.03.2001 @ 7:39 AM EDT)
Ionel Santa (01.03.2001 @ 8:21 AM EDT)
Daniel Li (01.03.2001 @ 10:30 AM EDT)
Vladimir Sedach (01.03.2001 @ 1:18 PM EDT)
Marian Olteanu (01.03.2001 @ 1:31 PM EDT)
John Hamilton (01.03.2001 @ 8:24 PM EDT)
Jacques Willekens (01.04.2001 @ 7:49 AM EDT)
Tim Edmonds (01.04.2001 @ 11:42 AM EDT)
Joseph DeVincentis (01.04.2001 @ 4:55 PM EDT)
Koen Claessen (01.04.2001 @ 10:28 PM EDT)
Gopika Goswami (01.05.2001 @ 10:58 PM EDT)
Rocke Verser (01.06.2001 @ 5:18 PM EDT)
Tom Blumer (01.08.2001 @ 8:57 PM EDT)
Alexey Vorobyov (01.08.2001 @ 9:05 PM EDT)
Se June Hong (01.09.2001 @ 4:12 PM EDT)
Derek Kisman (01.09.2001 @ 5:04 PM EDT)
Mihai Cioc (01.13.2001 @ 9:38 PM EDT)
Dan Peleg (01.14.2001 @ 12:23 AM EDT)
Maarten van Kasteel (01.14.2001 @ 5:17 PM EDT)
Niklas Een (01.14.2001 @ 5:59 PM EDT)
Vince Lynch (01.15.2001 @ 1:50 PM EDT)
Aron Fay (01.15.2001 @ 7:22 PM EDT)
Johannes Schindelin (01.15.2001 @ 12:30 PM EDT)
Prashanth Kota (01.16.2001 @ 4:54 AM EDT)
Andrew Lowry (01.16.2001 @ 2:05 PM EDT)
Joshua Berryman (01.16.2001 @ 3:01 PM EDT)
J vanDelden (01.17.2001 @ 4:11 AM EDT)
Jonathan Wildstrom (01.17.2001 @ 9:52 AM EDT)
Bill Schwennicke (01.19.2001 @ 2:49 PM EDT)
Nagendra (01.23.2001 @ 9:42 AM EDT)
Prakash Jalan (01.25.2001 @ 12:19 PM EDT)
Todd Pocklington (01.29.2001 @ 3:02 PM EDT)
Senthil Nathan G (01.30.2001 @ 3:22 PM EDT)
Preeti Kelkar (01.30.2001 @ 8:16 PM EDT)
Colin Bown (01.31.2001 @ 3:26 PM EDT)
Ming Song (01.31.2001 @ 7:46 PM EDT)
Tomkgalv (01.31.2001 @ 10:29 PM EDT)
Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.