Switching bodies problem?

Discussion in 'Math' started by spinnaker, Apr 30, 2011.

  1. spinnaker

    Thread Starter AAC Fanatic!

    Oct 29, 2009
    4,866
    988
    One of my favorite cartoons is Futurama. I happen to think the animation is fantastic.

    There is an episode where the professor builds a machine that allows to people to switch bodies.

    After the first switch he discovers there is a problem with his design. The problem is that once 2 people switch with another's body, you can't switch back.

    So he figures he would just use a third body as a temporary holding container but quickly realizes that two people will be left in the wrong bodies.

    The problem gets further complicated by several people switching bodies for various reasons.

    The professor is dumbfounded, so he enlists the help of aliens who happen to be math wizs (the Harlem Globe Trotters). One of the Globe Trotters quickly develops an algorithm to switch everyone back in the right bodies.

    I say two people will always be left out no matter how many people are involved.

    Is is true or not? If not true, what is the minimum number of people needed to make the switch?
     
  2. Wendy

    Moderator

    Mar 24, 2008
    20,764
    2,534
    Actually Stargate had the exact same scenario in their later shows, then solved it.

    I don't see the problem myself.

    Body, personality 1a,2b,3c
    1a<>2b = 1b, 2a, 3c
    1b<>3c = 1c, 2a, 3b
    2a<>3b = 1c, 2b, 3a
    1c<>3a = 1a, 2b, 3c

    A full rotation between all the bodies.
     
  3. spinnaker

    Thread Starter AAC Fanatic!

    Oct 29, 2009
    4,866
    988
    Not sure I understand your notation here but with only 3 bodies someone has to lose out right?

    P = personality B = body <> = swap

    P1B1 <> P2B2 = P1B2 and P2B1
    P3B3 <> P2B1 = P3B1 and P2B3
    P1B2 <> P3B1 = P1B1 and P3B2 P1 is now in the right body
    P3B2 <> P2B3 = This can't be done because P3 and P2 were already swapped in step 2 but in different bodies.
     
  4. Georacer

    Moderator

    Nov 25, 2009
    5,142
    1,266
    So what's the problem? From what I understand it's the combination of body-soul you can't switch back, not just the souls.

    Once again, the definition of the problem is everything...
     
  5. spinnaker

    Thread Starter AAC Fanatic!

    Oct 29, 2009
    4,866
    988
    But can it be done with more people. The Globe Trotter on Futurama supposedly figured it out.
     
  6. Georacer

    Moderator

    Nov 25, 2009
    5,142
    1,266
    Bill did it and I agree with his way. As I said, the problem doesn't prohibit you from switching the same pair of souls twice, just the combination of bodies-souls pairs.
     
  7. spinnaker

    Thread Starter AAC Fanatic!

    Oct 29, 2009
    4,866
    988

    No he didn't.

    Not according to the rules in the cartoon. Two personalities (or souls) can't switch if they have switched once before.
     
  8. Wendy

    Moderator

    Mar 24, 2008
    20,764
    2,534
    I suspect you will have to add a 4th person into the mix.
     
  9. Georacer

    Moderator

    Nov 25, 2009
    5,142
    1,266
    Hm... I did it with four persons and still circular rotation doesn't cut it. When you hav "a" in the last body you have already switched it with all of the other souls, so no other switch with a is allowed. We should search elsewhere.
     
  10. BillO

    Well-Known Member

    Nov 24, 2008
    985
    136
    I think the problem here is that there are more accessible states than there are allowed state changes.

    We have 3 entities with 2 components per entity. The components are body and person. Lets represent BODY in upper case and personality in lower case. The accessible states become:

    .... S1 ........ S2 ....... S3 ......... S4 ....... S5 ........ S6 ...
    (ALAN,alan) (ALAN,barb) (ALAN,barb) (ALAN,alan) (ALAN,doug) (ALAN,doug)
    (BARB,barb) (BARB,alan) (BARB,doug) (BARB,doug) (BARB,alan) (BARB,barb)
    (DOUG,doug) (DOUG,doug) (DOUG,alan) (DOUG,barb) (DOUG,barb) (DOUG,alan)

    That gives us a system with 6 possible states (S=6).

    Now, since each body can only exchange once with another, we have only the following allowed state changes:

    .... C1 ........ C2 ........ C3 ...
    (ALANxBARB) (BARBxDOUG) (DOUGxALAN)

    For a total of 3 changes (C=3)

    We can see the progression C1 -> C3 will get us from S1 -> S4 without any way back.

    We can also see that to go from S4 to S5, we need the change (ALANxBARB) which we cannot use again. The same case for the changes required to go from S5 to S6 and S6 back to S1.

    We need to make 6 changes in total to get everyone back yet we can make only 3.

    Let's generalize.


    Where you a system have n unique entities each with r significant components the number of states S, is given by;

    S=(n+r-1)!/r!(n-1)!

    And if you are not allowed to repeat state changes, the number of changes C, is given by:

    C=n!/r!(n-r)!

    Doing the math, you will always be short on the sate changes required to cycle through all possible states.

    In this case, where n=3 and r=2, you will only have half the state changes you need.





     
    Last edited: May 1, 2011
Loading...