Difference between revisions of "Arrangement Restriction Theorem"

(Added problem and solution)
 
(5 intermediate revisions by 3 users not shown)
Line 1: Line 1:
The <b>Arrangement Restriction Theorem</b> is discovered by [[User:aops-g5-gethsemanea2|aops-g5-gethsemanea2]] and is NOT an alternative to the [[Georgeooga-Harryooga Theorem]] because in this theorem the only situation that is not allowed is that all <math>k</math> objects are together.
+
The <b>Arrangement Restriction Theorem</b> is discovered by [[User:aops-g5-gethsemanea2|aops-g5-gethsemanea2]] and is not an alternative to the [[Georgeooga-Harryooga Theorem]] because in this theorem the only situation that is not allowed is that all <math>k</math> objects are together.
  
 
==Definition==
 
==Definition==
Line 9: Line 9:
  
 
So, by complementary counting, we get <math>n! - (n - k + 1)!k!</math>.
 
So, by complementary counting, we get <math>n! - (n - k + 1)!k!</math>.
 +
 +
==Problem==
 +
Alice, Bob, Carl, David, Eric, Fred, George, and Harry want to stand in a line to buy ice cream. Fred and George are identical twins, so they are indistinguishable. Alice, Bob, and Carl <b>cannot be altogether</b> in the line.
 +
 +
With these conditions, how many different ways can you arrange these kids in a line?
 +
 +
 +
Problem by Math4Life2020, edited by aops-g5-gethsemanea2
 +
 +
===Solution===
 +
By the Arrangement Restriction Theorem, we get <math>\frac{8! - (8 - 3 + 1)!3!}{2} = \boxed{18000}</math> because Fred and George are indistinguishable.
 +
 +
Solution by aops-g5-gethsemanea2
 +
 +
==Testimonials==
 +
 +
I like this theorem, but not as much as the [[Georgeooga-Harryooga Theorem]] or the [[Wooga Looga Theorem]] ~ ilp
 +
 +
"Very nice theorem but not as impressive as the [[Georgeooga-Harryooga Theorem]]." - [[User:RedFireTruck|RedFireTruck]]

Latest revision as of 00:16, 21 December 2020

The Arrangement Restriction Theorem is discovered by aops-g5-gethsemanea2 and is not an alternative to the Georgeooga-Harryooga Theorem because in this theorem the only situation that is not allowed is that all $k$ objects are together.

Definition

If there are $n$ objects to be arranged and $k$ of them should not be beside each other altogether, then the number of ways to arrange them is $n! - (n - k + 1)!k!$.

Proof/Derivation

If there are no restrictions, then we have $n!$. But, if we put $k$ objects beside each other, we have $(n-k+1)!k!$ because we can count the $k$ objects as one object and just rearrange them.

So, by complementary counting, we get $n! - (n - k + 1)!k!$.

Problem

Alice, Bob, Carl, David, Eric, Fred, George, and Harry want to stand in a line to buy ice cream. Fred and George are identical twins, so they are indistinguishable. Alice, Bob, and Carl cannot be altogether in the line.

With these conditions, how many different ways can you arrange these kids in a line?


Problem by Math4Life2020, edited by aops-g5-gethsemanea2

Solution

By the Arrangement Restriction Theorem, we get $\frac{8! - (8 - 3 + 1)!3!}{2} = \boxed{18000}$ because Fred and George are indistinguishable.

Solution by aops-g5-gethsemanea2

Testimonials

I like this theorem, but not as much as the Georgeooga-Harryooga Theorem or the Wooga Looga Theorem ~ ilp

"Very nice theorem but not as impressive as the Georgeooga-Harryooga Theorem." - RedFireTruck