You can click on the heading to sort by that heading.
Select  Problem  Description  Level and Difficulty  

A horse Named Sparky 
Butch and Sundance need to get out of Dodge. To travel as quickly as possible, each alternates walking and riding their only horse, Sparky, as follows. Butch begins by walking while Sundance rides. When Sundance reaches the first of the hitching posts that are conveniently located at onemile intervals along their route, he ties Sparky to the post and begins walking. When Butch reaches Sparky, he rides until he passes Sundance, then leaves Sparky at the next hitching post, and resumes walking, and they continue in this manner. Sparky, Butch and Sundance walk at 6, 4, and 2.5 miles per hour, respectively. The first time Butch and Sundance meet at a milepost, they are n miles from Dodge, and they have been traveling for t minutes. Find n + t. 


What is the sum 
For each integer $n>1$, let $F(n)$ be the number of solutions of the equation $\sin x = \sin nx$ on the interval $[0, \pi]$. What is $\sum_{n=2}^{2007} F(n)$\,? 


How many subsets are spacy 
Call a set of integers spacy if it contains no more than one out of any three consecutive integers. How many subsets of $\{1, 2, 3, \ldots, 12\}$, including the empty set, are spacy? 


Square ABCD 
Square $ABCD$ has area 36, and $\overline{AB}$ is parallel to the $x$axis. Vertices $A$, $B$, and $C$ are on the graphs of $y=\log_{a}x$, $y=2\log_{a}x$, and $y=3\log_{a}x$, respectively. What is $a$\,? 


Common value of sums, products of zeros and sum of coefficients 
The sum of the zeros, the product of the zeros, and the sum of the coefficients of the function $f(x) = ax^2 + bx + c$ are equal. Their common value must also be which of the following? 


Volume of tetrahedra removed from unit cube 
Corners are sliced off a unit cube so that the six faces each become regular octagons. What is the total volume of the removed tetrahedra? 


Triangle areas and sums of coordinates 
Triangles $ABC$ and $ADE$ have areas 2007 and 7002, respectively, with $B=(0,0)$, $C=(223,0)$, $D=(680,380)$, and $E=(689,389)$. What is the sum of all possible $x$coordinates of $A$\,? 


Polynomial with real coefficients 
The polynomial $f(x)=x^4+ax^3+bx^2+cx+d$ has real coefficients, and $f(2i)=f(2+i)=0$. What is $a+b+c+d$\,? 


Cos(ab) 
Suppose that $\sin a + \sin b = \sqrt{5/3}$ and $\cos a + \cos b = 1$. What is $\cos(ab)$\,? 


How many threedigit numbers 
How many threedigit numbers are composed of three distinct digits such that one digit is the average of the other two? 


Sum of all possible values 
The set $\{3, 6, 9, 10\}$ is augmented by a fifth element $n$, not equal to any of the other four. The median of the resulting set is equal to its mean. What is the sum of all possible values of $n$\,? 


ABCDE are distinct integers 
Let $a$, $b$, $c$, $d$, and $e$ be distinct integers such that \[(6a)(6b)(6c)(6d)(6e)=45.\] What is $a+b+c+d+e$\,? 


Coordinate plane mouse and cheese 
A piece of cheese is located at $(12,10)$ in a coordinate plane. A mouse is at $(4,2)$ and is running up the line $y=5x+18$. At the point $(a,b)$ the mouse starts getting farther from the cheese rather than closer to it. What is $a + b$\,? 


Measure of angles in starpolygon 
A starpolygon is drawn on a clock face by drawing a chord from each number to the fifth number counted clockwise from that number. That is, chords are drawn from 12 to 5, from 5 to 10, from 10 to 3, and so on, ending back at 12. What is the degree measure of the angle at each vertex in the starpolygon? 


Five consecutive terms 
Let $a$,$b$,$c$,$d$, and $e$ be five consecutive terms in an arithmetic sequence, and suppose that $a+b+c+d+e=30$. Which of the following can be found? 


Kate's average speed 
Kate rode her bicycle for 30 minutes at a speed of 16 mph, then walked for 90 minutes at a speed of 4 mph. What was her overall average speed in miles per hour? 


How many pairs of positive integers 
How many pairs of positive integers $(a,b)$ are there such that $a$ and $b$ have no common factors greater than 1 and \[\frac{a}{b}+\frac{14b}{9a} \] is an integer? 


Smallest positive integer 
Let $n$ denote the smallest positive integer that is divisible by both 4 and 9, and whose base10 representation consists of only 4's and 9's, with at least one of each. What are the last four digits of $n$? 


Pyramid cut by plane 
A pyramid with a square base is cut by a plane that is parallel to its base and is 2 units from the base. The surface area of the smaller pyramid that is cut from the top is half the surface area of the original pyramid. What is the altitude of the original pyramid? 


Choose a number, roll dice 
A player chooses one of the numbers 1 through 4. After the choice has been made, two regular foursided (tetrahedral) dice are rolled, with the sides of the dice numbered 1 through 4. If the number chosen appears on the bottom of exactly one die after it is rolled, then the player wins $\$ $1. If the number chosen appears on the bottom of both of the dice, then the player wins $\$ $2. If the number chosen does not appear on the bottom of either of the dice, the player loses $\$ $1. What is the expected return to the player, in dollars, for one roll of the dice? 


Square blocks and different combinations 
A set of 25 square blocks is arranged into a $5\times5$ square. How many different combinations of 3 blocks can be selected from that set so that no two are in the same row or column? 


Square inscribed in right triangle 
Right $\triangle ABC$ has $AB=3$, $BC=4$, and $AC=5$. Square $XYZW$ is inscribed in $\triangle ABC$ with $X$ and $Y$ on $\overline{AC}$, $W$ on $\overline{AB}$, and $Z$ on $\overline{BC}$. What is the side length of the square? 


Probability of designating shaded square 
The wheel shown is spun twice, and the randomly determined numbers opposite the pointer are recorded. The first number is divided by 4, and the second number is divided by 5. The first remainder designates a column, and the second remainder designates a row on the checkerboard shown. What is the probability that the pair of numbers designates a shaded square? 


Point in triangle 
Point $P$ is inside equilateral $\triangle ABC$. Points $Q$, $R$, and $S$ are the feet of the perpendiculars from $P$ to $\overline{AB}$, $\overline{BC}$, and $\overline{CA}$, respectively. Given that $PQ=1$, $PR=2$, and $PS=3$, what is $AB$? 


Circle surrounded by 4 circles 
A circle of radius 1 is surrounded by 4 circles of radius $r$ as shown. What is $r$? 


Test scores 
A teacher gave a test to a class in which 10 % of the students are juniors and 90 % are seniors. The average score on the test was 84. The juniors all received the same score, and the average score of the seniors was 83. What score did each of the juniors receive on the test? 


Angles of a quadrilateral 
The angles of quadrilateral $ABCD$ satisfy $\angle A = 2\angle B = 3\angle C = 4\angle D$. What is the degree measure of $\angle A$, rounded to the nearest whole number? 


Car wash fundraiser 
Some boys and girls are having a car wash to raise money for a class trip to China. Initially 40 % of the group are girls. Shortly thereafter two girls leave and two boys arrive, and then 30 % of the group are girls. How many girls were initially in the group? 


Area of intersection 
Two circles of radius 2 are centered at $(2,0)$ and at $(0,2)$. What is the area of the intersection of the interiors of the two circles? 


How old is Tom? 
Tom's age is $T$ years, which is also the sum of the ages of his three children. His age $N$ years ago was twice the sum of their ages then. What is $T/N$? 


Area of circle 
A circle passes through the three vertices of an isosceles triangle that has two sides of length 3 and a base of length 2. What is the area of this circle? 


Two points, one plane 
Two points $B$ and $C$ are in a plane. Let $S$ be the set of all points $A$ in the plane for which $\triangle ABC$ has area 1. Which of the following describes $S$? 


Cryptographic code 
A cryptographic code is designed as follows. The first time a letter appears in a given message it is replaced by the letter that is 1 place to its right in the alphabet (assuming that the letter A is one place to the right of the letter Z). The second time this same letter appears in the given message, it is replaced by the letter that is $1+2$ places to the right, the third time it is replaced by the letter that is $1+2+3$ places to the right, and so on. For example, with this code the word ``banana'' becomes ``cbodqg''. What letter will replace the last letter s in the message \[\text{``Lee's sis is a Mississippi miss, Chriss!''?} \] 


How many different 5 digit numbers 
On the trip home from the meeting where this AMC10 was constructed,the Contest Chair noted that his airport parking receipt had digits of the form $bbcac$, where $0\le a 


Convex pentagon 
All sides of the convex pentagon $ABCDE$ are of equal length, and $\angle A = \angle B = 90^\circ$. What is the degree measure of $\angle E$? 


2007 AMC 10 Score 
The 2007 AMC 10 will be scored by awarding 6 points for each correct response, 0 points for each incorrect response, and 1.5 points for each problem left unanswered. After looking over the 25 problems, Sarah has decided to attempt the first 22 and leave only the last 3 unanswered. How many of the first 22 problems must she solve correctly in order to score at least 100 points? 


Arogs, Brafs, Dramps and Crups 
In a certain land, all Arogs are Brafs, all Crups are Brafs, all Dramps are Arogs, and all Crups are Dramps. Which of the following statements is implied by these facts? 


Circle Circumscribed about a Triangle 
The point $O$ is the center of the circle circumscribed about 


Home From College 
A college student drove his compact car 120 miles home for the weekend and averaged 30 miles per gallon. On the return trip the student drove his parents' SUV and averaged only 20 miles per gallon. What was the average gas mileage, in miles per gallon, for the round trip? 


Odd Operators 2 
Define the operation $\star$ by $a \star b = (a + b)b$. What is $(3\star5) ? (5\star3)$? 


Painting Rooms 
Isabella's house has 3 bedrooms. Each bedroom is 12 feet long, 10 feet wide, and 8 feet high. Isabella must paint the walls of all the bedrooms. Doorways and windows, which will not be painted, occupy 60 square feet in each bedroom. How many square feet of walls must be painted? 


Holding hands with pidgeons. 
If 30 people hold hands, so each hand touches exactly one other hand, then one person states their name, and squeezes their right hand. Each person can call out their name when their hand is squeezed and then squeeze their other hand. Will the first person always get their left hand squeezed? 


Hand holding counts. 
In how many different ways can 30 people hold hands, so each hand is touching exactly one other hand? 


Fewest circles to construct a perpendicular to a line through a point on the line. 
Assume you wish to construct a perpendicular to a given line through a given point on the line with a straight edge and compass. If you start with exactly two points on the line and nothing else, what is the fewest number of circles you will need to draw? 


Minimal Perpendicular Construction 
Given two points on a line, what is the minimal number of steps required to construct 


Two Circles with Common Tangents 
Circles centered at $A$ and $B$ each have radius 2, as shown. Point $O$ is the midpoint of $\overline{AB}$, and $OA=2\sqrt{2}$. Segments $OC$ and $OD$ are tangent to the circles centered at $A$ and $B$, respectively, and $\overline{EF}$ is a common tangent. What is the area of the shaded region $ECODF$? 


The Difference of Squares 
How many ordered pairs $(m,n)$ of positive integers, with $m>n$, have the property that their squares differ by 96? 


Painting a Square 
A paint brush is swept along both diagonals of a square to produce the symmetric painted area, as shown. Half the area of the square is painted. What is the ratio of the side length of the square to the brush width? 


Twelve Sided Polygon 
Consider the 12sided polygon $ABCDEFGHIJKL$, as shown. Each of its sides has length 4, and each two consecutive sides form a right angle. Suppose that $\overline{AG}$ and $\overline{CH}$ meet at $M$. What is the area of quadrilateral $ABCM\,$? 


Two Circles with Common Tangents 
Circles centered at $A$ and $B$ each have radius 2, as shown. Point $O$ is the midpoint of $\overline{AB}$, and $OA=2\sqrt{2}$. Segments $OC$ and $OD$ are tangent to the circles centered at $A$ and $B$, respectively, and $\overline{EF}$ is a common tangent. What is the area of the shaded region $ECODF$? 


The Difference of Squares 
How many ordered pairs $(m,n)$ of positive integers, with $m>n$, have the property that their squares differ by 96? 


Common Sums on Cubes 
The numbers from 1 to 8 are placed at the vertices of a cube in such a manner that the sum of the four numbers on each face is the same. What is this common sum? 


Isosceles Triangles 
Triangles $ABC$ and $ADC$ are isosceles with $AB=BC$ and $AD=DC$. Point $D$ is inside $\triangle ABC$, $\angle ABC = 40^\circ$, and $\angle ADC = 140^\circ$. What is the degree measure of $\angle BAD\,$? 


Five Circles in a Square 
Four circles of radius 1 are each tangent to two sides of a square and externally tangent to a circle of radius 2, as shown. What is the area of the square? 


Sums of Digits of $n$ 
For each positive integer $n$, let $S(n)$ denote the sum of the digits of $n$. For how many values of $n$ is $n+S(n)+S(S(n))=2007\,$? 


Primes Dividing a Sequence 
A finite sequence of threedigit integers has the property that the tens and units digits of each term are, respectively, the hundreds and tens digits of the next term, and the tens and units digits of the last term are, respectively, the hundreds and tens digits of the first term. For example, such a sequence might begin with terms $247$, $475$, and $756$ and end with the term 824. Let $S$ be the sum of all the terms in the sequence. What is the largest prime number that always divides $S\,$? 


Spheres in a Cubes 
A sphere is inscribed in a cube that has a surface area of 24 square meters. A second cube is then inscribed within the sphere. What is the surface area in square meters of the inner cube? 


$ a + \frac{1}{a}$ 
Suppose that the number $a$ satisfies the equation $4 = a + a^{1}$. What is the value of $a^4 + a^{4}\,$? 


Prime Factors of a Cube 
Suppose that $m$ and $n$ are positive integers such that $75m=n^3$. What is the minimum possible value of $m+n\,$? 


Integer Probability 
Integers $a$, $b$, $c$, and $d$, not necessarily distinct, are chosen independently and at random from 0 to 2007, inclusive. What is the probability that $adbc$ is even? 


Triangle Inscribed in a Circle 
A triangle with side lengths in the ratio 3:4:5 is inscribed in a circle of radius 3. What is the area of the triangle? 


Permuting Tourists 
Two tour guides are leading six tourists. The guides decide to split up. Each tourist must choose one of the guides, but with the stipulation that each guide must take at least one tourist. How many different groupings of guides and tourists are possible? 


Average Age of the Dunbar Family 
The Dunbar family consists of a mother, a father, and some children. The average age of the members of the family is 20, the father is 48 years old, and the average age of the mother and children is 16. How many children are in the family? 


Exponential Unknowns 
Real numbers $a$ and $b$ satisfy the equations $3^a=81^{b+2}$ and $125^b=5^{a3}$. What is $ab\,$? 


Johns Federal Tax 
Last year Mr. John Q. Public received an inheritance. He paid 20% in federal taxes on the inheritance, and paid 10% of what he had left in state taxes. He paid a total of $ \$ $10,500 for both taxes. How many dollars was the inheritance? 


Eclid High 
At Euclid High School, the number of students taking the AMC10 was 60 in 2002, 66 in 2003, 70 in 2004, 76 in 2005, and 78 in 2006, and is 85 in 2007. Between what two consecutive years was there the largest percentage increase? 


School Supplies 
A school store sells 7 pencils and 8 notebooks for $\$ $4.15. It also sells 5 pencils and 3 notebooks for $\$ $1.77. How much do 16 pencils and 10 notebooks cost? 


Two consecutive integers 
The larger of two consecutive odd integers is three times the smaller. What is their sum? 


A Rectangular Aquarium 
An aquarium has a rectangular base that measures 100 cm by 40 cm and has a height of 50 cm. It is filled with water to a height of 40 cm. A brick with a rectangular base that measures 40 cm by 20 cm and a height of 10 cm is placed in the aquarium. By how many centimeters does the water rise? 


Odd operators 
Define $a@b=abb^2$ and $a\#b=a+bab^2$. What is $\frac{6@2}{6\#2}\,$? 


Tickets to a Show 
One ticket to a show costs $\$ $20 at full price. Susan buys 4 tickets using a coupon that gives her a 25% discount. Pam buys 5 tickets using a coupon that gives her a 30% discount. How many more dollars does Pam pay than Susan? 


Odd operators 
Define $a@b=abb^2$ and $a\#b=a+bab^2$. What is $\frac{6@2}{6\#2}\,$? 


General 3 penny touch 
For which numbers, n, is it possible to arrange a collection of that number (n) of 


Easy Penny Touch 
Is it possible for 25 pennies to be positioned so that each one touches exactly one more 


Local Penny Touch 
What is the fewest pennies that a given penny can touch? What is the most? Why? 


Penny touching 
Is it possible for $25$ pennies to be placed flat on a table so that each penny touches exactly three other pennies? Is this possible with $24$? 


Analyzing the game of Spot It 
Spot It costs about $\$ $10 at game stores. It consists of 55 cards with 8 pictures on each one. Each player gets one card. Deck goes in the middle. When you see a match between your card and the top card on the deck, you call it and collect that card, putting it on top of your old card. Your card will always have a match with the center card, so it's just a question of who can spot their match first. Fun game; no math content. The math question is how they did it. How can you make all those cards, with every pair of cards having exactly one match?! More information on using this in a math circle can be found at Math Mama Writes. 


Intersecting cylinders 
Construct a model of the intersection of two congruent infinite cylinders, when the axes of the cylinders meet at a right angle. 


Fruit cutting High School 
Take two sufficiently long congruent right prisms over regular ngons. If these intersect so that their axes (the line over the centroid) meet at a right angle, what is the smallest number of edges the resulting shape can have? What is the largest number of edges the resulting shape can have? Experiments can be done with fruit. 


Fruit cutting 68th grades 
Describe the possible sections of a right prism over a regular ngon. What is the smallest number of edges possible? What is the largest number of edges possible? Can the resulting sections be nonconvex? When can they be regular? Have right angles?... Explore. Repeat for sections of right pyramids over regular ngon bases. It is possible to experiment with fruit or cheese. 


Pumpkin cutting 
Consider cutting a pumpkin shell into parts. Is it possible to have 5 parts with 10 edges? Is it possible to have 5 parts with 3 edges. Describe the restrictions on the number of parts vs the number of edges. Is there any other variable that could be included to refine the description? 


Fruit cutting preK5th grade 
What is the minimal number of cuts it takes to create a cube out of an apple (or orange, or melon)? How about a trapezoidal or rhombic prism? What happens to the number of cuts as you go through polygon prisms, making triangular, quadrilateral, pentagonal, hexagonal etc. prisms? How about pyramids? Is it possible to cut an apple into two parts, so that the skin will be separated into three parts? Pedagogical notes: * Children may have fun poke holes in the definition of a "cut"  budget some time for this. Some pictures here: http://www.flickr.com/photos/26208371@N06/6197204225/in/photostream/ 


Specifying a pixel 
How many quantities are needed to specify a single colored pixel on a standard computer monitor? 


Distance between points in the plane 
In order to find the distance between two points in fourdimensional space, one must first understand distance in two and three dimensions. To begin, what is the distance between the points (2006, 2007) and (2010, 2002)? In general, how do we compute distance in the plane? 


Why twodimensional space? 
Why do we usually refer to a flat surface, such as a sheet of paper or a chalkboard, as a twodimensional space? 


The Game of Criss Cross 4 Point Outer Boundary Formula 
Suppose that we change the outer boundary of a CrissCross board so that it consists of four points at the corners of a square. Explain why 3F +1 = 2E on a completed game board with a square boundary. 


The Game of Criss Cross 4 Point Outer Boundary 
Suppose that we change the outer boundary of a CrissCross board so that it consists of four points at the corners of a square. Play games in which there are either one, two, or three additional points in the interior of this square. Based on the outcomes, make a conjecture regarding how to predict whether the first or second player will win on a square board. 


Criss Cross Village 
In a certain small country there are villages, expressways, and fields. Expressways only lead from one village to another and do not cross one another, and it is possible to travel from any village to any other village along the expressways. Each field is completely enclosed by expressways and villages. If there are 100 villages and 141 expressways, then how many fields are there? 


The Game of Criss Cross Who will win? 
Will the first or second player win on the lefthand game board? Explain why any game on this board always lasts for the same number of moves. Criss Cross: Players alternate turns drawing a single straight line segment joining any two points, as long as the segment does not pass through any other points or segments already appearing on the game board. The winner is the last player able to make a legal move. 


The Game of Criss Cross How Many Moves 
How many different moves can the first player make on the game board pictured at left? Criss Cross: Players alternate turns drawing a single straight line segment joining any two points, as long as the segment does not pass through any other points or segments already appearing on the game board. The winner is the last player able to make a legal move. 


Generating functions and binomial coefficients 
In the following exercise we study the $\textit{binomial coefficients }$ $\left( \begin{array}{c} n \\ k \end{array}\right)$. a) First assume that $n$ and $k$ are integers such that $0 \le k \le n$. Suppose you didn't know anything about $\left( \begin{array}{c} n \\ k \end{array}\right)$, except the relations \[ \left( \begin{array}{c} n \\ k \end{array}\right) = \left( \begin{array}{c} n1 \\ k1 \end{array}\right) + \left( \begin{array}{c} n1 \\ k \end{array}\right) \qquad \text{ and } \qquad \left( \begin{array}{c} n \\ 0 \end{array}\right) = 1 \, . \] Compute the generating function \[ B_n(x) := \sum_{ k \ge 0 } \left( \begin{array}{c} n \\ k \end{array}\right) x^k \] and use it to find a formula for $\left( \begin{array}{c} n \\ k \end{array}\right)$. b) Convince yourself that your computation is identical if we allow $n$ to be any complex number and $k$ to be any nonnegative integer. c) Compute the generating function \[ B(x) := \sum_{ n \ge 0 } \sum_{ k \ge 0 } \left( \begin{array}{c} n \\ k \end{array}\right) x^k y^n \] and use it to find a formula for the generating function $\beta_k(y) := \displaystyle \sum_{ n \ge k } \left( \begin{array}{c} n \\ k \end{array}\right) y^n$. 


Sum of cubes of roots of a quadratic 
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! 


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


Quadratic whose roots are cubes of another quadratic 
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$. 


Partitioning indistinguishable items 
In how many ways can 12 pennies be put in 5 purses? What 


Fibonacci sum by generating functions 
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) }{ 1x } \, . \] 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 \, . \] 


Roots and coefficients of a cubic 
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$. 


Generating function for number of ways to triangulate an $n$gon 
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$. Find a recurrence relation for $c_n$. 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$. 


Partitioning $k$ items into $n$ indistinguishable boxes 
In how many ways can you put k identical things into n boxes, 


Arbelos area 
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. 


Divisibility test for 8 
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. 


Sum of cubes of roots of a cubic 
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$. 


Coloring book covers 
A bookbinder must bind 12 identical books using red, green, 


Counting colorings of basic graphs 
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. The $\textit{null graph}$ $N_n$ consists of $n$ nodes and no edges. The $\textit{complete graph}$ $K_n$ consists of $n$ nodes with all possible edges between them. The $\textit{line graph}$ $L_n$ consists of $n$ nodes with edges that form a line segment. The $\textit{cycle}$ $C_n$ consists of $n$ nodes with edges that form a circle. What do you notice about 1. the leading coefficients? 2. the second leading coefficients? 3. the constant term? 4. the highest degree? 


Sum of powers of the roots of a cubic 
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$. 


Number of ways for $M$ people to disembark a train at one of $N$ stops 
A train with $M$ passengers must make $N$ stops. How many 


Coloring a graph with 1 colors 
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. 


Finding roots of a cubic in terms of sums of powers of the roots 
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$. 


Arranging objects with a nonadjacency restriction 
How many ways are there to arrange 5 red, 5 green, and 5 blue 


Existence of 2x2 magic squares 
Are there any magic $2 \times 2$ squares? Explain. 


Factoring $x^3 + a^3 + b^3  3abx$ 
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$.) 


Tower of Hanoi with cyclic moves 
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 counterclockwise. Express $Q_n$ and $R_n$ recursively. Alternatively: prove that $Q_0 = R_0 = 0$ and otherwise $Q_n = 2R_{n1}$ and $R_n = Q_n + Q_{n1} + 1$. 


Representations of 100000 as the product of 3 factors 
How many ways are there to represent 100000 as the product of 


Counting magic 3x3 squares 
How many magic $3 \times 3$ squares are there? 


Relation between coefficients and sums of powers of roots of a polynomial 
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$. 


Choosing books with no two adjacent 
There are 12 books on a shelf. In how many ways can you choose 


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


Sum of cubes of roots of a quartic 
Compute the sum of the cubes of the roots of $2z^4 + 3z^3 + z^2  4z  4$. 


Counting distinct necklaces 
In how many ways can a necklace be made using 5 identical red 


Constraints on weak $3 \times 3$ magic squares 
We define a $\textit{(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. a) Show that the center term $x_{ 22 }$ is the average over all $x_{ ij }$. b) Show that there are no magic $3 \times 3$ squares with line sum $t$, if $t$ is not a multiple of $3$. 


Sum of 1000th powers of roots of a 1000th degree polynomial 
Compute the sum of the $1000^{\rm th}$ powers of the roots of $z^{1000}  10z + 10$. 


Counting words with at least one ``A" 
How many 6letter ``words'' contain at least one letter ``A'' 


Choosing officers 
How many ways are there to choose a president, a vicepresident, and 


Last digit of fourth powers, and its generalizations 
Show that, if $a$ has no common factor with $10$ other than $\pm 1$ (we say that $a$ and $10$ are $\textit{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. 


Factor theorem and remainders 
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$. 


Paths in a complete graph 
Given 6 vertices of a regular hexagon, in how many ways can 


DiffieHellman introduction 
The code we'll describe in this exercise is due to Diffie and Hellman. It is a \emph{publickey 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 $p1$. Both of these numbers are public (so, e.g., you two can safely discuss these numbers on the phone or over emailif someone wiretaps you, no problem). 


Factor theorem and remainders 
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)$. 


Counting rectangles in the grid 
Within a table of $m$ rows and $n$ columns a box is marked at 


Euler phi function introduction 
Here's \emph{Euler's $\phi$function}: $\phi(n)$ counts the numbers between 1 and $n$ that are relatively prime to $n$. 


Paths through a cube 
A $10\times 10\times 10$ cube is formed of small unit cubes. 


Introduction to RSA cryptosystem 
This exercise is about the RSA cryptosystem, named after its discoverers Ron Rivest, Adi Shamir, and Leonard Adleman. 


Counting numbers with adjacent equal digits 
Find the number of integers from 0 to 999999 that have no two 


Arbelos construction 
Construct with proof, the twin circles in a given 


Counting (small) Sudoku 
A $\textit{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 $\textit{Sudoku puzzle}$, the square contains some entries (called $\textit{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 outthese squares are addictive). 1. How many Sudoku squares are there? 2. What is the minimum number of clues that yield a unique solution to a Sudoku puzzle? These are hard questions. In fact, (1) was answered only in 2005 (the number of Sudoku squares is $6\text{,}670\text{,}903\text{,}752\text{,}021\text{,}072\text{,}936\text{,}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. 


Partitioning a deck of cards 
How many ways are there to divide a deck of 52 cards into two 


Partitioning colored balls 
How many ways are there to place four black, four white, and four 


Lotto winners with at least one adjacent pair 
In Lotto, 6 numbers are chosen from the set $\{1, 2, \ldots, 


Combinatorial approach to computing \sum_{k=1}^n {n \choose k}k^3 
Find the sum $S_n = \sum_{k=1}^n {n \choose k}k^3$. Hint: the 


Choosing objects when some are distinguishable and some are not 
Given a set of $3n+1$ objects, assume that $n$ are 


Choosing an odd number of objects 
In how many ways can you take an odd number of objects from 


Distinct ways to sit around a circular table 
$n$ persons sit around a circular table. How many of the $n!$ 


Connecting points in pairs with nonintersecting segments 
$2n$ points are chosen on a circle. In how many ways can 


Ways to triangulate an $n$gon 
In how many ways can you triangulate a convex $n$gon using 


Divisibility test for $2^n$ 
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. 


Ways to nest parentheses 
If you have a set of $n$ pairs of parentheses, how many ways 


Can you arrange the numbers $1, 2, \ldots, 9$ along a circle 
Can you arrange the numbers $1, 2, \ldots, 9$ along a circle 


Choosing two distinct subsets 
In how many ways can you choose two distinct subsets from a 


In how many ways can you choose two distinct subsets from a 
In how many ways can you choose two distinct subsets from a 


Subsets with no consecutive elements 
How many subsets of the set $\{1, 2, 3, \ldots, N\}$ contain no 


Distributing billiard balls into pockets 
How many ways are there to put seven white and two black billiard 


Rearrangements with a maximum distance of 1 
Consider a circular set of $N$ seats, with a different child 


Polyhedra with odd faces and odd edges 
Can you find a polyhedron with an odd number of faces, where each 


Can you partition the set of positive integers into infinitely 
Can you partition the set of positive integers into infinitely 


Tower of Hanoi with duplicate discs 
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.) 


Sum of products of reciprocals of subsets 
Consider all $2^n  1$ nonempty subsets of the set $\{1, 2, \ldots, n\}$. 


Counting groupings (Stirling) 
How many ways are there to group 4 pieces of luggage? 5 pieces? 


Counting poker hands 
Find the number of poker hands of each type. For the Here are the definitions of the hands: $\textbf{ Royal flush:}$ $10$ through $A$ in the same suit. Example: $10\spadesuit$, $J\spadesuit$, $Q\spadesuit$, $\textbf{Straight flush:}$ 5 cards in sequence in the same suit, but not Example: $4\diamondsuit$, $5\diamondsuit$, $6\diamondsuit$, $\textbf{Four of a kind:}$ Four cards of the same rank. Example: $Q\spadesuit$, $Q\heartsuit$, $Q\diamondsuit$, $\textbf{ Full house:}$ Three cards of one rank and two of another. Example: $3\spadesuit$, $3\diamondsuit$, $3\clubsuit$, $\textbf{ Flush:}$ Five cards in the same suit that are not in sequence. Example: $3\clubsuit$, $4\clubsuit$, $5\clubsuit$, $\textbf{ Straight:}$ Five cards in sequence that are not all in the Example: $6\clubsuit$, $7\clubsuit$, $8\diamondsuit$, $\textbf{ Three of a kind:}$ Three cards of the same rank; the others of Example: $J\clubsuit$, $J\diamondsuit$, $J\spadesuit$, $\textbf{ Two pairs:}$ Two pairs of cards. Example: $5\heartsuit$, $5\spadesuit$, $8\diamondsuit$, $\textbf{ Pair:}$ A single pair of cards. Example: $3\clubsuit$, $3\diamondsuit$, $5\spadesuit$, $\textbf{ Bust:}$ A hand with none of the above. Example: $2\clubsuit$, $4\spadesuit$, $6\diamondsuit$, 


Counting zeroes used in counting to 333,333,333 
If you write out all the numbers from $1$ to $333,333,333$ how many 


Circles and Pythagoras 
Let $m$ and $n$ be integers. If $K_1$ is a circle of radius $1/m^2$ 


Diagonals in a dodecahedron 
How many internal threedimensional diagonals are there in a 


Pool table bounces 
A pool table is $4$ feet wide and $8$ feet long, and is 


Area of a flower 
A "flower" pattern is made as follows. A regular hexagon is 


Radius of circle circumscribed around three smaller ones 
Three mutually tangent circles of radius one are surrounded 


Radius of circles in a tangent ring 
Arrange $n$ circles or radius $r$, in a ring such that 


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


Alternating sum of binomial coefficients 
Show that 


Show that 
Show that 


Show that 
Show that 


Show that 
Show that 


Find a nice formula for the sum: 
Find a nice formula for the sum: 


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


Show that 
Show that 


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


Prove that for any $n > 0$: 
Prove that for any $n > 0$: 


Arbelos tangent radius 
Find the radius of the circle tangent to all three of the semicircles that form the arbelos (See Figure 4) 


Regions formed by lines in a plane 
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. 


Numbers that equal the sum of their digits plus the sum of the cubes of their digits 
``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. 


Sum of cubes  proof without words 
``Sums and Cubes II.'' The formula for the sum of the first $n$ cubes is: 


Sets of numbers such that the sum of their cubes equals the square of their sum 
``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 twodigit 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$. 


Nontransitive dice 
``Efron's Dice.'' Present the following four dice having the numbers listed below on their faces. $\textbf{A:}$ 0, 0, 4, 4, 4, 4 $\textbf{B:}$ 3, 3, 3, 3, 3, 3 $\textbf{C:}$ 2, 2, 2, 2, 6, 6 $\textbf{D:}$ 1, 1, 1, 5, 5, 5 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. 


Arrange $n$ lines to give 100 points of intersection 
``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. 


Locus of midpoint of sliding ladder 
``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? 


Regions formed by intersecting circles 
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?) 


Bijection between closed ray and open ray 
``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. 


Tile space with circles 
``Beguiling Tilings I'' Tile all of space with nondegenerate circles. 


Recognizing decimals 
``Name That Number'' a.) 3.162277660168379331998893544432718533720 b.) 2.718281828459045235360287471352662497757 c.) 1.618033988749894848204586834365638117720 d.) 1.570796326794896619231321691639751442099 e.) 0.707106781186547524400844362104849039284 


Tiling chessboard with corners removed 
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? 


Filling a grid 
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. 


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


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


Finding counterfeit coin in 2 weighings 
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? 


Two rooks on a chessboard 
How many ways to put a white and black rook on a 


Arbelos area 
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. 


Measuring using 13 and 21 
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.? 


Inaccessible squares for threedimensional knight 
Suppose we begin with a knight sitting at (1,0,0) in threedimensional space. A $\textit{threedimensional 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 threedimensional 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 threedimensional knight jumps. 


Triangulation of $n$gon 
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 $n2$ triangles so that every triangle vertex is one of the original vertices of the $n$gon. 


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


Sum of cubes formula by induction 
Show that: 


Breaking chocolate game 
Suppose that you begin with a chocolate bar made up of $n$ squares by $k$ squares. At each step, you choose a piece of chocolate that has more than two squares and snap it in two along any line, vertical or horizontal. Eventually, it will be reduced to single squares. Show by induction that the number of snaps required to reduce it to single squares is $nk1$. 


Show that $3^{n+1}$ divides evenly into $2^{3^n} +1$ for all $n \ge 0$. 
Show that $3^{n+1}$ divides evenly into $2^{3^n} +1$ for all $n \ge 0$. 


Consecutive Fibonacci are relatively prime 
Show that if $F(n)$ is the $n^{th}$ Fibonacci number and $n>0$, then $F(n)$ and $F(n+1)$ are relatively prime. 


Diameters of circles in an arbelos chain (Pappus) 
($\textbf{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$.) 


$\cos x\cdot\cos 2x\cdot\cos 4x\cdots 
Show that if $\sin x \ne 0$ and $n$ is a natural number, then: 


If there's enough gas in total, then there's enough gas for one car to make it around the circle 
Suppose there are $n$ identical cars on a circular track and among them there is enough gasoline for one car to make a complete loop around the track. Show that there is one car that can make it around the track by collecting all of the gasoline from each car that it passes as it moves. 


$\sum_{k=0}^n {n+k \choose k}\frac{1}{2^k} = 2^n$ 
Show using induction that: 


Divisibility test for 5 
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. 


Counting regions when the plane is cut by lines 
When you cut the plane with $n$ lines, how many $\textit{bounded}$ regions can you make? 


Two kings on a chessboard 
How many ways to put a white and black king on a 


Trigonometry and the 17gon 
Let $\theta = 2\pi/17.$ Compute $\cos\theta +\cos4\theta +\cos9\theta + 


Divisibility test for 10 
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$. 


Counting regions when the plane is cut by "zigzags" 
When you cut the plane with $n$ ``zigzags" (two antiparallel rays joined by a line segment), how many regions can you divide the plane into? 


Counting distinct words 
If you have an alphabet of 26 letters, how many 3letter 


Constructible numbers and the 17gon 
Convince yourself that ${\displaystyle\frac{1}{16}} \left(1 +\sqrt{17} + \sqrt{342\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}}$ 


Divisibility test for 3 
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. 


Divisibility test for 2 
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 2 if and only if $a_0$ is. 


Josephus recursion for even $n$ 
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$? 


Rearranging letters 
How many rearrangements can be made of the letters in the following words: 


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


Divisibility test for 9 
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. 


Josephus recursion for odd $n$ 
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$? 


Eight rooks on a chessboard 
How many ways can you put 8 mutually nonattacking rooks 


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


Divisibility test for 11 
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. 


Josephus problem, sequence of differences 
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$. 


Combinatorics of assigning people to rooms 
There are 3 rooms in a dormitory, a single, a double, 


Tower of Hanoi with special peg 
Tower of Hanoi: Find the shortest sequence of moves that transfers a tower from peg A to peg C if every transfer must be to or from peg B. 


Summing geometric series, inverse problem 
What geometric series has a sum of $\displaystyle\frac{4}{3+2x}$? 


Divisibility test for 7 
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. 


Counting numbers with repeated digits 
How many 10digit numbers have at least 2 equal digits? 


Finite geometric series exercise 
Find $\displaystyle \sum_{k=1}^{2002} \frac{1}{2^k}$. 


Divisibility test for 11 
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. 


Josephus problem, penultimate survivor 
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 secondtolast person to be dismissed. 


Two queens on a chessboard 
How many ways can you put 2 queens on a chessboard so that 


Infinite geometric series exercise 
Find $\displaystyle \sum_{n=1}^{\infty} \frac{2006^n}{2007^n}$. 


Divisibility test for 13 
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. 


Counting routes 
If $A$, $B$, and $C$ are cities If, in addition, there are 6 roads from $C\Longrightarrow D$, how many As in the problem above, but 4($A\Longrightarrow B$), 


Solving a recurrence 
Solve the recurrence $Q_0 = \alpha$, $Q_1 = \beta$, $Q_n = \displaystyle\frac{1+Q_{n1}}{Q_{n2}}, n>1$. Hint: $Q_4 = \displaystyle\frac{1+\alpha}{\beta}$ 


Number of ways to pair $2n$ people 
How many ways can you split 14 people into 7 pairs? 


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


Recursive divisibility test for 7 
Show that $a = 10x+y$ is divisible by 7 if and only if $x2y$ is. 


Solving a recurrence with different rules for even and odd indexes 
Solve the recurrence $g(1) = a$, $g(2n+1) = 3g(n) + bn + c$, $g(2n) = 3g(n) + bn + d$. 


Marriage problem 
N boys and N girls are in a dance class. How many ways are 


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


Divisibility test for 7 
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. 


All horses are the same color fallacy 
To show: all horses are the same color. 


Combinations exercise 
How many ways are there to choose a team of 3 students from a 


Archimedes lemma for tangent circles 
If two circles are tangent at $A$, and if $\overline {BD}$, 


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


Divisibility test for 7 
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 $(2)^d a_0 + (2)^{ d1 } a_1 + (2)^{ d2 } a_2 + \dots + a_d$ is. 


AMGM inequality 
We will prove the statement $P(n): x_1 x_2 \ldots x_n \leq \left( {\displaystyle\frac{x_1 + x_2 + \cdots + x_n}{n}} \right) ^n$ 


Combinations and pairings 
One student has 6 books and another has 8. In how many ways 


Telescoping series and partial fractions (quadratic) 
Find $\displaystyle \sum_{k=1}^{2007} \frac{1}{k(k+1)}$. Find $\displaystyle\sum_{n=1}^{\infty}\frac{1}{n(n+1)}$. 


Divisibility test for 17 
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 17 if and only if $(5)^d a_0 + (5)^{ d1 } a_1 + (5)^{ d2 } a_2 + \dots + a_d$ is. 


Quadratic game 
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? 


Combinations and forming teams 
How many ways can a group of 10 boys be divided into two 


Telescoping series and partial fractions (cubic) 
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)}$. 


Divisibility test for 19 
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 19 if and only if $2^d a_0 + 2^{ d1 } a_1 + 2^{ d2 } a_2 + \dots + a_d$ is. 


Divisibility test for 4 
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 4 if and only if $a_0 + 10 a_1$ is. 


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


Triangles formed by 10 points in the plane 
Ten points are marked on the plane so that no three of them are 


Telescoping series and partial fractions (nonconsecutive terms) 
Find $\displaystyle \sum_{k=1}^{n} \frac{3}{k(k+3)}$. Find $\displaystyle\sum_{n=1}^{\infty}\frac{3}{n(n+3)}$. 


Two polynomials whose coefficients are each others' roots 
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$? 


Choosing teams with specified roles 
A group of soldiers contains 3 officers, 6 sergeants, and 30 


Arctan identity 
Show $\displaystyle \arctan x \arctan y = \arctan\frac{xy}{1+xy}.$ 


Generating functions and squaring 
Compute the sequence $(a_k)$ that gives rise to the generating function $\sum_{ k \ge 0 } a_k \, x^k = \left( \frac 1 { 1x } \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)$? 


Symmetric polynomials of roots (quadratic) 
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$. 


Triangles formed by points on parallel lines 
Ten points are marked on a straight line and 11 on another 


Tower of Hanoi with special peg is universal 
Tower of Hanoi: Transferring a tower of three discs from peg A to peg C, with every move being to or from peg B, prove that every legal arrangement of three discs occurs along the way. 


Arctan identities and pi approximations 
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 


Generating functions to solve recursion 
Define a recursive sequence by setting $a_0 = 0$ and $a_{n+1} = 2 a_n + 1$ for $n \ge 0$. (a) Conjecture a formula for $a_k$ by experimenting. (b) 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$. (c) Expand your formula for $g(x)$ into partial fractions, and use the result to prove your conjectured formula for $a_k$. 


Sums of powers of roots (quadratic) 
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. 


Placing checkers 
How many ways can you put 10 white and 10 black checkers on 


Binomial theorem and approximating cube roots 
Find $\sqrt[3]{1729}$ to 4 decimal places in 40 seconds. (Hint 1: recall that 


Solving recursion (inhomogeneous) 
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$. 


Sum of cubes of roots of a quadratic 
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$. 


Counting numbers by sum of digits 
How many 10digit numbers have the sum of their digits equal 


Harmonic series diverges 
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. 


Difference of cubes, solving equations 
Given that $x$ is a real number satisfying $\sqrt[3]{x+9}  \sqrt[3]{x9} = 3$, compute $x^2$. 


Choosing team captains 
How many ways can you choose a captain and cocaptain of 


Lottery combinations 
To win the California lottery, you must choose 6 numbers 


Harmonic series with prime divisors restricted 
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}+ 


Fibonacci generating function 
The $\textit{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$. 


Difference of fourth powers, solving equations 
Find all solutions (real and complex) of $\sqrt[4]{x} + \sqrt[4]{97x} = 5$. 


Counting subsets  dinner party model 
A person has 10 friends. Over several days he invites some 


Solving recursion for Fibonaccilike sequence 
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$. 


Polynomials, sum of fifth powers 
Find all solutions of $x+y=3$, $x^5 + y^5 = 33$. 


Counting subsets  staircase model 
There are 7 steps in a flight of stairs (not counting the 


Sum of reciprocals of squares of odd numbers 
Euler showed that $\displaystyle\sum_{n=1}^{\infty}\frac{1}{n^2}=\frac{\pi^2}{6}$. 


Arbelos radii 
In an arbelos the two circles inscribed in regions $ACD$ and $BCD$ have equal radii. See Figure 3. Prove this. Find this radius in terms of the radii of the three semicircles that form the arbelos. (This is Proposition 5 in Archimedes' $\textit{The Book of Lemmas}$). 

To create a new problem set with these problems, first Create a Problem Set and then return to this page to add problems to it. 