0
$\begingroup$

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?

$\endgroup$

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Yup. I'm really just looking for the "mathy" way of solving it. $\endgroup$
    – Gerrat
    Commented Jan 3, 2014 at 20:32
  • $\begingroup$ I deleted that last sentence. I should stop selling my answers short like that. $\endgroup$
    – John
    Commented Jan 3, 2014 at 20:47
  • $\begingroup$ This isn't really what I'm looking for, but you get a +1 for the neat trick in your first sentence. Nice. $\endgroup$
    – Gerrat
    Commented Jan 3, 2014 at 21:01
  • $\begingroup$ 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... $\endgroup$
    – bonCodigo
    Commented Jun 17, 2014 at 1:03
0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ This is a PISA problem, but a programming problem. $\endgroup$
    – copper.hat
    Commented Jan 3, 2014 at 20:18
  • $\begingroup$ Did you mean "not a programming problem"? $\endgroup$
    – abden003
    Commented Jan 3, 2014 at 20:23
  • $\begingroup$ Yes, thanks, I meant 'not, not 'but'. $\endgroup$
    – copper.hat
    Commented Jan 3, 2014 at 20:26
  • $\begingroup$ 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. $\endgroup$
    – abden003
    Commented Jan 3, 2014 at 20:35
0
$\begingroup$

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).

$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .