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"
m (Formatting)
 
(85 intermediate revisions by 21 users not shown)
Line 1: Line 1:
−
<h1>Overview</h1>
+
==Definition==
 +
The Georgeooga-Harryooga Theorem states that if you have <math>a</math> distinguishable objects and <math>b</math> objects 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 in a line. Note that you should not use this theorem in a solution if you do not want to get points off.
  
−
This is not a legit theorem
+
Created by George and Harry of [//www.youtube.com/channel/UC50E9TuLIMWbOPUX45xZPaQ The Ooga Booga Tribe of The Caveman Society]
  
−
<i>@Sugar rush</i> Even though this is not a real theorem, it could be useful to use this, so I will bring parts of it back:
+
==Proofs==
−
 
+
===Proof 1===
−
<h1>Definition</h1>
 
−
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.
 
−
 
 
−
<h1>Proof</h1>
 
 
Let our group of <math>a</math> objects be represented like so <math>1</math>, <math>2</math>, <math>3</math>, ..., <math>a-1</math>, <math>a</math>. Let the last <math>b</math> objects be the ones we can't have together.
 
Let our group of <math>a</math> objects be represented like so <math>1</math>, <math>2</math>, <math>3</math>, ..., <math>a-1</math>, <math>a</math>. Let the last <math>b</math> objects be the ones we can't have together.
  
Line 17: Line 14:
 
Now we have <math>a-b+1</math> blanks and <math>b</math> other objects so we have <math>_{a-b+1}P_{b}=\frac{(a-b+1)!}{(a-2b+1)!}</math> ways to arrange the objects we can't put together.
 
Now we have <math>a-b+1</math> blanks and <math>b</math> other objects so we have <math>_{a-b+1}P_{b}=\frac{(a-b+1)!}{(a-2b+1)!}</math> ways to arrange the objects we can't put together.
  
−
By fundamental counting principal our answer is <math>\frac{(a-b)!(a-b+1)!}{(a-2b+1)!}</math>.
+
By The Fundamental Counting Principle our answer is <math>\frac{(a-b)!(a-b+1)!}{(a-2b+1)!}</math>.
  
  
−
Proof by [[User:Redfiretruck|RedFireTruck]]
+
Proof by [[User:RedFireTruck|<font color="#FF0000">RedFireTruck</font>]] ([[User talk:RedFireTruck|<font color="#FF0000">talk</font>]])
  
−
<h1>A side note by aryabhata000:</h1>
+
===Proof 2===
−
This can also be done by stars and bars like so:
 
 
Let us call the <math>b</math> people <math>1, 2, ... b</math>
 
Let us call the <math>b</math> people <math>1, 2, ... b</math>
  
−
Let the number of people before <math>1</math> in line be <math>y_1</math>, between <math>1, 2</math> be <math>y_2</math>, ... after <math>b</math> b3 <math>y_{b+1}</math>.
+
Let the number of people before <math>1</math> in line be <math>y_1</math>, between <math>1, 2</math> be <math>y_2</math>, ... after <math>b</math> be <math>y_{b+1}</math>.
 
We have <cmath>y_1 + y_2 + y_3 + \dots y_{b+1} = a-b</cmath>
 
We have <cmath>y_1 + y_2 + y_3 + \dots y_{b+1} = a-b</cmath>
  
 
The number of ways to determine <math>y_1, y_2, \dots</math> is equivalent to the number of positive integer solutions to:
 
The number of ways to determine <math>y_1, y_2, \dots</math> is equivalent to the number of positive integer solutions to:
−
<cmath>x_1 + x_2 + .. + x_{b+1}</cmath> where <math>(x_2, ... x_b) = (y_2, ..., y_b) </math> and <math>(x_1, x_{b+1}) = (y_1 +1, y_{b+1})</math>.
+
<cmath>x_1 + x_2 + .. + x_{b+1} = a-b + 2</cmath> where <math>(x_2, ... x_b) = (y_2, ..., y_b) </math> and <math>(x_1, x_{b+1}) = (y_1 +1, y_{b+1} + 1)</math>.
  
 
So, by stars and bars, the number of ways to determine <math>(y_2, ..., y_b) </math> is <cmath>F(a,b) = \dbinom{a-b+1}{b} = \frac {(a-b+1)!}{b!(a-2b+1)!}</cmath>
 
So, by stars and bars, the number of ways to determine <math>(y_2, ..., y_b) </math> is <cmath>F(a,b) = \dbinom{a-b+1}{b} = \frac {(a-b+1)!}{b!(a-2b+1)!}</cmath>
Line 38: Line 34:
 
Therefore, the final answer is <cmath>b! (a-b)! F(a,b) = \frac{(a-b)!(a-b+1)!}{(a-2b+1)!}</cmath>
 
Therefore, the final answer is <cmath>b! (a-b)! F(a,b) = \frac{(a-b)!(a-b+1)!}{(a-2b+1)!}</cmath>
  
−
<h1>Application</h1>
 
  
−
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.
+
Proof by Aryabhata000
 +
 
 +
==Problems==
 +
===Problem 1===
 +
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?
 
With these conditions, how many different ways can you arrange these kids in a line?
  
−
Problem by Math4Life2020
+
Problem by [//artofproblemsolving.com/community/c4h2342517p18900597 Math4Life2020]
 +
 
 +
====Solution====
 +
If Fred and George were distinguishable we would have <math>\frac{(8-3)!(8-3+1)!}{(8-2\cdot3+1)!}=14400</math> ways to arrange them by the [[Georgeooga-Harryooga Theorem]]. However, Fred and George are indistinguishable so we have to divide by <math>2!=2</math>. Therefore, our answer is <math>\frac{14400}2=\boxed{7200}</math>.
 +
 
 +
 
 +
Solution by [[User:RedFireTruck|<font color="#FF0000">RedFireTruck</font>]] ([[User talk:RedFireTruck|<font color="#FF0000">talk</font>]])
 +
 
 +
===Problem 2===
 +
Zara has a collection of <math>4</math> 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?
 +
 
 +
<math>\textbf{(A) }6 \qquad \textbf{(B) }8 \qquad \textbf{(C) }12 \qquad \textbf{(D) }18 \qquad \textbf{(E) }24</math>
 +
 
 +
([[2020 AMC 8 Problems/Problem 10|Source]])
 +
 
 +
===Problem 3===
 +
The <math>7</math> members of The Ooga Booga Tribe, Lord Ooga Booga, Ooga, Booga, Foogle, Hoogle, George, and Harry, are about to perform a ritual. They have invited <math>2</math> priests, Agoob and Agoo, from a neighboring tribe. In this ritual they will line up in a row and sit down. The <math>2</math> priests must sit next to each other. Lord Ooga Booga, Ooga, and Booga just had a family argument so they must stay away from each other. In how many ways can The Ooga Booga Tribe perform their ritual?
  
−
<h2>Solution</h2>
+
Problem by [//artofproblemsolving.com/community/c3h2319596p19094529 RedFireTruck]
  
−
If Eric and Fred were distinguishable we would have <math>\frac{(8-3)!(8-3+1)!}{(8-2\cdot3+1)!}=14400</math> ways to arrange them by the Georgeooga-Harryooga Theorem. However, Eric and Fred are indistinguishable so we have to divide by <math>2!=2</math>. Therefore, our answer is <math>\frac{14400}2=\boxed{7200}</math>.
+
====Solution====
 +
Let Agoob and Agoo be one object called Agooboo. Then, by the [[Georgeooga-Harryooga Theorem]] there are <math>\frac{(8-3)!(8-3+1)!}{(8-2\cdot3+1)!}=14400</math> ways to arrange the <math>7</math> members and Agooboo. However, there are <math>2</math> ways to "split" Agooboo. So, by the Fundamental Counting Principle, our answer is <math>14400\cdot2=\boxed{28800}</math>.
  
  
−
Solution by [[User:Redfiretruck|RedFireTruck]]
+
Solution by [[User:RedFireTruck|<font color="#FF0000">RedFireTruck</font>]] ([[User talk:RedFireTruck|<font color="#FF0000">talk</font>]])
−
<hr>
 
−
<strong>ALL THINGS ABOVE EXCEPT FOR THE OVERVIEW TAB AND THE PROBLEM IS MADE BY RedFireTruck </strong>
 

Latest revision as of 18:04, 15 January 2025

Definition

The Georgeooga-Harryooga Theorem states that if you have $a$ distinguishable objects and $b$ objects are kept away from each other, then there are $\frac{(a-b)!(a-b+1)!}{(a-2b+1)!}$ ways to arrange the objects in a line. Note that you should not use this theorem in a solution if you do not want to get points off.

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 The Fundamental Counting Principle our answer is $\frac{(a-b)!(a-b+1)!}{(a-2b+1)!}$.


Proof by RedFireTruck (talk)

Proof 2

Let us call the $b$ people $1, 2, ... b$

Let the number of people before $1$ in line be $y_1$, between $1, 2$ be $y_2$, ... after $b$ be $y_{b+1}$. We have \[y_1 + y_2 + y_3 + \dots y_{b+1} = a-b\]

The number of ways to determine $y_1, y_2, \dots$ is equivalent to the number of positive integer solutions to: \[x_1 + x_2 + .. + x_{b+1} = a-b + 2\] where $(x_2, ... x_b) = (y_2, ..., y_b)$ and $(x_1, x_{b+1}) = (y_1 +1, y_{b+1} + 1)$.

So, by stars and bars, the number of ways to determine $(y_2, ..., y_b)$ is \[F(a,b) = \dbinom{a-b+1}{b} = \frac {(a-b+1)!}{b!(a-2b+1)!}\]

Furthermore, after picking positions for the people, we have $(a-b)!$ ways to order the $(a-b)$ people who can be together, and $b!$ ways to order the $b$ people who cannot be together. So for each $(y_1, y_2, ... y_{b+1}$, we have $b! (a-b)!$ orderings.

Therefore, the final answer is \[b! (a-b)! F(a,b) = \frac{(a-b)!(a-b+1)!}{(a-2b+1)!}\]


Proof by Aryabhata000

Problems

Problem 1

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?

Problem by Math4Life2020

Solution

If Fred and George 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, Fred and George are indistinguishable so we have to divide by $2!=2$. Therefore, our answer is $\frac{14400}2=\boxed{7200}$.


Solution by RedFireTruck (talk)

Problem 2

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)

Problem 3

The $7$ members of The Ooga Booga Tribe, Lord Ooga Booga, Ooga, Booga, Foogle, Hoogle, George, and Harry, are about to perform a ritual. They have invited $2$ priests, Agoob and Agoo, from a neighboring tribe. In this ritual they will line up in a row and sit down. The $2$ priests must sit next to each other. Lord Ooga Booga, Ooga, and Booga just had a family argument so they must stay away from each other. In how many ways can The Ooga Booga Tribe perform their ritual?

Problem by RedFireTruck

Solution

Let Agoob and Agoo be one object called Agooboo. Then, by the Georgeooga-Harryooga Theorem there are $\frac{(8-3)!(8-3+1)!}{(8-2\cdot3+1)!}=14400$ ways to arrange the $7$ members and Agooboo. However, there are $2$ ways to "split" Agooboo. So, by the Fundamental Counting Principle, our answer is $14400\cdot2=\boxed{28800}$.


Solution by RedFireTruck (talk)

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