Difference between revisions of "Georgeooga-Harryooga Theorem"
Sugar rush (talk | contribs) |
m (→Testimonials) |
||
(106 intermediate revisions by 21 users not shown) | |||
Line 1: | Line 1: | ||
− | + | *Restored by Judgefan99* | |
− | + | =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. | ||
− | |||
− | < | + | Created by George and Harry of [https://www.youtube.com/channel/UC50E9TuLIMWbOPUX45xZPaQ The Ooga Booga Tribe of The Caveman Society] |
− | The Georgeooga-Harryooga Theorem states that if you have <math>a</math> distinguishable objects and <math>b</math> | + | |
+ | =Proofs= | ||
+ | ==Proof 1== | ||
+ | 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. | ||
+ | |||
+ | Then we can organize our objects like so <math>\square1\square2\square3\square...\square a-b-1\square a-b\square</math>. | ||
+ | |||
+ | We have <math>(a-b)!</math> ways to arrange the objects in that list. | ||
+ | |||
+ | 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 The Fundamental Counting Principle our answer is <math>\frac{(a-b)!(a-b+1)!}{(a-2b+1)!}</math>. | ||
+ | |||
+ | |||
+ | Proof by [[User:RedFireTruck|<font color="#FF0000">RedFireTruck</font>]] ([[User talk:RedFireTruck|<font color="#FF0000">talk</font>]]) 12:07, 1 February 2021 (EST) | ||
+ | |||
+ | ==Proof 2== | ||
+ | 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> be <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} = 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> | ||
+ | |||
+ | 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> | ||
+ | |||
+ | |||
+ | Proof by Aryabhata000 | ||
+ | |||
+ | =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? | ||
+ | |||
+ | |||
+ | Problem by [https://artofproblemsolving.com/community/c4h2342517p18900597 Math4Life2020] | ||
+ | |||
+ | ===Solutions=== | ||
+ | ====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>]]) 12:07, 1 February 2021 (EST) | ||
+ | |||
+ | ==Application 2== | ||
+ | ===Problem=== | ||
+ | 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> | ||
+ | |||
+ | |||
+ | Problem by [[2020 AMC 8 Problems/Problem 10|The Mathematical Association of America's American Mathematics Competitions]] | ||
+ | |||
+ | ===Solutions=== | ||
+ | ====Solution 1==== | ||
+ | By the [[Georgeooga-Harryooga Theorem]] there are <math>\frac{(4-2)!(4-2+1)!}{(4-2\cdot2+1)!}=\boxed{\textbf{(C) }12}</math> way to arrange the marbles. | ||
+ | |||
+ | |||
+ | Solution by [[User:RedFireTruck|<font color="#FF0000">RedFireTruck</font>]] ([[User talk:RedFireTruck|<font color="#FF0000">talk</font>]]) 12:07, 1 February 2021 (EST) | ||
+ | |||
+ | ====Solution 2==== | ||
+ | We can arrange our marbles like so <math>\square A\square B\square</math>. | ||
+ | |||
+ | To arrange the <math>A</math> and <math>B</math> we have <math>2!=2</math> ways. | ||
+ | |||
+ | To place the <math>S</math> and <math>T</math> in the blanks we have <math>_3P_2=6</math> ways. | ||
+ | |||
+ | By fundamental counting principle our final answer is <math>2\cdot6=\boxed{\textbf{(C) }12}</math> | ||
+ | |||
+ | |||
+ | Solution by [[User:RedFireTruck|<font color="#FF0000">RedFireTruck</font>]] ([[User talk:RedFireTruck|<font color="#FF0000">talk</font>]]) 12:07, 1 February 2021 (EST) | ||
+ | |||
+ | ====Solution 3==== | ||
+ | Let the Aggie, Bumblebee, Steelie, and Tiger, be referred to by <math>A,B,S,</math> and <math>T</math>, respectively. If we ignore the constraint that <math>S</math> and <math>T</math> cannot be next to each other, we get a total of <math>4!=24</math> ways to arrange the 4 marbles. We now simply have to subtract out the number of ways that <math>S</math> and <math>T</math> can be next to each other. If we place <math>S</math> and <math>T</math> 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. <math>ST\square\square, \square ST\square, \square\square ST</math>). However, we could also have placed <math>S</math> and <math>T</math> in the opposite order (i.e. <math>TS\square\square, \square TS\square, \square\square TS</math>). Thus there are 6 ways of placing <math>S</math> and <math>T</math> directly next to each other. Next, notice that for each of these placements, we have two open slots for placing <math>A</math> and <math>B</math>. Specifically, we can place <math>A</math> in the first open slot and <math>B</math> in the second open slot or switch their order and place <math>B</math> in the first open slot and <math>A</math> in the second open slot. This gives us a total of <math>6\times 2=12</math> ways to place <math>S</math> and <math>T</math> next to each other. Subtracting this from the total number of arrangements gives us <math>24-12=12</math> total arrangements <math>\implies\boxed{\textbf{(C) }12}</math>.<br> | ||
+ | |||
+ | We can also solve this problem directly by looking at the number of ways that we can place <math>S</math> and <math>T</math> such that they are not directly next to each other. Observe that there are three ways to place <math>S</math> and <math>T</math> (in that order) into the four slots so they are not next to each other (i.e. <math>S\square T\square, \square S\square T, S\square\square T</math>). However, we could also have placed <math>S</math> and <math>T</math> in the opposite order (i.e. <math>T\square S\square, \square T\square S, T\square\square S</math>). Thus there are 6 ways of placing <math>S</math> and <math>T</math> so that they are not next to each other. Next, notice that for each of these placements, we have two open slots for placing <math>A</math> and <math>B</math>. Specifically, we can place <math>A</math> in the first open slot and <math>B</math> in the second open slot or switch their order and place <math>B</math> in the first open slot and <math>A</math> in the second open slot. This gives us a total of <math>6\times 2=12</math> ways to place <math>S</math> and <math>T</math> such that they are not next to each other <math>\implies\boxed{\textbf{(C) }12}</math>.<br> | ||
+ | ~[http://artofproblemsolving.com/community/user/jmansuri junaidmansuri] | ||
+ | |||
+ | ====Solution 4==== | ||
+ | Let's try complementary counting. There <math>4!</math> ways to arrange the 4 marbles. However, there are <math>2\cdot3!</math> 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, <cmath>4!-2\cdot3!=\boxed{\textbf{(C)}~12}</cmath> | ||
+ | |||
+ | ====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 <math>2!</math> ways to arrange Steelie and Tiger within this "super marble." Then there are <math>3!</math> ways to arrange the "super marble" and Zara's two other marbles in a row. Since there are <math>4!</math> ways to arrange the marbles without any restrictions, the answer is given by <math>4!-2!\cdot 3!=\boxed{\textbf{(C)}~12}</math> | ||
+ | |||
+ | -franzliszt | ||
+ | |||
+ | ====Solution 6==== | ||
+ | |||
+ | We will use the following | ||
+ | |||
+ | <math>\textbf{Georgeooga-Harryooga Theorem:}</math> The [[Georgeooga-Harryooga Theorem]] states that if you have <math>a</math> distinguishable objects and <math>b</math> of them cannot be together, then there are <math>\frac{(a-b)!(a-b+1)!}{(a-2b+1)!}</math> ways to arrange the objects. | ||
+ | |||
+ | <math>\textit{Proof. (Created by AoPS user RedFireTruck)}</math> | ||
− | |||
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 20: | Line 121: | ||
− | Proof by [[User:Redfiretruck|RedFireTruck]] | + | Proof by [[User:RedFireTruck|<font color="#FF0000">RedFireTruck</font>]] ([[User talk:RedFireTruck|<font color="#FF0000">talk</font>]]) 12:07, 1 February 2021 (EST) |
+ | |||
+ | |||
+ | Back to the problem. By the [[Georgeooga-Harryooga Theorem]], our answer is <math>\frac{(4-2)!(4-2+1)!}{(4-2\cdot2+1)!}=\boxed{\textbf{(C)}~12}</math>. | ||
+ | |||
+ | -franzliszt | ||
+ | |||
+ | ====Solution 7==== | ||
+ | https://youtu.be/pB46JzBNM6g | ||
+ | |||
+ | ~savannahsolver | ||
+ | |||
+ | ==Application 3== | ||
+ | ===Problem=== | ||
+ | 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? | ||
+ | |||
+ | |||
+ | Problem by [https://artofproblemsolving.com/community/c3h2319596p19094529 RedFireTruck] | ||
+ | |||
+ | ===Solutions=== | ||
+ | ====Solution 1==== | ||
+ | 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|<font color="#FF0000">RedFireTruck</font>]] ([[User talk:RedFireTruck|<font color="#FF0000">talk</font>]]) 12:07, 1 February 2021 (EST) | ||
+ | |||
+ | =Testimonials= | ||
+ | "Thanks for rediscovering our theorem [[User:Redfiretruck|RedFireTruck]]" - George and Harry of [https://www.youtube.com/channel/UC50E9TuLIMWbOPUX45xZPaQ The Ooga Booga Tribe of The Caveman Society] | ||
+ | |||
+ | "Wow! George and Harry are alive???" ~ samrocksnature | ||
+ | |||
+ | "Hi" ~ jasperE3 | ||
− | < | + | "I used this theorem on the AMC 8 and got a 25. Very useful!" - [[User:RedFireTruck|<font color="#FF0000">RedFireTruck</font>]] ([[User talk:RedFireTruck|<font color="#FF0000">talk</font>]]) 11:01, 1 February 2021 (EST) |
− | + | "This is very complicated, but great." - Jiseop55406 | |
− | + | ||
+ | I used this theorem on the AMC 8 too! ~ ilp | ||
+ | |||
+ | "Very nice theorem" ~ IdkHowToAddNumbers | ||
+ | |||
+ | "This theorem is really worth of being used in the AMC 8! Very useful!" ~ [[User:Aops-g5-gethsemanea2|Aops-g5-gethsemanea2]] ([[User talk:Aops-g5-gethsemanea2|talk]]) 20:48, 21 December 2020 (EST) | ||
+ | |||
+ | "I have realized the way" ~ hi.. | ||
+ | |||
+ | "This theorem even works on AMC10 and 12" - TryhardMathlete | ||
+ | |||
+ | "This is very cool"~Physicsisfun123 | ||
+ | |||
+ | "Or you could just use a formular version of complementary counting: a!-b!*(a-b+1)!" ~tigeryun | ||
− | + | "Interesting!" ~justin6688 | |
− | + | I used this on AMC 8 problem 10 and I got it right! THANK YOU! -Onafets {Satire} | |
− | + | "This is useful on the IMO" ~ Taco12 | |
+ | “Ooga booga giv me my meat” -peelybonehead | ||
− | + | "This theorem is incredible, but the name could use some work..." ~ cxsmi | |
− | |||
− |
Latest revision as of 19:12, 8 January 2024
- Restored by Judgefan99*
Contents
Definition
The Georgeooga-Harryooga Theorem states that if you have distinguishable objects and
objects are kept away from each other, then there are
ways to arrange the objects in a line.
Created by George and Harry of The Ooga Booga Tribe of The Caveman Society
Proofs
Proof 1
Let our group of objects be represented like so
,
,
, ...,
,
. Let the last
objects be the ones we can't have together.
Then we can organize our objects like so .
We have ways to arrange the objects in that list.
Now we have blanks and
other objects so we have
ways to arrange the objects we can't put together.
By The Fundamental Counting Principle our answer is .
Proof by RedFireTruck (talk) 12:07, 1 February 2021 (EST)
Proof 2
Let us call the people
Let the number of people before in line be
, between
be
, ... after
be
.
We have
The number of ways to determine is equivalent to the number of positive integer solutions to:
where
and
.
So, by stars and bars, the number of ways to determine is
Furthermore, after picking positions for the people, we have ways to order the
people who can be together, and
ways to order the
people who cannot be together. So for each
, we have
orderings.
Therefore, the final answer is
Proof by Aryabhata000
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?
Problem by Math4Life2020
Solutions
Solution
If Fred and George were distinguishable we would have ways to arrange them by the Georgeooga-Harryooga Theorem. However, Fred and George are indistinguishable so we have to divide by
. Therefore, our answer is
.
Solution by RedFireTruck (talk) 12:07, 1 February 2021 (EST)
Application 2
Problem
Zara has a collection of 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?
Problem by The Mathematical Association of America's American Mathematics Competitions
Solutions
Solution 1
By the Georgeooga-Harryooga Theorem there are way to arrange the marbles.
Solution by RedFireTruck (talk) 12:07, 1 February 2021 (EST)
Solution 2
We can arrange our marbles like so .
To arrange the and
we have
ways.
To place the and
in the blanks we have
ways.
By fundamental counting principle our final answer is
Solution by RedFireTruck (talk) 12:07, 1 February 2021 (EST)
Solution 3
Let the Aggie, Bumblebee, Steelie, and Tiger, be referred to by and
, respectively. If we ignore the constraint that
and
cannot be next to each other, we get a total of
ways to arrange the 4 marbles. We now simply have to subtract out the number of ways that
and
can be next to each other. If we place
and
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.
). However, we could also have placed
and
in the opposite order (i.e.
). Thus there are 6 ways of placing
and
directly next to each other. Next, notice that for each of these placements, we have two open slots for placing
and
. Specifically, we can place
in the first open slot and
in the second open slot or switch their order and place
in the first open slot and
in the second open slot. This gives us a total of
ways to place
and
next to each other. Subtracting this from the total number of arrangements gives us
total arrangements
.
We can also solve this problem directly by looking at the number of ways that we can place and
such that they are not directly next to each other. Observe that there are three ways to place
and
(in that order) into the four slots so they are not next to each other (i.e.
). However, we could also have placed
and
in the opposite order (i.e.
). Thus there are 6 ways of placing
and
so that they are not next to each other. Next, notice that for each of these placements, we have two open slots for placing
and
. Specifically, we can place
in the first open slot and
in the second open slot or switch their order and place
in the first open slot and
in the second open slot. This gives us a total of
ways to place
and
such that they are not next to each other
.
~junaidmansuri
Solution 4
Let's try complementary counting. There ways to arrange the 4 marbles. However, there are
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,
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 ways to arrange Steelie and Tiger within this "super marble." Then there are
ways to arrange the "super marble" and Zara's two other marbles in a row. Since there are
ways to arrange the marbles without any restrictions, the answer is given by
-franzliszt
Solution 6
We will use the following
The Georgeooga-Harryooga Theorem states that if you have
distinguishable objects and
of them cannot be together, then there are
ways to arrange the objects.
Let our group of objects be represented like so
,
,
, ...,
,
. Let the last
objects be the ones we can't have together.
Then we can organize our objects like so .
We have ways to arrange the objects in that list.
Now we have blanks and
other objects so we have
ways to arrange the objects we can't put together.
By fundamental counting principal our answer is .
Proof by RedFireTruck (talk) 12:07, 1 February 2021 (EST)
Back to the problem. By the Georgeooga-Harryooga Theorem, our answer is .
-franzliszt
Solution 7
~savannahsolver
Application 3
Problem
The 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
priests, Agoob and Agoo, from a neighboring tribe. In this ritual they will line up in a row and sit down. The
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
Solutions
Solution 1
Let Agoob and Agoo be one object called Agooboo. Then, by the Georgeooga-Harryooga Theorem there are ways to arrange the
members and Agooboo. However, there are
ways to "split" Agooboo. So, by the Fundamental Counting Principle, our answer is
.
Solution by RedFireTruck (talk) 12:07, 1 February 2021 (EST)
Testimonials
"Thanks for rediscovering our theorem RedFireTruck" - George and Harry of The Ooga Booga Tribe of The Caveman Society
"Wow! George and Harry are alive???" ~ samrocksnature
"Hi" ~ jasperE3
"I used this theorem on the AMC 8 and got a 25. Very useful!" - RedFireTruck (talk) 11:01, 1 February 2021 (EST)
"This is very complicated, but great." - Jiseop55406
I used this theorem on the AMC 8 too! ~ ilp
"Very nice theorem" ~ IdkHowToAddNumbers
"This theorem is really worth of being used in the AMC 8! Very useful!" ~ Aops-g5-gethsemanea2 (talk) 20:48, 21 December 2020 (EST)
"I have realized the way" ~ hi..
"This theorem even works on AMC10 and 12" - TryhardMathlete
"This is very cool"~Physicsisfun123
"Or you could just use a formular version of complementary counting: a!-b!*(a-b+1)!" ~tigeryun
"Interesting!" ~justin6688
I used this on AMC 8 problem 10 and I got it right! THANK YOU! -Onafets {Satire}
"This is useful on the IMO" ~ Taco12
“Ooga booga giv me my meat” -peelybonehead
"This theorem is incredible, but the name could use some work..." ~ cxsmi