6
$\begingroup$

During couples-group-therapy, where two therapist and multiple couples consisting of two people each are present and we all sit on chairs forming a circle in the middle of the room. We often discuss more than one sensitive topic during a single session. To mentally put some distance between what we just talked about and the next topic, the therapists insists for everyone present to switch places with each other until the following criteria are met before tackling a second topic:

1.) After moving, everyone must have at least one chair between his old and new spot. (You can not just move one chair to the right or left.)

2.) After moving, noone can sit next to a person they sat next to before switching places.

This process tends to take up quite some time, so i thought about it for a while and came up with an algorithm that worked every time for our group consisting of an even number of people, no matter how many additional couples would join therapy - until sadly, one couple got a divorce and stopped coming. At that point i started refusing to change chairs at all, since there was no point in even trying.

Question: How many couples were left in the therapy group?

Bonus Question: How did the algorithm work? (Multiple answers possible)

Super Bonus Question: If all of a sudden just one therapist is with the 2-person-couples (i.e. an uneven number of people), but we assume that at least two new couples joined therapy, how can i change my algorithm to work under the new conditions? (Multiple answers possible)

$\endgroup$
  • 1
    $\begingroup$ Are the chairs arranged in a single line? (Or a circle?) $\endgroup$ – Gareth McCaughan May 13 '18 at 21:03
  • $\begingroup$ sorry, i had a clear picture in my head of people sitting in a circle, but i did forget to add this. i edited the question accordingly. - sorry again, i hope this does not discourage you from trying again :) $\endgroup$ – Timme May 13 '18 at 22:03
3
$\begingroup$

Note: My original answer was written before Timme clarified that the chairs are in a circle, and it assumed they were in a straight line. I've left it there because why not?, and added a solution for the problem as actually intended.


Solution for chairs in a circle

When you gave up, the number of couples left was

two. (So, six people.)

Because

first of all, with six people you indeed can't do the thing. Suppose you start with six people 123456 (and then 1 to the right of 6 because the chairs are in a circle). Then the "at least two seats away" condition leaves just three places for any of our people to go to. Suppose one of them (let's say 1) goes to the middle one. Then we have ...1.. and the permitted locations for 2 are ...222. Only the rightmost of those is possible without putting 2 on top of, or next to, 1. So then we have ...1.2 and now there is no place to put 3.

And

if you have eight people or more, you can follow the algorithm I'm about to describe.

The algorithm (mine; may of course not be the same as yours)

is as follows. Number the people, let's say from 1. Move the people in odd-numbered places two spaces left, and the people in even-numbered places two spaces right. Obviously everyone moves by at least two spaces. What happens to previously-adjacent pairs? Ones like 12 (odd on the left) turn into 1....2; ones like 23 (even on the left) turn into 3..2; in neither case have they moved far enough to wrap around and be adjacent "on the other side" when we have as many as 8 people around the circle.


Solution for chairs in a straight line

When you gave up, the number of couples left was

one. (So, four people.)

Because

first of all, with four people you indeed can't do the thing (if you start with 1234 then the only place for 2 to go that's far enough away is at the right end; similarly for 3 at the left end; so you have 3xx2, and now 1 can't go in second place because it's too near where they used to be, nor in third place because it's next to 2)

and

if you have six or more you can follow the algorithm I'm about to describe.

The algorithm (mine; may of course not be the same as yours)

is as follows: number the places 1 upwards from the left. Now all the odd-numbered people move left and the even-numbered people move right until they're segregated, odd on the left, even on the right (maintaining the relative order within these groups). And now each group "rotates" one place, in opposite directions, so that the people who used to be at the ends are now in the middle. So 123456 becomes 135/246 and then 351/624; 12345678 becomes 1357/2468 and then 3571/8246; 123456789A becomes 13579/2468A and then 35791/A2468. It's not hard to see that this always works.

I haven't given any thought to the "Super Bonus Question".

$\endgroup$
  • $\begingroup$ that is actually the exact same algorithm i came up with :) $\endgroup$ – Timme May 14 '18 at 2:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.