National Association of Math Circles

King Chickens

Variables
K: King Chicken

F: Field Marshal

C: Chicken
1. For each chicken in a flock, count the number of other chickens which that particular chicken pecks.
Formulate a conjecture about the coefficients
of the polynomials $ f_n(x) $.

Variables
K: King Chicken 1. For each chicken in a flock, count the number of other chickens which that particular chicken pecks.
Formulate a conjecture about the coefficients
of the polynomials $ f_n(x) $.

Variables
F: Field Marshall 1. For each chicken in a flock, count the number of other chickens which that particular chicken pecks.
Formulate a conjecture about the coefficients
of the polynomials $ f_n(x) $.

Variables
C: Chicken 2. How can we arrange for a flock (of any size) to have exactly one king?

Variables
K: King Chicken 2. How can we arrange for a flock (of any size) to have exactly one king?

Variables
F: Field Marshall 2. How can we arrange for a flock (of any size) to have exactly one king?

Variables
C: Chicken 3. If a chicken has the barnyard to itself, of course it is king. How many kings will there be in a flock with two chickens?

Variables
K: King Chicken 3. If a chicken has the barnyard to itself, of course it is king. How many kings will there be in a flock with two chickens?

Variables
F: Field Marshall 3. If a chicken has the barnyard to itself, of course it is king. How many kings will there be in a flock with two chickens?

Variables
C: Chicken 4. There are essentially two different possible pecking orders for a flock with three chickens. How many of the three chickens are kings in each case?

Variables
K: King Chicken 4. There are essentially two different possible pecking orders for a flock with three chickens. How many of the three chickens are kings in each case?

Variables
F: Field Marshall 4. There are essentially two different possible pecking orders for a flock with three chickens. How many of the three chickens are kings in each case?

Variables
C: Chicken
1. Suppose that pecking were transitive, meaning that given any three chickens, if C1 -> C2 and C2 -> C3. Show that in this case there must be some chicken who pecks all the others

Variables
K: King Chicken
1. Suppose that pecking were transitive, meaning that given any three chickens, if C1 -> C2 and C2 -> C3. Show that in this case there must be some chicken who pecks all the others

Variables
F: Field Marshall
1. Suppose that pecking were transitive, meaning that given any three chickens, if C1 -> C2 and C2 -> C3. Show that in this case there must be some chicken who pecks all the others

Variables
C: Chicken 2. Find a flock of six chickens in which every chicken is a king.

Variables
K: King Chicken 2. Find a flock of six chickens in which every chicken is a king.

Variables
F: Field Marshall 2. Find a flock of six chickens in which every chicken is a king.

Variables
C: Chicken 3. If a flock has exactly one king, prove that he must peck all the other chickens.

Variables
K: King Chicken 3. If a flock has exactly one king, prove that he must peck all the other chickens.

Variables
F: Field Marshall 3. If a flock has exactly one king, prove that he must peck all the other chickens.

Variables
C: Chicken
4. "Let K be a king which is pecked by some other chicken. Then there must be a king among the field marshalls of K." Is this statement valid for every pecking order? Either prove this assertion or find a counterexample.

Variables
K: King Chicken
4. "Let K be a king which is pecked by some other chicken. Then there must be a king among the field marshalls of K." Is this statement valid for every pecking order? Either prove this assertion or find a counterexample.

Variables
F: Field Marshall
4. "Let K be a king which is pecked by some other chicken. Then there must be a king among the field marshalls of K." Is this statement valid for every pecking order? Either prove this assertion or find a counterexample.

Variables
C: Chicken The arbelos consists of three points $ A,B $ and $ C $ which are collinear, together with the semicircles $ ADB $, $ AXC $ and $ CYB $ as shown in Figure 1. In the figure $ \overline {CD} $ has been added to the figure tangent to the two small semicircles. $ \overline {AD} $ intersects a small semicircle at $ X $ and $ \overline{BD} $ intersects the other small semicircle at $ Y $. $ \overline{XY} $ intersects $ \overline{AD} $ at $ P $. Prove the area of the arbelos is equal to the area of the circle with diameter $ \overline{CD} $, $ \overline{XY} $ and $ \overline{CD} $ bisect each other, and $ \overline{XY} $ is tangent to the small semicircles.

Variables


Variables
Write an integer $ a $ in terms of its decimal expansion: $ a = a_0 + 10 a_1 + 100 a_2 + \cdots + a_d 10^d $. Prove that $ a $ is divisible by 8 if and only if $ a_0 + 10 a_1 + 100 a_2 $ is.

Variables


Variables
Tower of Hanoi: Arrange the three pegs in a circle. Let $ Q_n $ be the number of moves it takes to move a tower of $ n $ discs from peg A to peg B with all moves being clockwise, and $ R_n $ with all moves being counter-clockwise. Express $ Q_n $ and $ R_n $ recursively. Alternatively: prove that $ Q_0 = R_0 = 0 $ and otherwise $ Q_n = 2R_{n-1} $ and $ R_n = Q_n + Q_{n-1} + 1 $.

Variables


Variables
How many ways are there to choose a president, a vice-president, andtreasurer from a club of 15, assuming all three are different people?

Variables


Variables
Construct with proof, the twin circles in a given arbelos with a straightedge and compass.

Variables


Variables
Write an integer $ a $ in terms of its decimal expansion: $ a = a_0 + 10 a_1 + 100 a_2 + \cdots + a_d 10^d $. Come up and prove a divisibility test for powers of 2.

Variables


Variables
Tower of Hanoi: A double tower consists of two discs of each of $ n $ sizes. How many moves does it take to transfer a double tower from peg A to peg B? (As usual, a bigger disc may never be placed on top of a smaller disc, but equal discs may be placed on top of each other.)

Variables


Variables
How many diagonals are there in a convex $ n $-gon?

Variables


Variables
Find the radius of the circle tangent to all three of the semicircles that form the arbelos (See Figure 4) in terms of the radii of these three semicircles. (This is Proposition 6 in Archimedes' \emph{Book of Lemmas}).

Variables


Variables
You can make Venn diagrams using circles that cut the plane into two regions with one circle, four regions with two circles, and eight regions with three circles. Is it possible to make sixteen regions with four circles? (Generalize: how many regions can be made with n circles?)

Variables


Variables
How many ways to put a white and black rook on achessboard so that neither can attack the other? (Rooks can onlyattack along rows and columns -- not along the diagonals.)

Variables


Variables
({\bf Pappus}) The chain of inscribed circles, $ C_n $, in an arbelos has the following property. The distance from the diameter of the largest semicircle to the center of the $ nth $ circle in the chain, $ C_n $, is exactly equal to $ n\cdot d_n $, where $ d_n $ is the diameter of $ C_n $. (Hint: Use inversion in a circle orthogonal to $ C_n $.)

Variables


Variables
Write an integer $ a $ in terms of its decimal expansion: $ a = a_0 + 10 a_1 + 100 a_2 + \cdots + a_d 10^d $. Prove that $ a $ is divisible by 5 if and only if $ a_0 $ is.

Variables


Variables
When you cut the plane with $ n $ lines, how many {\em bounded} regions can you make?

Variables


Variables
How many ways to put a white and black king on achessboard so that neither attacks the other? (A king attacks onlythose squares adjacent to it, so a king away from the edge of theboard attacks the 8 adjacent squares.)

Variables


Variables
Let $ \theta = 2\pi/17. $ Compute $ \cos\theta +\cos4\theta +\cos9\theta +\cos16\theta + \cdots +\cos\ 16^2\theta. $

Variables


Variables
Write an integer $ a $ in terms of its decimal expansion: $ a = a_0 + 10 a_1 + 100 a_2 + \cdots + a_d 10^d $. Prove that $ a $ is divisible by 10 if and only if $ a_0 = 0 $.

Variables


Variables
When you cut the plane with $ n $ "zig-zags" (two antiparallel rays joined by a line segment), how many regions can you divide the plane into?

Variables


Variables
If you have an alphabet of 26 letters, how many 3-letterwords can you make? What if the three letters all haveto be different? How many 5 letter words can you make,if you can repeat letters, but can't have 2 in a rowthat are the same?

Variables


Variables
Convince yourself that $ {\displaystyle\frac{1}{16}} \left(-1 +\sqrt{17} + \sqrt{34-2\sqrt{17}} + 2\sqrt{17 + 3\sqrt{17} - \sqrt {34 - 2 \sqrt17}- 2\sqrt{34 +2\sqrt{17}}} \right) $ is constructible by constructing $ 17 +3\sqrt{17} - \sqrt{34 -2\sqrt{17}} - 2 \sqrt{34 +2\sqrt{17}} $

Variables


Variables
Write an integer $ a $ in terms of its decimal expansion: $ a = a_0 + 10 a_1 + 100 a_2 + \cdots + a_d 10^d $. Prove that $ a $ is divisible by 3 if and only if $ a_0 + a_1 + a_2 + \cdots $ is.

Variables


Variables
Josephus problem: $ n $ people sit in a circle. Going around the circle, you alternately say "skip, dismissed, skip, dismissed", until finally only one person remains. For instance, with 4 people, you skip person 1, dismiss person 2, skip person 3, dismiss person 4, skip person 1, dismiss person 3, and finally person 1 remains. We denote this as $ J(n) = 1 $.For what even numbers $ 2n $ is it true that $ J(2n) = 2J(n) - 1 $?

Variables


Variables
How many rearrangements can be made of the letters in the following words:VECTOR, TRUST, CARAVAN, CLOSENESS, MATHEMATICAL? (For example, for``VECTOR'', some possibilities include: VECTRO, OTCEVR, and ROTVEC.)

Variables


Variables
If $ a $ is even and $ p $ is a prime that is not a factor of $ a $ and $ p|a^2 +1 $ (the notation $ a|b $ stands for $ a $ divides $ b $), then $ p =4k + 1 $ for some integer $ k $.

Variables


Variables
Write an integer $ a $ in terms of its decimal expansion: $ a = a_0 + 10 a_1 + 100 a_2 + \cdots + a_d 10^d $. Prove that $ a $ is divisible by 9 if and only if $ a_0 + a_1 + a_2 + \cdots $ is.

Variables


Variables
Josephus problem: $ n $ people sit in a circle. Going around the circle, you alternately say "skip, dismissed, skip, dismissed", until finally only one person remains. For instance, with 4 people, you skip person 1, dismiss person 2, skip person 3, dismiss person 4, skip person 1, dismiss person 3, and finally person 1 remains. We denote this as $ J(4) = 1 $.For what odd numbers $ 2n + 1 $ is it true that $ J(2n+1) = 2J(n) + 1 $?

Variables


Variables
How many ways can you put 8 mutually non-attacking rookson a standard $ 8 \times 8 $ chessboard?

Variables


Variables
Let $ F_n = 2^{2^n}+ 1 $ define the sequence of Fermat numbers. Prove that $ F_n | 2^{F_n} -2 $ for all $ n $.

Variables


Variables
Write an integer $ a $ in terms of its decimal expansion: $ a = a_0 + 10 a_1 + 100 a_2 + \cdots + a_d 10^d $. Prove that $ a $ is divisible by 11 if and only if $ a_0 - a_1 + a_2 - \cdots $ is.

Variables


Variables
Josephus problem: $ n $ people sit in a circle. Going around the circle, you alternately say "skip, dismissed, skip, dismissed", until finally only one person remains. For instance, with 4 people, you skip person 1, dismiss person 2, skip person 3, dismiss person 4, skip person 1, dismiss person 3, and finally person 1 remains. We denote this as $ J(4) = 1 $.Let $ H(n) = J(n+1) - J(n) $. Show that for any even number $ 2n $, $ H(2n) = 2 $.

Variables


Variables
There are 3 rooms in a dormitory, a single, a double,and a quad. How many ways are there to assign 7 peopleto the rooms?

Variables


Variables
What geometric series has a sum of $ \displaystyle\frac{4}{3+2x} $?

Variables


Variables
Write an integer $ a $ in terms of its decimal expansion: $ a = a_0 + 10 a_1 + 100 a_2 + \cdots + a_d 10^d $. Prove that $ a $ is divisible by 7 if and only if $ \left( a_0 + 10 a_1 + 100 a_2 \right) - \left( a_3 + 10 a_4 + 100 a_5 \right) + \left( a_6 + 10 a_7 + 100 a_8 \right) - \cdots $ is.

Variables


Variables
How many 10-digit numbers have at least 2 equal digits?

Variables


Variables
Find $ \displaystyle \sum_{k=1}^{2002} \frac{1}{2^k} $.

Variables


Variables
Write an integer $ a $ in terms of its decimal expansion: $ a = a_0 + 10 a_1 + 100 a_2 + \cdots + a_d 10^d $. Prove that $ a $ is divisible by 11 if and only if $ \left( a_0 + 10 a_1 + 100 a_2 \right) - \left( a_3 + 10 a_4 + 100 a_5 \right) + \left( a_6 + 10 a_7 + 100 a_8 \right) - \cdots $ is.

Variables


Variables
Josephus problem: $ n $ people sit in a circle. Going around the circle, you alternately say "skip, dismissed, skip, dismissed", until finally only one person remains. For instance, with 4 people, you skip person 1, dismiss person 2, skip person 3, dismiss person 4, skip person 1, dismiss person 3, and finally person 1 remains. We denote this as $ J(4) = 1 $.What is a formula for $ I(n) $, the number of the penultimate survivor? That is, where should Josephus's friend sit? In our example, $ I(4) = 3 $ since person 3 is the second-to-last person to be dismissed.

Variables


Variables
How many ways can you put 2 queens on a chessboard so thatthey don't attack each other? (Queens attack both on the rowsand on the diagonals of a chessboard.)

Variables


Variables
Find $ \displaystyle \sum_{n=1}^{\infty} \frac{2006^n}{2007^n} $.

Variables


Variables
Write an integer $ a $ in terms of its decimal expansion: $ a = a_0 + 10 a_1 + 100 a_2 + \cdots + a_d 10^d $. Prove that $ a $ is divisible by 13 if and only if $ \left( a_0 + 10 a_1 + 100 a_2 \right) - \left( a_3 + 10 a_4 + 100 a_5 \right) + \left( a_6 + 10 a_7 + 100 a_8 \right) - \cdots $ is.

Variables


Variables
Solve the recurrence $ Q_0 = \alpha $, $ Q_1 = \beta $, $ Q_n = \displaystyle\frac{1+Q_{n-1}}{Q_{n-2}}, n>1 $.Hint: $ Q_4 = \displaystyle\frac{1+\alpha}{\beta} $

Variables


Variables
How many ways can you split 14 people into 7 pairs?

Variables


Variables
Find $ \displaystyle \sum_{n=1}^{\infty} \frac{n}{2^n} $.

Variables


Variables
Show that $ a = 10x+y $ is divisible by 7 if and only if $ x-2y $ is.

Variables


Variables
Solve the recurrence $ g(1) = a $, $ g(2n+1) = 3g(n) + bn + c $, $ g(2n) = 3g(n) + bn + d $.

Variables


Variables
N boys and N girls are in a dance class. How many ways arethere to pair them all up?

Variables


Variables
Find $ \displaystyle\sum_{n=1}^{\infty} \frac{F_n}{3^n} $, where $ F_n $ is the $ n $th Fibonacci number.

Variables


Variables
Write an integer $ a $ in terms of its decimal expansion: $ a = a_0 + 10 a_1 + 100 a_2 + \cdots + a_d 10^d $. Prove that $ a $ is divisible by 7 if and only if $ \left( a_0 - 3 a_1 + 2 a_2 \right) - \left( a_3 - 3 a_4 + 2 a_5 \right) + \left( a_6 - 3 a_7 + 2 a_8 \right) - \cdots $ is.

Variables


Variables
To show: all horses are the same color.If there's one horse, certainly all horses are the same color.If there are $ n $ horses, then by the induction hypothesis horses 1 through $ n - 1 $ are the same color, and horses 2 through $ n $ are the same color, but since horse 2 through $ n - 1 $ are in both sets, they overlap, so all horses are the same color.What, if anything, is wrong with this logic?

Variables


Variables
How many ways are there to choose a team of 3 students from agroup of 30?

Variables


Variables
Find $ \displaystyle\sum_{n=1}^{\infty} \frac{n^3}{3^n} $.

Variables


Variables
Explain why this proves $ P(n) $ is true for all $ n $.

Variables


Variables
One student has 6 books and another has 8. In how many wayscan they exchange 3 books of the first student for 3 books of thesecond?

Variables


Variables
Find $ \displaystyle \sum_{k=1}^{2007} \frac{1}{k(k+1)} $. Find $ \displaystyle\sum_{n=1}^{\infty}\frac{1}{n(n+1)} $.

Variables


Variables
In the quadratic $ {\underline \qquad} x^2 + {\underline \qquad} x + {\underline \qquad} $, first Al says "real" or "complex" for the roots of the quadratic. Then Betty fills in one of the blanks with a real number, and then Al fills one in, and finally Betty fills one in. If the roots are as Al declared, then he wins, otherwise Betty wins.a) Which player should win if Al says "real"? What is the winning strategy?b) Which player should win if Al says "complex"? What is the winning strategy?c) Who wins the game if Al says "real" when the polynomial is $ x^4 + {\underline \qquad} x^3 + {\underline \qquad} x^2 + {\underline \qquad} x + 1 $ instead? (How will you judge it if some roots are real and some are complex?)d) What happens when Al says "complex" with this polynomial?

Variables


Variables
How many ways can a group of 10 boys be divided into twobasketball teams of 5 boys each?

Variables


Variables
Find $ \displaystyle \sum_{k=1}^{n} \frac{1}{k(k+1)(k+2)} $. Find $ \displaystyle\sum_{n=1}^{\infty}\frac{1}{n(n+1)(n+2)} $.

Variables


Variables
Is it possible that $ ax^2 + bx + c $, $ bx^2 + cx + a $, and $ cx^2 + ax + b $ all have real roots?

Variables


Variables
Ten points are marked on the plane so that no three of them arein a straight line. How many different triangles can be formedusing these 10 points as vertices?

Variables


Variables
Find $ \displaystyle \sum_{k=1}^{n} \frac{3}{k(k+3)} $. Find $ \displaystyle\sum_{n=1}^{\infty}\frac{3}{n(n+3)} $.

Variables


Variables
The roots of $ x^2 + ax + b $ are $ c $ and $ d $, and the roots of $ x^2 + cx + d $ are $ a $ and $ b $. All of the coefficients are nonzero. What are the values of $ a $, $ b $, $ c $, and $ d $?

Variables


Variables
A group of soldiers contains 3 officers, 6 sergeants, and 30privates. How many ways can a team be formed consisting of 1 officer,2 sergeants, and 20 privates?

Variables


Variables
Show $ \displaystyle \arctan x -\arctan y = \arctan\frac{x-y}{1+xy}. $

Variables


Variables
Compute the sequence $ (a_k) $ that gives rise to the generating function $ \sum_{ k \ge 0 } a_k \, x^k = \left( \frac 1 { 1-x } \right)^2 $, by looking at the product $ \left( 1 + x + x^2 + x^3 + \cdots \right) \left( 1 + x + x^2 + x^3 + \cdots \right) $. If you look at the result, can you think of a different way to compute $ (a_k) $?

Variables


Variables
For a quadratic polynomial $ a_2 x^2 + a_1 x + a_0 $, call the roots $ r_1 $ and $ r_2 $. Define $ s_k = r_1^k + r_2^k $ and $ p = r_1 r_2 $.Find formulas for $ s_1 $, $ s_2 $, $ s_k $, and $ p $ in terms of the coefficients $ a_2 $, $ a_1 $, and $ a_0 $.

Variables


Variables
Ten points are marked on a straight line and 11 on anotherline, parallel to the first. How many triangles can be formedfrom these points? How many quadrilaterals?

Variables


Variables
First show $ \displaystyle \arctan \frac{120}{119} -\arctan\frac{1}{239} = \frac{\pi}{4}. $ Then show that $ 4\arctan \frac{1}{5} = \arctan \frac{120}{119} $, so that$ 4\arctan \frac{1}{5} -\arctan\frac{1}{239} = \frac{\pi}{4}. $ Use the fact that $ \displaystyle \arctan x = \frac{x}{1}-\frac{x^3}{3}+\frac{x^5}{5}-\frac{x^7}{7}+\cdots $ to calculate $ \pi $ to 10 decimal places.

Variables


Variables
Define a recursive sequence by setting $ a_0 = 0 $ and $ a_{n+1} = 2 a_n + 1 $ for $ n \ge 0 $. \begin{enumerate}[(a)] \item Conjecture a formula for $ a_k $ by experimenting. \item Now put the sequence $ (a_k) $ into a generating function $ g(x) $ and find a formula for $ g(x) $ by utilizing the recursive definition of $ a_k $. \item Expand your formula for $ g(x) $ into partial fractions, and use the result to prove your conjectured formula for $ a_k $. \end{enumerate}

Variables


Variables
For a quadratic polynomial $ a_2 x^2 + a_1 x + a_0 $, call the roots $ r_1 $ and $ r_2 $. Define $ s_k = r_1^k + r_2^k $ and $ p = r_1 r_2 $.Prove that for the polynomial $ x^2 - 6x + 1 $, $ s_k $ is always an integer not divisible by 5.

Variables


Variables
How many ways can you put 10 white and 10 black checkers onthe black squares of a checkerboard?

Variables


Variables
Find $ \sqrt[3]{1729} $ to 4 decimal places in 40 seconds. (Hint 1: recall that1729 is the famous taxicab number that Ramanujan stated was the smallest integer that can be written as a sum of two cubes in two ways; $ 9^3+10^3 $ and $ 1^3+12^3 $.) (Hint 2: $ \displaystyle (x+1)^k = x^k +kx^{k-1} +\frac{k(k-1)}{1\cdot2}x^{k-2}+\frac{k(k-1)(k-2)}{1\cdot2\cdot3}x^{k-3}+\cdots $ \hspace{.1in} $ k\in \mathbb{R} $

Variables


Variables
Define a recursive sequence by setting $ a_0 = 1 $ and $ a_{n+1} = 2 a_n + n $ for $ n \ge 0 $. Find a formula for $ a_k $.

Variables


Variables
For a quadratic polynomial $ a_2 x^2 + a_1 x + a_0 $, call the roots $ r_1 $ and $ r_2 $. Define $ s_k = r_1^k + r_2^k $ and $ p = r_1 r_2 $.Find a formula for $ s_3 $ in terms of $ s_1 $ and $ s_2 $.

Variables


Variables
How many 10-digit numbers have the sum of their digits equalto 1? The sum equal to 2? To 3? To 4?

Variables


Variables
Show that $ 1 +\frac{1}{2} +\frac{1}{3}+ \cdots+ \frac{1}{n} $ can be made larger than any real number by choosing an appropriate $ n $. Then show that when all the terms with denominators that are not prime are removed, the series diverges. In other words the sum of the reciprocals of the prime numbers diverges. On the other hand, show when all the terms that contain the digit nine are deleted, the series converges. In fact, the sum is less than 90.

Variables


Variables
Given that $ x $ is a real number satisfying $ \sqrt[3]{x+9} - \sqrt[3]{x-9} = 3 $, compute $ x^2 $.

Variables


Variables
To win the California lottery, you must choose 6 numberscorrectly from a set of 51 numbers. How many ways are there toto make your 6 choices?

Variables


Variables
Note that $ 2002 = 2\cdot7\cdot11\cdot13 $. Find the sum of all the unit fractions that have denominators with only factors from the set $ \{2,7,11,13\} $. That is, find the following sum:\\ $ \frac{1}{2}+\frac{1}{4}+\frac{1}{7}+\frac{1}{8}+\frac{1}{11}+\frac{1}{13}+\frac{1}{14}+\frac{1}{16}+\frac{1}{22}+\frac{1}{26}+\frac{1}{28}+\cdots $.

Variables


Variables
The \emph{Fibonacci sequence} $ \left( f_n \right)_{ n \ge 0 } $ is given by the recursion

\[ f_0 = 0 , \ f_1 = 1 , \ f_{ n+2 } = f_{ n+1 } + f_n \ \text{ for } n \ge 0 \, . \]

Show that

\[ F(x) := \sum_{ n \ge 0 } f_n \, x^n = \frac{ x }{ 1 - x - x^2 } \]

and use this to derive a closed form for $ f_n $.

Variables


Variables
Find all solutions (real and complex) of $ \sqrt[4]{x} + \sqrt[4]{97-x} = 5 $.

Variables


Variables
A person has 10 friends. Over several days he invites someof them to a dinner party in such a way that he never invitesexactly the same group of people. How many days can he keepthis up, assuming that one of the possibilities is to asknobody to dinner?

Variables


Variables
Compute the generating function $ \displaystyle G(x) := \sum_{ n \ge 0 } g_n \, x^n $ for the sequence $ \left( g_n \right)_{ n \ge 0 } $ given by the recursion

\[ g_0 = g_{34} = 0 , \ g_{ n+2 } = g_{ n+1 } + g_n \ \text{ for } n \ge 0 \, . \]

If you feel like it, derive a closed form for $ g_n $.

Variables


Variables
Find all solutions of $ x+y=3 $, $ x^5 + y^5 = 33 $.

Variables


Variables
There are 7 steps in a flight of stairs (not counting thetop and bottom of the flight). When going down, you can jumpover some steps if you like, perhaps even all 7. In howmany different ways can you go down the stairs?

Variables


Variables
Euler showed that $ \displaystyle\sum_{n=1}^{\infty}\frac{1}{n^2}=\frac{\pi^2}{6} $. Find $ \displaystyle \sum_{n=1}^{\infty} \frac{1}{(2n-1)^2} $.

Variables


Variables
In the following exercise we study the \emph{binomial coefficients} $ \binom n k $. \begin{enumerate} \item First assume that $ n $ and $ k $ are integers such that $ 0 \le k \le n $. Suppose you didn't know anything about $ \binom n k $, except the relations

\[ \binom n k = \binom{ n-1 }{ k-1 } + \binom{ n-1 }{ k } \qquad \text{ and } \qquad \binom n 0 = 1 \, . \]

Compute the generating function

\[ B_n(x) := \sum_{ k \ge 0 } \binom n k x^k \]

and use it to find a formula for $ \binom n k $. \item Convince yourself that your computation is identical if we allow $ n $ to be any complex number and $ k $ to be any nonnegative integer. \item Compute the generating function

\[ B(x) := \sum_{ n \ge 0 } \sum_{ k \ge 0 } \binom n k x^k y^n \]

and use it to find a formula for the generating function $ \beta_k(y) := \displaystyle \sum_{ n \ge k } \binom n k y^n $. \end{enumerate}

Variables


Variables
For a quadratic polynomial $ a_2 x^2 + a_1 x + a_0 $, call the roots $ r_1 $ and $ r_2 $. Define $ s_k = r_1^k + r_2^k $ and $ p = r_1 r_2 $.Express $ s_3 $ in terms of $ s_1 $ and $ p $. This is a very popular math contest trick!

Variables


Variables
Find the sum of the first $ n $ squares by differentiating the generating function $ \displaystyle \sum_{ k=0 }^{ n } x^k $.

Variables


Variables
If the roots of $ x^2 + px + q $ are the cubes of the roots of $ x^2 + mx + n $, compute $ p $ in terms of $ m $ and $ n $.

Variables


Variables
In how many ways can 12 pennies be put in 5 purses? Whatif none of the purses can be empty?

Variables


Variables
Given a sequence $ \left( a_n \right)_{ n \ge 0 } $ with generating function $ A(x) := \sum_{ n \ge 0 } a_n \, x^n $, let

\[ B(x) = \sum_{ n \ge 0 } b_n \, x^n = \frac{ A(x) }{ 1-x } \, . \]

Find a formula for $ b_n $. Use this to prove that the Fibonacci numbers satisfy

\[ f_0 + f_1 + \dots + f_n = f_{ n+2 } - 1 \, . \]

Variables


Variables
For a cubic polynomial $ a_3 x^3 + a_2 x^2 + a_1 x + a_0 $, the roots $ r_1 $, $ r_2 $, and $ r_3 $ come in three symmetric combinations: $ \sigma_1 = r_1 + r_2 + r_3 $, $ \sigma_2 = r_1 r_2 + r_1 r_3 + r_2 r_3 $, and $ \sigma_3 = r_1 r_2 r_3 $.Express $ \sigma_1 $, $ \sigma_2 $, and $ \sigma_3 $ in terms of the coefficients of the polynomial $ a_0 $, $ a_1 $, $ a_2 $, and $ a_3 $.

Variables


Variables
In how many ways can you put k identical things into n boxes,where the boxes are numbered $ 1, \cdots, n $? What if you must put atleast one thing in each box (so, of course, $ k>n $)?

Variables


Variables
Let $ c_n $ denote the number of triangulations of an $ (n+2) $-gon, so e.g., $ c_1 = 1 $, $ c_2 = 2 $, $ c_3 = 5 $, etc. We also set $ c_0 = 1 $. \begin{enumerate} \item Find a recurrence relation for $ c_n $. \item Compute the generating function $ \displaystyle C(x) := \sum_{ n \ge 0 } c_n \, x^n $ and use it to find a closed form for $ c_n $. \end{enumerate}

Variables


Variables
For a cubic polynomial $ a_3 x^3 + a_2 x^2 + a_1 x + a_0 $, the roots $ r_1 $, $ r_2 $, and $ r_3 $ come in three symmetric combinations: $ \sigma_1 = r_1 + r_2 + r_3 $, $ \sigma_2 = r_1 r_2 + r_1 r_3 + r_2 r_3 $, and $ \sigma_3 = r_1 r_2 r_3 $.The sum of the $ k^{\rm th} $ powers of the roots is defined as $ s_k = r_1^k + r_2^k + r_3^k $.Express $ s_3 $ in terms of $ \sigma_1 $, $ \sigma_2 $, and $ \sigma_3 $.

Variables


Variables
A bookbinder must bind 12 identical books using red, green,or blue covers. In how many ways can this be done?

Variables


Variables
Given a graph $ G $ and a positive integer $ k $, let $ c_G(k) $ be the number of colorings of $ G $ that use at most $ k $ colors.Compute $ c_G(k) $ for the following four classes:\begin{itemize} \item The \emph{null graph} $ N_n $ consists of $ n $ nodes and no edges. \item The \emph{complete graph} $ K_n $ consists of $ n $ nodes with all possible edges between them. \item The \emph{line graph} $ L_n $ consists of $ n $ nodes with edges that form a line segment. \item The \emph{cycle} $ C_n $ consists of $ n $ nodes with edges that form a circle.\end{itemize}What do you notice about\begin{enumerate} \item the leading coefficients? \item the second leading coefficients? \item the constant term? \item the highest degree?\end{enumerate}

Variables


Variables
For a cubic polynomial $ a_3 x^3 + a_2 x^2 + a_1 x + a_0 $, the roots $ r_1 $, $ r_2 $, and $ r_3 $ come in three symmetric combinations: $ \sigma_1 = r_1 + r_2 + r_3 $, $ \sigma_2 = r_1 r_2 + r_1 r_3 + r_2 r_3 $, and $ \sigma_3 = r_1 r_2 r_3 $.The sum of the $ k^{\rm th} $ powers of the roots is defined as $ s_k = r_1^k + r_2^k + r_3^k $.Find $ s_1 $, $ s_2 $, and $ s_3 $ for the polynomial $ x^3 - x^2 + x - 2 $.

Variables


Variables
A train with $ M $ passengers must make $ N $ stops. How manyways are there for the passengers to get off the train at thestops? What if we only care about the number of passengers gettingoff at each stop?

Variables


Variables
Given a graph $ G $ and a positive integer $ k $, let $ c_G(k) $ be the number of colorings of $ G $ that use at most $ k $ colors.Experiment with the numbers $ c_G(-1) $ for different examples of graphs $ G $. Can you guess what they count? (Hint: look at \emph{acyclic orientations} of $ G $, i.e., give each edge a direction, in such a way that you can't see any coherently oriented cycle.) Try to prove your assertion.

Variables


Variables
For a cubic polynomial $ a_3 x^3 + a_2 x^2 + a_1 x + a_0 $, the roots $ r_1 $, $ r_2 $, and $ r_3 $ come in three symmetric combinations: $ \sigma_1 = r_1 + r_2 + r_3 $, $ \sigma_2 = r_1 r_2 + r_1 r_3 + r_2 r_3 $, and $ \sigma_3 = r_1 r_2 r_3 $.The sum of the $ k^{\rm th} $ powers of the roots is defined as $ s_k = r_1^k + r_2^k + r_3^k $.With $ s_1 = a $, $ s_2 = b^2 $, and $ s_3 = a^3 $, find the three roots in terms of $ a $ and $ b $.

Variables


Variables
How many ways are there to arrange 5 red, 5 green, and 5 blueballs in a row so that no two blue balls lie next to each other?

Variables


Variables
Are there any magic $ 2 \times 2 $ squares? Explain.

Variables


Variables
For a cubic polynomial $ a_3 x^3 + a_2 x^2 + a_1 x + a_0 $, the roots $ r_1 $, $ r_2 $, and $ r_3 $ come in three symmetric combinations: $ \sigma_1 = r_1 + r_2 + r_3 $, $ \sigma_2 = r_1 r_2 + r_1 r_3 + r_2 r_3 $, and $ \sigma_3 = r_1 r_2 r_3 $.The sum of the $ k^{\rm th} $ powers of the roots is defined as $ s_k = r_1^k + r_2^k + r_3^k $.First express $ s_3 $ in terms of $ \sigma_1 $, $ \sigma_2 $, and $ \sigma_3 $. Then use that answer to factor $ x^3 + a^3 + b^3 - 3abx $. (By the way, this is an important step in one derivation of the cubic formula. First transform to $ x^3 + px + q $, then let $ p = -3ab $ and $ q = a^3 + b^3 $.)

Variables


Variables
How many ways are there to represent 100000 as the product of3 factors if we consider products that differ in the order of factorsto be different?

Variables


Variables
How many magic $ 3 \times 3 $ squares are there?

Variables


Variables
For a cubic polynomial $ a_3 x^3 + a_2 x^2 + a_1 x + a_0 $, the roots $ r_1 $, $ r_2 $, and $ r_3 $ come in three symmetric combinations: $ \sigma_1 = r_1 + r_2 + r_3 $, $ \sigma_2 = r_1 r_2 + r_1 r_3 + r_2 r_3 $, and $ \sigma_3 = r_1 r_2 r_3 $.The sum of the $ k^{\rm th} $ powers of the roots is defined as $ s_k = r_1^k + r_2^k + r_3^k $.a) Prove that $ a_3 s_1 + a_2 = 0 $.b) Prove that $ a_3 s_2 + a_2 s_1 + 2a_1 = 0 $.c) Generalize to something that starts with $ a_3 s_k $. Generalize further to polynomials of degree $ n $.

Variables


Variables
There are 12 books on a shelf. In how many ways can you choose5 of them so that no two of the chosen books are next to each otheron the shelf?

Variables


Variables
Find a formula for the magic sum of an $ n \times n $ square.

Variables


Variables
Compute the sum of the cubes of the roots of $ 2z^4 + 3z^3 + z^2 - 4z - 4 $.

Variables


Variables
In how many ways can a necklace be made using 5 identical redbeads and 2 identical blue beads?

Variables


Variables
We define a \emph{(weak) magic square} to be a square matrix whose entries are nonnegative integers and whose rows, columns, and main diagonals sum to the same number.Let $ \left( x_{ ij } \right)_{ 1 \le i, j \le 3 } $ be a magic $ 3 \times 3 $ square.\begin{enumerate}[(a)]\item Show that the center term $ x_{ 22 } $ is the average over all $ x_{ ij } $.\item Show that there are no magic $ 3 \times 3 $ squares with line sum $ t $, if $ t $ is not a multiple of~3.\end{enumerate}

Variables


Variables
Compute the sum of the $ 1000^{\rm th} $ powers of the roots of $ z^1000 - 10z + 10 $.

Variables


Variables
How many 6-letter ``words'' contain at least one letter ``A''(if any sequence of letters counts as a word)?

Variables


Variables
Show that, if $ a $ has no common factor with 10 other than $ \pm 1 $ (we say that $ a $ and 10 are \emph{relatively prime}), then $ a^4 \equiv 1 \bmod 10 $. Can you see where the exponent 4 comes from? Come up with a similar equation for a general modulus $ m $ and think about how you could prove that equation.

Variables


Variables
In general, the key to polynomial division is to recognize that dividing $ p(x) $ by $ f(x) $ lets you write $ p(x) = f(x) q(x) + r(x) $, where $ q $ is the quotient and $ r $ is the remainder. Plugging in clever values of $ x $ is almost always a good idea.a) Find the remainder when $ x^{2001} + 1 $ is divided by $ x+1 $.b) Find the remainder when $ x^{2001} + 1 $ is divided by $ x-1 $.c) Find the remainder when $ x^{2001} + 1 $ is divided by $ x^2 - 1 $.

Variables


Variables
Given 6 vertices of a regular hexagon, in how many ways canyou draw a path that hits all the vertices exactly once?

Variables


Variables
The code we'll describe in this exercise is due to Diffie and Hellman. It is a \emph{public-key code} because part of the code is known to everyone. Here's how it works: you and your friend choose a prime number $ p $ and an integer $ g $ between 2 and $ p-1 $. Both of these numbers are public (so, e.g., you two can safely discuss these numbers on the phone or over email---if someone wiretaps you, no problem).Now you \emph{secretely} choose an integer $ m $, and your friend \emph{secretely} chooses an integer $ n $. You compute $ g^m \bmod p $ and tell your friend the result. Your friend computs $ g^n \bmod p $ and tells you the result. The secret key that you both can use is

\[ s \equiv g^{ mn } \equiv \left( g^m \right)^n \equiv \left( g^n \right)^m \bmod p \, .\]

The last two equalities explain why both you and your friend can easily compute $ s $.You can now use $ s $ to encode messages, e.g., using multiplication mod $ p $, and $ s^{ -1 } $ to decode.Can you see why it's hard to compute $ s $ if you know $ p $, $ g $, $ g^m $, and $ g^n $? How could you make this cryptosystem safer? Do you see a way to ``break" it?

Variables


Variables
In general, the key to polynomial division is to recognize that dividing $ p(x) $ by $ f(x) $ lets you write $ p(x) = f(x) q(x) + r(x) $, where $ q $ is the quotient and $ r $ is the remainder. Plugging in clever values of $ x $ is almost always a good idea.Find the remainder when $ x^{1959} - 1 $ is divided by $ (x^2 + 1)(x^2 + x + 1) $.

Variables


Variables
Within a table of $ m $ rows and $ n $ columns a box is marked atthe intersection of the $ p^{\hbox {th}} $ row and $ q^{\hbox {th}} $ column.How many of the rectangles formed by the boxes of the tablecontain the marked box?

Variables


Variables
Here's \emph{Euler's $ \phi $-function}: $ \phi(n) $ counts the numbers between 1 and $ n $ that are relatively prime to $ n $.Compute the first couple of values of this function: $ \phi(1), \phi(2), \phi(3), \dots $ Find a formula for $ \phi(n) $ when $ n $ is prime. Find a formula for $ \phi(mn) $ in terms of $ \phi(m) $ and $ \phi(n) $ in the case that $ m $ and $ n $ are relatively prime.One of Euler's theorem says that, if $ a $ is relatively prime to $ n $, then $ a^{ \phi(n) } \equiv 1 \bmod n $.Conclude that, if $ b \cdot c \equiv 1 \bmod \phi(n) $, then $ \left( a^b \right)^c \equiv a \bmod n $.

Variables


Variables
A $ 10\times 10\times 10 $ cube is formed of small unit cubes.A grasshopper sits in the center $ O $ of one of the corner cubes. Ata given moment, it can jump to the center of any of the cubeswhich has a common face with the cube where it sits, as long as thejump increases the distance between point $ O $ and the currentposition of the grasshopper. How many ways are there for thegrasshopper to reach the unit cube at the opposite corner?

Variables


Variables
This exercise is about the RSA cryptosystem, named after its discoverers Ron Rivest, Adi Shamir, and Leonard Adleman.Here's how it works: You need two prime numbers $ p $ and $ q $, compute their product $ m = pq $, find a number $ b $ that is relatively prime to $ \phi(m) = (p-1)(q-1) $, and compute an inverse $ c $ of $ b $ modulo $ \phi(m) $, i.e., $ bc \equiv 1 \bmod \phi(m) $.You keep all of this private except for the numbers $ m $ and $ b $ which you make public (in particular, your friends know $ m $ and $ b $). To send you a message $ d $, your friend encodes it as

\[ e = d^b \bmod m \, .\]

You can decode your friend's message by computing

\[ d = e^c \bmod m \, .\]

Explain why this decoding works.What makes this cryptosystem safe? How could you make it safer? What would one need to break it?

Variables


Variables
Find the number of integers from 0 to 999999 that have no twoequal neighboring digits in their decimal representation.

Variables


Variables
A \emph{Sudoku square} is a $ 9 \times 9 $ grid filled with nine symbols (such as the numbers from 1 to 9) in such a way that each row, column, and the nine $ 3 \times 3 $ subsquares (shown above) contain each symbol exactly once. In a \emph{Sudoku puzzle}, the square contains some entries (called \emph{clues}), and the goal is to complete the Sudoku square. In the classical setting, the clues are chosen such that there is only one way to complete each square. You may try your luck with the two Sudoku puzzles above (caveat: If you've never played a Sudoku puzzle, watch out---these squares are addictive).We will work on two problems regarding Sudoku squares:\begin{enumerate}[(1)]\item How many Sudoku squares are there?\item What is the minimum number of clues that yield a unique solution to a Sudoku puzzle?\end{enumerate}These are hard questions. In fact, (1) was answered only in 2005 (the number of Sudoku squares is $ 6\,670\,903\,752\,021\,072\,936\,960 $), and (2) remains open (it is conjectured that the minimum number is 17). So we will simplify the problems and work with $ 4 \times 4 $ Sudoku squares. Experiment with questions (1) and (2) in the $ 4 \times 4 $ case.

Variables


Variables
How many ways are there to divide a deck of 52 cards into twohalves such that each half contains exactly 2 aces?

Variables


Variables
How many ways are there to place four black, four white, and fourblue balls into six different boxes?

Variables


Variables
In Lotto, 6 numbers are chosen from the set $ \{1, 2, \ldots,49\} $. In how many ways can this be done such that the chosen subsethas at least one pair of neighbors?

Variables


Variables
Find the sum $ S_n = \sum_{k=1}^n {n \choose k}k^3 $. Hint: thesum can be interpreted as the number of ways to choose a committeof at least one that includes a president,vice-president, and treasurer (not necessarily distinct persons) froma set of $ n $ people.

Variables


Variables
Given a set of $ 3n+1 $ objects, assume that $ n $ areindistinguishable, and the other $ 2n+1 $ are distinct. Show thatwe can choose $ n $ objects from this set in $ 2^{2n} $ ways.

Variables


Variables
In how many ways can you take an odd number of objects froma set of $ n $ objects?

Variables


Variables
$ n $ persons sit around a circular table. How many of the $ n! $arrangements are distinct, i.e., do not have the same neighboringrelations?

Variables


Variables
$ 2n $ points are chosen on a circle. In how many ways canyou connect them all in pairs such that none of the segmentsoverlap?

Variables


Variables
In how many ways can you triangulate a convex $ n $-gon usingonly the original vertices?

Variables


Variables
If you have a set of $ n $ pairs of parentheses, how many wayscan you arrange them ``sensibly''. For example, if you have3 pairs, the following 5 arrangements are possible:((())), (())(), ()(()), (()()), ()()().

Variables


Variables
Can you arrange the numbers $ 1, 2, \ldots, 9 $ along a circlesuch that the sum of two neighbors is never divisible by 3, 5, or7?

Variables


Variables
In how many ways can you choose two distinct subsets from acollection of $ N $ items? The two subsets together need notinclude all $ N $ items.

Variables


Variables
In how many ways can you choose two distinct subsets from acollection of $ N $ items? The two subsets together need notinclude all $ N $ items.

Variables


Variables
How many subsets of the set $ \{1, 2, 3, \ldots, N\} $ contain notwo successive numbers?

Variables


Variables
How many ways are there to put seven white and two black billiardballs into nine pockets? Some of the pockets may be empty andthe pockets are considered distinguishable.

Variables


Variables
Consider a circular set of $ N $ seats, with a different childsitting in each. How many ways can you rearrange the childrenso that no child moves more than one seat to the right or theleft of his/her original position?

Variables


Variables
Can you find a polyhedron with an odd number of faces, where eachface has an odd number of edges?

Variables


Variables
Can you partition the set of positive integers into infinitelymany infinite subsets such that each subset is generated fromany other by adding the same positive integer to each elementof the subset?

Variables


Variables
Consider all $ 2^n - 1 $ nonempty subsets of the set $ \{1, 2, \ldots, n\} $.For every such subset, we find the product of the reciprocals of eachof its elements. Find the sum of all these products. (For example,if the set consists of $ \{1, 2, 3\} $, the subsets are $ \{1\} $,$ \{2\} $, $ \{3\} $, $ \{1,2\} $, $ \{1,3\} $, $ \{2,3\} $, and $ \{1,2,3\} $.The products of the reciprocals are 1, 1/2, 1/3, 1/2, 1/3, 1/6, and1/6, respectively. The sum of all of them is 3.

Variables


Variables
How many ways are there to group 4 pieces of luggage? 5 pieces?(Here are the groupings of 3 pieces, $ A $, $ B $, and $ C $: $ ABC $, $ A\midBC $, $ B\mid AC $, $ C\mid AB $, $ A\mid B\mid C $. The vertical barsrepresent divisions into groups.)

Variables


Variables
Find the number of poker hands of each type. For thepurposes of this problem, a poker hand consists of 5 cards chosenfrom a standard pack of 52 (no jokers). Also for the purposes ofthis problem, the ace can only be a high card. In other words, thecard sequence $ A\clubsuit $, $ 2\diamondsuit $, $ 3\diamondsuit $,$ 4\spadesuit $, $ 5\heartsuit $ is not a straight, since the ace isa high card only.\par\vskip .2inHere are the definitions of the hands:\vskip .1in{\bf Royal flush:} $ 10 $ through $ A $ in the same suit.\par\hskip .3in Example: $ 10\spadesuit $, $ J\spadesuit $, $ Q\spadesuit $,$ K\spadesuit $, $ A\spadesuit $.\par{\bf Straight flush:} 5 cards in sequence in the same suit, but nota Royal flush.\par\hskip .3in Example: $ 4\diamondsuit $, $ 5\diamondsuit $, $ 6\diamondsuit $,$ 7\diamondsuit $, $ 8\diamondsuit $.\par{\bf Four of a kind:} Four cards of the same rank.\par\hskip .3in Example: $ Q\spadesuit $, $ Q\heartsuit $, $ Q\diamondsuit $,$ Q\clubsuit $, $ 7\spadesuit $.\par{\bf Full house:} Three cards of one rank and two of another.\par\hskip .3in Example: $ 3\spadesuit $, $ 3\diamondsuit $, $ 3\clubsuit $,$ 9\heartsuit $, $ 9\diamondsuit $.\par{\bf Flush:} Five cards in the same suit that are not in sequence.\par\hskip .3in Example: $ 3\clubsuit $, $ 4\clubsuit $, $ 5\clubsuit $,$ 6\clubsuit $, $ 8\clubsuit $.\par{\bf Straight:} Five cards in sequence that are not all in thesame suit.\par\hskip .3in Example: $ 6\clubsuit $, $ 7\clubsuit $, $ 8\diamondsuit $,$ 9\spadesuit $, $ 10\clubsuit $.\par{\bf Three of a kind:} Three cards of the same rank; the others ofdifferent rank.\par\hskip .3in Example: $ J\clubsuit $, $ J\diamondsuit $, $ J\spadesuit $,$ 7\diamondsuit $, $ K\heartsuit $.\par{\bf Two pairs:} Two pairs of cards.\par\hskip .3in Example: $ 5\heartsuit $, $ 5\spadesuit $, $ 8\diamondsuit $,$ 8\clubsuit $, $ A\spadesuit $.\par{\bf Pair:} A single pair of cards.\par\hskip .3in Example: $ 3\clubsuit $, $ 3\diamondsuit $, $ 5\spadesuit $,$ 9\diamondsuit $, $ Q\diamondsuit $.\par{\bf Bust:} A hand with none of the above.\par\hskip .3in Example: $ 2\clubsuit $, $ 4\spadesuit $, $ 6\diamondsuit $,$ 8\heartsuit $, $ 10\clubsuit $.

Variables


Variables
If you write out all the numbers from $ 1 $ to $ 333,333,333 $ how manyzeroes will you need to use?

Variables


Variables
Let $ m $ and $ n $ be integers. If $ K_1 $ is a circle of radius $ 1/m^2 $and $ K_2 $ is a circle of radius $ 1/n^2 $, and if $ K_1 $, and $ K_2 $,are tangent to each other and both are tangent to the same line,find the radius of the circle tangent to both $ K_1 $ and $ K_2 $ andto the line that lies in the area enclosed by them.

Variables


Variables
How many internal three-dimensional diagonals are there in aregular dodecahedron? (A regular dodecahedron is a polyhedronwith 12 identical faces, each of which is a regular pentagon. Adiagonal connects a vertex with another vertex, but other than thevertices, lies entirely within the solid.)

Variables


Variables
A pool table is $ 4 $ feet wide and $ 8 $ feet long, and isarranged in a coordinate system where $ 1 $ unit is $ 1 $ foot so thatone corner is at $ (0,0) $ and the $ 8 $-foot side lies along the$ x $-axis. If you strike a ball initially placed at $ (2,2) $ sothat its first bounce is against the wall at $ y = 4 $, in how manyplaces can you hit that wall so that the ball goes into the pocketat $ (8,0) $ after exactly $ 11 $ total bounces against the walls$ y=0 $ and $ y=4 $? It doesn't matter how many times the ballbounces against the walls at $ x=0 $ and $ x=8 $. Assume the ballalways bounces so that it's angle of incidence is equal to it'sangle of reflection.

Variables


Variables
A "flower" pattern is made as follows. A regular hexagon isinscribed in a circle of radius $ 1 $. A circle is drawn with eachof the edges of the hexagon as diameter. The flower consists ofeverything inside the original circle or inside any of the sixsmaller circles. What is the area of the flower?

Variables


Variables
Three mutually tangent circles of radius one are surroundedby a larger circle that is simultaneously tangent to all three.What is the radius of the larger circle?

Variables


Variables
Show that

\[ \sum_{k=0}^n (-1)^k{n \choose k} = 0.\]

Variables


Variables
Show that

\[ {r \choose m}{m \choose k} = {r \choose k} {r-k \choose m-k}. \]

Variables


Variables
Show that

\[ \sum_{k=0}^n {k \choose m} = {n+1 \choose m+1}. \]

Variables


Variables
Show that

\[ \sum_{r=1}^n r{n \choose r} = n2^{n-1}. \]

Variables


Variables
Find a nice formula for the sum:

\[ {n \choose 0}^2 + {n \choose 1}^2 + {n \choose 2}^2 + \cdots + {n \choose n}^2. \]

Variables


Variables
Show that if $ m > k $ and $ n > k $ then:

\[\sum_{j=0}^k {n \choose j}{m \choose k-j} = {n+m \choose k}. \]

Variables


Variables
Show that

\[ \sum_{k=0}^n {r+k \choose k} = {r+n+1 \choose n}.\]

Variables


Variables
Show that $ 3^n \ge 2^n $.

Variables


Variables
Prove that for any $ n > 0 $:

\[1^2 + 4^2 + 7^2 + 10^2 + \cdots+ (3n-2)^2 = n(6n^2 - 3n - 1)/2. \]

Variables


Variables
Show that if $ n $ lines are drawn on the plane so that none of them are parallel, and so that no three lines intersect at a point, then the plane is divided by those lines into $ (n^2+n+2)/2 $ regions.

Variables


Variables
``Sums and Cubes I.'' Find three integers satisfying $ x+y+z=3 $ and $ x^3+y^3+z^3=3 $. Now find a second solution. Next define a \textit{beastly number} as a positive integer which is equal to the sum of its digits plus the sum of the cubes of its digits. Demonstrate that 152 is not beastly. \\ There are precisely six beastly numbers, find as many as you can.

Variables


Variables
warm-up, excercise

Variables


Variables
``Sums and Cubes II.'' The formula for the sum of the first $ n $ cubes is:

\[ 1^3+2^3+3^3+\cdots+n^3 = (1+2+3+\cdots+n)^2. \]

Find a proof by picture of this fact.

Variables


Variables
``Sums and Cubes III.'' The following gem is due to Ross Honsberger. \\ The first $ n $ positive integers are not the only set of numbers with the property that the sum of their cubes is equal to the square of their sum. Choose any two-digit number $ N $, preferably not prime. Then list all the positive divisors of this number, including 1 and $ N $. Finally, underneath each number in this list tally how many positive divisors it has, thereby creating a new list of equal length. Then this new list has the desired property. For example, the divisors of~6 are 1, 2, 3, and~6; which have 1, 2, 2, and~4 positive divisors, respectively. Sure enough, $ 1^3+2^3+2^3+4^3=81=(1+2+2+4)^2 $.

Variables


Variables
warm-up, excercise

Variables


Variables
``Efron's Dice.'' Present the following four dice having the numbers listed below on their faces.\medskip\centerline{\textbf{A:} \ 0, 0, 4, 4, 4, 4 \hspace{2cm} \textbf{B:} \ 3, 3, 3, 3, 3, 3}\centerline{\textbf{C:} \ 2, 2, 2, 2, 6, 6 \hspace{2cm} \textbf{D:} \ 1, 1, 1, 5, 5, 5}\medskip\noindent Then imagine a game in which two players each pick a die and roll it once, the winner being the person with the higher number. Compute the probability of winning in the games A vs B, B vs C, C vs D, and D vs A.

Variables


Variables
``Points of Intersection'' The goal is to position a prescribed number of lines in the (Euclidean) plane to obtain exactly 100 points of intersection. Begin with 100 lines, then try 29 lines, 21 lines, 19 lines, and finally 15 lines.

Variables


Variables
``A Ladder Locus'' A ladder, originally upright against a vertical wall, slides downward and outward, always in contact with the wall, until it crashes to the ground. What figure is traced out by a hapless painter positioned midway up the ladder?

Variables


Variables
``Mix and Match'' Draw a closed ray and an open ray, such as the sets of points $ (x,0) $ with $ x\ge0 $ and $ (x,1) $ for $ x>0 $. Which object contains more points?\\ Challenge: find an explicit bijection between the two sets.

Variables


Variables
``Beguiling Tilings I'' Tile all of space with non-degenerate circles.

Variables


Variables
The arbelos consists of three points $ A,B $ and $ C $ which are collinear, together with the semicircles $ ADB $, $ AXC $ and $ CYB $ as shown in Figure 1. In the figure $ \overline {CD} $ has been added to the figure tangent to the two small semicircles. $ \overline {AD} $ intersects a small semicircle at $ X $ and $ \overline{BD} $ intersects the other small semicircle at $ Y $. $ \overline{XY} $ intersects $ \overline{AD} $ at $ P $. Prove the area of the arbelos is equal to the area of the circle with diameter $ \overline{CD} $, $ \overline{XY} $ and $ \overline{CD} $ bisect each other, and $ \overline{XY} $ is tangent to the small semicircles.

Variables


Variables
Suppose we take a 8 x 8 chessboard and cut off two opposite corners. We have some rectangular 2 x 1 dominoes, each of which can cover exactly two adjacent squares. Can we tile the chessboard with these dominoes?

Variables


Variables
On a 5 x 5 grid, we begin with some squares with X's in them and the rest of the squares blank. If any empty square is surrounded on at least 2 sides by squares with X's in them then we draw an X in this empty square as well. We repeat this until every square either has an X in it or shares at most one edge with such a square. \\Show that if we start with a grid with less than five X's in it, then when we finish this process, some squares will still be blank.

Variables


Variables
Show that if five points lie on the surface of a sphere, then there is some hemisphere containing four of them.

Variables


Variables
What is the maximum number of bishops one can place on a 8x8 chessboard such that no bishop can capture any other?

Variables


Variables
Suppose we have a balance (i.e. a scale with two arms, which can only tell us whether the items place on one arm weigh less than or more than the items place on the other arm). We are given 9 coins, one of which is counterfeit and weighs more than its real counterparts. Using only two weighings, is it possible to determine which of the 9 coins is counterfeit? Suppose instead we start with 10 coins; is it now possible to determine which is counterfeit in only two weighings?

Variables


Variables
Suppose we have two drinking glasses, one of which holds 21 oz. and one which holds 13 oz. Is it possible to measure exactly 1 oz. of water using only these two cups? What if our two cups are 8 oz. and 10 oz.?

Variables


Variables
Suppose we begin with a knight sitting at (1,0,0) in three-dimensional space. A \textit{three-dimensional knight jump} is a move where a piece goes $ \pm 1 $ along one axis (i.e. in the $ x $, $ y $, or $ z $-directions), $ \pm 2 $ along a second axis, and $ \pm 3 $ along the remaining axis. For example, our knight at (1,0,0) could make a three-dimensional knight jump to (1,0,0) +(2,-1,3) = (3,-1,3), or perhaps to (1,0,0) + (-1,-3,-2) = (0,-3,-2). Show that it is not possible for our knight to reach (0,0,0) by making a finite number of three-dimensional knight jumps.

Variables


Variables
Assume that any simple (but not necessarily convex) $ n $-gon (where $ n > 3 $) has at least one diagonal that lies completely within the $ n $-gon. Show that any $ n $-gon can be subdivided into exactly $ n-2 $ triangles so that every triangle vertex is one of the original vertices of the $ n $-gon.

Variables


Variables
Prove by induction the formula for the sum of a geometric series:

\[ a + ar + ar^2 + \cdots + ar^{n-1} =a\frac{r^n-1}{r-1}. \]

Variables


Variables
Show that:

<