Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Georgeooga-Harryooga Theorem"
Line 1: Line 1:
−
=Icematrix Please Stop=
 
 
=Definition=
 
=Definition=
 
The Georgeooga-Harryooga Theorem states that if you have <math>a</math> distinguishable objects and <math>b</math> are kept away from each other, then there are <math>\frac{(a-b)!(a-b+1)!}{(a-2b+1)!}</math> ways to arrange the objects.
 
The Georgeooga-Harryooga Theorem states that if you have <math>a</math> distinguishable objects and <math>b</math> are kept away from each other, then there are <math>\frac{(a-b)!(a-b+1)!}{(a-2b+1)!}</math> ways to arrange the objects.

Revision as of 11:38, 21 November 2020

Definition

The Georgeooga-Harryooga Theorem states that if you have $a$ distinguishable objects and $b$ are kept away from each other, then there are $\frac{(a-b)!(a-b+1)!}{(a-2b+1)!}$ ways to arrange the objects.


Created by George and Harry of The Ooga Booga Tribe of The Caveman Society

Proofs

Proof 1

Let our group of $a$ objects be represented like so $1$, $2$, $3$, ..., $a-1$, $a$. Let the last $b$ objects be the ones we can't have together.

Then we can organize our objects like so $\square1\square2\square3\square...\square a-b-1\square a-b\square$.

We have $(a-b)!$ ways to arrange the objects in that list.

Now we have $a-b+1$ blanks and $b$ other objects so we have $_{a-b+1}P_{b}=\frac{(a-b+1)!}{(a-2b+1)!}$ ways to arrange the objects we can't put together.

By fundamental counting principal our answer is $\frac{(a-b)!(a-b+1)!}{(a-2b+1)!}$.


Proof by RedFireTruck

Applications

Application 1

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 had a serious disagreement in 6th grade, so none of them can be together in the line.

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


Source

Solutions

Solution 1

If Eric and Fred were distinguishable we would have $\frac{(8-3)!(8-3+1)!}{(8-2\cdot3+1)!}=14400$ ways to arrange them by the Georgeooga-Harryooga Theorem. However, Eric and Fred are indistinguishable so we have to divide by $2!=2$. Therefore, our answer is $\frac{14400}2=\boxed{7200}$.


Solution by RedFireTruck

Application 2

Problem

Zara has a collection of $4$ marbles: an Aggie, a Bumblebee, a Steelie, and a Tiger. She wants to display them in a row on a shelf, but does not want to put the Steelie and the Tiger next to one another. In how many ways can she do this?

$\textbf{(A) }6 \qquad \textbf{(B) }8 \qquad \textbf{(C) }12 \qquad \textbf{(D) }18 \qquad \textbf{(E) }24$


Source

Solutions

Solution 1

By the Georgeooga-Harryooga Theorem there are $\frac{(4-2)!(4-2+1)!}{(4-2\cdot2+1)!}=\boxed{\textbf{(C) }12}$ way to arrange the marbles.


Solution by RedFireTruck

Solution 2

We can arrange our marbles like so $\square A\square B\square$.

To arrange the $A$ and $B$ we have $2!=2$ ways.

To place the $S$ and $T$ in the blanks we have $_3P_2=6$ ways.

By fundamental counting principle our final answer is $2\cdot6=\boxed{\textbf{(C) }12}$


Solution by RedFireTruck

Solution 3

Let the Aggie, Bumblebee, Steelie, and Tiger, be referred to by $A,B,S,$ and $T$, respectively. If we ignore the constraint that $S$ and $T$ cannot be next to each other, we get a total of $4!=24$ ways to arrange the 4 marbles. We now simply have to subtract out the number of ways that $S$ and $T$ can be next to each other. If we place $S$ and $T$ next to each other in that order, then there are three places that we can place them, namely in the first two slots, in the second two slots, or in the last two slots (i.e. $ST\square\square, \square ST\square, \square\square ST$). However, we could also have placed $S$ and $T$ in the opposite order (i.e. $TS\square\square, \square TS\square, \square\square TS$). Thus there are 6 ways of placing $S$ and $T$ directly next to each other. Next, notice that for each of these placements, we have two open slots for placing $A$ and $B$. Specifically, we can place $A$ in the first open slot and $B$ in the second open slot or switch their order and place $B$ in the first open slot and $A$ in the second open slot. This gives us a total of $6\times 2=12$ ways to place $S$ and $T$ next to each other. Subtracting this from the total number of arrangements gives us $24-12=12$ total arrangements $\implies\boxed{\textbf{(C) }12}$.

We can also solve this problem directly by looking at the number of ways that we can place $S$ and $T$ such that they are not directly next to each other. Observe that there are three ways to place $S$ and $T$ (in that order) into the four slots so they are not next to each other (i.e. $S\square T\square, \square S\square T, S\square\square T$). However, we could also have placed $S$ and $T$ in the opposite order (i.e. $T\square S\square, \square T\square S, T\square\square S$). Thus there are 6 ways of placing $S$ and $T$ so that they are not next to each other. Next, notice that for each of these placements, we have two open slots for placing $A$ and $B$. Specifically, we can place $A$ in the first open slot and $B$ in the second open slot or switch their order and place $B$ in the first open slot and $A$ in the second open slot. This gives us a total of $6\times 2=12$ ways to place $S$ and $T$ such that they are not next to each other $\implies\boxed{\textbf{(C) }12}$.
~junaidmansuri

Solution 4

Let's try complementary counting. There $4!$ ways to arrange the 4 marbles. However, there are $2\cdot3!$ arrangements where Steelie and Tiger are next to each other. (Think about permutations of the element ST, A, and B or TS, A, and B). Thus, \[4!-2\cdot3!=\boxed{12 \textbf{(C)}}\]

Solution 5

We use complementary counting: we will count the numbers of ways where Steelie and Tiger are together and subtract that from the total count. Treat the Steelie and the Tiger as a "super marble." There are $2!$ ways to arrange Steelie and Tiger within this "super marble." Then there are $3!$ ways to arrange the "super marble" and Zara's two other marbles in a row. Since there are $4!$ ways to arrange the marbles without any restrictions, the answer is given by $4!-2!\cdot 3!=\textbf{(C) }12$

-franzliszt

Solution 6

We will use the following

$\textbf{Georgeooga-Harryooga Theorem:}$ The Georgeooga-Harryooga Theorem states that if you have $a$ distinguishable objects and $b$ of them cannot be together, then there are $\frac{(a-b)!(a-b+1)!}{b!}$ ways to arrange the objects.

$\textit{Proof. (Created by AoPS user RedFireTruck)}$

Let our group of $a$ objects be represented like so $1$, $2$, $3$, ..., $a-1$, $a$. Let the last $b$ objects be the ones we can't have together.

Then we can organize our objects like so $\square1\square2\square3\square...\square a-b-1\square a-b\square$.

We have $(a-b)!$ ways to arrange the objects in that list.

Now we have $a-b+1$ blanks and $b$ other objects so we have $_{a-b+1}P_{b}=\frac{(a-b+1)!}{(a-2b+1)!}$ ways to arrange the objects we can't put together.

By fundamental counting principal our answer is $\frac{(a-b)!(a-b+1)!}{(a-2b+1)!}$.


Proof by RedFireTruck


Back to the problem. By the Georgeooga-Harryooga Theorem, our answer is $\frac{(4-2)!(4-2+1)!}{(4-2\cdot2+1)!}=\textbf{(C) }12$.

-franzliszt

Solution 7

https://youtu.be/pB46JzBNM6g

~savannahsolver

Testimonials

"Thanks for rediscovering our theorem RedFireTruck" - George and Harry of The Ooga Booga Tribe of The Caveman Society

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Georgeooga-Harryooga_Theorem&oldid=138075"