3
$\begingroup$

15 people will be seat in a row of 15 chairs. Two seating plan are considered the same if two plans share same adjacent quadruples. What is the maximum number of seating plans can be made? For example; if 15 people seated left to right in order 1,2,3,4,5,...15 then 12 quadruples:1234,2345,3456,...12131415 can't use in other plans.

$\endgroup$
  • $\begingroup$ What does it mean to 'share same adjacent quadruples'? $\endgroup$ – tylerc0816 Oct 16 '13 at 18:01
  • $\begingroup$ Adjacent quadruples sounds like a group of four people seated next to each other. Do the orders of the four have to match, or just the selection of four people? Do they have to be in the same seats? This will be a big mess in any case. $\endgroup$ – Ross Millikan Oct 16 '13 at 18:02
  • $\begingroup$ Clarification: Adjacent quadruples are orders of 4 people seated next to each other. For example; if 15 people seated left to right in order 1,2,3,4,5,...15 then 12 quadruples:1234,2345,3456,...12131415 can't use in other plans. $\endgroup$ – Jonathan Oct 16 '13 at 22:06
  • $\begingroup$ This should be an edit to the question. There is an edit button below your question to do that. Also please state whether a quadruple 3412 is prohibited. $\endgroup$ – Ross Millikan Oct 16 '13 at 22:11
1
$\begingroup$

You want to know the maximal number $N_\max$ of coexisting seating plans under the given condition. Such combinatorial extremal problems are notoriously hard. Read here about Ramsey numbers, the most famous combinatorial extremal problem of all.

In order to prove that in your example $N_\max=576$ (say) you have to perform two tasks: You have to come up with a list of 576 coexisting seating plans (maybe found with the help of a computer), or provide a non-constructive, so-called "probabilistic" proof that such a list exists; and on the other hand you have to prove that for some systematic or accidental reason more than 576 coexisting plans are impossible. The second is the more difficult task.

A "systematic" reason that $N_\max\leq2730$ is the following: There are $15\cdot14\cdot13\cdot 12$ ordered quadruples from $[15]$, and each plan consumes $12$ of them.

$\endgroup$
0
$\begingroup$

According to me, the answer would be:-
15!-$^{15}C$4 *12!, which is equal to:- 653837184000

$\endgroup$
  • 2
    $\begingroup$ It is much more complicated than this. For starters, your subtraction double counts cases where there are two matching quadruples. Matching quintuples are a problem as well. We also don't know if the quadruples have to match in order. $\endgroup$ – Ross Millikan Oct 16 '13 at 18:00

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.