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"

(Undo revision 140236 by Redfiretruck (talk))
(Tag: Undo)
Line 21: Line 21:
  
 
Proof by [[User:Redfiretruck|RedFireTruck]]
 
Proof by [[User:Redfiretruck|RedFireTruck]]
 +
 +
<h2>A side note by aryabhata000:</h2>
 +
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 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>.
 +
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:
 +
<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}).
 +
 +
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>.
 +
 +
Furthermore, after picking positions for the people, we have </math>(a-b)!<math> ways to order the </math>(a-b)<math> people who can be together, and </math>b!<math> ways to order the </math>b<math> people who cannot be together. So for each </math>(y_1, y_2, ... y_{b+1}<math>, we have </math>b! (a-b)!<math> orderings.
 +
 +
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>
 
<h1>Application</h1>
Line 31: Line 47:
 
<h2>Solution</h2>
 
<h2>Solution</h2>
  
−
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>.
+
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}$.
  
  

Revision as of 20:37, 22 December 2020

Overview

This is not a legit theorem

@Sugar rush Even though this is not a real theorem, it could be useful to use this, so I will bring parts of it back:

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.

Proof

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

A side note by aryabhata000:

This can also be done by stars and bars like so: 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$ b3 $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}\], where $(x_2, ... x_b) = (y_2, ..., y_b)$ and $(x_1, x_{b+1}) = (y_1 +1, y_{b+1}).

So, by stars and bars, the number of ways to determine$ (Error compiling LaTeX. Unknown error_msg)(y_2, ..., y_b) $is <cmath>F(a,b) = \dbinom{a-b+1}{b} = \frac {(a-b+1)!}{b!(a-2b+1)!}</cmath>.

Furthermore, after picking positions for the people, we have$ (Error compiling LaTeX. Unknown error_msg)(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 <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. With these conditions, how many different ways can you arrange these kids in a line?

Problem by Math4Life2020

<h2>Solution</h2>

If Eric and Fred were distinguishable we would have$ (Error compiling LaTeX. Unknown error_msg)\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

ALL THINGS ABOVE EXCEPT FOR THE OVERVIEW TAB AND THE PROBLEM IS MADE BY RedFireTruck

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