Difference between revisions of "Georgeooga-Harryooga Theorem"
Redfiretruck (talk | contribs) |
Icematrix2 (talk | contribs) |
||
Line 1: | Line 1: | ||
=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. Note these are imaginary people who exist only in redfiretruck's mind. |
Line 28: | Line 28: | ||
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? | ||
− | |||
[https://artofproblemsolving.com/community/c4h2342517p18900597 Source] | [https://artofproblemsolving.com/community/c4h2342517p18900597 Source] | ||
===Solutions=== | ===Solutions=== | ||
====Solution 1==== | ====Solution 1==== | ||
− | 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 [[ | + | 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 [[Georgeogoa-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 by [[User:RedFireTruck|RedFireTruck]] | Solution by [[User:RedFireTruck|RedFireTruck]] | ||
− | |||
==Application 2== | ==Application 2== | ||
===Problem=== | ===Problem=== | ||
Line 111: | Line 108: | ||
~savannahsolver | ~savannahsolver | ||
− | |||
− | |||
− |
Revision as of 16:41, 20 November 2020
Contents
Definition
The Georgeooga-Harryooga Theorem states that if you have distinguishable objects and
are kept away from each other, then there are
ways to arrange the objects. Note these are imaginary people who exist only in redfiretruck's mind.
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 fundamental counting principal our answer is .
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?
Solutions
Solution 1
If Eric and Fred were distinguishable we would have ways to arrange them by the Georgeogoa-Harryooga Theorem. However, Eric and Fred are indistinguishable so we have to divide by
. Therefore, our answer is
.
Solution by RedFireTruck
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?
Solutions
Solution 1
By the Georgeooga-Harryooga Theorem there are way to arrange the marbles.
Solution by RedFireTruck
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
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
Back to the problem. By the Georgeooga-Harryooga Theorem, our answer is .
-franzliszt
Solution 7
~savannahsolver