The Math Factor Podcast

3 Comments »

1. Michael_O said,

   March 12, 2009 at 9:38 am

   I was working on the solution to this problem, and I can seem to get to 137 arrangements as stated in the podcast.  Here are the arrangments I have so far:

   (Notation:  astronauts A, B, C, and D; ship S; A > B means A is tethered to B)

   A > B > C > D > S  (24 variations)

   B > C > D > S; A > C  (12 variations)

   B > C > D > S; A > D  (24 variations)

   B > C > D > S; A > S  (24 variations)

   C > D > S; A > B > S  (12 variations)

   C > D > S; A > D; B > S  (12 variations)

   C > D > S; A > S; B > S  (12 variations)

   A > S; B > A; C > A; D > A  (4 variations)

   A > s; B > S; C > S; D > S  (1 variation)

   This adds up to a total of 125 variations; am I overlooking something?  Thanks!

2. strauss said,

   March 12, 2009 at 11:59 am

   Hi,
   I think you’re right; probably I overcounted one of the 12’s as a 24. (Of course this was so long ago I don’t remember where it went wrong!)

   I’ll make little pictures, so people can more easily see what we’re saying. Here are the nine possibilities you discuss, in the same order. We’re just showing the tethers.

    |    
    |    \/    |         |
    |     |      \/      |        | |     \/       |         \|/
    |     |       |       | |      | |      |  |     | | |      |      | | | |
   =================================
   24  12   24     24      12     12      12      4      1
   

   In each case the number is 24 — the number of ways to assign four objects into four roles — divided by some symmetries in the arrangement — the ways to interchange various roles. For example in the second-to-last arrangement, there are six ways to shuffle around the three tethers out the top.

3. gsw71 said,

   April 20, 2009 at 2:23 pm

   This problem can also be expressed in terms of graph theory. If you connect up 5 points (the 4 astronauts and the spaceship) using the smallest number of edges you have created what in graph theory is called a spanning tree. Cayley’s formula (named for Arthur Cayley :1821-1895) says there are  n^(n-2) different spanning trees for n points. So for our 5 points there would be 5^(5-2)=5^3=125 different possibilities (as calculated by permutations above). If spaceman Erp joined in there would be 6 points (A,B,C,D,E and the Spaceship) so there will be 6^4 = 1296. To prove this is quite tricky but google Cayley’s Formula for more info.  

RSS feed for comments on this post · TrackBack URL

Leave a Comment

You must be logged in to post a comment.

Podcast powered by podPress v8.8.10.17