https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Patopato&feedformat=atomAoPS Wiki - User contributions [en]2022-10-06T17:39:27ZUser contributionsMediaWiki 1.31.1https://artofproblemsolving.com/wiki/index.php?title=Principle_of_Inclusion-Exclusion&diff=119043Principle of Inclusion-Exclusion2020-03-11T01:33:41Z<p>Patopato: /* Three Set Examples */</p>
<hr />
<div>The '''Principle of Inclusion-Exclusion''' (abbreviated PIE) provides an organized method/formula to find the number of [[element]]s in the [[union]] of a given group of [[set]]s, the size of each set, and the size of all possible [[intersection]]s among the sets.<br />
<br />
==Important Note(!)==<br />
An important note when using PIE is to understand how to strategically overcount and undercount, in the end making sure every element is counted once and only once. In particular, memorizing a formula for PIE is a bad idea for problem solving.<br />
<br />
== Application ==<br />
Here we will illustrate how PIE is applied with various numbers of sets.<br />
<br />
=== Two Set Example ===<br />
Assume we are given the sizes of two sets, <math>|A_1|</math> and <math>|A_2|</math>, and the size of their intersection, <math>|A_1\cap A_2|</math>. We wish to find the size of their union, <math>|A_1\cup A_2|</math>.<br />
<br />
To find the union, we can add <math>|A_1|</math> and <math>|A_2|</math>. In doing so, we know we have counted everything in <math>|A_1\cup A_2|</math> at least once. However, some things were counted twice. The elements that were counted twice are precisely those in <math> {}A_1\cap A_2 </math>. Thus, we have that:<br />
<br />
<center><math> |A_1 \cup A_2| = |A_1| + |A_2| - |A_1\cap A_2|</math>.</center><br />
<br />
=== Three Set Examples ===<br />
Assume we are given the sizes of three sets, <math>|A_1|, |A_2|,{}</math> and <math>|A_3|</math>, the size of their pairwise intersections, <math>|A_1\cap A_2|, |A_2\cap A_3|</math>, and <math>|A_3\cap A_1|</math>, and the size their overall intersection, <math>|A_1\cap A_2\cap A_3|</math>. We wish to find the size of their union, <math>|A_1\cup A_2\cup A_3|</math>.<br />
<br />
Just like in the Two Set Examples, we start with the sum of the sizes of the individual sets <math>|A_1|+|A_2|+|A_3|</math>. We have counted the elements which are in exactly one of the original three sets once, but we've obviously counted other things twice, and even other things thrice! To account for the elements that are in two of the three sets, we first subtract out <math>|A_1\cap A_2|+|A_2\cap A_3| + |A_3\cap A_1|</math>. Now we have correctly accounted for them since we counted them twice originally, and just subtracted them out once. However, the elements that are in all three sets were originally counted three times and then subtracted out three times. We have to add back in <math>|A_1\cap A_2\cap A_3|</math>. Putting this all together gives:<br />
<br />
<center><math> |A_1\cup A_2\cup A_3| = |A_1| + |A_2| + |A_3| -|A_1\cap A_2| - |A_2\cap A_3| - |A_3\cap A_1| +|A_1\cap A_2\cap A_3|</math>.</center><br />
<br />
=== Four Set Example ===<br />
==== Problem ====<br />
<br />
Six people of different heights are getting in line to buy donuts. Compute the number of ways they can arrange themselves in line such that no three consecutive people are in increasing order of height, from front to back. (2015 ARML I10)<br />
<br />
==== Solution ====<br />
<br />
Let <math>A</math> be the event that the first, second, and third people are in ordered height, <math>B</math> be the event that the second, third, and fourth people are in ordered height, <math>C</math> be the event that the third, fourth, and fifth people are in ordered height, and <math>D</math> be the event that the fourth, fifth and sixth people are in ordered height. By a combination of complementary counting and PIE, we have that our answer will be <math>720-|A|-|B|-|C|-|D|+|A\cap B|+|A\cap C|+|A\cap D|+|B\cap C|+|B\cap D|+|C\cap D|-|A\cap B\cap C|-|A\cap B\cap D|-|A\cap C\cap D|-|B\cap C\cap D|+|A\cap B\cap C\cap D|</math>. Now for the daunting task of evaluating all of this.<br />
<br />
For <math>|A|</math>, we just choose <math>3</math> people and there is only one way to put them in order, then <math>3!</math> ways to order the other three guys for <math>3!\binom{6}{3}=120</math>. Same goes for <math>|B|</math>, <math>|C|</math>, and <math>|D|</math>.<br />
<br />
Now, for <math>|A\cap B|</math>, that's just putting four guys in order. By the same logic as above, this is <math>2!\binom{6}{4}=30</math>. Again, <math>|A\cap C|</math> would be putting five guys in order, so <math>1!\binom{6}{5}=6</math>. <math>|A\cap D|</math> is just choosing <math>3</math> guys out of <math>6</math>, then <math>3</math> guys out of <math>3</math> for <math>\binom{6}{3}=20</math>. Now, <math>|B\cap C|</math> is just the same as <math>|A\cap B|</math>, so <math>30</math>, <math>|B\cap D|</math> is <math>|A\cap C|</math> so <math>6</math>, and <math>|C\cap D|</math> is <math>|A\cap B|</math> so <math>30</math>.<br />
<br />
Moving on to the next set: <math>|A\cap B\cap C|</math> is the same as <math>|A\cap C|</math> which is <math>6</math>, <math>|A\cap B\cap D|</math> is ordering everybody so <math>1</math>, <math>|A\cap C\cap D|</math> is again ordering everybody which is <math>1</math>, and <math>|B\cap C\cap D|</math> is the same as <math>|A\cap B\cap C|</math> so <math>6</math>.<br />
<br />
Finally, <math>|A\cap B\cap C\cap D|</math> is ordering everybody so <math>1</math>.<br />
<br />
Now, lets substitute everything back in. We get a massive expression of <math>720-120-120-120-120+30+6+20+30+6+30-6-1-1-6+1=\boxed{349}</math>.<br />
<br />
=== Five Set Example ===<br />
==== Problem ====<br />
<br />
There are five courses at my school. Students take the classes as follows:<br />
243 take algebra.<br />
323 take language arts.<br />
143 take social studies.<br />
241 take biology.<br />
300 take history.<br />
213 take algebra and language arts.<br />
264 take algebra and social studies.<br />
144 take algebra and biology.<br />
121 take algebra and history.<br />
111 take language arts and social studies.<br />
90 take language arts and biology.<br />
80 take language arts and history.<br />
60 take social studies and biology.<br />
70 take social studies and history.<br />
60 take biology and history.<br />
50 take algebra, language arts, and social studies.<br />
50 take algebra, language arts, and biology.<br />
50 take algebra, language arts, and history.<br />
50 take algebra, social studies, and biology.<br />
50 take algebra, social studies, and history.<br />
50 take algebra, biology, and history.<br />
50 take language arts, social studies, and biology.<br />
50 take language arts, social studies, and history.<br />
50 take language arts, biology, and history.<br />
50 take social studies, biology, and history.<br />
20 take algebra, language arts, social studies, and biology.<br />
15 take algebra, language arts, social studies, and history.<br />
15 take algebra, language arts, biology, and history.<br />
10 take algebra, social studies, biology, and history.<br />
10 take language arts, social studies, biology, and history.<br />
5 take all five.<br />
None take none. <br />
<br />
How many people are in my school?<br />
<br />
==== Solution ====<br />
Let A be the subset of students who take Algebra, L-languages, S-Social Studies, B-biology, H-history, M-the set of all students. We have:<br />
<br />
<math>|M|=|A|+|L|+|S|+|B|+|H|-|A\cap L|-|A\cap S|-|A\cap B|-|A\cap H|-|L\cap S|-|L\cap B|</math><br />
<br />
<math>-|L\cap H|-|S\cap B|-|S\cap H|-|B\cap H|+|A\cap L\cap S|+|A\cap L\cap B|+|A\cap L\cap H|+|A\cap S\cap B|+|A\cap S\cap H|</math><br />
<br />
<math>+|A\cap B\cap H|+|L\cap S\cap H|+|L\cap S \cap B|+|S\cap B\cap H|+|L \cap B\cap H|-|A\cap L\cap S\cap B|-|A\cap L\cap S\cap H|</math><br />
<br />
<math>-|A\cap L\cap B\cap H|-|A\cap S\cap B\cap H|-|L\cap S\cap B\cap H|+|A\cap L\cap S\cap B\cap H|</math><br />
<br />
<math>=243+323+143+241+300-213-264-144-121-111-90-80-60-70-60</math><br />
<br />
<math>+50+50+50+50+50+50+50+50+50+50-20-15-15-10-10+5=472</math><br />
<br />
Thus, there are <math> \boxed{472} </math> people in my school.<br />
<br />
== Statement ==<br />
If <math>(A_i)_{1\leq i\leq n}</math> are finite sets, then:<br />
<center><math> \left|\bigcup_{i=1}^n A_i\right|=\sum_{i=1}^n\left|A_i\right|<br />
-\sum_{i < j}\left|A_i\cap A_j\right| +\sum_{i<j<k}\left|A_i\cap A_j\cap A_k\right|-\cdots\ +(-1)^{n-1} \left|A_1\cap\cdots\cap A_n\right|{}</math>.</center><br />
<br />
== Proof ==<br />
We prove that each element is counted once.<br />
<br />
Say that some element <math>X</math> is in <math>k</math> sets. Without loss of generality, these sets are <math>A_1,A_2,\dots,A_k.</math><br />
<br />
We proceed by induction. This is obvious for <math>k=1.</math><br />
<br />
If this is true for <math>k,</math> we prove this is true for <math>k+1.</math> For every set of sets not containing <math>A_{k+1}</math> with size <math>i,</math> there is a set of sets containing <math>A_{k+1}</math> with size <math>i+1.</math> In PIE, the sum of how many times these sets are counted is <math>0.</math> There is also one additional set of sets <math>\{A_{k+1}\},</math> so <math>X</math> is counted exactly once.<br />
<br />
== Remarks ==<br />
Sometimes it is also useful to know that, if you take into account only the first <math>m\le n</math> sums on the right, then you will get an overestimate if <math>m</math> is [[odd integer | odd]] and an underestimate if <math>m</math> is [[even integer | even]].<br />
So, <br />
<br />
<math>\left|\bigcup_{i=1}^n A_i\right|\le \sum_{i=1}^n\left|A_i\right|</math>,<br />
<br />
<math>\left|\bigcup_{i=1}^n A_i\right|\ge \sum_{i=1}^n\left|A_i\right|-\sum_{i < j}\left|A_i\cap A_j\right|</math>,<br />
<br />
<math>\left|\bigcup_{i=1}^n A_i\right|\le \sum_{i=1}^n\left|A_i\right|-\sum_{i < j}\left|A_i\cap A_j\right| +\sum_{i<j<k}\left|A_i\cap A_j\cap A_k\right|</math>,<br />
<br />
and so on.<br />
<br />
== Examples ==<br />
2002 AIME I Problems/Problem 1<br />
http://artofproblemsolving.com/wiki/index.php?title=2002_AIME_I_Problems/Problem_1#Problem<br />
<br />
2011 AMC 8 Problems/Problem 6<br />
https://artofproblemsolving.com/wiki/index.php?title=2011_AMC_8_Problems/Problem_6<br />
<br />
2017 AMC 10B Problems/Problem 13<br />
https://artofproblemsolving.com/wiki/index.php?title=2017_AMC_10B_Problems/Problem_13<br />
<br />
== See also ==<br />
* [[Combinatorics]]<br />
* [[Overcounting]]<br />
<br />
[[Category:Combinatorics]]</div>Patopatohttps://artofproblemsolving.com/wiki/index.php?title=Principle_of_Inclusion-Exclusion&diff=119042Principle of Inclusion-Exclusion2020-03-11T01:33:17Z<p>Patopato: /* Three Set Examples */</p>
<hr />
<div>The '''Principle of Inclusion-Exclusion''' (abbreviated PIE) provides an organized method/formula to find the number of [[element]]s in the [[union]] of a given group of [[set]]s, the size of each set, and the size of all possible [[intersection]]s among the sets.<br />
<br />
==Important Note(!)==<br />
An important note when using PIE is to understand how to strategically overcount and undercount, in the end making sure every element is counted once and only once. In particular, memorizing a formula for PIE is a bad idea for problem solving.<br />
<br />
== Application ==<br />
Here we will illustrate how PIE is applied with various numbers of sets.<br />
<br />
=== Two Set Example ===<br />
Assume we are given the sizes of two sets, <math>|A_1|</math> and <math>|A_2|</math>, and the size of their intersection, <math>|A_1\cap A_2|</math>. We wish to find the size of their union, <math>|A_1\cup A_2|</math>.<br />
<br />
To find the union, we can add <math>|A_1|</math> and <math>|A_2|</math>. In doing so, we know we have counted everything in <math>|A_1\cup A_2|</math> at least once. However, some things were counted twice. The elements that were counted twice are precisely those in <math> {}A_1\cap A_2 </math>. Thus, we have that:<br />
<br />
<center><math> |A_1 \cup A_2| = |A_1| + |A_2| - |A_1\cap A_2|</math>.</center><br />
<br />
====== Three Set Examples ======<br />
Assume we are given the sizes of three sets, <math>|A_1|, |A_2|,{}</math> and <math>|A_3|</math>, the size of their pairwise intersections, <math>|A_1\cap A_2|, |A_2\cap A_3|</math>, and <math>|A_3\cap A_1|</math>, and the size their overall intersection, <math>|A_1\cap A_2\cap A_3|</math>. We wish to find the size of their union, <math>|A_1\cup A_2\cup A_3|</math>.<br />
<br />
Just like in the Two Set Examples, we start with the sum of the sizes of the individual sets <math>|A_1|+|A_2|+|A_3|</math>. We have counted the elements which are in exactly one of the original three sets once, but we've obviously counted other things twice, and even other things thrice! To account for the elements that are in two of the three sets, we first subtract out <math>|A_1\cap A_2|+|A_2\cap A_3| + |A_3\cap A_1|</math>. Now we have correctly accounted for them since we counted them twice originally, and just subtracted them out once. However, the elements that are in all three sets were originally counted three times and then subtracted out three times. We have to add back in <math>|A_1\cap A_2\cap A_3|</math>. Putting this all together gives:<br />
<br />
<center><math> |A_1\cup A_2\cup A_3| = |A_1| + |A_2| + |A_3| -|A_1\cap A_2| - |A_2\cap A_3| - |A_3\cap A_1| +|A_1\cap A_2\cap A_3|</math>.</center><br />
<br />
=== Four Set Example ===<br />
==== Problem ====<br />
<br />
Six people of different heights are getting in line to buy donuts. Compute the number of ways they can arrange themselves in line such that no three consecutive people are in increasing order of height, from front to back. (2015 ARML I10)<br />
<br />
==== Solution ====<br />
<br />
Let <math>A</math> be the event that the first, second, and third people are in ordered height, <math>B</math> be the event that the second, third, and fourth people are in ordered height, <math>C</math> be the event that the third, fourth, and fifth people are in ordered height, and <math>D</math> be the event that the fourth, fifth and sixth people are in ordered height. By a combination of complementary counting and PIE, we have that our answer will be <math>720-|A|-|B|-|C|-|D|+|A\cap B|+|A\cap C|+|A\cap D|+|B\cap C|+|B\cap D|+|C\cap D|-|A\cap B\cap C|-|A\cap B\cap D|-|A\cap C\cap D|-|B\cap C\cap D|+|A\cap B\cap C\cap D|</math>. Now for the daunting task of evaluating all of this.<br />
<br />
For <math>|A|</math>, we just choose <math>3</math> people and there is only one way to put them in order, then <math>3!</math> ways to order the other three guys for <math>3!\binom{6}{3}=120</math>. Same goes for <math>|B|</math>, <math>|C|</math>, and <math>|D|</math>.<br />
<br />
Now, for <math>|A\cap B|</math>, that's just putting four guys in order. By the same logic as above, this is <math>2!\binom{6}{4}=30</math>. Again, <math>|A\cap C|</math> would be putting five guys in order, so <math>1!\binom{6}{5}=6</math>. <math>|A\cap D|</math> is just choosing <math>3</math> guys out of <math>6</math>, then <math>3</math> guys out of <math>3</math> for <math>\binom{6}{3}=20</math>. Now, <math>|B\cap C|</math> is just the same as <math>|A\cap B|</math>, so <math>30</math>, <math>|B\cap D|</math> is <math>|A\cap C|</math> so <math>6</math>, and <math>|C\cap D|</math> is <math>|A\cap B|</math> so <math>30</math>.<br />
<br />
Moving on to the next set: <math>|A\cap B\cap C|</math> is the same as <math>|A\cap C|</math> which is <math>6</math>, <math>|A\cap B\cap D|</math> is ordering everybody so <math>1</math>, <math>|A\cap C\cap D|</math> is again ordering everybody which is <math>1</math>, and <math>|B\cap C\cap D|</math> is the same as <math>|A\cap B\cap C|</math> so <math>6</math>.<br />
<br />
Finally, <math>|A\cap B\cap C\cap D|</math> is ordering everybody so <math>1</math>.<br />
<br />
Now, lets substitute everything back in. We get a massive expression of <math>720-120-120-120-120+30+6+20+30+6+30-6-1-1-6+1=\boxed{349}</math>.<br />
<br />
=== Five Set Example ===<br />
==== Problem ====<br />
<br />
There are five courses at my school. Students take the classes as follows:<br />
243 take algebra.<br />
323 take language arts.<br />
143 take social studies.<br />
241 take biology.<br />
300 take history.<br />
213 take algebra and language arts.<br />
264 take algebra and social studies.<br />
144 take algebra and biology.<br />
121 take algebra and history.<br />
111 take language arts and social studies.<br />
90 take language arts and biology.<br />
80 take language arts and history.<br />
60 take social studies and biology.<br />
70 take social studies and history.<br />
60 take biology and history.<br />
50 take algebra, language arts, and social studies.<br />
50 take algebra, language arts, and biology.<br />
50 take algebra, language arts, and history.<br />
50 take algebra, social studies, and biology.<br />
50 take algebra, social studies, and history.<br />
50 take algebra, biology, and history.<br />
50 take language arts, social studies, and biology.<br />
50 take language arts, social studies, and history.<br />
50 take language arts, biology, and history.<br />
50 take social studies, biology, and history.<br />
20 take algebra, language arts, social studies, and biology.<br />
15 take algebra, language arts, social studies, and history.<br />
15 take algebra, language arts, biology, and history.<br />
10 take algebra, social studies, biology, and history.<br />
10 take language arts, social studies, biology, and history.<br />
5 take all five.<br />
None take none. <br />
<br />
How many people are in my school?<br />
<br />
==== Solution ====<br />
Let A be the subset of students who take Algebra, L-languages, S-Social Studies, B-biology, H-history, M-the set of all students. We have:<br />
<br />
<math>|M|=|A|+|L|+|S|+|B|+|H|-|A\cap L|-|A\cap S|-|A\cap B|-|A\cap H|-|L\cap S|-|L\cap B|</math><br />
<br />
<math>-|L\cap H|-|S\cap B|-|S\cap H|-|B\cap H|+|A\cap L\cap S|+|A\cap L\cap B|+|A\cap L\cap H|+|A\cap S\cap B|+|A\cap S\cap H|</math><br />
<br />
<math>+|A\cap B\cap H|+|L\cap S\cap H|+|L\cap S \cap B|+|S\cap B\cap H|+|L \cap B\cap H|-|A\cap L\cap S\cap B|-|A\cap L\cap S\cap H|</math><br />
<br />
<math>-|A\cap L\cap B\cap H|-|A\cap S\cap B\cap H|-|L\cap S\cap B\cap H|+|A\cap L\cap S\cap B\cap H|</math><br />
<br />
<math>=243+323+143+241+300-213-264-144-121-111-90-80-60-70-60</math><br />
<br />
<math>+50+50+50+50+50+50+50+50+50+50-20-15-15-10-10+5=472</math><br />
<br />
Thus, there are <math> \boxed{472} </math> people in my school.<br />
<br />
== Statement ==<br />
If <math>(A_i)_{1\leq i\leq n}</math> are finite sets, then:<br />
<center><math> \left|\bigcup_{i=1}^n A_i\right|=\sum_{i=1}^n\left|A_i\right|<br />
-\sum_{i < j}\left|A_i\cap A_j\right| +\sum_{i<j<k}\left|A_i\cap A_j\cap A_k\right|-\cdots\ +(-1)^{n-1} \left|A_1\cap\cdots\cap A_n\right|{}</math>.</center><br />
<br />
== Proof ==<br />
We prove that each element is counted once.<br />
<br />
Say that some element <math>X</math> is in <math>k</math> sets. Without loss of generality, these sets are <math>A_1,A_2,\dots,A_k.</math><br />
<br />
We proceed by induction. This is obvious for <math>k=1.</math><br />
<br />
If this is true for <math>k,</math> we prove this is true for <math>k+1.</math> For every set of sets not containing <math>A_{k+1}</math> with size <math>i,</math> there is a set of sets containing <math>A_{k+1}</math> with size <math>i+1.</math> In PIE, the sum of how many times these sets are counted is <math>0.</math> There is also one additional set of sets <math>\{A_{k+1}\},</math> so <math>X</math> is counted exactly once.<br />
<br />
== Remarks ==<br />
Sometimes it is also useful to know that, if you take into account only the first <math>m\le n</math> sums on the right, then you will get an overestimate if <math>m</math> is [[odd integer | odd]] and an underestimate if <math>m</math> is [[even integer | even]].<br />
So, <br />
<br />
<math>\left|\bigcup_{i=1}^n A_i\right|\le \sum_{i=1}^n\left|A_i\right|</math>,<br />
<br />
<math>\left|\bigcup_{i=1}^n A_i\right|\ge \sum_{i=1}^n\left|A_i\right|-\sum_{i < j}\left|A_i\cap A_j\right|</math>,<br />
<br />
<math>\left|\bigcup_{i=1}^n A_i\right|\le \sum_{i=1}^n\left|A_i\right|-\sum_{i < j}\left|A_i\cap A_j\right| +\sum_{i<j<k}\left|A_i\cap A_j\cap A_k\right|</math>,<br />
<br />
and so on.<br />
<br />
== Examples ==<br />
2002 AIME I Problems/Problem 1<br />
http://artofproblemsolving.com/wiki/index.php?title=2002_AIME_I_Problems/Problem_1#Problem<br />
<br />
2011 AMC 8 Problems/Problem 6<br />
https://artofproblemsolving.com/wiki/index.php?title=2011_AMC_8_Problems/Problem_6<br />
<br />
2017 AMC 10B Problems/Problem 13<br />
https://artofproblemsolving.com/wiki/index.php?title=2017_AMC_10B_Problems/Problem_13<br />
<br />
== See also ==<br />
* [[Combinatorics]]<br />
* [[Overcounting]]<br />
<br />
[[Category:Combinatorics]]</div>Patopatohttps://artofproblemsolving.com/wiki/index.php?title=Principle_of_Inclusion-Exclusion&diff=119041Principle of Inclusion-Exclusion2020-03-11T01:32:33Z<p>Patopato: /* Three Set Examples */</p>
<hr />
<div>The '''Principle of Inclusion-Exclusion''' (abbreviated PIE) provides an organized method/formula to find the number of [[element]]s in the [[union]] of a given group of [[set]]s, the size of each set, and the size of all possible [[intersection]]s among the sets.<br />
<br />
==Important Note(!)==<br />
An important note when using PIE is to understand how to strategically overcount and undercount, in the end making sure every element is counted once and only once. In particular, memorizing a formula for PIE is a bad idea for problem solving.<br />
<br />
== Application ==<br />
Here we will illustrate how PIE is applied with various numbers of sets.<br />
<br />
=== Two Set Example ===<br />
Assume we are given the sizes of two sets, <math>|A_1|</math> and <math>|A_2|</math>, and the size of their intersection, <math>|A_1\cap A_2|</math>. We wish to find the size of their union, <math>|A_1\cup A_2|</math>.<br />
<br />
To find the union, we can add <math>|A_1|</math> and <math>|A_2|</math>. In doing so, we know we have counted everything in <math>|A_1\cup A_2|</math> at least once. However, some things were counted twice. The elements that were counted twice are precisely those in <math> {}A_1\cap A_2 </math>. Thus, we have that:<br />
<br />
<center><math> |A_1 \cup A_2| = |A_1| + |A_2| - |A_1\cap A_2|</math>.</center><br />
<br />
======== Three Set Examples ========<br />
Assume we are given the sizes of three sets, <math>|A_1|, |A_2|,{}</math> and <math>|A_3|</math>, the size of their pairwise intersections, <math>|A_1\cap A_2|, |A_2\cap A_3|</math>, and <math>|A_3\cap A_1|</math>, and the size their overall intersection, <math>|A_1\cap A_2\cap A_3|</math>. We wish to find the size of their union, <math>|A_1\cup A_2\cup A_3|</math>.<br />
<br />
Just like in the Two Set Examples, we start with the sum of the sizes of the individual sets <math>|A_1|+|A_2|+|A_3|</math>. We have counted the elements which are in exactly one of the original three sets once, but we've obviously counted other things twice, and even other things thrice! To account for the elements that are in two of the three sets, we first subtract out <math>|A_1\cap A_2|+|A_2\cap A_3| + |A_3\cap A_1|</math>. Now we have correctly accounted for them since we counted them twice originally, and just subtracted them out once. However, the elements that are in all three sets were originally counted three times and then subtracted out three times. We have to add back in <math>|A_1\cap A_2\cap A_3|</math>. Putting this all together gives:<br />
<br />
<center><math> |A_1\cup A_2\cup A_3| = |A_1| + |A_2| + |A_3| -|A_1\cap A_2| - |A_2\cap A_3| - |A_3\cap A_1| +|A_1\cap A_2\cap A_3|</math>.</center><br />
<br />
=== Four Set Example ===<br />
==== Problem ====<br />
<br />
Six people of different heights are getting in line to buy donuts. Compute the number of ways they can arrange themselves in line such that no three consecutive people are in increasing order of height, from front to back. (2015 ARML I10)<br />
<br />
==== Solution ====<br />
<br />
Let <math>A</math> be the event that the first, second, and third people are in ordered height, <math>B</math> be the event that the second, third, and fourth people are in ordered height, <math>C</math> be the event that the third, fourth, and fifth people are in ordered height, and <math>D</math> be the event that the fourth, fifth and sixth people are in ordered height. By a combination of complementary counting and PIE, we have that our answer will be <math>720-|A|-|B|-|C|-|D|+|A\cap B|+|A\cap C|+|A\cap D|+|B\cap C|+|B\cap D|+|C\cap D|-|A\cap B\cap C|-|A\cap B\cap D|-|A\cap C\cap D|-|B\cap C\cap D|+|A\cap B\cap C\cap D|</math>. Now for the daunting task of evaluating all of this.<br />
<br />
For <math>|A|</math>, we just choose <math>3</math> people and there is only one way to put them in order, then <math>3!</math> ways to order the other three guys for <math>3!\binom{6}{3}=120</math>. Same goes for <math>|B|</math>, <math>|C|</math>, and <math>|D|</math>.<br />
<br />
Now, for <math>|A\cap B|</math>, that's just putting four guys in order. By the same logic as above, this is <math>2!\binom{6}{4}=30</math>. Again, <math>|A\cap C|</math> would be putting five guys in order, so <math>1!\binom{6}{5}=6</math>. <math>|A\cap D|</math> is just choosing <math>3</math> guys out of <math>6</math>, then <math>3</math> guys out of <math>3</math> for <math>\binom{6}{3}=20</math>. Now, <math>|B\cap C|</math> is just the same as <math>|A\cap B|</math>, so <math>30</math>, <math>|B\cap D|</math> is <math>|A\cap C|</math> so <math>6</math>, and <math>|C\cap D|</math> is <math>|A\cap B|</math> so <math>30</math>.<br />
<br />
Moving on to the next set: <math>|A\cap B\cap C|</math> is the same as <math>|A\cap C|</math> which is <math>6</math>, <math>|A\cap B\cap D|</math> is ordering everybody so <math>1</math>, <math>|A\cap C\cap D|</math> is again ordering everybody which is <math>1</math>, and <math>|B\cap C\cap D|</math> is the same as <math>|A\cap B\cap C|</math> so <math>6</math>.<br />
<br />
Finally, <math>|A\cap B\cap C\cap D|</math> is ordering everybody so <math>1</math>.<br />
<br />
Now, lets substitute everything back in. We get a massive expression of <math>720-120-120-120-120+30+6+20+30+6+30-6-1-1-6+1=\boxed{349}</math>.<br />
<br />
=== Five Set Example ===<br />
==== Problem ====<br />
<br />
There are five courses at my school. Students take the classes as follows:<br />
243 take algebra.<br />
323 take language arts.<br />
143 take social studies.<br />
241 take biology.<br />
300 take history.<br />
213 take algebra and language arts.<br />
264 take algebra and social studies.<br />
144 take algebra and biology.<br />
121 take algebra and history.<br />
111 take language arts and social studies.<br />
90 take language arts and biology.<br />
80 take language arts and history.<br />
60 take social studies and biology.<br />
70 take social studies and history.<br />
60 take biology and history.<br />
50 take algebra, language arts, and social studies.<br />
50 take algebra, language arts, and biology.<br />
50 take algebra, language arts, and history.<br />
50 take algebra, social studies, and biology.<br />
50 take algebra, social studies, and history.<br />
50 take algebra, biology, and history.<br />
50 take language arts, social studies, and biology.<br />
50 take language arts, social studies, and history.<br />
50 take language arts, biology, and history.<br />
50 take social studies, biology, and history.<br />
20 take algebra, language arts, social studies, and biology.<br />
15 take algebra, language arts, social studies, and history.<br />
15 take algebra, language arts, biology, and history.<br />
10 take algebra, social studies, biology, and history.<br />
10 take language arts, social studies, biology, and history.<br />
5 take all five.<br />
None take none. <br />
<br />
How many people are in my school?<br />
<br />
==== Solution ====<br />
Let A be the subset of students who take Algebra, L-languages, S-Social Studies, B-biology, H-history, M-the set of all students. We have:<br />
<br />
<math>|M|=|A|+|L|+|S|+|B|+|H|-|A\cap L|-|A\cap S|-|A\cap B|-|A\cap H|-|L\cap S|-|L\cap B|</math><br />
<br />
<math>-|L\cap H|-|S\cap B|-|S\cap H|-|B\cap H|+|A\cap L\cap S|+|A\cap L\cap B|+|A\cap L\cap H|+|A\cap S\cap B|+|A\cap S\cap H|</math><br />
<br />
<math>+|A\cap B\cap H|+|L\cap S\cap H|+|L\cap S \cap B|+|S\cap B\cap H|+|L \cap B\cap H|-|A\cap L\cap S\cap B|-|A\cap L\cap S\cap H|</math><br />
<br />
<math>-|A\cap L\cap B\cap H|-|A\cap S\cap B\cap H|-|L\cap S\cap B\cap H|+|A\cap L\cap S\cap B\cap H|</math><br />
<br />
<math>=243+323+143+241+300-213-264-144-121-111-90-80-60-70-60</math><br />
<br />
<math>+50+50+50+50+50+50+50+50+50+50-20-15-15-10-10+5=472</math><br />
<br />
Thus, there are <math> \boxed{472} </math> people in my school.<br />
<br />
== Statement ==<br />
If <math>(A_i)_{1\leq i\leq n}</math> are finite sets, then:<br />
<center><math> \left|\bigcup_{i=1}^n A_i\right|=\sum_{i=1}^n\left|A_i\right|<br />
-\sum_{i < j}\left|A_i\cap A_j\right| +\sum_{i<j<k}\left|A_i\cap A_j\cap A_k\right|-\cdots\ +(-1)^{n-1} \left|A_1\cap\cdots\cap A_n\right|{}</math>.</center><br />
<br />
== Proof ==<br />
We prove that each element is counted once.<br />
<br />
Say that some element <math>X</math> is in <math>k</math> sets. Without loss of generality, these sets are <math>A_1,A_2,\dots,A_k.</math><br />
<br />
We proceed by induction. This is obvious for <math>k=1.</math><br />
<br />
If this is true for <math>k,</math> we prove this is true for <math>k+1.</math> For every set of sets not containing <math>A_{k+1}</math> with size <math>i,</math> there is a set of sets containing <math>A_{k+1}</math> with size <math>i+1.</math> In PIE, the sum of how many times these sets are counted is <math>0.</math> There is also one additional set of sets <math>\{A_{k+1}\},</math> so <math>X</math> is counted exactly once.<br />
<br />
== Remarks ==<br />
Sometimes it is also useful to know that, if you take into account only the first <math>m\le n</math> sums on the right, then you will get an overestimate if <math>m</math> is [[odd integer | odd]] and an underestimate if <math>m</math> is [[even integer | even]].<br />
So, <br />
<br />
<math>\left|\bigcup_{i=1}^n A_i\right|\le \sum_{i=1}^n\left|A_i\right|</math>,<br />
<br />
<math>\left|\bigcup_{i=1}^n A_i\right|\ge \sum_{i=1}^n\left|A_i\right|-\sum_{i < j}\left|A_i\cap A_j\right|</math>,<br />
<br />
<math>\left|\bigcup_{i=1}^n A_i\right|\le \sum_{i=1}^n\left|A_i\right|-\sum_{i < j}\left|A_i\cap A_j\right| +\sum_{i<j<k}\left|A_i\cap A_j\cap A_k\right|</math>,<br />
<br />
and so on.<br />
<br />
== Examples ==<br />
2002 AIME I Problems/Problem 1<br />
http://artofproblemsolving.com/wiki/index.php?title=2002_AIME_I_Problems/Problem_1#Problem<br />
<br />
2011 AMC 8 Problems/Problem 6<br />
https://artofproblemsolving.com/wiki/index.php?title=2011_AMC_8_Problems/Problem_6<br />
<br />
2017 AMC 10B Problems/Problem 13<br />
https://artofproblemsolving.com/wiki/index.php?title=2017_AMC_10B_Problems/Problem_13<br />
<br />
== See also ==<br />
* [[Combinatorics]]<br />
* [[Overcounting]]<br />
<br />
[[Category:Combinatorics]]</div>Patopatohttps://artofproblemsolving.com/wiki/index.php?title=Principle_of_Inclusion-Exclusion&diff=119039Principle of Inclusion-Exclusion2020-03-11T01:32:15Z<p>Patopato: </p>
<hr />
<div>The '''Principle of Inclusion-Exclusion''' (abbreviated PIE) provides an organized method/formula to find the number of [[element]]s in the [[union]] of a given group of [[set]]s, the size of each set, and the size of all possible [[intersection]]s among the sets.<br />
<br />
==Important Note(!)==<br />
An important note when using PIE is to understand how to strategically overcount and undercount, in the end making sure every element is counted once and only once. In particular, memorizing a formula for PIE is a bad idea for problem solving.<br />
<br />
== Application ==<br />
Here we will illustrate how PIE is applied with various numbers of sets.<br />
<br />
=== Two Set Example ===<br />
Assume we are given the sizes of two sets, <math>|A_1|</math> and <math>|A_2|</math>, and the size of their intersection, <math>|A_1\cap A_2|</math>. We wish to find the size of their union, <math>|A_1\cup A_2|</math>.<br />
<br />
To find the union, we can add <math>|A_1|</math> and <math>|A_2|</math>. In doing so, we know we have counted everything in <math>|A_1\cup A_2|</math> at least once. However, some things were counted twice. The elements that were counted twice are precisely those in <math> {}A_1\cap A_2 </math>. Thus, we have that:<br />
<br />
<center><math> |A_1 \cup A_2| = |A_1| + |A_2| - |A_1\cap A_2|</math>.</center><br />
<br />
============= Three Set Examples =============<br />
Assume we are given the sizes of three sets, <math>|A_1|, |A_2|,{}</math> and <math>|A_3|</math>, the size of their pairwise intersections, <math>|A_1\cap A_2|, |A_2\cap A_3|</math>, and <math>|A_3\cap A_1|</math>, and the size their overall intersection, <math>|A_1\cap A_2\cap A_3|</math>. We wish to find the size of their union, <math>|A_1\cup A_2\cup A_3|</math>.<br />
<br />
Just like in the Two Set Examples, we start with the sum of the sizes of the individual sets <math>|A_1|+|A_2|+|A_3|</math>. We have counted the elements which are in exactly one of the original three sets once, but we've obviously counted other things twice, and even other things thrice! To account for the elements that are in two of the three sets, we first subtract out <math>|A_1\cap A_2|+|A_2\cap A_3| + |A_3\cap A_1|</math>. Now we have correctly accounted for them since we counted them twice originally, and just subtracted them out once. However, the elements that are in all three sets were originally counted three times and then subtracted out three times. We have to add back in <math>|A_1\cap A_2\cap A_3|</math>. Putting this all together gives:<br />
<br />
<center><math> |A_1\cup A_2\cup A_3| = |A_1| + |A_2| + |A_3| -|A_1\cap A_2| - |A_2\cap A_3| - |A_3\cap A_1| +|A_1\cap A_2\cap A_3|</math>.</center><br />
<br />
=== Four Set Example ===<br />
==== Problem ====<br />
<br />
Six people of different heights are getting in line to buy donuts. Compute the number of ways they can arrange themselves in line such that no three consecutive people are in increasing order of height, from front to back. (2015 ARML I10)<br />
<br />
==== Solution ====<br />
<br />
Let <math>A</math> be the event that the first, second, and third people are in ordered height, <math>B</math> be the event that the second, third, and fourth people are in ordered height, <math>C</math> be the event that the third, fourth, and fifth people are in ordered height, and <math>D</math> be the event that the fourth, fifth and sixth people are in ordered height. By a combination of complementary counting and PIE, we have that our answer will be <math>720-|A|-|B|-|C|-|D|+|A\cap B|+|A\cap C|+|A\cap D|+|B\cap C|+|B\cap D|+|C\cap D|-|A\cap B\cap C|-|A\cap B\cap D|-|A\cap C\cap D|-|B\cap C\cap D|+|A\cap B\cap C\cap D|</math>. Now for the daunting task of evaluating all of this.<br />
<br />
For <math>|A|</math>, we just choose <math>3</math> people and there is only one way to put them in order, then <math>3!</math> ways to order the other three guys for <math>3!\binom{6}{3}=120</math>. Same goes for <math>|B|</math>, <math>|C|</math>, and <math>|D|</math>.<br />
<br />
Now, for <math>|A\cap B|</math>, that's just putting four guys in order. By the same logic as above, this is <math>2!\binom{6}{4}=30</math>. Again, <math>|A\cap C|</math> would be putting five guys in order, so <math>1!\binom{6}{5}=6</math>. <math>|A\cap D|</math> is just choosing <math>3</math> guys out of <math>6</math>, then <math>3</math> guys out of <math>3</math> for <math>\binom{6}{3}=20</math>. Now, <math>|B\cap C|</math> is just the same as <math>|A\cap B|</math>, so <math>30</math>, <math>|B\cap D|</math> is <math>|A\cap C|</math> so <math>6</math>, and <math>|C\cap D|</math> is <math>|A\cap B|</math> so <math>30</math>.<br />
<br />
Moving on to the next set: <math>|A\cap B\cap C|</math> is the same as <math>|A\cap C|</math> which is <math>6</math>, <math>|A\cap B\cap D|</math> is ordering everybody so <math>1</math>, <math>|A\cap C\cap D|</math> is again ordering everybody which is <math>1</math>, and <math>|B\cap C\cap D|</math> is the same as <math>|A\cap B\cap C|</math> so <math>6</math>.<br />
<br />
Finally, <math>|A\cap B\cap C\cap D|</math> is ordering everybody so <math>1</math>.<br />
<br />
Now, lets substitute everything back in. We get a massive expression of <math>720-120-120-120-120+30+6+20+30+6+30-6-1-1-6+1=\boxed{349}</math>.<br />
<br />
=== Five Set Example ===<br />
==== Problem ====<br />
<br />
There are five courses at my school. Students take the classes as follows:<br />
243 take algebra.<br />
323 take language arts.<br />
143 take social studies.<br />
241 take biology.<br />
300 take history.<br />
213 take algebra and language arts.<br />
264 take algebra and social studies.<br />
144 take algebra and biology.<br />
121 take algebra and history.<br />
111 take language arts and social studies.<br />
90 take language arts and biology.<br />
80 take language arts and history.<br />
60 take social studies and biology.<br />
70 take social studies and history.<br />
60 take biology and history.<br />
50 take algebra, language arts, and social studies.<br />
50 take algebra, language arts, and biology.<br />
50 take algebra, language arts, and history.<br />
50 take algebra, social studies, and biology.<br />
50 take algebra, social studies, and history.<br />
50 take algebra, biology, and history.<br />
50 take language arts, social studies, and biology.<br />
50 take language arts, social studies, and history.<br />
50 take language arts, biology, and history.<br />
50 take social studies, biology, and history.<br />
20 take algebra, language arts, social studies, and biology.<br />
15 take algebra, language arts, social studies, and history.<br />
15 take algebra, language arts, biology, and history.<br />
10 take algebra, social studies, biology, and history.<br />
10 take language arts, social studies, biology, and history.<br />
5 take all five.<br />
None take none. <br />
<br />
How many people are in my school?<br />
<br />
==== Solution ====<br />
Let A be the subset of students who take Algebra, L-languages, S-Social Studies, B-biology, H-history, M-the set of all students. We have:<br />
<br />
<math>|M|=|A|+|L|+|S|+|B|+|H|-|A\cap L|-|A\cap S|-|A\cap B|-|A\cap H|-|L\cap S|-|L\cap B|</math><br />
<br />
<math>-|L\cap H|-|S\cap B|-|S\cap H|-|B\cap H|+|A\cap L\cap S|+|A\cap L\cap B|+|A\cap L\cap H|+|A\cap S\cap B|+|A\cap S\cap H|</math><br />
<br />
<math>+|A\cap B\cap H|+|L\cap S\cap H|+|L\cap S \cap B|+|S\cap B\cap H|+|L \cap B\cap H|-|A\cap L\cap S\cap B|-|A\cap L\cap S\cap H|</math><br />
<br />
<math>-|A\cap L\cap B\cap H|-|A\cap S\cap B\cap H|-|L\cap S\cap B\cap H|+|A\cap L\cap S\cap B\cap H|</math><br />
<br />
<math>=243+323+143+241+300-213-264-144-121-111-90-80-60-70-60</math><br />
<br />
<math>+50+50+50+50+50+50+50+50+50+50-20-15-15-10-10+5=472</math><br />
<br />
Thus, there are <math> \boxed{472} </math> people in my school.<br />
<br />
== Statement ==<br />
If <math>(A_i)_{1\leq i\leq n}</math> are finite sets, then:<br />
<center><math> \left|\bigcup_{i=1}^n A_i\right|=\sum_{i=1}^n\left|A_i\right|<br />
-\sum_{i < j}\left|A_i\cap A_j\right| +\sum_{i<j<k}\left|A_i\cap A_j\cap A_k\right|-\cdots\ +(-1)^{n-1} \left|A_1\cap\cdots\cap A_n\right|{}</math>.</center><br />
<br />
== Proof ==<br />
We prove that each element is counted once.<br />
<br />
Say that some element <math>X</math> is in <math>k</math> sets. Without loss of generality, these sets are <math>A_1,A_2,\dots,A_k.</math><br />
<br />
We proceed by induction. This is obvious for <math>k=1.</math><br />
<br />
If this is true for <math>k,</math> we prove this is true for <math>k+1.</math> For every set of sets not containing <math>A_{k+1}</math> with size <math>i,</math> there is a set of sets containing <math>A_{k+1}</math> with size <math>i+1.</math> In PIE, the sum of how many times these sets are counted is <math>0.</math> There is also one additional set of sets <math>\{A_{k+1}\},</math> so <math>X</math> is counted exactly once.<br />
<br />
== Remarks ==<br />
Sometimes it is also useful to know that, if you take into account only the first <math>m\le n</math> sums on the right, then you will get an overestimate if <math>m</math> is [[odd integer | odd]] and an underestimate if <math>m</math> is [[even integer | even]].<br />
So, <br />
<br />
<math>\left|\bigcup_{i=1}^n A_i\right|\le \sum_{i=1}^n\left|A_i\right|</math>,<br />
<br />
<math>\left|\bigcup_{i=1}^n A_i\right|\ge \sum_{i=1}^n\left|A_i\right|-\sum_{i < j}\left|A_i\cap A_j\right|</math>,<br />
<br />
<math>\left|\bigcup_{i=1}^n A_i\right|\le \sum_{i=1}^n\left|A_i\right|-\sum_{i < j}\left|A_i\cap A_j\right| +\sum_{i<j<k}\left|A_i\cap A_j\cap A_k\right|</math>,<br />
<br />
and so on.<br />
<br />
== Examples ==<br />
2002 AIME I Problems/Problem 1<br />
http://artofproblemsolving.com/wiki/index.php?title=2002_AIME_I_Problems/Problem_1#Problem<br />
<br />
2011 AMC 8 Problems/Problem 6<br />
https://artofproblemsolving.com/wiki/index.php?title=2011_AMC_8_Problems/Problem_6<br />
<br />
2017 AMC 10B Problems/Problem 13<br />
https://artofproblemsolving.com/wiki/index.php?title=2017_AMC_10B_Problems/Problem_13<br />
<br />
== See also ==<br />
* [[Combinatorics]]<br />
* [[Overcounting]]<br />
<br />
[[Category:Combinatorics]]</div>Patopatohttps://artofproblemsolving.com/wiki/index.php?title=Principle_of_Inclusion-Exclusion&diff=119038Principle of Inclusion-Exclusion2020-03-11T01:31:26Z<p>Patopato: </p>
<hr />
<div>The '''Principle of Inclusion-Exclusion''' (abbreviated PIE) provides an organized method/formula to find the number of [[element]]s in the [[union]] of a given group of [[set]]s, the size of each set, and the size of all possible [[intersection]]s among the sets.<br />
<br />
==Important Note(!)==<br />
An important note when using PIE is to understand how to strategically overcount and undercount, in the end making sure every element is counted once and only once. In particular, memorizing a formula for PIE is a bad idea for problem solving.<br />
<br />
== Application ==<br />
Here we will illustrate how PIE is applied with various numbers of sets.<br />
<br />
=== Two Set Example ===<br />
Assume we are given the sizes of two sets, <math>|A_1|</math> and <math>|A_2|</math>, and the size of their intersection, <math>|A_1\cap A_2|</math>. We wish to find the size of their union, <math>|A_1\cup A_2|</math>.<br />
<br />
To find the union, we can add <math>|A_1|</math> and <math>|A_2|</math>. In doing so, we know we have counted everything in <math>|A_1\cup A_2|</math> at least once. However, some things were counted twice. The elements that were counted twice are precisely those in <math> {}A_1\cap A_2 </math>. Thus, we have that:<br />
<br />
<center><math> |A_1 \cup A_2| = |A_1| + |A_2| - |A_1\cap A_2|</math>.</center><br />
<br />
=== Three Set Examples ===<br />
Assume we are given the sizes of three sets, <math>|A_1|, |A_2|,{}</math> and <math>|A_3|</math>, the size of their pairwise intersections, <math>|A_1\cap A_2|, |A_2\cap A_3|</math>, and <math>|A_3\cap A_1|</math>, and the size their overall intersection, <math>|A_1\cap A_2\cap A_3|</math>. We wish to find the size of their union, <math>|A_1\cup A_2\cup A_3|</math>.<br />
<br />
Just like in the Two Set Examples, we start with the sum of the sizes of the individual sets <math>|A_1|+|A_2|+|A_3|</math>. We have counted the elements which are in exactly one of the original three sets once, but we've obviously counted other things twice, and even other things thrice! To account for the elements that are in two of the three sets, we first subtract out <math>|A_1\cap A_2|+|A_2\cap A_3| + |A_3\cap A_1|</math>. Now we have correctly accounted for them since we counted them twice originally, and just subtracted them out once. However, the elements that are in all three sets were originally counted three times and then subtracted out three times. We have to add back in <math>|A_1\cap A_2\cap A_3|</math>. Putting this all together gives:<br />
<br />
<center><math> |A_1\cup A_2\cup A_3| = |A_1| + |A_2| + |A_3| -|A_1\cap A_2| - |A_2\cap A_3| - |A_3\cap A_1| +|A_1\cap A_2\cap A_3|</math>.</center><br />
<br />
=== Four Set Example ===<br />
==== Problem ====<br />
<br />
Six people of different heights are getting in line to buy donuts. Compute the number of ways they can arrange themselves in line such that no three consecutive people are in increasing order of height, from front to back. (2015 ARML I10)<br />
<br />
==== Solution ====<br />
<br />
Let <math>A</math> be the event that the first, second, and third people are in ordered height, <math>B</math> be the event that the second, third, and fourth people are in ordered height, <math>C</math> be the event that the third, fourth, and fifth people are in ordered height, and <math>D</math> be the event that the fourth, fifth and sixth people are in ordered height. By a combination of complementary counting and PIE, we have that our answer will be <math>720-|A|-|B|-|C|-|D|+|A\cap B|+|A\cap C|+|A\cap D|+|B\cap C|+|B\cap D|+|C\cap D|-|A\cap B\cap C|-|A\cap B\cap D|-|A\cap C\cap D|-|B\cap C\cap D|+|A\cap B\cap C\cap D|</math>. Now for the daunting task of evaluating all of this.<br />
<br />
For <math>|A|</math>, we just choose <math>3</math> people and there is only one way to put them in order, then <math>3!</math> ways to order the other three guys for <math>3!\binom{6}{3}=120</math>. Same goes for <math>|B|</math>, <math>|C|</math>, and <math>|D|</math>.<br />
<br />
Now, for <math>|A\cap B|</math>, that's just putting four guys in order. By the same logic as above, this is <math>2!\binom{6}{4}=30</math>. Again, <math>|A\cap C|</math> would be putting five guys in order, so <math>1!\binom{6}{5}=6</math>. <math>|A\cap D|</math> is just choosing <math>3</math> guys out of <math>6</math>, then <math>3</math> guys out of <math>3</math> for <math>\binom{6}{3}=20</math>. Now, <math>|B\cap C|</math> is just the same as <math>|A\cap B|</math>, so <math>30</math>, <math>|B\cap D|</math> is <math>|A\cap C|</math> so <math>6</math>, and <math>|C\cap D|</math> is <math>|A\cap B|</math> so <math>30</math>.<br />
<br />
Moving on to the next set: <math>|A\cap B\cap C|</math> is the same as <math>|A\cap C|</math> which is <math>6</math>, <math>|A\cap B\cap D|</math> is ordering everybody so <math>1</math>, <math>|A\cap C\cap D|</math> is again ordering everybody which is <math>1</math>, and <math>|B\cap C\cap D|</math> is the same as <math>|A\cap B\cap C|</math> so <math>6</math>.<br />
<br />
Finally, <math>|A\cap B\cap C\cap D|</math> is ordering everybody so <math>1</math>.<br />
<br />
Now, lets substitute everything back in. We get a massive expression of <math>720-120-120-120-120+30+6+20+30+6+30-6-1-1-6+1=\boxed{349}</math>.<br />
<br />
=== Five Set Example ===<br />
==== Problem ====<br />
<br />
There are five courses at my school. Students take the classes as follows:<br />
243 take algebra.<br />
323 take language arts.<br />
143 take social studies.<br />
241 take biology.<br />
300 take history.<br />
213 take algebra and language arts.<br />
264 take algebra and social studies.<br />
144 take algebra and biology.<br />
121 take algebra and history.<br />
111 take language arts and social studies.<br />
90 take language arts and biology.<br />
80 take language arts and history.<br />
60 take social studies and biology.<br />
70 take social studies and history.<br />
60 take biology and history.<br />
50 take algebra, language arts, and social studies.<br />
50 take algebra, language arts, and biology.<br />
50 take algebra, language arts, and history.<br />
50 take algebra, social studies, and biology.<br />
50 take algebra, social studies, and history.<br />
50 take algebra, biology, and history.<br />
50 take language arts, social studies, and biology.<br />
50 take language arts, social studies, and history.<br />
50 take language arts, biology, and history.<br />
50 take social studies, biology, and history.<br />
20 take algebra, language arts, social studies, and biology.<br />
15 take algebra, language arts, social studies, and history.<br />
15 take algebra, language arts, biology, and history.<br />
10 take algebra, social studies, biology, and history.<br />
10 take language arts, social studies, biology, and history.<br />
5 take all five.<br />
None take none. <br />
<br />
How many people are in my school?<br />
<br />
==== Solution ====<br />
Let A be the subset of students who take Algebra, L-languages, S-Social Studies, B-biology, H-history, M-the set of all students. We have:<br />
<br />
<math>|M|=|A|+|L|+|S|+|B|+|H|-|A\cap L|-|A\cap S|-|A\cap B|-|A\cap H|-|L\cap S|-|L\cap B|</math><br />
<br />
<math>-|L\cap H|-|S\cap B|-|S\cap H|-|B\cap H|+|A\cap L\cap S|+|A\cap L\cap B|+|A\cap L\cap H|+|A\cap S\cap B|+|A\cap S\cap H|</math><br />
<br />
<math>+|A\cap B\cap H|+|L\cap S\cap H|+|L\cap S \cap B|+|S\cap B\cap H|+|L \cap B\cap H|-|A\cap L\cap S\cap B|-|A\cap L\cap S\cap H|</math><br />
<br />
<math>-|A\cap L\cap B\cap H|-|A\cap S\cap B\cap H|-|L\cap S\cap B\cap H|+|A\cap L\cap S\cap B\cap H|</math><br />
<br />
<math>=243+323+143+241+300-213-264-144-121-111-90-80-60-70-60</math><br />
<br />
<math>+50+50+50+50+50+50+50+50+50+50-20-15-15-10-10+5=472</math><br />
<br />
Thus, there are <math> \boxed{472} </math> people in my school.<br />
<br />
== Statement ==<br />
If <math>(A_i)_{1\leq i\leq n}</math> are finite sets, then:<br />
<center><math> \left|\bigcup_{i=1}^n A_i\right|=\sum_{i=1}^n\left|A_i\right|<br />
-\sum_{i < j}\left|A_i\cap A_j\right| +\sum_{i<j<k}\left|A_i\cap A_j\cap A_k\right|-\cdots\ +(-1)^{n-1} \left|A_1\cap\cdots\cap A_n\right|{}</math>.</center><br />
<br />
== Proof ==<br />
We prove that each element is counted once.<br />
<br />
Say that some element <math>X</math> is in <math>k</math> sets. Without loss of generality, these sets are <math>A_1,A_2,\dots,A_k.</math><br />
<br />
We proceed by induction. This is obvious for <math>k=1.</math><br />
<br />
If this is true for <math>k,</math> we prove this is true for <math>k+1.</math> For every set of sets not containing <math>A_{k+1}</math> with size <math>i,</math> there is a set of sets containing <math>A_{k+1}</math> with size <math>i+1.</math> In PIE, the sum of how many times these sets are counted is <math>0.</math> There is also one additional set of sets <math>\{A_{k+1}\},</math> so <math>X</math> is counted exactly once.<br />
<br />
== Remarks ==<br />
Sometimes it is also useful to know that, if you take into account only the first <math>m\le n</math> sums on the right, then you will get an overestimate if <math>m</math> is [[odd integer | odd]] and an underestimate if <math>m</math> is [[even integer | even]].<br />
So, <br />
<br />
<math>\left|\bigcup_{i=1}^n A_i\right|\le \sum_{i=1}^n\left|A_i\right|</math>,<br />
<br />
<math>\left|\bigcup_{i=1}^n A_i\right|\ge \sum_{i=1}^n\left|A_i\right|-\sum_{i < j}\left|A_i\cap A_j\right|</math>,<br />
<br />
<math>\left|\bigcup_{i=1}^n A_i\right|\le \sum_{i=1}^n\left|A_i\right|-\sum_{i < j}\left|A_i\cap A_j\right| +\sum_{i<j<k}\left|A_i\cap A_j\cap A_k\right|</math>,<br />
<br />
and so on.<br />
<br />
== Examples ==<br />
2002 AIME I Problems/Problem 1<br />
http://artofproblemsolving.com/wiki/index.php?title=2002_AIME_I_Problems/Problem_1#Problem<br />
<br />
2011 AMC 8 Problems/Problem 6<br />
https://artofproblemsolving.com/wiki/index.php?title=2011_AMC_8_Problems/Problem_6<br />
<br />
2017 AMC 10B Problems/Problem 13<br />
https://artofproblemsolving.com/wiki/index.php?title=2017_AMC_10B_Problems/Problem_13<br />
<br />
== See also ==<br />
* [[Combinatorics]]<br />
* [[Overcounting]]<br />
<br />
[[Category:Combinatorics]]</div>Patopatohttps://artofproblemsolving.com/wiki/index.php?title=Gmaas&diff=112669Gmaas2019-12-07T21:47:03Z<p>Patopato: Replaced content with "Joe mama"</p>
<hr />
<div>Joe mama</div>Patopatohttps://artofproblemsolving.com/wiki/index.php?title=Gmaas&diff=111546Gmaas2019-11-18T22:30:25Z<p>Patopato: </p>
<hr />
<div>[size=200]GMAAS uses aimbot.[/size]<br />
<br />
Nothing more to say about that.<br />
<br />
GMAAS is our leader. We shall worship him. To prove yourself worthy of the great GMAAS, you must memorize facts about him:<br />
-------------------------------------------------------<br />
<br />
-3.14159265358979... GMAAS is our almighty leader. He will help us be more like him in all ways. If you wish to become more like GMAAS, make sure everytime you speak his name, it is in all capitals. Otherwise he will shoot a flaming ball of hair at you. YOU HAVE BEEN WARNED!<br />
<br />
-1.5. GMAAS wants you to worship him. And you will. Or else.<br />
<br />
-1. GMAAS looks like this when he is mad: https://cdn.artofproblemsolving.com/images/7/4/b/74b21fec95225e1621c71ec8f17f343c48a726e0.jpg GMAAS permits to post this picture.<br />
<br />
0. THE FACTS ABOUT THE GREAT EPIC AWESOME GMAAS: Words fail to describe the epic nature of GMAAS, for he is too almighty and powerful to be bound by the plebeian and trifling words. But even the Great Epic Awesome Plenipotentiary GMAAS cannot get rid of a language that's been around for a <math>999999999999999999999999999999999999999999^{9999999999999999999999999999999999999}</math> years and counting. That's older than he is. EDIT: It is not older than he is because Gmaas is infinity years old. EDIT EDIT: He has now<br />
<br />
1. GMAAS's theorem states that for any math problem, GMAAS knows the answer to it. This theorem was proved by GMAAS. But then GMAAS forgot about the theorem so later, the mathematician named usernameyourself proved it again: [b]Proof of the GMAAS theorem[/b]: The GMAAS theorem states that for every math problem, GMAAS knows the answer. Using the 1.26 GMAAS theorem, stating that "26. GMAAS's Theorem states that GMAAS knows the answer to any math problem. EDIT: That theorem was proved by GMAAS. EDIT: GMAAS's Theorem has real-world applications: because GMAAS knows the answer to any math problem, you can use GMAAS to solve math problems. GMAAS is busy, so he charges a fee of one dollar for 1,000,000 math problems. EDIT: The fee has gone up. It is now 1,000,000 dollars for one math problem. Gmaas's technician made a mistake and reciprocated the fee," you must pay <math>1,000,000</math> to solve a problem using the Gmaas theorem. You wouldn't waste that much money to solve one problem. Therefore, I proved that you cannot use the Gmaas theorem to solve problems. But using theorem 1.24 "24. Gmaas can turn things into gold. EDIT: Gmaas can turn anything into anything," Gmaas may turn anything into anything. This means he can turn grass into millions of dollars. I take one million and solve the problem. Therefore, you can use the Gmaas theorem to solve any problem.<br />
<br />
2. The GMATS were supposed to be called the GMAAS, but the manager, gmaas, wanted to eat some gnats. Gmaas has stopped eating gnats because they taste dreadful. EDIT: He now eats gnats again. He thinks that they taste like pie. EDIT: He ate 3,141,592,653,589,793,238,462,643,383 so far.<br />
<br />
3. Gmaas' archenemy is John Wick. John Wick once gave Gmaas 31,415,926,535,897,932,384 Oren Berries, but Gmaas thought they were Oran Berries. That is why Gmaas hates John Wick. Gmaas knew they were Oren Berries because Gmaas knows everything, but he decided to play along.<br />
<br />
4. Gmaas wants every fact to have a pi reference. Gmaas created pi. EDIT: He made it 314 times.<br />
<br />
5. Gmaas owned many memes. Then they died. He left the meme business because others took it over. Gmaas decided to make some more memes after that. Since then, he has been working for the government. All of the politicians are his henchmen. He controls the government. He wrote all of the laws and documents including the U.S. constitution. However, Gmaas doesn't believe in constitutions. He simply writes them for fun (or not, only gmaas knows!!!) EDIT: His favorite is memedog<br />
<br />
6. Gmaas owns Scratch. Gmaas sued them because Scratch cat was supposed to be a picture of Gmaas. But this was one lawsuit he lost. Gmaas won that lawsuit, but he ate food so he calmed down and dropped the case.<br />
<br />
7. Thanos wishes he could be like Gmaas. It's why he got the Infinity Stones and snapped.<br />
<br />
8. Gmaas dies in Endgame, but he somehow possesses Thanos and kills everyone. Gmaas never dies. Gmaas has the power to die whenever he wants and frequently does this to escape others' woes in life. Of course, he never faces such troubles.<br />
<br />
9. He hates contemporary music. He only like Renaissance music, Baroque music, Classical music, and Romantic music. His only exception is Queen music(Especially Bohemian Rhapsody). Gmaas also likes Debussy. But he thinks rock'n'roll is awful.EDIT: Gmass doesn't like music that much; it hurts his ears.<br />
<br />
10. Gmaas is superior to you. If you see Gmaas or a picture of the Great Gmaas, DON"T bow down. It is proper to have a painting or lifesize sculpture of Gmaas. If you do not, Gmaas will put one of them there himself. EDIT: That is exactly why you should not have a statue of Gmaas: Gmaas will give you one for free. A life-size sculpture of Gmaas will be infinitely large because that is how superior Gmaas is. Pictures also have power, so pictures require power to make. Making a sculpture of Gmaas will require almost an infinite amount of power. Only Gmaas can make a quality sculpture of himself, and if anyone makes a low-quality sculpture of Gmaas, it will be disrespectful to such a superior power. Therefore, it is best to let Gmaas make a proper sculpture of himself, so he is respected. If you want to respect him the most, you should NOT have a high-quality sculpture of Gmaas.<br />
<br />
11. Gmaas is known to barf entire universes at will. EDIT: Every once in a while, he barfs a furball, which always turns into a black hole. The less impressive ones turn into neutron stars.<br />
<br />
12. Gmaas farted and created a false vacuum, but then he burped, destroying the false vacuum.<br />
<br />
13. Gmaas was the first person to use the Infinity Gauntlet. EDIT: Gmaas created the Infinity Gauntlet and the Infinity Stones. EDIT: But Thanos stole them after Gmaas died for 0.31415926535 seconds.<br />
<br />
14. Gmaas killed Thanos with a swat of Gmaas's tail. Gmaas barfed and created a furball, which leads to a new dimension, where he put a newly revived Thanos to become a farmer when Thor aimed for the head. Gmaas got mad and made him fat. EDIT: The presence of Gmaas killed Thanos.<br />
<br />
15. Gmaas won an infinite amount of games against AlphaGo and Gary Kasparov while eating dinner, chasing sseraj, and doing a handstand.<br />
<br />
16. Gmaas owns a pet: sseraj. Gmaas likes to play chess with his pets. EDIT: Gmaas has long moved on from chess because he was too good for it.<br />
<br />
17. Gmaas is so interesting that an entire science has been devoted to studying him: Gmaasology.<br />
<br />
18. Gmaas is the only known living being who has a Ph.D. in Gmaasology.<br />
<br />
19. Most universities, including Harvard, are beginning to offer MAs in Gmaasology.<br />
<br />
20. Gmaasology is one of the most eminent fields of science, falling behind Physics, Biology, Chemistry, Economics, Geology, and Computer Programming.<br />
<br />
21. Gmaas wants his AoPS Wiki page to be the longest ever. EDIT: Sadly, the Gmaas page is only the fourth-longest page on AoPS wiki. It has around 50,000 bytes. EDIT: The Gmaas page is getting closer and closer! Gmaas has beaten Primitive Pythagorean Triple and Proofs without words and is the second-longest AoPS Wiki page. It now has around 60,000 bytes. However, it will still be a challenger to overcome 2008 most iT Problems, which has around 73,000 bytes. EDIT: Gmaas has beaten 2008 most iT Problems! It is the longest AoPS Wiki article ever. Gmaas's article has 89,119 bytes.<br />
<br />
22. Gmaas has the longest lifespan of any cat. He has lived for 3,141,592,653,589,793,238,462,643,383,279 years. (He is older than the universe.)<br />
<br />
23. Gmaas is the ancient Greek god of cats and catfish. EDIT: He is the god of everything<br />
<br />
24. Gmaas can turn things into gold. EDIT: Gmaas can turn anything into anything.<br />
<br />
25. Gmaas can eat lava. EDIT: Everyone can eat lava once. After you eat it once, you die. EDIT: Gmaas can eat anything.<br />
<br />
26. Gmaas's Theorem states that Gmaas knows the answer to any math problem. EDIT: That theorem was proved by Gmaas EDIT: Gmaas's Theorem has real-world applications: because Gmaas knows the answer to any math problem, you can use Gmaas to solve math problems. Gmaas is busy, so he charges a fee of one dollar for 1,000,000 math problems. EDIT: The fee has gone up. It is now 1,000,000 dollars for one math problem. Gmaas's technician made a mistake and reciprocated the fee.<br />
<br />
27. Gmaas can only be described as Gmaas. EDIT: Gmaas has an age, but his age changes all the time. Every second his age increases by one second.<br />
<br />
28. Gmaas should be capitalized to show respect. EDIT: It is normal to capitalize on people's names. EDIT: Gmaas isn't a person, he is a divine entity that takes the form of a cat, and should, therefore, be worshipped.<br />
<br />
29. The steps to summon Gmaas can be found at Talk: Gmaas.<br />
<br />
30. Gmaas owns your AoPS account 31.415926% of the time. EDIT: There is an exception to this: Gmaas owns his own account 99.9999% of the time. The only time when Gmaas did not control his AoPS account was when he had slow internet. For Gmaas, "slow internet" happens when it takes more than a nanosecond to load a webpage. EDIT: Gmaas owns every AoPS account at some point. EDIT: You are controlled by Gmaas. So actually, Gmaas owns your AoPS account 100% of the time, and his AoPS account is owned by him 314% of the time.<br />
<br />
31. Everyone, except for me, is Gmaas. EDIT: You are also Gmaas. Gmaas is not me nor you. Gmaas is in us all and also not in us all. Why? The power of Gmaas. Gmaas is an energy field created by all living things. It surrounds us and penetrates us. It binds the galaxy together.<br />
<br />
32. Gmaas used to be a dog, but he didn't like to be a dog. So he became a cat.<br />
<br />
33. Gmaas can be spotted in The Matrix at 31:41:59, metric time. EDIT: This fact is incorrect because there have only been 30 sightings, all of them inconsistent.<br />
<br />
34. The Metropolitan Museum of Art and the Louvre are Gmaas's private art collections from 3:14 AM to 3:15 AM. EDIT: The only exception was on the 3141st day after its opening. EDIT: All the paintings in these museums are secretly portraits of Gmaas in his most glorious human/animal forms.<br />
<br />
35. Gmaas is a Gmaas who is owned by Gmaas who is owned by Gmaas who is owned by Gmaas who is owned by Gmaas who is owned by Gmaas who is owned by Gmaas who is owned by Gmaas who is owned by Gmaas who is owned by Gmaas who is blah blah blah blah blah blah blah blah blah blah blah blah blah blah.<br />
<br />
36. Gmaas says hello. EDIT: Gmaas does not speak; he only uses mind signals. Speaking is too primitive for Gmaas.<br />
<br />
37. For one day, Gmaas was Richard Rusczyk, Gmaas, and David Patrick at the same time. It felt strange, so Gmaas stopped.<br />
<br />
38. Gmaas, in addition to being the oldest cat in history, the most powerful cat in history, and the most confusing cat in history is also the largest cat in history.<br />
<br />
39. Gmaas is dead--he was eaten for lunch. EDIT: The above sentence is incorrect. Gmaas has not sent a gamma-ray burst to destroy the planet, which has happened every time someone has eaten Gmaas.<br />
<br />
40. Gmaas is the creator of the BCPI Ai project.<br />
<br />
41. Gmaas exists in <math>2\pi^2</math> dimensions because he doesn't like string theory.<br />
<br />
42. Christmas was supposed to be called Gmaasmas. Until it wasn't. EDIT: Christ is Gmaas. EDIT: Why? Because of the power of Gmaas.<br />
<br />
43. <math>\pi</math> is a representation of how many pies Gmaas has eaten. EDIT: The number <math>\pi</math> was created by Gmaas. He took a ten-sided die and flipped it an infinite number of times. The numbers he rolled became the digits of <math>\pi</math>.<br />
<br />
44. <math>e</math> is a representation of how many days Gmaas forgot to eat. EDIT: The number <math>e</math> was created by Gmaas. He took a book that has infinite pages and flipped to a random page. The digits of the page number became digits of <math>e</math>. EDIT: That is impossible. The previous fact would mean that <math>e</math> has the last digit, which it does not. EDIT: That is why Gmaas is still flipping to this day. EDIT: Why would he still be doing that? That would be boring. EDIT: Gmaas is not flipping the book now because he can flip an infinite amount of pages in <math>\frac{1}{\infty}</math> seconds. EDIT: Then why isn't he done? EDIT: The power of Gmaas. EDIT: The editors of the Gmaas article like to make long chains of edits, don't we? : Yes, we do. : I do too. So do I. EDIT: The number of edits only verifies how high-quality this holy bible of Gmaas is, because, with each edit, this bible becomes better. That is exactly why we are editing this. I will make one more edit, just to respect Gmaas EDIT: Gmass rules! <br />
<br />
45. Gmaas is the creator of everything including nothing.<br />
<br />
46. According to recent DNA tests, famous historical people, such as Euclid, Julius Caesar, Omar Khayyam, George Washington, and Ramanujan are Gmaas in disguise. Gmaas has been thousands of people; only 99.9% of them were important historical figures. EDIT: They aren't dead. They're still alive. They are all dead reincarnations of Gmaas. Gmaas only has one reincarnation at a time. He is right now a cat living in sseraj's house.<br />
<br />
47. Gmaas is a cat. EDIT: How many times do we say this? EDIT: Very many times. EDIT: Gmaas can be anything, but he chooses to be a cat. EDIT: He has been a human dozen of times. Gmaas painted the Lascaux cave paintings.<br />
<br />
<br />
48. Gmaas has the following powers: trout, carp, earthworm, and catfish. Gmaas never uses any of them because Gmaas has an infinite number of powers. EDIT: Gmaas has used his catfish power several times. EDIT: Gmaas once used all his powers 3,141,592,653,589,793,238,462,643,383,279 times in 1 second.<br />
<br />
49. Gmaas was once spotted in Minecraft chewing a tree. EDIT: The tree broke. EDIT: Gmaas once broke a Nokia. EDIT: Gmaas can break anything except for Gmaas's logic. It is too strong. EDIT: Gmaas is strong.<br />
<br />
50. Gmaas was spotted in Roblox eating a taco cat. EDIT: Tacocat is just what happens when Gmaas sheds. Shedding is annoying for Gmaas, so he sheds no more. Therefore, there are only 271,828,182 taco cats in the world. EDIT: However, Tacocats reproduce, so they are not in danger of extinction.<br />
<br />
51. Gmaas would like to go to Taco Bell, but Gmaas goes to Wendy's instead. No one knows why. EDIT: Because Taco Bell doesn't serve tacocats.<br />
<br />
52. Gmaas real name is Grayson Maas. He is the CEO of AoPS. EDIT: Gmaas's real name is Gmaas. He is not the CEO of AoPS. EDIT: Gmaas has always been the master of AoPS as he is AoPS.<br />
<br />
53. Gmaas has a pet pufferfish named Pafferfash. EDIT: He also has a goldfish named Sylar.<br />
<br />
54. Gmaas has colonized the universe. EDIT: Gmaas created the universe, so he is allowed to claim control over it. EDIT EDIT: Gmaas created every universe.<br />
<br />
55. Some people think that Gmaas is human. However, this has never been proven. Many AoPSers believe Gmaas is a cat. EDIT: Gmaas is a cat. EDIT: Yeah, we've said that already. EDIT: It does not matter how many times we say it; it will always be true. EDIT: Gmaas is a cat. EDIT: Right now he is a cat, but many of his lives have been other species. EDIT: He has been a dog, as said before, but it was too boring.<br />
<br />
56. Gmaas started Pastafarianism. But then converted to Catholicism because Gmaas knows all EDIT: In that religion, one can only eat pasta.<br />
<br />
57. Gmaas could eat your hand, but he would not because hands taste bad.<br />
<br />
58. According to the Interuniversal Gmaas Society, 17.548 percent of the universe's population thinks that Gmaas is spelled "Gmass". EDIT: In case you don't know already, the name Gmass is spelled Gmaas. Alternative spellings include GMAAS, gmaas, gmaas, Gmaas, Gmail, Maas, G. Maas, G. Mass, Gabriel Maas, Genius of Maas, General Maas, Greek Mass, and the big fluffy kitty who lives in sseraj's house. These are no longer accepted spellings, and Gmaas is the current acceptable spelling.<br />
<br />
59. The Interuniversal Gmaas Society was founded in 1314 on May 9th at 2:06:53 PM. EDIT: Ever since then, Gmaas day has been celebrated on May 9th.<br />
<br />
60. The Interuniversal Gmaas Society has just reconstructed a lost book about Gmaas from Lucretius's De Rerum Natura. They researched this for three years. EDIT: A few years ago the Society compiled a biography of Gmaas's last twenty lives. EDIT: The only copies of these biographies are locked in the Gmaasian Library beneath the Library of Congress. EDIT: See the Gmaasology page for more information on these projects and others made by the Interuniversal Gmaas Society.<br />
<br />
61. The Interuniversal Gmaas society has found out all of the information and more. For details on the history of the Interuniversal Gmaas Society, see the Gmaathamatics page.<br />
<br />
62. GMAAS likes to surprise unsuspecting people. People cannot surprise GMAAS because GMAAS knows what everyone is doing and will do.<br />
<br />
63. Gmaas loves sparkly mechanical pencils. EDIT: Gmaas has eaten several mechanical pencils. EDIT: He absorbed them and became colorful for 0.271828182846 seconds. EDIT: Then, he came colorful for 3.1415926535897932384626433832 more seconds.<br />
<br />
64. This page is Gmaas's holy book where people go to worship Gmaas in Maas. EDIT: This is an unusual holy where everyone edits it. EDIT: That is the point. Gmaas is too lazy to write or to hire someone to write his holy book, so he lets people write it for free. EDIT: Gmaas does not like being called lazy. Our language is simply too unimportant for him to waste time on.<br />
<br />
65. Gmaas tastes like a furry meatball. EDIT: No one has ever tasted Gmaas's sacred body before. EDIT: Once, he was a catfish, and someone ate him for dinner. Gmaas was angry and the entire planet exploded. (This was on the planet, Demeter. It blew up into so many pieces that the Asteroid Belt was formed. The biggest asteroid in the belt is called Ceres, the Roman version of Demeter, in honor of the lost planet.)<br />
<br />
66. Gmaas's favorite food is pepperoni pizza. EDIT: Gmaas's favorite food is turnips. EDIT: Gmaas hates catnip and turnips, and pepperoni. He only likes alien alienish H2So4. EDIT: He does love turnips. He has a secret turnip garden under sseraj's house.<br />
<br />
67. Gmaas is Johnny Johnny's Papa. EDIT: We'll never know. EDIT: Gmaas caught Johnny Johnny eating sugar and lying. He is Johnny Johnny's Papa.<br />
<br />
68. Gmaas is in you, and Gmaas is in you, and Gmaas is in me. EDIT: Gmaas is in all cats. EDIT: He is not in every cat. The Guinness Book of World Records has a cat that does not have any Gmaas. EDIT: Gmaas invented The Guinness Book of World Records. EDIT: Gmaas invented the world. EDIT: Gmaas will also destroy the world.<br />
<br />
69. Gmaas always remembers not to destroy the universe. EDIT: Once he forgot and had to travel back in time to stop it.<br />
<br />
70. Gmaas created many user's accounts. EDIT: All accounts on AoPS are Gmaas in disguise since you are Gmaas in disguise. Except for maybe Geoflex and CrazyEyeMoody.EDIT: Everyone is Gmass, even Geoflex and CrazyEyeMoody EDIT: How? EDIT: The power of Gmass.<br />
<br />
71. Gmaas is both living and nonliving. EDIT: He is living 90% of the time. Every once in a while he takes a break and dies.<br />
<br />
72. Gmaas cannot comprehend the stupidity of humans.<br />
<br />
73. All hail the Gmaas cloud! EDIT: Gmaas is a cloud: a cloud of electrons and nuclei.<br />
<br />
74. Some things are beyond possible human comprehension. Nothing is beyond Gmaas. EDIT: The only thing beyond Gmaas is his tail; he has never managed to eat it. EDIT: Once he ate it. It tasted bad, so he didn't ever eat it again.<br />
<br />
75. Gmaas eats food and resides at King Arthur's throne when he feels like it. EDIT: King Arthur is dead. However, Welsh folk stories say that he will come back if the Welsh people are in trouble. EDIT: King Arthur lives on paper flour bags. He came back when the Welsh people didn't have enough bread. EDIT: Because Gmaas ate 31415926535897932984626433 loaves of bread.<br />
<br />
76. Gmaas owns a rabbit. EDIT: Gmaas ate it on March 19, 2019. It reincarnated on the other side of the planet. EDIT: Gmaas ate it again on April 31, 2019.<br />
<br />
77. Gmaas is both singular and plural. EDIT: It is usually singular. EDIT: The plural of Gmaas in English and Latin is Gmaases. (Gmaas is a third declension noun: Gmaas, Gmaasis, m.) EDIT: But there is no use for the plural, because there is only one Gmaas.<br />
<br />
78. Gmaas eats disbelievers as if they were donuts for breakfast. (Yet I'm somehow still alive. Do you think Gmaas ate my soul?) EDIT: Yes, I do. Gmaas is just typing through your account. EDIT: Gmaas typed through everyone's account. EDIT: Gmaas owns most AoPSers, including me. So that's why I'm typing. EDIT: That is why everyone here is typing.<br />
<br />
79. Gmaas knows Jon Snow's parents. EDIT: Gmaas was Jon Snow's parents for 0.3141592653589793238 seconds, but it felt weird. So he became Gmaas again.<br />
<br />
80. All Gmaas article editors will be escorted to Gmaas heaven after they die. EDIT: I hope so because I edited this article. EDIT: Me too. EDIT EDIT: Me three. EDIT EDIT EDIT: That are good!<br />
<br />
81. Gmaas won all the wars. EDIT: He did not win the Intergmaasian War, which was between Gmaas's head and his tail. His tail won. Two flees died in the war. EDIT: Stefán Karl Stefansson died in the war, which made Gmaas very sad. Because of this, Gmaas started the world peace movement.<br />
<br />
82. Gmail was named after Gmaas. EDIT: Google was named after Gmaas. EDIT: Almost every word starting with G is named after Gmaas. EDIT: Every word starting with G is named after Gmaas.<br />
<br />
83. Gmaas ate cat-food today. EDIT: Gmaas also ate it yesterday. EDIT: Only because there was no alien alienish H2So4.<br />
<br />
84. Gmaas won Battle For Dream Island and Total Drama Island. EDIT: Gmaas made Dream Island. And he ate it. It tasted like dirt.<br />
<br />
<br />
85. Somehow Gmaas exists at all places at the same time. EDIT: Gmaas does not exist in my kitchen. EDIT: I'll just go check. Aaaaaaaaah! He is in my kitchen. He is eating everything! EDIT: Seriously? Oh ya, the power of Gmass.<br />
<br />
<br />
86. Gmaas can lift with Gmaas's will. EDIT: Gmaas can lift with no one's will while he is sleepwalking.<br />
<br />
87. Gmaas is the rightful heir to the Iron Throne. EDIT: Gmaas made the Iron Throne.<br />
<br />
<br />
88. Gmaas is Teemo in League of Legends because Gmaas made LoL and they made an honorary Gmaas character. EDIT: LoL must be used in this article more than once. EDIT: It is. In fact, twice in this message.<br />
<br />
89. Gmaas started the Game of Thrones. EDIT: Gmaas will end the Game of Thrones.<br />
<br />
90. Gmaas has killed himself hundreds of times. He was reincarnated as a different species each time. EDIT: Gmaas has only died two times. Other times he was putting on a magic show. The kids were very impressed. EDIT: Gmaas has died and reincarnated thousands of times.<br />
<br />
91. Gmaas created everything after puking. EDIT: He could not have puked because he is a god. Gods do not do that. EDIT: Gmaas does that. EDIT: Why? EDIT: The power of Gmaas. EDIT: He almost never does it, only if he wants to.. Also he did not puke and made everything.<br />
<br />
<br />
92. Gordan's last name was named after Gmaas. EDIT: But Gmaas did not want people disrupting his beauty sleep. So he changed it.<br />
<br />
This article is spam<br />
93. Gmaas is more powerful than Gohan.<br />
<br />
94. Gmaas is over 90000 years old. EDIT: Gmaas is trillions of years old.<br />
<br />
95. Gmaas has 1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 cat lives, maybe even more. Gmaas has 0 dog lives. EDIT: He has 314,159,265 fish lives. EDIT: Out of Gmaas's 314,159,265 fish lives, 271,828,182 are catfish lives. He has used up 141,421,356 of them. EDIT: Gmaas has infinitely lives of all types. EDIT: How? EDIT: The power of Gmaas.<br />
<br />
96. Who wrote Harry Potter? None other than Gmaas himself. EDIT: That is incorrect. EDIT: The above post is irrelevant. Gmaas created J. K. Rowling. Therefore, he created Harry Potter. EDIT: Gmaas has strong logic. No one can break it. Not even Gmaas himself. He is still trying to this day. EDIT: Why? EDIT: The power of Gmass.<br />
<br />
97. Gmaas created the catfish. EDIT: See a few posts above for more information about Gmaas and catfish.<br />
<br />
98. Gmaas has proven that the universe is infinite by traveling to the edge of the universe in a second. EDIT: He has never repeated this experiment because Gmaas is busy and has better things to do.<br />
<br />
99. Gmaas founded Target, but then Gmaas sued them for making the mascot look like a dog when it was supposed to look like Gmaas. EDIT: They went broke because Gmaas sued them but then Gmaas ate a fudge popsicle that made him super hyper and he made Target not broke anymore in his hyperness.<br />
<br />
100. Everyone has a bit of Gmaas inside them. EDIT: I don't. EDIT: Yes, you do. EDIT: Gmass: LoL<br />
<br />
101. Gmaas likes to eat popsicles. Especially the fudge ones that get him hyper. EDIT: Gmaas is a popsicle. EDIT: Then how come Gmaas hasn't melted? EDIT: The power of Gmaas.<br />
<br />
102. When Gmaas is hyper, he runs across Washington D.C. and grabs unsuspecting pedestrians, steals their phones, hacks into them, and downloads PubG onto their phone.<br />
<br />
103. Gmaas's favorite cereal is fruit loops. Gmaas thinks it tastes like unicorns jumping on rainbows. EDIT: Gmaas eats unicorns jumping on rainbows like a toddler eats Goldfish.<br />
<br />
104. Gmaas thinks that the McChicken has too much mayonnaise. EDIT: Gmaas thinks McDonald's is not good enough for him. He like KFC better.<br />
<br />
This article is yellow idk why<br />
105. Gmaas is a champion pillow-fighter. EDIT: Gmaas invented pillows.<br />
<br />
This article is spam<br />
106. Gmaas colonized Mars. EDIT: Gmaas also colonized Jupiter, Pluto, and several other galaxies. Gmaas cloned little Gmaas robots (with Gmaas's amazingly robotic skill of coding) and put them all over a galaxy called Gmaasalaxy. EDIT: Gmaas has colonized the whole universe.<br />
<br />
This article is spam ==== This article is spam ==== This article is spam ==== This article is spam ==== This article is spam ==== This article is spam ==== This article is spam ==== This article is spam<br />
This article is spam<br />
107. Gmaas can make every device play "The Duck Song" at will. EDIT: "The Duck Song" was copied off of the "Gmaas song," but the animators though Gmaas wasn't catchy enough.<br />
<br />
108. Gmaas once caught the red dot and ate it. EDIT: Gmaas is a red dot.<br />
<br />
109. Gmaas's favorite color is Gmaasian blue, a very rare blue that shines with the brightness of lightning. EDIT: it's <math>1000^{1000}</math> times brighter than lightning. Gmaasian blue occurs when a meteor hits the earth and usually is only seen for a few seconds. Only Gmaas has good enough eyesight to see it for that short a time.<br />
<br />
110. Gmaas can create wormholes and false vacuums. EDIT: He is made out of exotic matter.<br />
<br />
111. Gmaas is a champion PVP Minecraft player.<br />
<br />
112. Gmaas doesn't like tacos. The last time he tried one he turned into a mouse and then caught himself.<br />
<br />
113. Gmaas is the coach of True Ninja Music and Myth.<br />
<br />
114. Gmaas caught a CP 6000 Mewtwo with a normal Pokeball in Pokemon Go.<br />
<br />
115. Gmaas founded Costco.<br />
<br />
116. Gmaas does not need to attend the FIFA World Cup. If Gmaas did, he would start the game with a goal and break the ankles of everyone watching the World Cup, including you, at the same time in a fraction of a second, even if you are watching from a device. EDIT: Gmaas created your device. EDIT: Gmaas is your device.<br />
<br />
117. Gmaas can solve any puzzle instantly except for the 3x3 Rubik's Cube. EDIT: When Gmaas is handed a 3x3 Rubik's Cube, it is always already solved. Why? The power of Gmaas.<br />
<br />
118. Gmaas caught a CP 20,000 Mewtwo with a normal Pokeball and no berries blindfolded first try in Pokemon Go.<br />
<br />
119. When Gmaas flips coins, they always land tails, except when Gmaas makes bets with Zeus.<br />
<br />
120. On Gmaas's math tests, Gmaas always gets <math>\infty</math>. EDIT: He gets a 26 on the AMC8 every year. The results never show him because Gmaas is no longer in middle school.<br />
<br />
121. Gmaas's favorite number is <math>\pi</math>. It is also one of Gmaas's favorite foods. EDIT: Gmaas created <math>\pi</math>, as well as most other constants, such as <math>e</math> and <math>\sqrt{2}</math>.<br />
<br />
122. Gmaas's burps created all gaseous planets.<br />
<br />
123. Gmaas beat Luke Robatille in an epic showdown of catnip consumption.<br />
<br />
124. Gmaas's wealth is unknown, but it is estimated to be more than Scrooge's. EDIT: It may be more than John D. Rockefeller. EDIT: More accurate estimates predict that Gmaas's wealth is infinite.<br />
<br />
125. Gmaas has a summer house on Mars. EDIT: Gmaas has a fall house on Venus. EDIT: Gmaas has a winter house on Jupiter. EDIT: Gmaas has a spring house on Earth. EDIT: Gmaas also experiences a fifth season called wintrautumn. It happens during November and December and is the cross between fall and winter. Everything is dreary, but there is no snow. Gmaas spends wintrautumn in his house on Venus, where he is incinerated daily. He reincarnates every night through the power of Gmaas. EDIT: Gmaas invented a new season on Feb. 31, 2019, called winter-summer. It is spring but transcends spring.<br />
<br />
126. The Earth and all known planets are Gmaas's hairballs.<br />
<br />
This article is spam<br />
127. Gmaas attended Harvard, Yale, Stanford, MIT, UC Berkeley, Princeton, Columbia, and Caltech at the same time using a time-turner.<br />
<br />
128. Gmaas attended Hogwarts and was a perfect. EDIT: Gmaas is headmaster. EDIT: Hogwarts was supposed to be called Hogmaas.<br />
<br />
129. Mrs. Norris is Gmaas's archenemy. Gmaas yawned, and Ms. Norris was petrified. EDIT: Gmaas is the basilisk, and he let Harry Potter pet him. Harry did not kill the basilisk, he only gave Gmaas a haircut. EDIT: Gmaas hates having a haircuts, so he reincarnated Voldemort to punish Harry.Edit: Not true at all.<br />
<br />
This article is spam<br />
130. Gmaas is a demigod and attends Camp Half-Blood over summer. Gmaas is the counselor for the Apollo cabin because cats can be demigod counselors too. EDIT: Apollo was one of the many reincarnations of Gmaas.<br />
<br />
131. Gmaas has completed over 2,000 quests and is very popular throughout Camp Half-Blood. Gmaas has also been to Camp Jupiter. EDIT: Gmaas is Camp Jupiter, he is also Camp Half-Blood. EDIT: How? EDIT: The power of Gmaas.<br />
<br />
132. Percy Jackson was only able to complete his quests because Gmaas helped him. EDIT: Gmaas is Percy Jackson. You are Gmaas, but Gmaas is not you.<br />
<br />
133. Gmaas painted the Mona Lisa, The Last Supper, and A Starry Night. EDIT: Gmaas knows that their real names are Gmaasa Lisa, The Last Domestic Meal, and Far-away Light.<br />
<br />
134. Gmaas knows that the Blood Moon is just the red dot. He has not caught it yet. EDIT: He caught it during the super blue blood moon.<br />
<br />
135. Gmaas attended all the Ivy Leagues.<br />
<br />
136. I am Gmaas. EDIT: No you are not. You only have part of Gmaas inside of you. EDIT: I am also Gmaas. EDIT: But it is I who am Gmaas. EDIT: Gmaas is in us all. EDIT: Gmaas is all of us yet none of us. EDIT: Gmaas is a cat. EDIT: He is only in a cat form right now. He can be whatever he wants to be. EDIT: This chain of edits has superseded another chain of edits on this page for the record of the longest chain of edits on AoPS Wiki. EDIT: But the edits in this chain tend to be shorter than most. EDIT: You're right. But we sure do love strings of edits, don't we? EDIT: Gmaas makes the edits. He is in your head spinning edits in your brain. EDIT: Gmaas is made to be edited. EDIT: Gmaas pays people to edit. EDIT: Some people edit even without Gmaas's payment. They do it because they are believers.<br />
<br />
137. In 2018 Gmaas once challenged Magnus Carlsen to a chess game. Gmaas won every round. EDIT: Gmaas ate the chess pieces afterward. They tasted funny.<br />
<br />
138. Gmaas was captured in 2017 but was released due to sympathy. EDIT: Gmaas was only captured in his concrete form; his abstract form cannot be processed by a feeble human brain.<br />
<br />
139. Gmaas's fur is white, black, grey, yellow, red, blue, green, brown, pink, orange, turquoise, and purple at the same time. EDIT: Gmaas can make his fur any color he wants. EDIT: Gmaas's fur color can be ultraviolet.<br />
<br />
140. Gmaas crossed the event horizon of a black hole and ended up in the AoPS universe.<br />
<br />
141. Gmaas crossed the Delaware River with Washington. EDIT: Gmaas also crossed the Atlantic with the pilgrims.<br />
<br />
142. If you can capture a Gmaas hair, Gmaas will give you some of his Gmaas power. EDIT: Gmaas does not shed and will eat anyone who has Gmaas hair. EDIT: Gmaas used to shed. The sheddings became tacocats.<br />
<br />
143. Chuck Norris makes Gmaas jokes. EDIT: Those jokes all praise Gmaas.<br />
<br />
144. Gmaas is also the ruler of Oceania, Eastasia, and Eurasia. EDIT: Gmaas wrote the book "1984."<br />
<br />
145. Gmaas killed Big Brother by farting on him. Though Gmaas was caught by the Ministry of Love, Gmaas escaped easily. EDIT: Gmaas used to be Big Brother. EDIT: Gmaas destroyed the Ministry of Love.<br />
<br />
146. Gmaas was not affected by Thanos's snap; in fact Gmaas is the creator of the Infinity Stones. EDIT: Gmaas is Thanos.<br />
<br />
147. Everyone knows that Gmaas is a god. EDIT: That is because he is a god.<br />
<br />
148. Gmaas also owns Animal Farm. Napoleon was Gmaas's servant. EDIT: Napoleon was Gmaas's slave.<br />
<br />
This article is spam<br />
149. Gmaas is the only person who knows where Amelia Earhart is. EDIT: Gmaas! Please tell us! It would be a great contribution to historical knowledge! EDIT: Gmaas responds, "No."<br />
<br />
150. Gmaas is the only cat that has been proven transcendental. EDIT: Gmaas has been proved to be normal as well.<br />
<br />
151. Grumpy cat reads Gmaas memes. EDIT: Grumpy cat then steals them and claims they're his. Gmaas isn't very happy about that, either. EDIT: That is why he looks grumpy in the memes.<br />
<br />
152. The reason why AIME cutoffs aren't out yet is that Gmaas refused to grade them due to too much problem misplacement. EDIT: Gmaas controls the MAA. EDIT: Gmaas founded the MAA. EDIT: Gmaas is the MAA.<br />
<br />
153. Gmaas dueled Grumpy Cat and won. Gmaas wasn't trying. EDIT: Gmaas killed Grumpy cat. EDIT: Gmaas revived Grumpy cat because he has not other rival.<br />
<br />
154. Gmaas sits on the statue of Pallas and says forevermore. EDIT: When Gmaas was a statue, people hid him in a basement and forgot about him. Then civilization collapsed and the Middle Ages began. People finally discovered and melted down the statue of Gmaas around 1350 to make a church bell. Gmaas was free and reincarnated again, bringing about the Renaissance. EDIT: Despite the efforts of the recently founded National Gmatthematical Society of Florence, the statue was melted down. For more information about the National Gmatthematical Society of Florence, see the Gmaasology page.<br />
<br />
155. Gmaas is a big fan of Edgar Allan Poe because he is actually Poe. EDIT: He became Poe during his thirty-year depression in the 19th century.<br />
<br />
156. Gmaas does merely not use USD; he owns it.<br />
<br />
157. In 2003, Gmaas used elliptical curves to force his reign over AoPS.<br />
<br />
158. "Actually, my name is spelled "GMAAS"." (Citation needed)<br />
<br />
159. Gmaas is Link in the Legend of Zelda. He despises Calamity Ganon in Breath of the Wild. "Too much of a hog..."<br />
<br />
160. Gmaas is the smartest living being in the universe. EDIT: Notice how this sentences says "living being," so Gmaas might be dummer than some dead person. EDIT: Gmaas is the smartest being that has lived, lives, and will live. EDIT: How? EDIT: The power of Gmaas. EDIT: HOW DARE YOU QUESTION THE POWER OF GMAAS!?!?!?<br />
<br />
161. Gmaas helped Sun Wukong on the Journey to the West.<br />
<br />
162. Gmaas was the creator of Wikipedia.<br />
<br />
163. Gmaas can hack any website he desires. EDIT: He can edit any website with the words Gmaas in it. EDIT: AoPS includes the word Gmaas right here, so Gmaas can hack it. EDIT: Gmaas can edit any website he desires.<br />
<br />
164. Gmaas is the basis of Greek and Egyptian mythology. EDIT: He is also the basis for Aztec mythology. He once had a craving for human flesh, so he created human sacrifice.<br />
<br />
165. Gmaas once sold Google to a man for around 12 dollars! EDIT: Gmaas has not spent those 12 dollars and is waiting for the economy to crash. EDIT: Why would he do that? EDIT: The power of Gmaas. EDIT: Gmaas is smarter than you think he is. Do you think you know how smart Gmaas is now? If so, then you are still wrong.<br />
<br />
This article is spam<br />
166. Gmaas uses a HP printer. It is specifically a HP 21414144124124142141414412412414214141441241241421414144124124142141414412412414 printer.<br />
<br />
167. Gmaas owns all AoPS staff including Richard Rusczyk. EDIT: Richard Rusczyk is one of Gmaas's many code names.<br />
<br />
168. Gmaas saw Yoda's birth. EDIT: Gmaas was Yoda's father. EDIT: Was Gmaas green like Yoda back then? EDIT: Yes. EDIT: Why? EDIT: The power of Gmaas.<br />
<br />
169. Gmaas's true number of lives left is unknown; however, Gmaas recently confirmed that he had at least one left. Why doesn't Gmaas have so many more lives than other cats? The power of Gmaas. EDIT: This is all not true. EDIT: This is all true. EDIT: Gmaas has an infinite number of lives. EDIT: Gmaas does not have an infinite number of lives. He just has an unlimited number of lives. EDIT: Gmass has an infinite and unlimited number of lives.<br />
<br />
170. sseraj once spelled Gmaas as gmASS by accident in Introduction to Geometry (1532). sseraj’s life was never the same afterwards. EDIT: Gmaas created sseraj. He is a Gmaas, but without the face, body, legs, and tail.<br />
<br />
171. Gmaas has beaten Chuck Norris, The Rock, and John Cena all together in a fight.<br />
<br />
172. Gmaas is a South Korean, North Korean, Palestinian, Israeli, U.S., Soviet, Russian, and Chinese citizen at the same time. EDIT: Gmaas is a citizen of every country in the world. Gmaas seems to enjoy the country of AoPS best, however.<br />
<br />
173. "I am sand" destroyed Gmaas in FTW. EDIT: Because Gmaas accidentally died, he defeated "I am sand" 3,141,592,653 times after.<br />
<br />
174. sseraj posted a picture of Gmaas with a game controller in Introduction to Geometry (1532).<br />
<br />
175. Gmaas plays Roblox mobile edition and likes Minecraft, Candy Crush, and Club Penguin Rewritten. He also loves Catch that fish. EDIT Gmass likes Minecraft better than Roblox<br />
<br />
176. Gmaas is Roy Moore's horse in the shape of a cat.<br />
<br />
177. Gmaas is a known roblox/club penguin rewritten player and is a legend at it. He has over <math>289547987693</math> roblox and <math>190348</math> in CPR.<br />
<br />
178. This is all hypothetical. EDIT: This is all factual. For reference, see an earlier post.<br />
<br />
179. Gmaas's real name is Princess. He has a sibling named Rusty/Fireheart/Firestar. EDIT: That is incorrect. Gmaas's real name is Gmaas. EDIT: Gmass named himself. That's why his name is amazing.<br />
<br />
180. Gmaas is capable of salmon powers. EDIT: Gmaas is capable of everything. Nothing is beyond Gmaas.<br />
<br />
181. Gmaas told Richard Rusczyk to make AoPS.<br />
<br />
182. The Gmaas is everything. Yes, you are part of the Gmaas-Dw789. EDIT: Gmaas is older than the universe. He is more than everything.<br />
<br />
183. The Gmaas knows every dimension up to 99999999999999999999999999999999999999999999999999999999999999999999999999999999999th dimension. EDIT: He is working on the higher dimensions presently. It takes up 1% of his time. He spends the remaining 99% of his time eating, sleeping, and being. EDIT: Does that mean he stops being while he learns higher dimensions? EDIT: Yes. EDIT: Why? EDIT: The power of Gmaas.<br />
<br />
This article is spam<br />
184. Gmaas went into a black hole and exited the white hole. He ended up in the 15th dimension where people drink tea every day. He stole 31,415,926,535,897,932,384 buckets of tea.<br />
<br />
This article is spam<br />
185. Gmaas is "TIRED OF PEOPLE ADDING TO HIS PAGE!!" (Maas 45). EDIT: This is Gmaas's holy, so he wants to have a longer version. For reference, see Maas 3,141,592,653,589,793,238,462. Gmaas is too lazy to write this book himself or to hire someone to do this for him, so he has assembled a group of unpaid freelancers on AoPS to write his holy book for him. He is watching it grow. However, Gmaas sometimes sees a comment that he does not like on the Gmaas article. He possesses an editor of Gmaas and makes him/her delete it. EDIT: AoPS itself is just an elaborately concealed piece of Gmaas propaganda. EDIT: How dare you reveal the truth! *Zaps previous editor out of existence* Now, where were we...<br />
<br />
186. Gmaas is a Gmaas who is actually Gmaas. EDIT: Gmaas is omnipotent and omniscient. However, he is not always benevolent.<br />
<br />
187. Gmaas has a penguin servant who runs GMAASINC. The penguin may or may not be dead. He had another penguin, who is mostly alive.<br />
<br />
188. Gmaas owns a TARDIS, and can sometimes be seen traveling to other times for reasons unknown. EDIT: Gmass is the doctor<br />
<br />
189. Gmaas knows how to hack into top secret AoPS community pages. EDIT: AoPS is just Gmaas's elaborately-concealed blog.<br />
<br />
This article is spam<br />
190. Gmaas used to be river clan cat who crossed the event horizon of a black hole and came out the other end. EDIT: He eventually created sseraj and has lived with sseraj ever since.<br />
<br />
191. Gmaas is king of the first men, the anduls.<br />
<br />
192. Gmaas is a well known professor at Meowston Academy. EDIT: He is professor of Gmaasology there. EDIT: Gmaas founded Meowston Academy. EDIT: It is actually called Gmaaston Academy<br />
<br />
193. Gmaas comes from Gmaas Land, a magical place where pie is infinite and everything starts with a g<br />
<br />
194. Gmaas is the CEO of Caterpillar.<br />
<br />
195. Gmaas drinks at Starbucks everyday.<br />
<br />
196. Gmaas is addicted to tuna, along with other more potent fish, such as salmon and trout.<br />
<br />
197. Gmaas likes turning into fish and catching himself. EDIT: So far, Gmaas has spent 2,718,281 of his many lives as a catfish. However, sometimes, he has been catched as a catfish by other people. Luckily, Gmaas has always escaped.<br />
<br />
198. Gmaas won the reward of being cutest and fattest cat ever--he surpassed grumpy cat. (He also out-grumped grumpy cat!!!) EDIT: He is in the Guinness Book of World Records for fluffiest cat ever.<br />
<br />
199. He was last sighted at 1665 Alligator Swamp-A 4/1/18 at 3:14:15.92653589793238462 PM.<br />
<br />
200. Gmaas is the owner of sseraj, not his pet. EDIT: Gmaas also created sseraj.<br />
<br />
This article is spam<br />
201. Gmaas is the embodiment of life, the universe, and beyond.<br />
<br />
202. Gmaas watches memes about Gmaas. EDIT: All memes originate with Gmaas, but they are often posted by others. EDIT EDIT: Gmaas is getting rather tired of memes.<br />
<br />
203. After death Gmaas became the god of hyperdeath and obtained over 9000 souls.<br />
<br />
204. One of Gmaas's many real names is Pablo Diego José Francisco de Paula Juan Nepomuceno María de los Remedios Cipriano de la Santísima Trinidad Ruiz y Picasso.<br />
<br />
This article is spam<br />
205. Gmaas is a certified Slytherin. EDIT: Gmaas is actually a certified Ravenclaw.<br />
<br />
This article is spam<br />
206. Gmaas once slept on sseraj's private water bed, so sseraj locked him in the bathroom. EDIT: Gmaas has superpowers that allowed him to overcome the horrors of Mr. Toilet while locked in the bathroom.<br />
<br />
207. Gmaas once sat on an orange on a pile of AoPS books, causing an orange flavored equation explosion.<br />
<br />
208. Gmaas conquered the moon and imprinted his face on it until asteroids came and erased it.<br />
<br />
209. Gmaas is a supreme overlord who must be given<cmath>1000^{1,000,000,000,000,000,000,000^{1,000,000,000,000,000,000,000}}</cmath>minecraft diamonds. EDIT: Gmaas owns Mojang, but Gmaas sued them when it was supposed to be called Gmaascraft. EDIT: A previous fact said that Gmaas only lost one lawsuit. Why is this Minecraft not called Gmaascraft if he won the lawsuit?<br />
<br />
210. Gmaas is the Doctor Who lord, sports Dalek-painted cars, and eats human finger cheese, custard, and black holes. EDIT: Gmaas once ate a white hole. Gmaas then exploded and made a new universe.<br />
<br />
211. Gmaas is everyone's favorite animal.<br />
<br />
This article is spam<br />
212. Gmaas is a Persian Smoke.<br />
<br />
213. Gmaas lives with sseraj.<br />
<br />
214. Gmaas dislikes geometry but enjoys number theory. EDIT: sseraj once posted a picture of Gmaas being grumpy after seeing an olympiad geometry problem.<br />
<br />
215. Gmaas is often overfed (with probability <math>\frac{3972}{7891}</math>), or malnourished (with probability <math>\frac{3919}{7891}</math>) by sseraj. EDIT: Gmaas does not need food. He just eats food because it tastes good. EDIT: Gmaas does not like vegetables.<br />
<br />
This article is spam<br />
216. Gmaas has<cmath>\sum_{k=1}^{267795} [k(k+1)]+GMAAS+GMAAAAAAAAAAS</cmath>supercars, excluding the Purrari and the 138838383 Teslas.<br />
<br />
This article is spam<br />
217. Gmaas employs AoPS. EDIT: Gmaas is the reason why AoPS exists. EDIT: Gmaas is the reason why everything exists.<br />
<br />
This article is spam<br />
218. Gmaas is a Gmaas with yellow fur and white hypnotizing eyes. EDIT: His fur is not always yellow. His fur can be wha== This article is spam == 219. Gmaas has the ability to divide by zero. EDIT: Gmaas knows what 1/0 is. What is it? We'll never know. EDIT: 1/0 = 0. How? The power of Gmaas. EDIT: The previous editor was wrong. 1/0 = Gmaas. EDIT: The previous editor was wrong. <math>\frac{1}{\infty}=</math> GMAAS<br />
<br />
220. Gmaas was born with a tail that is a completely different color from the rest of his fur. EDIT: Gmaas can change the color of his fur.<br />
<br />
This article is spam<br />
221. Gmaas's stare is very hypnotizing and effective at getting table scraps. EDIT: Gmaas's stare turned Medusa into rock, King Midas into gold, and sseraj into sseraj.<br />
<br />
222. Gmaas always appears several minutes before certain classes start as an administrator. EDIT: This is becoming more and more infrequent. Sadly, sseraj rarely posts pictures of Gmaas before classes anymore. EDIT: Why is this happening? EDIT: The power of Gmaas.<br />
<br />
223. Gmaas is an AoPS administrator under the alias Grayson Maas. EDIT: Gmaas always posts class surveys. He has a fake photo on his bio and has a real one on his community page. However, Gmaas himself has not yet posted on the Gmaas forum. EDIT: He also has not edited the Gmaas article, the Talk: Gmaas article, the Gmaasology article, or the sseraj article. EDIT: The final one is surprising because Gmaas knows more about sseraj than even sseraj does.<br />
<br />
224. Gmaas died from too many Rubik's cubes in an Introduction to Algebra A class, but he was revived by the Dark Lord at 12:13:37 AM the next day. EDIT: This was thanks in return for Gmaas reincarnating him during the Triumverate Tournament.<br />
<br />
225. It is uncertain whether or not Gmaas is a cat or is merely some sort of beast that has chosen to take the form of a cat (specifically a Persian Smoke). EDIT: He is both. EDIT: Actually, Gmaas is a cat. Gmaas said so, and science says so. EDIT: The profile for Gmaas on the list of AoPS teachers does not mention him being a cat. EDIT: The above post is irrelevant. Gmaas hides his identity under the alias Grayson Maas. EDIT: Gmaas us everything yet nothing. EDIT: How is that? The power of Gmaas.<br />
<br />
226. Gmaas is distant relative of the chair of the department of Gmaasology at Princeton. EDIT: In the last few years, many universities have been opening Gmaasology departments. For more information, see the Gmaasology page.<br />
<br />
227. Gmaas cannot be Force choked. Darth Vader learned that the hard way...<br />
<br />
228. Gmaas is famous, and mods always talk about him before class starts.<br />
<br />
229. Gmaas's favorite food is AoPS textbooks because they help him digest problems. EDIT: Gmaas wrote all AoPS textbooks but is never listed in the acknowledgments section. EDIT: That is because Gmaas is very humble except for when he isn't.<br />
<br />
230. Gmaas tends to reside in sseraj's fridge. EDIT: Gmaas once ate all sseraj's fridge food, so sseraj had to put him in the freezer. EDIT: Gmaas's fur can protect him from the harsh conditions of a freezer. EDIT: Then Gmaas ate all the food in sseraj's freezer. He enjoyed the ice cream in the freezer the most. EDIT: Gmaas also ate sseraj's freezer.<br />
<br />
231. Gmaas once demanded Epic Games to give him 5,000,000 V-bucks for his 569823rd birthday. EDIT: This is why Gmaas no longer has an Epic Games account. EDIT: Gmaas created Epic Games, though.<br />
<br />
232. Gmaas sightings are not very common. There have only been 30 confirmed sightings of Gmaas in the wild.<br />
<br />
233. Gmaas is a sage omniscient cat.<br />
<br />
<br />
235. Gmaas is looking for suitable places other than sseraj's fridge to live in.<br />
<br />
<br />
236. List of places where Gmaas sightings have happened:<br />
<br />
- 1. The Royal Scoop ice cream store in Bonita Beach Florida<br />
<br />
- 2. Inside the abandoned hospital on Rosevelt Island in New York City, which is also a feral cat sanctuary.<br />
<br />
- 3. MouseFeastForCats/CAT 8 Mouse Apartment 1083<br />
<br />
- 4. Gmaasology 2 (1440)<br />
<br />
- 5. Alligator Swamp A 1072<br />
<br />
- 6. Alligator Swamp B 1073<br />
<br />
- 7. Gmaasology A (1488)<br />
<br />
- 8. Introduction to Gmaasology A (1170)<br />
<br />
This article is spam<br />
- 9. Introduction to Gmaasology B (1529)<br />
<br />
- 10. Welcome to Panda Town Gate 1076<br />
<br />
- 11. Welcome to Gmaas Town Gate 1221<br />
<br />
- 12. Welcome to Gmaas Town Gate 1125<br />
<br />
- 13. 33°01'17.4"N 117°05'40.1"W (Rancho Bernardo Road, San Diego, CA)<br />
<br />
- 14. The other side of the ice in Antarctica<br />
<br />
- 15. Feisty Alligator Swamp 1115<br />
<br />
- 16. Intermediate Gmaas and Gmaasology 1207<br />
<br />
- 17. Posting student surveys<br />
<br />
- 18. USF Castle Walls - Elven Tribe 1203<br />
<br />
- 19. The Dark Lord's Hut 1210<br />
<br />
- 20. Gmathamatical Problem Series 1200<br />
<br />
- 21. Intermediate Gmaasology 1138<br />
<br />
- 22. Intermediate Number Theory 1476<br />
<br />
- 23. Introduction to Gmaasology 1204 on July 27, 2016<br />
<br />
- 24. Gmaasology B 1112<br />
<br />
- 25. Intermediate Algebra 1561 7:17 PM 12/11/16<br />
<br />
- 26. Nowhere Else, Tasmania<br />
<br />
- 27. The Gmaathamatics School of Gmaasology<br />
<br />
237. Gmaas can communicate with, and sometimes control, any other cats; however, this is very rare, as cats normally have a very strong will.<br />
<br />
238. A picture of Gmaas: http://i.imgur.com/PP9xi.png<br />
<br />
239. Gmaas met Mike Miller. EDIT: Gmaas ate Mike Miller.<br />
<br />
240. Gmaas got mad at sseraj once, so Gmaas locked sseraj in sseraj's freezer.<br />
<br />
241. Then, sseraj decided to eat all of Gmaas's hidden turnips in the freezer as punishment. EDIT: sseraj could not eat all of them so, he put the remaining turnips in the fire.<br />
<br />
242. Gmaas once ate a pie. EDIT: He only ate the first 31415926535897932384626433832 digits.<br />
<br />
153 A Gmaas bite is 314159265358979323846264 psi.<br />
<br />
154 Many people have met Gmaas, although many of these sightings are dubious. EDIT: It is just like alien sightings.<br />
<br />
155 Gmaas can talk but normally hates talking.<br />
<br />
156 Gmaas likes to eat his own fur. That's why he doesn't have any as of late<br />
<br />
157 Gmaas is bigger than an ant. EDIT: so is a regular cat<br />
<br />
158 Gmaas once ate the king of the ants. EDIT: Ants do not have kings; they have queens.<br />
<br />
159 Gmaas lives somewhere over the rainbow. EDIT: He lives in sseraj's house. EDIT: sseraj lives somewhere over the rainbow.<br />
<br />
160 Gmaas is an obviously omnipotent cat.<br />
<br />
- sseraj is known to post pictures of Gmaas on various AoPS classrooms. It is not known if these photos have been altered with the editing program called 'Photoshop.'<br />
<br />
171 Gmaas EDIT: This is a waste of a fact.<br />
<br />
172 sseraj has posted pictures of Gmaas in Introduction to Algebra before class started with the title "caption contest." Anyone who posted a caption mysteriously vanished in the middle of the night. EDIT: This has happened many times, including in Introduction to Geometric Gmaasology 1533, among other active classes. The person writing this did participate, and did not disappear. (You could argue Gmaas is typing this through his/her account...)<br />
<br />
173 Gmaas once slept in your bed and made it gray. EDIT: My bed is not gray. EDIT: Nor is mine.<br />
<br />
174 Richard Rusczyk actually Gmaas in disguise. EDIT: That is false. Gmaas is only in one form at a time. EDIT: This is also false, you are Gmaas and Gmaas owns you. EDIT: This is false too. Gmaas can only be in one form.<br />
<br />
175 Gmaas is suspected to be a cat in disguise. EDIT: He is a cat in disguise. See the results on the Gmaas poll in the Gmaas forum.<br />
<br />
176 Gmaas is a cat but has characteristics of every other animal on Earth. EDIT: Gmaas does not have the characteristic of being able to eat plankton. EDIT: Yes he does. He just has not decided to reincarnate as a blue whale yet.<br />
<br />
177 Pegasus was modeled off Gmaas. EDIT: Pegasus used to be Gmaas's pet, but Pegasus escaped and joined Bellerophon.<br />
<br />
178 Gmaas is the ruler of the universe and has been known to be the creator of the species "Gmaasians". EDIT: He is the universe<br />
<br />
179 There is a rumor that Gmaas is starting a poll. EDIT: He has. It is on the Gmaas forum, made by his minions. EDIT: We are all his minions.<br />
<br />
180 Gmaas is a Persian smoke who ran away, founded GmaasClan, and became a kitty-pet.<br />
<br />
181 There is a sport called "Gmaas Hunting" where people try to successfully capture Gmaas in the wild with video/camera/eyes. Strangely, no one has been able to do this, and those that have have mysteriously disappeared into the night. Nobody knows why. Many people have tried Gmaas Hunting, but they never have been successful.<br />
<br />
182 Gmaas burped and caused an earthquake.<br />
<br />
183 Gmaas once drank from a teacup.<br />
<br />
184 GMAAS IS HERE.... PURRRRRRRRRRRRRRRRRRRR EDIT: Gmaas is everywhere. EDIT: He is behind you.<br />
<br />
185 Gmaas made and currently owns the Matrix. EDIT: The above fact is true. Therefore, this is an illusion. EDIT: Gmaas is not an illusion.<br />
<br />
186 Gmaas is the reason Salah will become better than Ronaldo.<br />
<br />
187 Who is Gmaas, really? EDIT: Gmaas is a cat. EDIT: Who cares how much we mention it? Gmass is a cat.<br />
<br />
188 Gmaas is a heavenly being. EDIT: He is immortal. EDIT: He is not immortal. He just tricked you to think he is immortal. Gmaas is good at tricking.<br />
<br />
189 Gmaas is a cat with no fur or tail. In fact he's a human wearing a cat costume. EDIT: This fact is false. 31415 times false.<br />
<br />
190 Illuminati was a manifestation of Gmaas, but Gmaas decided Illuminati was not great enough for his godly self.<br />
<br />
This article is spam<br />
191 sseraj has met Gmaas, and Gmaas is his best friend. EDIT: sseraj is Gmaas's great great great great great grandson.<br />
<br />
192 Gmaas read Twilight. EDIT: ...and SURVIVED.<br />
<br />
193 There is a secret code when put into super smash where Gmaas would be a playable character. Too bad he didn't say it.<br />
<br />
194 Gmaas was a tribute to one of the Hunger Games, came out a Victor, and now lives in District 4. EDIT: This fact is true and not true. He is everywhere.<br />
<br />
195 Gmaas is the only known creature that will survive the destruction of Earth in 99,999,999 years. EDIT: The Earth will probably die in around 5,000,000,000 years.<br />
<br />
196 5space (side admin) is one of Gmaas's slaves. EDIT: Gmaas owns all AoPS site administrators. EDIT: He owns Himself.<br />
<br />
197 Gmaas photos − https://cdn.artofproblemsolving.com/images/f/f/8/ff8efef3a0d2eb51254634e54bec215b948a1bba.jpg<br />
<br />
http://disneycreate.wikia.com/wiki/File:Troll_cat_gif_(1).gif<br />
<br />
This article is spam<br />
He was also sighted here.<br />
<br />
198 Gmaas in Popular Culture:<br />
<br />
BREAKING NEWS: A Gmaasologist has found a possible cousin to Gmaas in Raymond Feist's book Silverthorn. They are mountain dwellers, gwali. Not much are known about them either, and when someone asked,"What are gwali?" the customary answer "This is gwali" is returned. Another eminent Gmaasologist is now looking into it.<br />
199 Someone is writing a book about Gmaas.<br />
<br />
200 Sighting of Gmaas: https://2017.spaceappschallenge.org/challenges/warning-danger-ahead/and-you-can-help-fight-fires/teams/gmaas/project<br />
<br />
201 Oryx the mad god is actually Gmaas wearing a suit of armor. This explains why he is never truly killed.<br />
<br />
202 Potential sighting of Gmaas [1]<br />
<br />
203 Gmaas has been spotted in some Doctor Who and Phineas and Ferb episodes, such as Aliens of London, Phineas and Ferb Save Summer, Dalek, Rollercoaster, Rose, Boom Town, The Day of The Doctor, Candace Gets Busted, The Name of the Doctor, Silence in the Library, The Idiots Lantern and many more.<br />
<br />
204 Gmaas can be found in many places in Plants vs. Zombies Garden Warfare 2 and Bloons TD Battles.<br />
<br />
205 Gmaas was an un-credited actor in the Doctor Who story Knock Knock, playing a Dryad. How he shrunk, we will never know.<br />
<br />
206 An eminent Gmaasologist is also writing a story about him. He is continuing the book that was started by the professor of Gmaasology at Harvard. When he is done he will post it here.<br />
<br />
207 Gmaas is a time traveler from 0.99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999 B.C.<br />
<br />
208 No one knows if Gmaas is a Mr. Mime in a cat skin, the other way around, or just a downright combination of both. EDIT: Gmaas is an immortal in a cat body.<br />
<br />
209 In it, it mentions these four links as things Gmaas is having trouble (specifically technical difficulties). What could it mean? Links:<br />
<br />
https://docs.google.com/document/d/1NZ0XcFYm80sA-fAoxnm7ulMCwdNU75Va_6ZjRHfSHV0<br />
<br />
https://docs.google.com/document/d/1ELN7ORauFFv1dwpU_u-ah_dFJHeuJ3szYxoeC1LlDQg/<br />
<br />
https://docs.google.com/document/d/1oy9Q3F7fygHw-OCWNEVE8d-Uob2dxVACFcGUcLmk3fA<br />
<br />
https://docs.google.com/document/d/1jzb9Q6FmDmrRyXwnik3e0sYw5bTPMo7aBwugmUbA13o<br />
<br />
210 Another possible Gmaas sighting?<br />
<br />
211 <math>Another</math> sighting? [3]<br />
<br />
212 Yet Another Gmaas sighting? [4]<br />
<br />
213 Gmaas has been sighted several times on the Global Announcements forum.<br />
<br />
214 Gmaas uses the following transportation: <img> http://cdn.artofproblemsolving.com/images/3/6/8/368da4e615ea3476355ee3388b39f30a48b8dd48.jpg </img> EDIT: He also sometimes uses a TARDIS<br />
<br />
215 When Gmaas was angry, he started world wars 1 & 2. It is only because of Gmaas that we have not had World War 3. EDIT: He was starting to have to get angry in the Cold War, especially around the Cuban Missile Crisis and the Ronald Regan era, but he decided to eat food, which calmed him down.<br />
<br />
216 Gmaas is the only cat to have been proved irrational and transcendental, though we suspect all cats fall in the first category.<br />
<br />
217 Gmaas belongs to a secret club of transcendental cats. EDIT: That club is located underneath the Eiffel Tower. EDIT EDIT: Gustave Eiffel was Gmaas in disguise and designed the club.<br />
<br />
218 Gmaas plays Geometry Dash. His username is D3m0nG4m1n9. EDIT: Gmaas only does this to punish himself. Olympiad Geometry is his least favorite thing to do. EDIT: None of these are true.<br />
<br />
219 Gmaas likes to whiz on the wilzo.<br />
<br />
220 Gmaas has been spotted in many AoPS classes, such as AMC 8 Basics. EDIT: Many of the AoPS classes Gmaas has visited can be found in the Gmaas sightings section of this article.<br />
<br />
This article is spam<br />
221 Gmaas is cool. EDIT: He was not cool in summer, so he invented air conditioning. EDIT: He is air conditioning, in fact he is the entire universe.<br />
<br />
222 Gmaas hemoon card that does over 9000000 dmg.<br />
<br />
This article is spam<br />
223 Gmaas is a skilled swordsman who should not to be mistaken for Puss in Boots. Some say he even trained the mysterious and valiant Meta Knight.<br />
<br />
224 Kirby once swallowed Gmaas. Gmaas had to spit him out.<br />
<br />
225 Gmaas was the creator of pokemon, and his pokemon card can OHKO anyone in one turn. He is invisible and he will always move first.<br />
<br />
226 Gmaas beat Dongmin in The Genius Game Seasons 1, 2, 3, 4, 5, 6, and 7.<br />
<br />
227 Gmaas has five letters. Pizza also has five letters. Pizzas are round. Eyes are round. There is an eye in the illuminati symbol. EDIT: Gmaas is a fluffy cat.<br />
<br />
This article is spam<br />
228 Gmaas knows both 'table' and 'tabular' in LaTeX, and can do them in his sleep. EDIT: Gmaas invented LaTeX in his sleep.<br />
<br />
This article is spam<br />
229 Gmaas does not hate cheddar cheese, but he doesn't love it either.<br />
<br />
This article is spam<br />
230 Gmaas is a cat and not a cat. EDIT: He is a cat.<br />
<br />
This article is spam<br />
231 Gmaas was born on the sun. EDIT: Not the sun, the suns. He was born on all the suns at once.<br />
<br />
232 Gmaas eats tape. EDIT: Gmaas invented tape. EDIT: Gmaas eats everything. Gmaas eats computers.<br />
<br />
233 Gmaas likes Bubble Gum.<br />
<br />
234 Thomas Edison did not invent the lightbulb; Gmaas did.<br />
<br />
235 Gmaas invented the alphabet. EDIT: Gmaas thought that hieroglyphs were too complicated, so he invented the alphabet.<br />
<br />
236 Gmaas eats metal. EDIT: Gmaas once ate so much metal that he turned into a bronze statue.<br />
<br />
237 Gmaas is over 9000 years old! EDIT: This is just a DBZ reference, and bears no reality to his true age. EDIT: Gmaas is trillions of years old.<br />
<br />
238 Gmaas is a cat and not a cat. EDIT: He is a cat. EDIT: This fact has been stated 31,415 times in this article.<br />
<br />
239 Gmaas started the Iron Age. EDIT: He thought civilization was getting too advanced. So he sent out the Sea People to destroy civilization.<br />
<br />
240 Gmaas made the dinosaurs go extinct. EDIT: That happened when he got angry that a dinosaur stepped on his toe.<br />
<br />
241 Gmaas created life. Then he destroyed it, and in doing so, destroyed himself. Until his son, Gmaas II took over and saved the planet.<br />
<br />
242 Gmaas created AoPS. EDIT: AoPS was actually born out of a small fraction of Gmaas's abstract reality, and only the sheer amount math can keep it here. (It is also rumored that when he reclaims it, the USF will be deleted, as that is where 83% of the factions of his abstract reality lives, and when people leave USF, more and more escapes.)<br />
<br />
243 Gmaas created mathematics.<br />
<br />
244 Gmaas does not like Roblox.<br />
<br />
245 Gmaas told Steve Jobs to start a company.<br />
<br />
246 Gmaas invented Geometry Dash. EDIT: Gmaas hates Olympiad Geometry. [Source: sseraj]<br />
<br />
247 Gmaas got to<math>\infty</math>in Flappy Bird. EDIT: Gmaas broke the game. <br />
<br />
248 Gmaas invented Helix Jump.<br />
<br />
249 Gmaas can play Happy Birthday on the Violin.<br />
<br />
250 Gmaas has mastered Paganini. EDIT: Paganini was Gmaas in disguise. EDIT: Gmaas was Paganini in one of his 100,000 human lives. He does not have a human life now because he has a cat life.<br />
<br />
251 Gmaas discovered Atlantis after one dive underwater.<br />
<br />
252 Gmaas made a piano with 89 keys. EDIT: The piano was made out of chocolate. EDIT: He also made a piano bench made out of chocolate. EDIT: Gmaas ate them<br />
<br />
253 Gmaas can see the future and how to change it.<br />
<br />
254 Gmaas has every super power you can imagine. EDIT: Gmaas has more superpowers than you can imagine.<br />
<br />
255 Gmaas made a Violin with 9 strings.<br />
<br />
256 Gmaas can read 5 books at once. EDIT: It is slightly difficult for Gmaas to do this because he has no fingers. But somehow, Gmaas finds a way. EDIT: He uses his mind to hold open the books.<br />
<br />
This article is spam<br />
257 Gmaas eats rubber bands. EDIT: Gmaas once reincarnated as a rubber band. He thought it was the worst period in his life. Eventually he was snapped and reincarnated as a bacterium, which was also boring.<br />
<br />
258 Gmaas married Mrs. Norris. EDIT: Mrs. Norris is his second worst enemy. They say keep your enemies close. EDIT: Gmaas eventually divorced Mrs. Norris for her astounding lack of inteligence and short life span.<br />
<br />
259 Gmaas can fly faster than anything. EDIT: No one can travel faster than light. EDIT: Gmaas can.<br />
<br />
260 Grumpy cat is his son. EDIT: Grumpy cat is his worst enemy and his son.<br />
<br />
261 Gmaas eats paper. EDIT: According to Gmaas, recycled paper tastes the very good. Paper with steak juice on it tastes even better.<br />
<br />
262 Gmaas likes lollipops. EDIT: Gmaas was reincarnated as a lollypop. He did not appreciate having spit all over him while he dissolved.<br />
<br />
263 Gmaas nibbles on pencils.<br />
<br />
264 Gmaas is alive. EDIT: He is both alive and dead. (For reference, see later post.) EDIT: He can make people alive and dead.<br />
-----------------------------------------------------<br />
- Gmaas is Ninja in Fortnite. EDIT: Gmaas possesses Ninja in Fortnite.<br />
<br />
- Gmaas is love; Gmaas is life. EDIT: Scientist do not know how life was formed. Gmaas does.<br />
<br />
- Gmaas taught Richard Rusczyk everything he knows about mathematics. EDIT: Many famous mathematicians have been Gmaas in disguise.== This article is spam == EDIT: This article is not spam! IT is fr worshiping Gmaas.<br />
<br />
- Gmaas can control matter by looking at it. EDIT: He once looked at a galaxy while he was angry. Everything in the galaxy exploded.<br />
<br />
- Gmaas created AoPS. EDIT: He created 99% of all websites. 98% of those websites are blank and unreachable, but the ones that are not are interesting.<br />
<br />
- Gmaas is a quantum particle. EDIT: Gmaas is multiple quantum particles. He is a macroscopic collection of them.<br />
<br />
This article is spam<br />
- Gmaas is alive and dead at the same time. EDIT: He is usually alive.<br />
<br />
This article is spam<br />
- Gmaas likes snow. EDIT: Once Gmaas was reincarnated as a polar bear around 1,000,000 years ago. He had the best time of his lives. EDIT: While he was a polar bear, he ate many fish.<br />
<br />
- GMAAS LIKES THE NEW AOPS UPDATE! EDIT: Are you sure he does? Did you ask him? EDIT: Yes, I did.<math>\textrm{Gmaas is right behind you}</math>EDIT: Gmaas is everywhere. He is in a quantum superposition. He is still in the superposition until someone sees him. The chance of him being behind you is 0.0000000000000000000000000000000000000000000000000000001%. But, you never know. Is he behind you? Is he behind me right now? He is!!! Aaaaaaaaaah... THUMP<br />
<br />
- Gmaas likes his eggs hard boiled.<br />
<br />
- Gmaas doesn't take showers; he only takes bloodbaths.<br />
<br />
- When the bogeyman goes to sleep, he checks his closet for Gmaas.<br />
<br />
- When Gmaas crosses the street, cars have to look both ways.<br />
<br />
- Gmaas has counted to infinity an infinite amount of times.<br />
<br />
- Gmaas pulled the pin in a grenade. 1 billion people died. Then he threw it.<br />
<br />
- Gmaas controls the Illuminati and controls all the world's resources. He also is the ruler of a communist society on Mars.<br />
<br />
- Gmaas has taken the AHSME/AMC 10, AIME, USAJMO, USAMO, and IMO all the years it has come out. It is rumored that for 2018, Gmaas got a 163.5 on the AMC 12A, a 156 on the AMC 12B, and 17 problems right on the AIME I. EDIT: He also got 51 on USAMO. EDIT: He invented the AMC, AIME, USAJMO, and IMO<br />
<br />
- Gmaas has designed most of the AMC tests. EDIT: He didn't design them in 2015 because he was hibernating too long.<br />
<br />
- Gmaas is a koala. EDIT: Gmaas was actually the first koala. He wanted to reincarnate himself into something new, so he created a whole other species. [Source Wikipedia: Koala] EDIT: Gmaas is a Koala when they are not alive, which is 10% of the time. When they are alive, Gmaas is a cat.<br />
<br />
- Time is Gmaas's vacation home. EDIT: Gmaas created time as a science project.<br />
<br />
- Gmass is Catholic<br />
<br />
- Gmaas was once reincarnated as Chuck Norris, but he missed being a cat. Then he became a cat.<br />
<br />
- Gmaas once resided with a certain physicist named Schrödinger, but he left because Schrödinger was too confusing. Granted, nothing is too confusing for Gmaas but Schrödinger also made Gmaas alive and dead, which felt weird.<br />
<br />
- Gmaas once decided to eat a carrot. He decided turnips were better.<br />
<br />
- Gmaasology used to be called Gmaathamatics. It was renamed a few years ago. For more information, see the Gmaasology page. That page needs expanding.<br />
<br />
- \gmaas should be made into a LaTeX command. Its function should be to summon Gmaas.<br />
<br />
-<math>\gmaas</math> GMAAS has entered the room<br />
<br />
- Grumpy cat pretends to be a descendent of Gmaas because he is jealous. He is not a descendant of Gmaas.<br />
<br />
- Every IMO Gold Medalist is two of Gmaas, standing on top of each other in a trenchcoat.<br />
<br />
- Gmaas has been everywhere in the world. EDIT: Gmaas has been everywhere in the universe and multiverse.<br />
<br />
- The degree used to be called the Gmaas Arc, but the name was too long for most people, so they switched the name.<br />
<br />
- Gmaas is famous on AoPS. EDIT: Gmaas is AoPS.<br />
<br />
- Gmaas invented every math theorem and in fact invented math.<br />
<br />
- Gmaas made 31.41592653589793238462643383279502884% of memes. EDIT: This is incorrect. This is only an estimate.<br />
<br />
- Gmaas is a Gmaas since Gmaas likes to Gmaas and Gmaas is cool because he is named Gmaas.<br />
<br />
- Gmaas once ate Big Chungus. EDIT: Gmaas also once ate cat food. EDIT: Gmaas hates cat food. EDIT: Gmaas also hates dog food. EDIT: Gmaas does not need to eat, he is an all-conquering god who never/rarely dies. EDIT: Gmaas is Big Chungus EDIT: He was Big Chungus for 3.14159265358979323846327656180937734 seconds. EDIT: This is only an rough estimate<br />
<br />
- Garfield is Gmaas in disguise. EDIT: But Gmaas also created Garfield. He took a Gar and a Field, and added them. Boom. He made Garfield.<br />
<br />
-Gmaas didn't create the world. He didn't create the universe. The didn't create multiverses. He is the world. He is the universe. He is the multiverses<br />
<br />
-Gmaas has a cult with many followers. This is the page for his followers. They pray to him and remember him for his deeds.<br />
<br />
- Garfield ate Gmaas but then Gmaas ate garfield. Then they ate each other. EDIT: Gmaas ate Garfield at the end because Gmaas.<br />
<br />
- Gmaas has an existential crisis every 99.0000000000000000000000000000000000009123659812374 seconds.<br />
<br />
- Gmaas married and then divorced a picture of himself EDIT: He then destroyed all evidence of this by swallowing it and barfing it out as a hairball<br />
<br />
- Gmaas needed light to read and he turned into a lamp called the sun and created 51.59265358979% of life. EDIT: Gmaas uses a new type of tetradecimal number system where the digits are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, G, M, A, and S. The number 416877 is Gmaas's favorite integer. (Convert it to this number system)<br />
<br />
-None of this is true. Except for maybe that last one. EDIT: This fact is therefore not true. EDIT This fact is a paradox. Gmaas does not like paradoxes. Therefore Gmaas does not like this fact.<br />
<br />
-Gmaas has only done 3 problems on alcumus, and he got one wrong! EDIT: Gmass is the creator of Alcumus, so he got all right<br />
<br />
(Why is this a thing?) Because we are all worshippers of Gmaas.<br />
<br />
This article is NOT spam otherwise it would have been deleted by now. Edit: This article is spam.<br />
<br />
Gmaas is actually an AoPS site admin... (And a human) not a cat... His username is Gmaasrocks32 EDIT: His username is all the accounts.<br />
<br />
All hail Gmaas!<br />
--------------------<br />
<br />
P.S. Gmaas won USAMO 5 times in a row. That's because he invented USAMO. When Gmaas took it nobody knew about it and he was the only one who took it. So of course, he won. How dare you spell Gmaas with a lowercase G? He is the supreme and awesome ruler of the universe!<br />
<br />
P.P.S. Gmaas invented the word Yeet.<br />
<br />
P.P.P.S. Gmass is the first person who played the game YECK (Moth poth 2019 reference)<br />
<br />
P.P.P.P.S. Gmaas is a non-human who can snap anyone out of existence without anything.<br />
<br />
P.P.P.P.P.S. Gmaas was the first person who did math,<br />
<br />
P.P.P.P.P.P.S. Gmaas invented proof by dictatorship<br />
<br />
P.P.P.P.P.P.P.S Gmaas invented proof by procrastination<br />
<br />
P.P.P.P.P.P.P.P.S Gmaas invented proofs!<br />
<br />
P.P.P.P.P.P.P.P.P.S Gmaas invented everything.<br />
<br />
P.P.P.P.P.P.P.P.P.P.S Gmaas did not invent roblox. Gmaas invented Minecraft.<br />
<br />
P.P.P.P.P.P.P.P.P.P.P.S Gmaas is superior to all other site admins, including RRusczyk himself.Edit: He is not superior. EDIT: Whoever is saying this article is spam and he is not superior his mean. None of his facts are true. EDIT: This is ThriphtyPiano or whatever you call him he does not deserve the respect.<br />
<br />
P.P.P.P.P.P.P.P.P.P.P.P.S. ThriftyPiano is telling all the false facts. Do not listen to him. Or whatever you call him, we don't respect him, but we do with Gmass. Whenever you see This article is spam, it is his doing</div>Patopatohttps://artofproblemsolving.com/wiki/index.php?title=1957_AHSME_Problems/Problem_2&diff=1096081957 AHSME Problems/Problem 22019-09-02T12:57:57Z<p>Patopato: Blanked the page</p>
<hr />
<div></div>Patopatohttps://artofproblemsolving.com/wiki/index.php?title=1957_AHSME_Problems/Problem_2&diff=1096071957 AHSME Problems/Problem 22019-09-02T12:57:46Z<p>Patopato: Created page with "patopato is awesome. PROOF: I am awesome. I never lie. Therefore, I am awesome."</p>
<hr />
<div>patopato is awesome. <br />
<br />
PROOF:<br />
<br />
I am awesome. I never lie. Therefore, I am awesome.</div>Patopatohttps://artofproblemsolving.com/wiki/index.php?title=Distinguishability&diff=105865Distinguishability2019-05-19T23:10:58Z<p>Patopato: /* Distinguishable to distinguishable, with duplicates */</p>
<hr />
<div>When distributing <math>n</math> things to <math>k</math> other things, one has to consider the '''distinguishability''' of the objects (i.e. if they're distinguishable or not). If the <math>n</math> things are distinguishable, one also has to consider if duplicates are allowed (i.e. if we can repeat). For these problems, it is best to think about it first.<br />
==Distinguishable to distinguishable, with duplicates==<br />
For each of the <math>k</math> things, there are <math>n</math> choices, for a total of <math>\underbrace{n\cdot n\cdot\cdots\cdot n\cdot n}_k= n^k</math> ways.<br />
<br />
==Distinguishable to distinguishable, without duplicates==<br />
For each of the <math>n</math> things, there are <math>k</math> choices, for a total of <math>\underbrace{k\cdot k\cdot\cdots\cdot k\cdot k}_n = k^n</math> ways.<br />
==Distinguishable to indistinguishable, with duplicates==<br />
This is "reverse" Balls and Urns, or essentially distributing <math>k</math> indistinguishable objects to <math>n</math> distinguishable objects. Refer to 6; this case has <math>\binom{n + k - 1}{k-1}</math> ways. Now we can just switch the <math>n</math> and the <math>k</math>, so there are <math>\binom{k+n-1}{n-1}</math> ways.<br />
<br />
==Distinguishable to indistinguishable, without duplicates==<br />
This is probably the most tedious case, as it involves the most casework. One way is to first find all the partitions (refer to 5) of <math>n</math> with <math>k</math> addends, (i.e. all solutions to <math>a_1 + a_2 + \cdots + a_k = n</math> in which the addends are indistinguishable). Then, for each partition, separately calculate the number of ways, and finally, add these results together.<br />
<br />
For example, if <math>(n,k) = (5,3)</math>, then our partitions are:<br />
<math>\{5,0,0\}</math>--this case has <math>1</math> way.<br />
<math>\{4,1,0\}</math>--we choose one of <math>n</math> to be the "<math>1</math>", so there are <math>5</math> ways.<br />
<math>\{3,2,0\}</math>--we choose three objects to be the "<math>3</math>'s" (the rest are determined after this), so there are <math>\binom53 = 10</math> ways for this.<br />
<math>\{3,1,1\}</math>--again, we choose three objects to be the "<math>3</math>'s" (the rest are determined after this), so there are <math>\binom53 = 10</math> ways for this.<br />
<math>\{2,2,1\}</math>--first, we choose one object to be the "<math>1</math>", which has <math>5</math> ways. Then, we can choose any two of the remaining four to be one of the "<math>2</math>'s", and there are <math>\binom42 = 6</math> ways for this. However, we must divide this by <math>2</math>, since the two "<math>2</math>'s" are interchangeable, and the total for this case is <math>5\cdot6\cdot\frac12 = 15</math>.<br />
<br />
Adding up, we get <math>1 + 5 + 10 + 10 + 15 = 41</math> ways.<br />
<br />
All of these problems are similar to this one in that you divide them up into smaller counting problems.<br />
<br />
==Indistinguishable to indistinguishable==<br />
This is part of the partition problem. Imagine that you are finding the number of solutions to <math>a_1 + a_2 + \cdots + a_k = n</math>, where <math>a_1,a_2,\ldots,a_k</math> are indistinguishable.<br />
<br />
This can be done with casework; the method is best explained with an example: say that <math>(n,k) = (5,3)</math>. Our partitions are then <math>\{5,0,0\},\{4,1,0\},\{3,2,0\},\{3,1,1\},\{2,2,1\}</math>, so there are <math>5</math> partitions.<br />
==Indistinguishable to distinguishable (Balls and Urns/ Sticks and Stones)==<br />
This is "Balls and Urns". In general, if one has <math>n</math> indistinguishable objects that one wants to distribute to <math>k</math> distinguishable objects, then there are <math>\binom{n + k - 1}{k - 1}</math> ways to do so.<br />
<br />
Imagine that there are <math>k - 1</math> dividers, denoted by <math>\mid</math>, and <math>n</math> objects, denoted by <math>\star</math>, so we have <math>\underbrace{\mid\mid\mid\cdots\mid\mid\mid}_{k-1}</math> and <math>\underbrace{\star\star\star\cdots\star\star\star}_n</math>. Then, label the regions formed by the dividers, so we get <math>1\mid2\mid3\mid\cdots\mid(k - 2)\mid(k - 1)\mid k</math> (since there are <math>k-1</math> dividers) and our <math>n</math> objects <math>\underbrace{\star\star\star\cdots\star\star\star}_n</math>. We can now see that there are <math>k</math> distinct regions (corresponding to the <math>k</math> distinguishable objects) in which we can place our <math>n</math> identical objects (corresponding to the <math>n</math> indistinguishable objects that one is distributing), which is analogous to the original problem. Finally, there are <math>\binom{n+k-1}n=\binom{n + k - 1}{k - 1}</math> arrangements of the <math>n</math> stars and the <math>(k - 1)\ \mid\text{'s}</math> by basic permutations with repeated items. '''Note:''' the number of stars that appears in each of the regions <math>1\mid2\mid3\mid\cdots\mid(k - 2)\mid(k - 1)\mid k</math> represents the number of indistinguishable objects (the <math>n</math> stars) given to a particular distinguishable object (of the <math>k</math> dividers). For example, if we're distributing <math>9</math> stars to <math>5</math> kids, then one arrangement is <math>\star\mid\mid\star\star\star\mid\star\star\star\mid\star\star</math> corresponding to <math>1</math> star to the first kid, <math>0</math> to the second, <math>3</math> to the third, <math>3</math> to the fourth, and <math>2</math> to the fifth.<br />
<br />
One problem that can be solved by this is finding the number of solutions to <math>a_1 + a_2 + \cdots + a_k = n</math>, where <math>a_1,a_2,\ldots,a_n\ge0</math>, which has <math>\binom{n + k - 1}{k - 1}</math> solutions.<br />
<br />
[[Category:Combinatorics]]</div>Patopatohttps://artofproblemsolving.com/wiki/index.php?title=Distinguishability&diff=105843Distinguishability2019-05-17T19:41:24Z<p>Patopato: /* Distinguishable to distinguishable, with duplicates */</p>
<hr />
<div>When distributing <math>n</math> things to <math>k</math> other things, one has to consider the '''distinguishability''' of the objects (i.e. if they're distinguishable or not). If the <math>n</math> things are distinguishable, one also has to consider if duplicates are allowed (i.e. if we can repeat). For these problems, it is best to think about it first.<br />
==Distinguishable to distinguishable, with duplicates==<br />
For each of the <math>k</math> things, there are <math>n</math> choices, for a total of <math>\underbrace{n\cdot n\cdot\cdots\cdot n\cdot n}_k= n^k</math> ways.<br />
<math>\begin{tabular}{l c c c c}<br />
patopato & 100 & 100 & 100 \\<br />
potatoFace & 100 & 99 & 69 & 100 \\<br />
\end{tabular}</math><br />
<br />
==Distinguishable to distinguishable, without duplicates==<br />
For each of the <math>n</math> things, there are <math>k</math> choices, for a total of <math>\underbrace{k\cdot k\cdot\cdots\cdot k\cdot k}_n = k^n</math> ways.<br />
==Distinguishable to indistinguishable, with duplicates==<br />
This is "reverse" Balls and Urns, or essentially distributing <math>k</math> indistinguishable objects to <math>n</math> distinguishable objects. Refer to 6; this case has <math>\binom{n + k - 1}{k-1}</math> ways. Now we can just switch the <math>n</math> and the <math>k</math>, so there are <math>\binom{k+n-1}{n-1}</math> ways.<br />
<br />
==Distinguishable to indistinguishable, without duplicates==<br />
This is probably the most tedious case, as it involves the most casework. One way is to first find all the partitions (refer to 5) of <math>n</math> with <math>k</math> addends, (i.e. all solutions to <math>a_1 + a_2 + \cdots + a_k = n</math> in which the addends are indistinguishable). Then, for each partition, separately calculate the number of ways, and finally, add these results together.<br />
<br />
For example, if <math>(n,k) = (5,3)</math>, then our partitions are:<br />
<math>\{5,0,0\}</math>--this case has <math>1</math> way.<br />
<math>\{4,1,0\}</math>--we choose one of <math>n</math> to be the "<math>1</math>", so there are <math>5</math> ways.<br />
<math>\{3,2,0\}</math>--we choose three objects to be the "<math>3</math>'s" (the rest are determined after this), so there are <math>\binom53 = 10</math> ways for this.<br />
<math>\{3,1,1\}</math>--again, we choose three objects to be the "<math>3</math>'s" (the rest are determined after this), so there are <math>\binom53 = 10</math> ways for this.<br />
<math>\{2,2,1\}</math>--first, we choose one object to be the "<math>1</math>", which has <math>5</math> ways. Then, we can choose any two of the remaining four to be one of the "<math>2</math>'s", and there are <math>\binom42 = 6</math> ways for this. However, we must divide this by <math>2</math>, since the two "<math>2</math>'s" are interchangeable, and the total for this case is <math>5\cdot6\cdot\frac12 = 15</math>.<br />
<br />
Adding up, we get <math>1 + 5 + 10 + 10 + 15 = 41</math> ways.<br />
<br />
All of these problems are similar to this one in that you divide them up into smaller counting problems.<br />
<br />
==Indistinguishable to indistinguishable==<br />
This is part of the partition problem. Imagine that you are finding the number of solutions to <math>a_1 + a_2 + \cdots + a_k = n</math>, where <math>a_1,a_2,\ldots,a_k</math> are indistinguishable.<br />
<br />
This can be done with casework; the method is best explained with an example: say that <math>(n,k) = (5,3)</math>. Our partitions are then <math>\{5,0,0\},\{4,1,0\},\{3,2,0\},\{3,1,1\},\{2,2,1\}</math>, so there are <math>5</math> partitions.<br />
==Indistinguishable to distinguishable (Balls and Urns/ Sticks and Stones)==<br />
This is "Balls and Urns". In general, if one has <math>n</math> indistinguishable objects that one wants to distribute to <math>k</math> distinguishable objects, then there are <math>\binom{n + k - 1}{k - 1}</math> ways to do so.<br />
<br />
Imagine that there are <math>k - 1</math> dividers, denoted by <math>\mid</math>, and <math>n</math> objects, denoted by <math>\star</math>, so we have <math>\underbrace{\mid\mid\mid\cdots\mid\mid\mid}_{k-1}</math> and <math>\underbrace{\star\star\star\cdots\star\star\star}_n</math>. Then, label the regions formed by the dividers, so we get <math>1\mid2\mid3\mid\cdots\mid(k - 2)\mid(k - 1)\mid k</math> (since there are <math>k-1</math> dividers) and our <math>n</math> objects <math>\underbrace{\star\star\star\cdots\star\star\star}_n</math>. We can now see that there are <math>k</math> distinct regions (corresponding to the <math>k</math> distinguishable objects) in which we can place our <math>n</math> identical objects (corresponding to the <math>n</math> indistinguishable objects that one is distributing), which is analogous to the original problem. Finally, there are <math>\binom{n+k-1}n=\binom{n + k - 1}{k - 1}</math> arrangements of the <math>n</math> stars and the <math>(k - 1)\ \mid\text{'s}</math> by basic permutations with repeated items. '''Note:''' the number of stars that appears in each of the regions <math>1\mid2\mid3\mid\cdots\mid(k - 2)\mid(k - 1)\mid k</math> represents the number of indistinguishable objects (the <math>n</math> stars) given to a particular distinguishable object (of the <math>k</math> dividers). For example, if we're distributing <math>9</math> stars to <math>5</math> kids, then one arrangement is <math>\star\mid\mid\star\star\star\mid\star\star\star\mid\star\star</math> corresponding to <math>1</math> star to the first kid, <math>0</math> to the second, <math>3</math> to the third, <math>3</math> to the fourth, and <math>2</math> to the fifth.<br />
<br />
One problem that can be solved by this is finding the number of solutions to <math>a_1 + a_2 + \cdots + a_k = n</math>, where <math>a_1,a_2,\ldots,a_n\ge0</math>, which has <math>\binom{n + k - 1}{k - 1}</math> solutions.<br />
<br />
[[Category:Combinatorics]]</div>Patopatohttps://artofproblemsolving.com/wiki/index.php?title=Distinguishability&diff=105842Distinguishability2019-05-17T19:40:44Z<p>Patopato: /* Distinguishable to distinguishable, with duplicates */</p>
<hr />
<div>When distributing <math>n</math> things to <math>k</math> other things, one has to consider the '''distinguishability''' of the objects (i.e. if they're distinguishable or not). If the <math>n</math> things are distinguishable, one also has to consider if duplicates are allowed (i.e. if we can repeat). For these problems, it is best to think about it first.<br />
==Distinguishable to distinguishable, with duplicates==<br />
For each of the <math>k</math> things, there are <math>n</math> choices, for a total of <math>\underbrace{n\cdot n\cdot\cdots\cdot n\cdot n}_k= n^k</math> ways.<br />
\begin{tabular}{l c c c c}<br />
patopato & 100 & 100 & 100 \\<br />
potatoFace & 100 <math> 99 </math> 69 $ 100 \\<br />
\end{tabular}<br />
<br />
==Distinguishable to distinguishable, without duplicates==<br />
For each of the <math>n</math> things, there are <math>k</math> choices, for a total of <math>\underbrace{k\cdot k\cdot\cdots\cdot k\cdot k}_n = k^n</math> ways.<br />
==Distinguishable to indistinguishable, with duplicates==<br />
This is "reverse" Balls and Urns, or essentially distributing <math>k</math> indistinguishable objects to <math>n</math> distinguishable objects. Refer to 6; this case has <math>\binom{n + k - 1}{k-1}</math> ways. Now we can just switch the <math>n</math> and the <math>k</math>, so there are <math>\binom{k+n-1}{n-1}</math> ways.<br />
<br />
==Distinguishable to indistinguishable, without duplicates==<br />
This is probably the most tedious case, as it involves the most casework. One way is to first find all the partitions (refer to 5) of <math>n</math> with <math>k</math> addends, (i.e. all solutions to <math>a_1 + a_2 + \cdots + a_k = n</math> in which the addends are indistinguishable). Then, for each partition, separately calculate the number of ways, and finally, add these results together.<br />
<br />
For example, if <math>(n,k) = (5,3)</math>, then our partitions are:<br />
<math>\{5,0,0\}</math>--this case has <math>1</math> way.<br />
<math>\{4,1,0\}</math>--we choose one of <math>n</math> to be the "<math>1</math>", so there are <math>5</math> ways.<br />
<math>\{3,2,0\}</math>--we choose three objects to be the "<math>3</math>'s" (the rest are determined after this), so there are <math>\binom53 = 10</math> ways for this.<br />
<math>\{3,1,1\}</math>--again, we choose three objects to be the "<math>3</math>'s" (the rest are determined after this), so there are <math>\binom53 = 10</math> ways for this.<br />
<math>\{2,2,1\}</math>--first, we choose one object to be the "<math>1</math>", which has <math>5</math> ways. Then, we can choose any two of the remaining four to be one of the "<math>2</math>'s", and there are <math>\binom42 = 6</math> ways for this. However, we must divide this by <math>2</math>, since the two "<math>2</math>'s" are interchangeable, and the total for this case is <math>5\cdot6\cdot\frac12 = 15</math>.<br />
<br />
Adding up, we get <math>1 + 5 + 10 + 10 + 15 = 41</math> ways.<br />
<br />
All of these problems are similar to this one in that you divide them up into smaller counting problems.<br />
<br />
==Indistinguishable to indistinguishable==<br />
This is part of the partition problem. Imagine that you are finding the number of solutions to <math>a_1 + a_2 + \cdots + a_k = n</math>, where <math>a_1,a_2,\ldots,a_k</math> are indistinguishable.<br />
<br />
This can be done with casework; the method is best explained with an example: say that <math>(n,k) = (5,3)</math>. Our partitions are then <math>\{5,0,0\},\{4,1,0\},\{3,2,0\},\{3,1,1\},\{2,2,1\}</math>, so there are <math>5</math> partitions.<br />
==Indistinguishable to distinguishable (Balls and Urns/ Sticks and Stones)==<br />
This is "Balls and Urns". In general, if one has <math>n</math> indistinguishable objects that one wants to distribute to <math>k</math> distinguishable objects, then there are <math>\binom{n + k - 1}{k - 1}</math> ways to do so.<br />
<br />
Imagine that there are <math>k - 1</math> dividers, denoted by <math>\mid</math>, and <math>n</math> objects, denoted by <math>\star</math>, so we have <math>\underbrace{\mid\mid\mid\cdots\mid\mid\mid}_{k-1}</math> and <math>\underbrace{\star\star\star\cdots\star\star\star}_n</math>. Then, label the regions formed by the dividers, so we get <math>1\mid2\mid3\mid\cdots\mid(k - 2)\mid(k - 1)\mid k</math> (since there are <math>k-1</math> dividers) and our <math>n</math> objects <math>\underbrace{\star\star\star\cdots\star\star\star}_n</math>. We can now see that there are <math>k</math> distinct regions (corresponding to the <math>k</math> distinguishable objects) in which we can place our <math>n</math> identical objects (corresponding to the <math>n</math> indistinguishable objects that one is distributing), which is analogous to the original problem. Finally, there are <math>\binom{n+k-1}n=\binom{n + k - 1}{k - 1}</math> arrangements of the <math>n</math> stars and the <math>(k - 1)\ \mid\text{'s}</math> by basic permutations with repeated items. '''Note:''' the number of stars that appears in each of the regions <math>1\mid2\mid3\mid\cdots\mid(k - 2)\mid(k - 1)\mid k</math> represents the number of indistinguishable objects (the <math>n</math> stars) given to a particular distinguishable object (of the <math>k</math> dividers). For example, if we're distributing <math>9</math> stars to <math>5</math> kids, then one arrangement is <math>\star\mid\mid\star\star\star\mid\star\star\star\mid\star\star</math> corresponding to <math>1</math> star to the first kid, <math>0</math> to the second, <math>3</math> to the third, <math>3</math> to the fourth, and <math>2</math> to the fifth.<br />
<br />
One problem that can be solved by this is finding the number of solutions to <math>a_1 + a_2 + \cdots + a_k = n</math>, where <math>a_1,a_2,\ldots,a_n\ge0</math>, which has <math>\binom{n + k - 1}{k - 1}</math> solutions.<br />
<br />
[[Category:Combinatorics]]</div>Patopatohttps://artofproblemsolving.com/wiki/index.php?title=Distinguishability&diff=105841Distinguishability2019-05-17T19:40:33Z<p>Patopato: /* Distinguishable to distinguishable, with duplicates */</p>
<hr />
<div>When distributing <math>n</math> things to <math>k</math> other things, one has to consider the '''distinguishability''' of the objects (i.e. if they're distinguishable or not). If the <math>n</math> things are distinguishable, one also has to consider if duplicates are allowed (i.e. if we can repeat). For these problems, it is best to think about it first.<br />
==Distinguishable to distinguishable, with duplicates==<br />
For each of the <math>k</math> things, there are <math>n</math> choices, for a total of <math>\underbrace{n\cdot n\cdot\cdots\cdot n\cdot n}_k= n^k</math> ways.<br />
<math>\begin{tabular}{l c c c c}<br />
patopato & 100 & 100 & 100 \\<br />
potatoFace & 100 </math> 99 <math> 69 </math> 100 \\<br />
\end{tabular}<br />
<br />
==Distinguishable to distinguishable, without duplicates==<br />
For each of the <math>n</math> things, there are <math>k</math> choices, for a total of <math>\underbrace{k\cdot k\cdot\cdots\cdot k\cdot k}_n = k^n</math> ways.<br />
==Distinguishable to indistinguishable, with duplicates==<br />
This is "reverse" Balls and Urns, or essentially distributing <math>k</math> indistinguishable objects to <math>n</math> distinguishable objects. Refer to 6; this case has <math>\binom{n + k - 1}{k-1}</math> ways. Now we can just switch the <math>n</math> and the <math>k</math>, so there are <math>\binom{k+n-1}{n-1}</math> ways.<br />
<br />
==Distinguishable to indistinguishable, without duplicates==<br />
This is probably the most tedious case, as it involves the most casework. One way is to first find all the partitions (refer to 5) of <math>n</math> with <math>k</math> addends, (i.e. all solutions to <math>a_1 + a_2 + \cdots + a_k = n</math> in which the addends are indistinguishable). Then, for each partition, separately calculate the number of ways, and finally, add these results together.<br />
<br />
For example, if <math>(n,k) = (5,3)</math>, then our partitions are:<br />
<math>\{5,0,0\}</math>--this case has <math>1</math> way.<br />
<math>\{4,1,0\}</math>--we choose one of <math>n</math> to be the "<math>1</math>", so there are <math>5</math> ways.<br />
<math>\{3,2,0\}</math>--we choose three objects to be the "<math>3</math>'s" (the rest are determined after this), so there are <math>\binom53 = 10</math> ways for this.<br />
<math>\{3,1,1\}</math>--again, we choose three objects to be the "<math>3</math>'s" (the rest are determined after this), so there are <math>\binom53 = 10</math> ways for this.<br />
<math>\{2,2,1\}</math>--first, we choose one object to be the "<math>1</math>", which has <math>5</math> ways. Then, we can choose any two of the remaining four to be one of the "<math>2</math>'s", and there are <math>\binom42 = 6</math> ways for this. However, we must divide this by <math>2</math>, since the two "<math>2</math>'s" are interchangeable, and the total for this case is <math>5\cdot6\cdot\frac12 = 15</math>.<br />
<br />
Adding up, we get <math>1 + 5 + 10 + 10 + 15 = 41</math> ways.<br />
<br />
All of these problems are similar to this one in that you divide them up into smaller counting problems.<br />
<br />
==Indistinguishable to indistinguishable==<br />
This is part of the partition problem. Imagine that you are finding the number of solutions to <math>a_1 + a_2 + \cdots + a_k = n</math>, where <math>a_1,a_2,\ldots,a_k</math> are indistinguishable.<br />
<br />
This can be done with casework; the method is best explained with an example: say that <math>(n,k) = (5,3)</math>. Our partitions are then <math>\{5,0,0\},\{4,1,0\},\{3,2,0\},\{3,1,1\},\{2,2,1\}</math>, so there are <math>5</math> partitions.<br />
==Indistinguishable to distinguishable (Balls and Urns/ Sticks and Stones)==<br />
This is "Balls and Urns". In general, if one has <math>n</math> indistinguishable objects that one wants to distribute to <math>k</math> distinguishable objects, then there are <math>\binom{n + k - 1}{k - 1}</math> ways to do so.<br />
<br />
Imagine that there are <math>k - 1</math> dividers, denoted by <math>\mid</math>, and <math>n</math> objects, denoted by <math>\star</math>, so we have <math>\underbrace{\mid\mid\mid\cdots\mid\mid\mid}_{k-1}</math> and <math>\underbrace{\star\star\star\cdots\star\star\star}_n</math>. Then, label the regions formed by the dividers, so we get <math>1\mid2\mid3\mid\cdots\mid(k - 2)\mid(k - 1)\mid k</math> (since there are <math>k-1</math> dividers) and our <math>n</math> objects <math>\underbrace{\star\star\star\cdots\star\star\star}_n</math>. We can now see that there are <math>k</math> distinct regions (corresponding to the <math>k</math> distinguishable objects) in which we can place our <math>n</math> identical objects (corresponding to the <math>n</math> indistinguishable objects that one is distributing), which is analogous to the original problem. Finally, there are <math>\binom{n+k-1}n=\binom{n + k - 1}{k - 1}</math> arrangements of the <math>n</math> stars and the <math>(k - 1)\ \mid\text{'s}</math> by basic permutations with repeated items. '''Note:''' the number of stars that appears in each of the regions <math>1\mid2\mid3\mid\cdots\mid(k - 2)\mid(k - 1)\mid k</math> represents the number of indistinguishable objects (the <math>n</math> stars) given to a particular distinguishable object (of the <math>k</math> dividers). For example, if we're distributing <math>9</math> stars to <math>5</math> kids, then one arrangement is <math>\star\mid\mid\star\star\star\mid\star\star\star\mid\star\star</math> corresponding to <math>1</math> star to the first kid, <math>0</math> to the second, <math>3</math> to the third, <math>3</math> to the fourth, and <math>2</math> to the fifth.<br />
<br />
One problem that can be solved by this is finding the number of solutions to <math>a_1 + a_2 + \cdots + a_k = n</math>, where <math>a_1,a_2,\ldots,a_n\ge0</math>, which has <math>\binom{n + k - 1}{k - 1}</math> solutions.<br />
<br />
[[Category:Combinatorics]]</div>Patopatohttps://artofproblemsolving.com/wiki/index.php?title=Distinguishability&diff=105838Distinguishability2019-05-17T17:45:50Z<p>Patopato: /* Distinguishable to distinguishable, with duplicates */ the sid</p>
<hr />
<div>When distributing <math>n</math> things to <math>k</math> other things, one has to consider the '''distinguishability''' of the objects (i.e. if they're distinguishable or not). If the <math>n</math> things are distinguishable, one also has to consider if duplicates are allowed (i.e. if we can repeat). For these problems, it is best to think about it first.<br />
==Distinguishable to distinguishable, with duplicates==<br />
For each of the <math>k</math> things, there are <math>n</math> choices, for a total of <math>\underbrace{n\cdot n\cdot\cdots\cdot n\cdot n}_k= n^k</math> ways.<br />
I am the one the only one<br />
<br />
==Distinguishable to distinguishable, without duplicates==<br />
For each of the <math>n</math> things, there are <math>k</math> choices, for a total of <math>\underbrace{k\cdot k\cdot\cdots\cdot k\cdot k}_n = k^n</math> ways.<br />
==Distinguishable to indistinguishable, with duplicates==<br />
This is "reverse" Balls and Urns, or essentially distributing <math>k</math> indistinguishable objects to <math>n</math> distinguishable objects. Refer to 6; this case has <math>\binom{n + k - 1}{k-1}</math> ways. Now we can just switch the <math>n</math> and the <math>k</math>, so there are <math>\binom{k+n-1}{n-1}</math> ways.<br />
<br />
==Distinguishable to indistinguishable, without duplicates==<br />
This is probably the most tedious case, as it involves the most casework. One way is to first find all the partitions (refer to 5) of <math>n</math> with <math>k</math> addends, (i.e. all solutions to <math>a_1 + a_2 + \cdots + a_k = n</math> in which the addends are indistinguishable). Then, for each partition, separately calculate the number of ways, and finally, add these results together.<br />
<br />
For example, if <math>(n,k) = (5,3)</math>, then our partitions are:<br />
<math>\{5,0,0\}</math>--this case has <math>1</math> way.<br />
<math>\{4,1,0\}</math>--we choose one of <math>n</math> to be the "<math>1</math>", so there are <math>5</math> ways.<br />
<math>\{3,2,0\}</math>--we choose three objects to be the "<math>3</math>'s" (the rest are determined after this), so there are <math>\binom53 = 10</math> ways for this.<br />
<math>\{3,1,1\}</math>--again, we choose three objects to be the "<math>3</math>'s" (the rest are determined after this), so there are <math>\binom53 = 10</math> ways for this.<br />
<math>\{2,2,1\}</math>--first, we choose one object to be the "<math>1</math>", which has <math>5</math> ways. Then, we can choose any two of the remaining four to be one of the "<math>2</math>'s", and there are <math>\binom42 = 6</math> ways for this. However, we must divide this by <math>2</math>, since the two "<math>2</math>'s" are interchangeable, and the total for this case is <math>5\cdot6\cdot\frac12 = 15</math>.<br />
<br />
Adding up, we get <math>1 + 5 + 10 + 10 + 15 = 41</math> ways.<br />
<br />
All of these problems are similar to this one in that you divide them up into smaller counting problems.<br />
<br />
==Indistinguishable to indistinguishable==<br />
This is part of the partition problem. Imagine that you are finding the number of solutions to <math>a_1 + a_2 + \cdots + a_k = n</math>, where <math>a_1,a_2,\ldots,a_k</math> are indistinguishable.<br />
<br />
This can be done with casework; the method is best explained with an example: say that <math>(n,k) = (5,3)</math>. Our partitions are then <math>\{5,0,0\},\{4,1,0\},\{3,2,0\},\{3,1,1\},\{2,2,1\}</math>, so there are <math>5</math> partitions.<br />
==Indistinguishable to distinguishable (Balls and Urns/ Sticks and Stones)==<br />
This is "Balls and Urns". In general, if one has <math>n</math> indistinguishable objects that one wants to distribute to <math>k</math> distinguishable objects, then there are <math>\binom{n + k - 1}{k - 1}</math> ways to do so.<br />
<br />
Imagine that there are <math>k - 1</math> dividers, denoted by <math>\mid</math>, and <math>n</math> objects, denoted by <math>\star</math>, so we have <math>\underbrace{\mid\mid\mid\cdots\mid\mid\mid}_{k-1}</math> and <math>\underbrace{\star\star\star\cdots\star\star\star}_n</math>. Then, label the regions formed by the dividers, so we get <math>1\mid2\mid3\mid\cdots\mid(k - 2)\mid(k - 1)\mid k</math> (since there are <math>k-1</math> dividers) and our <math>n</math> objects <math>\underbrace{\star\star\star\cdots\star\star\star}_n</math>. We can now see that there are <math>k</math> distinct regions (corresponding to the <math>k</math> distinguishable objects) in which we can place our <math>n</math> identical objects (corresponding to the <math>n</math> indistinguishable objects that one is distributing), which is analogous to the original problem. Finally, there are <math>\binom{n+k-1}n=\binom{n + k - 1}{k - 1}</math> arrangements of the <math>n</math> stars and the <math>(k - 1)\ \mid\text{'s}</math> by basic permutations with repeated items. '''Note:''' the number of stars that appears in each of the regions <math>1\mid2\mid3\mid\cdots\mid(k - 2)\mid(k - 1)\mid k</math> represents the number of indistinguishable objects (the <math>n</math> stars) given to a particular distinguishable object (of the <math>k</math> dividers). For example, if we're distributing <math>9</math> stars to <math>5</math> kids, then one arrangement is <math>\star\mid\mid\star\star\star\mid\star\star\star\mid\star\star</math> corresponding to <math>1</math> star to the first kid, <math>0</math> to the second, <math>3</math> to the third, <math>3</math> to the fourth, and <math>2</math> to the fifth.<br />
<br />
One problem that can be solved by this is finding the number of solutions to <math>a_1 + a_2 + \cdots + a_k = n</math>, where <math>a_1,a_2,\ldots,a_n\ge0</math>, which has <math>\binom{n + k - 1}{k - 1}</math> solutions.<br />
<br />
[[Category:Combinatorics]]</div>Patopato