Comments on: FD. Space Walkers

By: gsw71

gsw71 — Mon, 20 Apr 2009 20:23:05 +0000

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.

By: strauss

strauss — Thu, 12 Mar 2009 17:59:56 +0000

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.

By: Michael_O

Michael_O — Thu, 12 Mar 2009 15:38:14 +0000

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!