Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The following question is from the "OECD Pisa questions"

[I found it via a link from the guardian newspaper].

It is Alan's birthday and he is having a party. 
Seven other people will attend: Amy, Brad, Beth, Charles, Debbie, 
Emily and Frances.

Everyone will sit around the circular dining table. 
The seating arrangement must meet the following conditions:

• Amy and Alan sit together

• Brad and Beth sit together

• Charles sits next to either Debbie or Emily

• Frances sits next to Debbie

• Amy and Alan do not sit next to either Brad or Beth

• Brad does not sit next to Charles or Frances

• Debbie and Emily do not sit next to each other

• Alan does not sit next to either Debbie or Emily

• Amy does not sit next to Charles

Arrange the guests around the table to meet all of the conditions listed above.

If I were to use each name as a variable name, and their seat number as the value of that variable (wrapping 8's to 1's - yes I realize there's still an issue around that); and arbitrarily assigning Alan = 1, we have:

  • Alan = 1
  • Amy = (2 or 7)
  • Brad = (Beth + 1) or (Beth - 1)
  • Charles = (Debbie + 1) or (Debbie - 1) or (Emily + 1) or (Emily-1)
  • ...and now we get into a bunch more or's and equations stating inequalities.

I'm not really sure if I could solve it this way...or whether this is even be a good way of looking at the problem. When I solved it by trial-and-error, I treated the pairs that had to sit together as one, and just swapped their positions whenever some inconsistency came up. I think I was basically just solving via brute force. Is there a better way?

I'm not really interested in the actual solution per se (I found a solution through trial and error in a few minutes), but an algebraic way of finding a solution to these types of problems in general. And by these types of problems, I guess I mean this class of word problems. Is this still just a bunch of linear equations when it involves inequalities and logical operators?

share|improve this question

3 Answers 3

One way to simplify the circular part is to seat (say) Amy and Alan, chop the table between them, and then unroll the table. So Alan sits in space 1 (say) and Amy in space 8.

You can do this because it doesn't matter where Alan sits, so you can pick space 1. It also doesn't matter whether Amy sits to his right or his left, so pick one of those.

Now you have hard boundary conditions for the other six, and it's clear who's sitting next to whom without needing to "wrap around the end of the table."

From here on, though, the "polarity" of each pair matters, since we've broken the symmetry of the problem. Whether Brad is to Beth's right or to her left matters now.

Now, Alan seems pretty picky. There are only two people left that he can sit next to: Charles or Frances. The breadth of the search is reduced considerably if you tackle this one next; you've eliminated a whole bunch of possibilities.

If Charles or Frances is in space 2, then Brad cannot be in space 3. Which means that Beth cannot be in space 4.

To sum up, look for the "long poles" in the tent to reduce your search space, and simplify out things by symmetry.

share|improve this answer
    
Yup. I'm really just looking for the "mathy" way of solving it. –  Gerrat Jan 3 at 20:32
    
I deleted that last sentence. I should stop selling my answers short like that. –  John Jan 3 at 20:47
    
This isn't really what I'm looking for, but you get a +1 for the neat trick in your first sentence. Nice. –  Gerrat Jan 3 at 21:01
    
I am curious to know how I may adapt similar concept to fit into an algorithm for dynamic seating in places like cafes where we merge and split tables... –  bonCodigo Jun 17 at 1:03

These problems are best solved with methods of discrete mathematics (combinations, permutations, etc). You see many of these type of questions in coding problems (projecteuler.net is a good example) where one is to write an efficient algorithm to solve the problem at hand. Dynamic programming is usually used to solve such problems.

share|improve this answer
    
This is a PISA problem, but a programming problem. –  copper.hat Jan 3 at 20:18
    
Did you mean "not a programming problem"? –  abden003 Jan 3 at 20:23
    
Yes, thanks, I meant 'not, not 'but'. –  copper.hat Jan 3 at 20:26
    
When these problems get complicated they can only be solved (in reasonable time) with computers. To solve these problems you need a well thought out algorithm involving a lot of math and cleverness (a naive algorithm would be exponential or n!, which would take too long even on a modern computer). The link between the computer and algorithm is programming. That is why I felt it was appropriate to mention it. –  abden003 Jan 3 at 20:35

Premises:

  1. Amy and Alan sit together
  2. Brad and Beth sit together
  3. Charles sits next to either Debbie or Emily
  4. Frances sits next to Debbie
  5. Amy and Alan do not sit next to either Brad or Beth
  6. Brad does not sit next to Charles or Frances
  7. Debbie and Emily do not sit next to each other
  8. Alan does not sit next to either Debbie or Emily
  9. Amy does not sit next to Charles

Additionally (implicitly), we have:

Alan != Amy != Brad != Charles != Frances != Emily != Beth != Debbie

Let's designate the seats 1-8, and seat Alan at 1.

We'll just start filling in seats that are consistent with the premises and backtrack when we hit an inconsistency:

Alan = 1 (arbitrary, so I assigned)
Amy = 8 (neat trick John mentioned)
    Try: Brad = 2...fail (#5)
    Try: Charles = 2: (next #3 says pick between Debbie and Emily):
        Try: Debbie = 3, Frances = 4 (from #4), 
            Try: Brad = 5...fail (#6)
            Try: Beth = 5, Brad = 6 (from #2), Emily = 7 (last seat)

...success!!!

Ok, much, much faster than I expected (I think this run just got lucky and didn't have to backtrack).

So we have Alan-Charles-Debbie-Frances-Beth-Brad-Emily-Amy (and back to Alan, in a circle). Double checking the original premises, this satisfies.

I like this method, as it is algorithmic (but I'd still prefer a (simple) method that solved a system of equations involving inequalities and booleans if such a thing existed).

share|improve this answer
    
Ok, I guess one way of categorizing this type of problem is a Constraint satisfaction problem, and backtracking is actually a half decent way to solve these! –  Gerrat Jan 3 at 22:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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