So this blog wouldnt contain any code, just pure math that I think might help with programming↵
+ I wouild recmmend knowing math because know good math allow you to save A LOT of code.↵
+ This is my blog to compile what I've learned, I hope that when you read this you would learn something.↵
↵
+ Theory:↵
+ definition n! = n * (n-1) * (n-2) * .... * 1↵
+ amount of ways to permute a sequence of n numbers is n!, this can be proven by fixing the first element which we can take n element as the first element, then it would be a sub problem, permutating n-1 elemnts, so we get n! = (n-1)! * n -> we have proven for all n↵
+ amount of ways to permute k elements out of n elements is (n!/ (n — k)!), this is simple because we can use the same proof as n!, but we have and ending at n — k.↵
+ amount of ways to of picking k elements out of n elements where order doesen't matter is (n! / (n-k)!k!), this is simple, we continue from permutating k elements out of n elements, and then because the k element could be permutate in k! (first proof), we can just divide by k! so we fix the order without overcounting the permutations.↵
+ The amount of ways to permute a sequence of duplicate elemnts is (n! / (c1! * c2! * c3!...)) where c stand for each character amount, why this work, for each subset of characters, we could permute then c1! ways, because its duplicate, all permutation the same so we want to divide by c1! so they dont count duplicates.↵
↵
Problems:↵
1. How many distinguishable arrangements are there of 1 brown tile, 1 purple tile, 2↵
green tiles, and 3 yellow tiles in a row from left to right? (Tiles of the same color are↵
indistinguishable.)↵
- Use the word arranging theory I said above↵
- (1 + 1 + 2 + 3)! / 3! / 2! = 7! / 3! / 2! = 420↵
2. A child builds towers using identically shaped cubes of different colors. How many↵
different towers with a height of 8 cubes can the child build with 2 red cubes, 3 blue↵
cubes, and 4 green cubes? (One cube will be left out.)↵
+ This is simple test, casework:↵
+ if red cubes is left out, 8! / (3! * 4!) = 280↵
+ if blue cub is left out, 8! / (2! * 2! * 4!) = 420↵
+ if green cube is left out, 8! / (2! * 3! * 3!) = 560↵
+ answer = 280 + 420 + 560 = 1260 ways.↵
3. A license plate in a certain state consists of 4 digits, not necessarily distinct, and 2↵
letters, also not necessarily distinct. These six characters may appear in any order, except↵
that the two letters must appear next to each other. How many distinct license plates↵
are possible?↵
+ Consider the permutations in letter and numbers↵
+ for the numbers we have 4 numbers, and foe each number it could be either from 1 to 10↵
+ so the amount of permutation for the numbers is 10^4↵
+ for each character we have 26 options, so we 26^2↵
+ for the amount of different license plate, the positions I could choose for the 2 characters is (6 — 2 + 1) because it could be entirely to the left of the numbers↵
answer = 10^4 * 26^2 * 5 = 33,800,000↵
↵
4. At a gathering of 30 people, there are 20 people who all know each other and 10↵
people who know no one. People who know each other hug, and people who do not know↵
each other shake hands. How many handshakes occur within the group?↵
+ Total amount of Handshake is C(30, 2) ↵
+ Amount of handshake/hug that people who know each other do is C(20 2)↵
+ we can caculate by hand as below (30 * 29) / 2 — (20 * 19) / 2↵
=> 15 * 29 — 190 = 435 — 190 = 245↵
↵
5. In a table tennis tournament every participant played every other participant exactly↵
once. Although there were twice as many right-handed players as left-handed players, the↵
number of games won by left-handed players was 40% more than the number of games↵
won by right-handed players. (There were no ties and no ambidextrous players.) What is↵
the total number of games played?↵
+ This problem compared to the previous problem is more obscure but we could solve by putting limits on N could be↵
+ Consider the number of right player = 2n, left player = n;↵
+ Ratio of games win, left player : right player -> 7 : 5↵
+ total amount of games = C(3n, 2)↵
+ we get this inequality -> 5/12 * C(3n,2) >= C(2n, 2)↵
-> 2n(2n-1) <= 5/12 * 3n(3n-1)↵
- > 24(n-1) <= 15(3n-1)↵
- > 48n — 24 <= 45n — 15↵
- > 3n <= 9 => n <= 3 ↵
After getting n <= 3, we can just test n for every value = {1,2,3} and find the valid one.↵
↵
6.n't contain any code, just pure math that I think might help with programming.↵
↵
+ I would recommend learning math because knowing good math allows you to save A LOT of code.↵
+ This is my blog to compile what I've learned. I hope that when you read this, you learn something.↵
↵
## Theory↵
↵
+ Definition: $n! = n\cdot(n-1)\cdot(n-2)\cdots1$, with $0!=1$.↵
↵
+ The number of ways to permute a sequence of $n$ distinct elements is $n!$. This can be proven by choosing the first element: we have $n$ choices for it. Then we have a subproblem of permuting the remaining $n-1$ elements, so we get $n!=n\cdot(n-1)!$. Starting with $0!=1$, this proves the formula for all nonnegative integers $n$.↵
↵
+ The number of ways to choose and permute $k$ elements out of $n$ distinct elements is $\frac{n!}{(n-k)!}$. This is simple because we can use the same proof as for $n!$, but stop after choosing $k$ elements:↵
↵
$$n\cdot(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!}.$$↵
↵
+ The number of ways to pick $k$ elements out of $n$ distinct elements, where order doesn't matter, is $\frac{n!}{(n-k)!k!}$. This is simple: we start with the number of ways to choose and permute $k$ elements out of $n$. Since the same $k$ elements can be permuted in $k!$ ways, we divide by $k!$ so we don't overcount their different orders. We write this as $\binom{n}{k}$.↵
↵
+ The number of ways to permute a sequence containing duplicate elements is $\frac{n!}{c_1!c_2!c_3!\cdots}$, where $c_i$ stands for the number of occurrences of each distinct element. Why does this work? For each group of identical elements, we could permute them in $c_i!$ ways, but all these permutations look the same. Therefore, we divide by $c_i!$ for each group so we don't count duplicates.↵
↵
## Problems↵
↵
### 1.↵
↵
How many distinguishable arrangements are there of 1 brown tile, 1 purple tile, 2 green tiles, and 3 yellow tiles in a row from left to right? Tiles of the same color are indistinguishable.↵
↵
+ Use the theory for arranging repeated elements that I mentioned above.↵
↵
$$\frac{(1+1+2+3)!}{3!\cdot2!}=\frac{7!}{3!\cdot2!}=420.$$↵
↵
### 2.↵
↵
A child builds towers using identically shaped cubes of different colors. How many different towers with a height of 8 cubes can the child build with 2 red cubes, 3 blue cubes, and 4 green cubes? One cube will be left out.↵
↵
+ This is simple casework.↵
↵
+ If a red cube is left out:↵
↵
$$\frac{8!}{3!\cdot4!}=280.$$↵
↵
+ If a blue cube is left out:↵
↵
$$\frac{8!}{2!\cdot2!\cdot4!}=420.$$↵
↵
+ If a green cube is left out:↵
↵
$$\frac{8!}{2!\cdot3!\cdot3!}=560.$$↵
↵
+ The answer is $280+420+560=1260$ ways.↵
↵
### 3.↵
↵
A license plate in a certain state consists of 4 digits, not necessarily distinct, and 2 letters, also not necessarily distinct. These six characters may appear in any order, except that the two letters must appear next to each other. How many distinct license plates are possible?↵
↵
+ Consider the choices for the letters and digits.↵
↵
+ We have 4 digits, and each digit can be anything from 0 to 9.↵
↵
+ So the number of possibilities for the digits is $10^4$.↵
↵
+ For each letter, we have 26 options, so we have $26^2$ possibilities.↵
↵
+ The number of positions we can choose for the pair of letters is $6-2+1=5$, including placing them entirely to the left of the digits.↵
↵
+ The answer is↵
↵
$$10^4\cdot26^2\cdot5=33\,800\,000.$$↵
↵
### 4.↵
↵
At a gathering of 30 people, there are 20 people who all know each other and 10 people who know no one. People who know each other hug, and people who do not know each other shake hands. How many handshakes occur within the group?↵
↵
+ The total number of handshakes and hugs is $\binom{30}{2}$.↵
↵
+ The number of hugs between people who know each other is $\binom{20}{2}$.↵
↵
+ We can calculate the number of handshakes by hand as follows:↵
↵
$$\frac{30\cdot29}{2}-\frac{20\cdot19}{2}=15\cdot29-190=435-190=245.$$↵
↵
### 5.↵
↵
In a table tennis tournament, every participant played every other participant exactly once. Although there were twice as many right-handed players as left-handed players, the number of games won by left-handed players was 40% more than the number of games won by right-handed players. There were no ties and no ambidextrous players. What is the total number of games played?↵
↵
+ Compared to the previous problem, this problem is more obscure, but we can solve it by putting a limit on what $n$ can be.↵
↵
+ Let the number of right-handed players be $2n$ and the number of left-handed players be $n$.↵
↵
+ The ratio of games won by left-handed players to games won by right-handed players is $7:5$.↵
↵
+ The total number of games is $\binom{3n}{2}$.↵
↵
+ Every game between two right-handed players gives one win to a right-handed player, so we get this inequality:↵
↵
$$\frac{5}{12}\binom{3n}{2}\geq\binom{2n}{2}.$$↵
↵
$$2n(2n-1)\leq\frac{5}{12}\cdot3n(3n-1).$$↵
↵
$$24(2n-1)\leq15(3n-1).$$↵
↵
$$48n-24\leq45n-15.$$↵
↵
$$3n\leq9\implies n\leq3.$$↵
↵
+ After getting $n\leq3$, we can test every value in $\{1,2,3\}$ and find the valid one.↵
↵
### 6.↵
↵
Each square in a $3\times3$ grid of squares is colored red, white, blue, or green so that every $2\times2$ square contains one square of each color. How many different colorings are possible?↵
↵
+ This problem is really great because it involves some casework.↵
↵
+ At first, it looks really hard, but if you fix one $2\times2$ square, you can work out the others.↵
↵
+ Let's say we fix the top-left $2\times2$ square. We have the following arrangement:↵
↵
$$\begin{matrix} A & B & x_1 \\ C & D & x_2 \\ x_5 & x_4 & x_3 \end{matrix}$$↵
↵
+ Here, the $x_i$ represent empty squares, and $A,B,C,D$ are the four different colors. The number of ways to arrange these colors in the fixed square is $4!$.↵
↵
+ Now let's fix the other elements. Consider the pair $(x_1,x_2)$. We can put either $(A,C)$ or $(C,A)$. Let's first put $(C,A)$.↵
↵
+ If we put $(C,A)$, then $(x_5,x_4)$ must be $(A,B)$, because choosing $(B,A)$ would create a duplicate $A$ in the bottom-right $2\times2$ square.↵
↵
+ If we put $(A,C)$, then either $(A,B)$ or $(B,A)$ works for $(x_5,x_4)$.↵
↵
+ After fixing $x_1,x_2,x_4,x_5$, the value of $x_3$ is automatically fixed.↵
↵
+ So the number of ways is↵
↵
$$4!(2+1)=24\cdot3=72.$$↵
↵
### 7.↵
↵
Henry's Hamburger Haven offers its hamburgers with the following condiments: ketchup, mustard, mayonnaise, tomato, lettuce, pickles, cheese, and onions. A customer can choose one, two, or three meat patties and any collection of condiments. How many different kinds of hamburgers can be ordered?↵
↵
+ The number of condiments is 8.↵
↵
+ The number of patties the customer can choose is in $\{1,2,3\}$.↵
↵
+ Each condiment can either be included or left out, so the total number of ways is↵
↵
$$2^8\cdot3=768.$$↵
↵
### 8.↵
↵
How many 15-letter arrangements of 5 A's, 5 B's, and 5 C's have no A's in the first 5 letters, no B's in the next 5 letters, and no C's in the last 5 letters?↵
↵
+ If we fix two of the three letters, then we can fix the last letter. Let's fix A and C because they are the letters allowed in the middle block.↵
↵
+ If we fix the arrangement in the middle 5 positions, we can then arrange the remaining letters in the first 5 and last 5 positions.↵
↵
+ The formula we want is↵
↵
$$\sum_{k=0}^{5}\binom{5}{k}^3.$$↵
↵
+ Let's explain why. Let $k$ be the number of A's in the middle 5 positions, where $k$ goes from 0 to 5.↵
↵
+ The number of ways to put these A's in the middle is $\binom{5}{k}$.↵
↵
+ After putting the A's in the middle, the positions of the C's in the middle are fixed. There are $5-k$ of them.↵
↵
+ After that, we must put the remaining $k$ C's in the first 5 positions, giving $\binom{5}{k}$ arrangements.↵
↵
+ We must also put the remaining $5-k$ A's in the last 5 positions, giving $\binom{5}{5-k}$ arrangements.↵
↵
+ All remaining positions are B's.↵
↵
+ Because $\binom{5}{k}=\binom{5}{5-k}$ by symmetry, the final formula is↵
↵
$$\sum_{k=0}^{5}\binom{5}{k}^3.$$↵
↵
### 9.↵
↵
Three numbers, $a_1,a_2,a_3$, are drawn randomly and without replacement from the set $\{1,2,3,\ldots,1000\}$. Three other numbers, $b_1,b_2,b_3$, are then drawn randomly and without replacement from the remaining set of 997 numbers.↵
↵
Let $p$ be the probability that, after suitable rotation, a brick of dimensions $a_1\times a_2\times a_3$ can be enclosed in a box of dimensions $b_1\times b_2\times b_3$, with the sides of the brick parallel to the sides of the box. If $p$ is written as a fraction in lowest terms, what is the sum of the numerator and denominator?↵
↵
+ Denote the sets by $A=\{a_1,a_2,a_3\}$ and $B=\{b_1,b_2,b_3\}$.↵
↵
+ Let's consider the set $\{a_1,a_2,a_3,b_1,b_2,b_3\}$. The number of ways to pick this set is $\binom{1000}{6}$.↵
↵
+ Now we just need to count the valid ways to assign the elements of each chosen set to $A$ and $B$. Multiplying this by the number of ways to pick the set gives the total number of valid assignments.↵
↵
+ Name the six elements $x_1,x_2,x_3,x_4,x_5,x_6$ in increasing order. There are some observations we can make.↵
↵
+ $x_1$ must be in set $A$. If $x_1$ were in $B$, it would be smaller than every element in $A$, so the box could not contain the brick.↵
↵
+ $x_6$ must be in set $B$, because no other element is bigger than $x_6$.↵
↵
+ So we have $\{x_2,x_3,x_4,x_5\}$ left. Now we can try every combination and check whether the sorted dimensions of $A$ are smaller than the corresponding sorted dimensions of $B$.↵
↵
1. $A=\{x_1,x_2,x_3\}$, $B=\{x_4,x_5,x_6\}$: correct.↵
↵
2. $A=\{x_1,x_2,x_4\}$, $B=\{x_3,x_5,x_6\}$: correct.↵
↵
3. $A=\{x_1,x_3,x_4\}$, $B=\{x_2,x_5,x_6\}$: correct.↵
↵
4. $A=\{x_1,x_2,x_5\}$, $B=\{x_3,x_4,x_6\}$: correct.↵
↵
5. $A=\{x_1,x_3,x_5\}$, $B=\{x_2,x_4,x_6\}$: correct.↵
↵
6. $A=\{x_1,x_4,x_5\}$, $B=\{x_2,x_3,x_6\}$: incorrect.↵
↵
+ So there are 5 valid assignments for every set of six elements. There are $\binom{6}{3}$ equally likely assignments in total, so↵
↵
$$p=\frac{5}{\binom{6}{3}}=\frac{5}{20}=\frac14=25\%.$$
+ I wouild recmmend knowing math because know good math allow you to save A LOT of code.↵
+ This is my blog to compile what I've learned, I hope that when you read this you would learn something.↵
↵
+ Theory:↵
+ definition n! = n * (n-1) * (n-2) * .... * 1↵
+ amount of ways to permute a sequence of n numbers is n!, this can be proven by fixing the first element which we can take n element as the first element, then it would be a sub problem, permutating n-1 elemnts, so we get n! = (n-1)! * n -> we have proven for all n↵
+ amount of ways to permute k elements out of n elements is (n!/ (n — k)!), this is simple because we can use the same proof as n!, but we have and ending at n — k.↵
+ amount of ways to of picking k elements out of n elements where order doesen't matter is (n! / (n-k)!k!), this is simple, we continue from permutating k elements out of n elements, and then because the k element could be permutate in k! (first proof), we can just divide by k! so we fix the order without overcounting the permutations.↵
+ The amount of ways to permute a sequence of duplicate elemnts is (n! / (c1! * c2! * c3!...)) where c stand for each character amount, why this work, for each subset of characters, we could permute then c1! ways, because its duplicate, all permutation the same so we want to divide by c1! so they dont count duplicates.↵
↵
Problems:↵
1. How many distinguishable arrangements are there of 1 brown tile, 1 purple tile, 2↵
green tiles, and 3 yellow tiles in a row from left to right? (Tiles of the same color are↵
indistinguishable.)↵
- Use the word arranging theory I said above↵
- (1 + 1 + 2 + 3)! / 3! / 2! = 7! / 3! / 2! = 420↵
2. A child builds towers using identically shaped cubes of different colors. How many↵
different towers with a height of 8 cubes can the child build with 2 red cubes, 3 blue↵
cubes, and 4 green cubes? (One cube will be left out.)↵
+ This is simple test, casework:↵
+ if red cubes is left out, 8! / (3! * 4!) = 280↵
+ if blue cub is left out, 8! / (2! * 2! * 4!) = 420↵
+ if green cube is left out, 8! / (2! * 3! * 3!) = 560↵
+ answer = 280 + 420 + 560 = 1260 ways.↵
3. A license plate in a certain state consists of 4 digits, not necessarily distinct, and 2↵
letters, also not necessarily distinct. These six characters may appear in any order, except↵
that the two letters must appear next to each other. How many distinct license plates↵
are possible?↵
+ Consider the permutations in letter and numbers↵
+ for the numbers we have 4 numbers, and foe each number it could be either from 1 to 10↵
+ so the amount of permutation for the numbers is 10^4↵
+ for each character we have 26 options, so we 26^2↵
+ for the amount of different license plate, the positions I could choose for the 2 characters is (6 — 2 + 1) because it could be entirely to the left of the numbers↵
answer = 10^4 * 26^2 * 5 = 33,800,000↵
↵
4. At a gathering of 30 people, there are 20 people who all know each other and 10↵
people who know no one. People who know each other hug, and people who do not know↵
each other shake hands. How many handshakes occur within the group?↵
+ Total amount of Handshake is C(30, 2) ↵
+ Amount of handshake/hug that people who know each other do is C(20 2)↵
+ we can caculate by hand as below (30 * 29) / 2 — (20 * 19) / 2↵
=> 15 * 29 — 190 = 435 — 190 = 245↵
↵
5. In a table tennis tournament every participant played every other participant exactly↵
once. Although there were twice as many right-handed players as left-handed players, the↵
number of games won by left-handed players was 40% more than the number of games↵
won by right-handed players. (There were no ties and no ambidextrous players.) What is↵
the total number of games played?↵
+ This problem compared to the previous problem is more obscure but we could solve by putting limits on N could be↵
+ Consider the number of right player = 2n, left player = n;↵
+ Ratio of games win, left player : right player -> 7 : 5↵
+ total amount of games = C(3n, 2)↵
+ we get this inequality -> 5/12 * C(3n,2) >= C(2n, 2)↵
-> 2n(2n-1) <= 5/12 * 3n(3n-1)↵
- > 24(n-1) <= 15(3n-1)↵
- > 48n — 24 <= 45n — 15↵
- > 3n <= 9 => n <= 3 ↵
After getting n <= 3, we can just test n for every value = {1,2,3} and find the valid one.↵
↵
6.
↵
+ I would recommend learning math because knowing good math allows you to save A LOT of code.↵
+ This is my blog to compile what I've learned. I hope that when you read this, you learn something.↵
↵
## Theory↵
↵
+ Definition: $n! = n\cdot(n-1)\cdot(n-2)\cdots1$, with $0!=1$.↵
↵
+ The number of ways to permute a sequence of $n$ distinct elements is $n!$. This can be proven by choosing the first element: we have $n$ choices for it. Then we have a subproblem of permuting the remaining $n-1$ elements, so we get $n!=n\cdot(n-1)!$. Starting with $0!=1$, this proves the formula for all nonnegative integers $n$.↵
↵
+ The number of ways to choose and permute $k$ elements out of $n$ distinct elements is $\frac{n!}{(n-k)!}$. This is simple because we can use the same proof as for $n!$, but stop after choosing $k$ elements:↵
↵
$$n\cdot(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!}.$$↵
↵
+ The number of ways to pick $k$ elements out of $n$ distinct elements, where order doesn't matter, is $\frac{n!}{(n-k)!k!}$. This is simple: we start with the number of ways to choose and permute $k$ elements out of $n$. Since the same $k$ elements can be permuted in $k!$ ways, we divide by $k!$ so we don't overcount their different orders. We write this as $\binom{n}{k}$.↵
↵
+ The number of ways to permute a sequence containing duplicate elements is $\frac{n!}{c_1!c_2!c_3!\cdots}$, where $c_i$ stands for the number of occurrences of each distinct element. Why does this work? For each group of identical elements, we could permute them in $c_i!$ ways, but all these permutations look the same. Therefore, we divide by $c_i!$ for each group so we don't count duplicates.↵
↵
## Problems↵
↵
### 1.↵
↵
How many distinguishable arrangements are there of 1 brown tile, 1 purple tile, 2 green tiles, and 3 yellow tiles in a row from left to right? Tiles of the same color are indistinguishable.↵
↵
+ Use the theory for arranging repeated elements that I mentioned above.↵
↵
$$\frac{(1+1+2+3)!}{3!\cdot2!}=\frac{7!}{3!\cdot2!}=420.$$↵
↵
### 2.↵
↵
A child builds towers using identically shaped cubes of different colors. How many different towers with a height of 8 cubes can the child build with 2 red cubes, 3 blue cubes, and 4 green cubes? One cube will be left out.↵
↵
+ This is simple casework.↵
↵
+ If a red cube is left out:↵
↵
$$\frac{8!}{3!\cdot4!}=280.$$↵
↵
+ If a blue cube is left out:↵
↵
$$\frac{8!}{2!\cdot2!\cdot4!}=420.$$↵
↵
+ If a green cube is left out:↵
↵
$$\frac{8!}{2!\cdot3!\cdot3!}=560.$$↵
↵
+ The answer is $280+420+560=1260$ ways.↵
↵
### 3.↵
↵
A license plate in a certain state consists of 4 digits, not necessarily distinct, and 2 letters, also not necessarily distinct. These six characters may appear in any order, except that the two letters must appear next to each other. How many distinct license plates are possible?↵
↵
+ Consider the choices for the letters and digits.↵
↵
+ We have 4 digits, and each digit can be anything from 0 to 9.↵
↵
+ So the number of possibilities for the digits is $10^4$.↵
↵
+ For each letter, we have 26 options, so we have $26^2$ possibilities.↵
↵
+ The number of positions we can choose for the pair of letters is $6-2+1=5$, including placing them entirely to the left of the digits.↵
↵
+ The answer is↵
↵
$$10^4\cdot26^2\cdot5=33\,800\,000.$$↵
↵
### 4.↵
↵
At a gathering of 30 people, there are 20 people who all know each other and 10 people who know no one. People who know each other hug, and people who do not know each other shake hands. How many handshakes occur within the group?↵
↵
+ The total number of handshakes and hugs is $\binom{30}{2}$.↵
↵
+ The number of hugs between people who know each other is $\binom{20}{2}$.↵
↵
+ We can calculate the number of handshakes by hand as follows:↵
↵
$$\frac{30\cdot29}{2}-\frac{20\cdot19}{2}=15\cdot29-190=435-190=245.$$↵
↵
### 5.↵
↵
In a table tennis tournament, every participant played every other participant exactly once. Although there were twice as many right-handed players as left-handed players, the number of games won by left-handed players was 40% more than the number of games won by right-handed players. There were no ties and no ambidextrous players. What is the total number of games played?↵
↵
+ Compared to the previous problem, this problem is more obscure, but we can solve it by putting a limit on what $n$ can be.↵
↵
+ Let the number of right-handed players be $2n$ and the number of left-handed players be $n$.↵
↵
+ The ratio of games won by left-handed players to games won by right-handed players is $7:5$.↵
↵
+ The total number of games is $\binom{3n}{2}$.↵
↵
+ Every game between two right-handed players gives one win to a right-handed player, so we get this inequality:↵
↵
$$\frac{5}{12}\binom{3n}{2}\geq\binom{2n}{2}.$$↵
↵
$$2n(2n-1)\leq\frac{5}{12}\cdot3n(3n-1).$$↵
↵
$$24(2n-1)\leq15(3n-1).$$↵
↵
$$48n-24\leq45n-15.$$↵
↵
$$3n\leq9\implies n\leq3.$$↵
↵
+ After getting $n\leq3$, we can test every value in $\{1,2,3\}$ and find the valid one.↵
↵
### 6.↵
↵
Each square in a $3\times3$ grid of squares is colored red, white, blue, or green so that every $2\times2$ square contains one square of each color. How many different colorings are possible?↵
↵
+ This problem is really great because it involves some casework.↵
↵
+ At first, it looks really hard, but if you fix one $2\times2$ square, you can work out the others.↵
↵
+ Let's say we fix the top-left $2\times2$ square. We have the following arrangement:↵
↵
$$\begin{matrix} A & B & x_1 \\ C & D & x_2 \\ x_5 & x_4 & x_3 \end{matrix}$$↵
↵
+ Here, the $x_i$ represent empty squares, and $A,B,C,D$ are the four different colors. The number of ways to arrange these colors in the fixed square is $4!$.↵
↵
+ Now let's fix the other elements. Consider the pair $(x_1,x_2)$. We can put either $(A,C)$ or $(C,A)$. Let's first put $(C,A)$.↵
↵
+ If we put $(C,A)$, then $(x_5,x_4)$ must be $(A,B)$, because choosing $(B,A)$ would create a duplicate $A$ in the bottom-right $2\times2$ square.↵
↵
+ If we put $(A,C)$, then either $(A,B)$ or $(B,A)$ works for $(x_5,x_4)$.↵
↵
+ After fixing $x_1,x_2,x_4,x_5$, the value of $x_3$ is automatically fixed.↵
↵
+ So the number of ways is↵
↵
$$4!(2+1)=24\cdot3=72.$$↵
↵
### 7.↵
↵
Henry's Hamburger Haven offers its hamburgers with the following condiments: ketchup, mustard, mayonnaise, tomato, lettuce, pickles, cheese, and onions. A customer can choose one, two, or three meat patties and any collection of condiments. How many different kinds of hamburgers can be ordered?↵
↵
+ The number of condiments is 8.↵
↵
+ The number of patties the customer can choose is in $\{1,2,3\}$.↵
↵
+ Each condiment can either be included or left out, so the total number of ways is↵
↵
$$2^8\cdot3=768.$$↵
↵
### 8.↵
↵
How many 15-letter arrangements of 5 A's, 5 B's, and 5 C's have no A's in the first 5 letters, no B's in the next 5 letters, and no C's in the last 5 letters?↵
↵
+ If we fix two of the three letters, then we can fix the last letter. Let's fix A and C because they are the letters allowed in the middle block.↵
↵
+ If we fix the arrangement in the middle 5 positions, we can then arrange the remaining letters in the first 5 and last 5 positions.↵
↵
+ The formula we want is↵
↵
$$\sum_{k=0}^{5}\binom{5}{k}^3.$$↵
↵
+ Let's explain why. Let $k$ be the number of A's in the middle 5 positions, where $k$ goes from 0 to 5.↵
↵
+ The number of ways to put these A's in the middle is $\binom{5}{k}$.↵
↵
+ After putting the A's in the middle, the positions of the C's in the middle are fixed. There are $5-k$ of them.↵
↵
+ After that, we must put the remaining $k$ C's in the first 5 positions, giving $\binom{5}{k}$ arrangements.↵
↵
+ We must also put the remaining $5-k$ A's in the last 5 positions, giving $\binom{5}{5-k}$ arrangements.↵
↵
+ All remaining positions are B's.↵
↵
+ Because $\binom{5}{k}=\binom{5}{5-k}$ by symmetry, the final formula is↵
↵
$$\sum_{k=0}^{5}\binom{5}{k}^3.$$↵
↵
### 9.↵
↵
Three numbers, $a_1,a_2,a_3$, are drawn randomly and without replacement from the set $\{1,2,3,\ldots,1000\}$. Three other numbers, $b_1,b_2,b_3$, are then drawn randomly and without replacement from the remaining set of 997 numbers.↵
↵
Let $p$ be the probability that, after suitable rotation, a brick of dimensions $a_1\times a_2\times a_3$ can be enclosed in a box of dimensions $b_1\times b_2\times b_3$, with the sides of the brick parallel to the sides of the box. If $p$ is written as a fraction in lowest terms, what is the sum of the numerator and denominator?↵
↵
+ Denote the sets by $A=\{a_1,a_2,a_3\}$ and $B=\{b_1,b_2,b_3\}$.↵
↵
+ Let's consider the set $\{a_1,a_2,a_3,b_1,b_2,b_3\}$. The number of ways to pick this set is $\binom{1000}{6}$.↵
↵
+ Now we just need to count the valid ways to assign the elements of each chosen set to $A$ and $B$. Multiplying this by the number of ways to pick the set gives the total number of valid assignments.↵
↵
+ Name the six elements $x_1,x_2,x_3,x_4,x_5,x_6$ in increasing order. There are some observations we can make.↵
↵
+ $x_1$ must be in set $A$. If $x_1$ were in $B$, it would be smaller than every element in $A$, so the box could not contain the brick.↵
↵
+ $x_6$ must be in set $B$, because no other element is bigger than $x_6$.↵
↵
+ So we have $\{x_2,x_3,x_4,x_5\}$ left. Now we can try every combination and check whether the sorted dimensions of $A$ are smaller than the corresponding sorted dimensions of $B$.↵
↵
1. $A=\{x_1,x_2,x_3\}$, $B=\{x_4,x_5,x_6\}$: correct.↵
↵
2. $A=\{x_1,x_2,x_4\}$, $B=\{x_3,x_5,x_6\}$: correct.↵
↵
3. $A=\{x_1,x_3,x_4\}$, $B=\{x_2,x_5,x_6\}$: correct.↵
↵
4. $A=\{x_1,x_2,x_5\}$, $B=\{x_3,x_4,x_6\}$: correct.↵
↵
5. $A=\{x_1,x_3,x_5\}$, $B=\{x_2,x_4,x_6\}$: correct.↵
↵
6. $A=\{x_1,x_4,x_5\}$, $B=\{x_2,x_3,x_6\}$: incorrect.↵
↵
+ So there are 5 valid assignments for every set of six elements. There are $\binom{6}{3}$ equally likely assignments in total, so↵
↵
$$p=\frac{5}{\binom{6}{3}}=\frac{5}{20}=\frac14=25\%.$$
