Math Circle Problem Collection Home | Math Circle Problem Sets | Math Circle Problem List | Math Circle Lesson Plans

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 one-mile 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.

EasyModerateChallengingPerplexing
1-2
3-4
 
5-6
 
 
7-8
 
 
9-10
 
11-12
 
 
13-14
 
 

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)$\,?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

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$\,?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

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$\,?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

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$\,?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

Cos(a-b)

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

How many three-digit numbers

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

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$\,?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

ABCDE are distinct integers

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

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$\,?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 

Measure of angles in star-polygon

A star-polygon 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 star-polygon?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
7-8
 
 
9-10
 
 
11-12
 
13-14

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

Smallest positive integer

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

Choose a number, roll dice

A player chooses one of the numbers 1 through 4. After the choice has been made, two regular four-sided (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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

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$?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

Circle surrounded by 4 circles

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
7-8
 
 
9-10
 
 
11-12
 
13-14

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

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$?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

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$?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

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!''?} \]

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
7-8
 
 
9-10
 
 
11-12
 
13-14

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

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$?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
7-8
 
 
9-10
 
 
11-12
 
13-14

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 

Circle Circumscribed about a Triangle

The point $O$ is the center of the circle circumscribed about
$\triangle ABC$, with $\angle BOC = 120^{\circ}$ and $\angle AOB =
140^{\circ}$, as shown. What is the degree measure of $\angle
ABC$?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

Odd Operators 2

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
7-8
 
 
9-10
 
 
11-12
 
13-14

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
7-8
 
 
9-10
 
 
11-12
 
13-14

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
7-8
 
9-10
 
11-12
 
 
13-14
 
 

Hand holding counts.

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
 
11-12
 
 
13-14
 
 

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
 
9-10
 
 
11-12
 
 
13-14
 

Minimal Perpendicular Construction

Given two points on a line, what is the minimal number of steps required to construct
a perpendicular to the line through one of the points using a straight edge and compass?
Why?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
 
 
9-10
 
11-12
 
13-14
 
 

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$?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

Twelve Sided Polygon

Consider the 12-sided 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\,$?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

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$?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 

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\,$?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

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\,$?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

Primes Dividing a Sequence

A finite sequence of three-digit 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\,$?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

$ 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}\,$?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

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\,$?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

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 $ad-bc$ is even?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 
 

Exponential Unknowns

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
7-8
 
 
9-10
 
 
11-12
 
13-14

Two consecutive integers

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
7-8
 
 
9-10
 
11-12
 
13-14

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
7-8
 
 
9-10
 
 
11-12
 
 
13-14
 

Odd operators

Define $a@b=ab-b^2$ and $a\#b=a+b-ab^2$. What is $\frac{6@2}{6\#2}\,$?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
7-8
 
 
9-10
 
 
11-12
 
13-14

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
7-8
 
 
9-10
 
11-12
 
13-14

Odd operators

Define $a@b=ab-b^2$ and $a\#b=a+b-ab^2$. What is $\frac{6@2}{6\#2}\,$?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
7-8
 
 
9-10
 
 
11-12
 
13-14

General 3 penny touch

For which numbers, n, is it possible to arrange a collection of that number (n) of
pennies, so that every penny touches exactly three other pennies?

EasyModerateChallengingPerplexing
1-2
 
3-4
 
5-6
 
 
7-8
 
 
9-10
 
 
11-12
 
 
 
13-14
 
 
 

Easy Penny Touch

Is it possible for 25 pennies to be positioned so that each one touches exactly one more
penny? Is this possible with 24 pennies?

EasyModerateChallengingPerplexing
1-2
 
3-4
 
5-6
 
7-8
 
9-10
 
11-12
13-14

Local Penny Touch

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

EasyModerateChallengingPerplexing
1-2
 
3-4
 
 
5-6
 
 
7-8
 
9-10
 
11-12
 
13-14
 

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$?

EasyModerateChallengingPerplexing
1-2
 
 
3-4
 
 
5-6
 
 
7-8
 
 
9-10
 
11-12
 
13-14
 

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.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
 
11-12
 
13-14

Intersecting cylinders

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Fruit cutting High School

Take two sufficiently long congruent right prisms over regular n-gons. 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.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Fruit cutting 6-8th grades

Describe the possible sections of a right prism over a regular n-gon. What is the smallest number of edges possible? What is the largest number of edges possible? Can the resulting sections be non-convex? When can they be regular? Have right angles?... Explore. Repeat for sections of right pyramids over regular n-gon bases. It is possible to experiment with fruit or cheese.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Fruit cutting preK-5th 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.
* Likewise, the definitions of "prism" and "pyramid" need to be created together.
* Wait for children to imagine the cuts before each experiment. Encourage them to gesture as if cutting, to feel the shapes better.
* Children usually start yelling out hypotheses about answers, as you are preparing to cut apples. After they do for a while, go through every number they offered, and ask everybody who thinks this will be the answer to wave. Otherwise kids can keep repeating their answers all day (they want to make sure they are heard).

Some pictures here: http://www.flickr.com/photos/26208371@N06/6197204225/in/photostream/

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Specifying a pixel

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Distance between points in the plane

In order to find the distance between two points in four-dimensional 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?

EasyModerateChallengingPerplexing
1-2
 
3-4
 
5-6
 
7-8
 
9-10
 
11-12
 
13-14
 

Why two-dimensional space?

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

The Game of Criss Cross- 4 Point Outer Boundary Formula

Suppose that we change the outer boundary of a Criss-Cross 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.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

The Game of Criss Cross- 4 Point Outer Boundary

Suppose that we change the outer boundary of a Criss-Cross 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.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

The Game of Criss Cross- Who will win?

Will the first or second player win on the left-hand 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.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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} n-1 \\ k-1 \end{array}\right) + \left( \begin{array}{c} n-1 \\ 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$.

EasyModerateChallengingPerplexing
1-2
 
3-4
5-6
7-8
9-10
11-12
13-14

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!

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
 
9-10
11-12
13-14

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$.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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$.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Partitioning indistinguishable items

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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) }{ 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 \, . \]

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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$.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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$.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
 
11-12
 
 
13-14
 

Partitioning $k$ items into $n$ indistinguishable boxes

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 at
least one thing in each box (so, of course, $k>n$)?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
 
9-10
 
11-12
 
 
13-14
 
 

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.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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$.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Coloring book covers

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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.
Compute $c_G(k)$ for the following four classes:

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
 
 
11-12
13-14

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$.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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
ways are there for the passengers to get off the train at the
stops? What if we only care about the number of passengers getting
off at each stop?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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$.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Arranging objects with a nonadjacency restriction

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Existence of 2x2 magic squares

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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$.)

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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 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$.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Representations of 100000 as the product of 3 factors

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Counting magic 3x3 squares

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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$.
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$.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Choosing books with no two adjacent

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Magic sum for $n \times n$ square

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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$.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Counting distinct necklaces

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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.
Let $\left( x_{ ij } \right)_{ 1 \le i, j \le 3 }$ be a magic $3 \times 3$ square.

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$.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
7-8
 
9-10
11-12
13-14

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$.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14
 
 

Counting words with at least one ``A"

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Choosing officers

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
 
 
9-10
 
11-12
13-14

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$.
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$.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Paths in a complete graph

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Diffie-Hellman introduction

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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)$.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Counting rectangles in the grid

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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$.
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$.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Paths through a cube

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. At
a given moment, it can jump to the center of any of the cubes
which has a common face with the cube where it sits, as long as the
jump increases the distance between point $O$ and the current
position of the grasshopper. How many ways are there for the
grasshopper to reach the unit cube at the opposite corner?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Introduction to RSA cryptosystem

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Counting numbers with adjacent equal digits

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Arbelos construction

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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 out---these squares are addictive).
We will work on two problems regarding Sudoku squares:

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.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
 
 
9-10
 
11-12
13-14

Partitioning a deck of cards

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Partitioning colored balls

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Lotto winners with at least one adjacent pair

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 subset
has at least one pair of neighbors?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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
sum can be interpreted as the number of ways to choose a committe
of at least one that includes a president,
vice-president, and treasurer (not necessarily distinct persons) from
a set of $n$ people.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Choosing objects when some are distinguishable and some are not

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Choosing an odd number of objects

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Distinct ways to sit around a circular table

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Connecting points in pairs with nonintersecting segments

$2n$ points are chosen on a circle. In how many ways can
you connect them all in pairs such that none of the segments
overlap?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Ways to triangulate an $n$-gon

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Ways to nest parentheses

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Can you arrange the numbers $1, 2, \ldots, 9$ along a circle
such that the sum of two neighbors is never divisible by 3, 5, or
7?

Can you arrange the numbers $1, 2, \ldots, 9$ along a circle
such that the sum of two neighbors is never divisible by 3, 5, or
7?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Choosing two distinct subsets

In how many ways can you choose two distinct subsets from a
collection of $N$ items? The two subsets together need not
include all $N$ items.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

In how many ways can you choose two distinct subsets from a
collection of $N$ items? The two subsets together need not
include all $N$ items.

In how many ways can you choose two distinct subsets from a
collection of $N$ items? The two subsets together need not
include all $N$ items.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Subsets with no consecutive elements

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Distributing billiard balls into pockets

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Rearrangements with a maximum distance of 1

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Polyhedra with odd faces and odd edges

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Can you partition the set of positive integers into infinitely
many infinite subsets such that each subset is generated from
any other by adding the same positive integer to each element
of the subset?

Can you partition the set of positive integers into infinitely
many infinite subsets such that each subset is generated from
any other by adding the same positive integer to each element
of the subset?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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.)

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Sum of products of reciprocals of subsets

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 each
of 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, and
1/6, respectively. The sum of all of them is 3.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Counting groupings (Stirling)

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\mid
BC$, $B\mid AC$, $C\mid AB$, $A\mid B\mid C$. The vertical bars
represent divisions into groups.)

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Counting poker hands

Find the number of poker hands of each type. For the
purposes of this problem, a poker hand consists of 5 cards chosen
from a standard pack of 52 (no jokers). Also for the purposes of
this problem, the ace can only be a high card. In other words, the
card sequence $A\clubsuit$, $2\diamondsuit$, $3\diamondsuit$,
$4\spadesuit$, $5\heartsuit$ is not a straight, since the ace is
a high card only.

Here are the definitions of the hands:

$\textbf{ Royal flush:}$ $10$ through $A$ in the same suit.

Example: $10\spadesuit$, $J\spadesuit$, $Q\spadesuit$,
$K\spadesuit$, $A\spadesuit$.

$\textbf{Straight flush:}$ 5 cards in sequence in the same suit, but not
a Royal flush.

Example: $4\diamondsuit$, $5\diamondsuit$, $6\diamondsuit$,
$7\diamondsuit$, $8\diamondsuit$.

$\textbf{Four of a kind:}$ Four cards of the same rank.

Example: $Q\spadesuit$, $Q\heartsuit$, $Q\diamondsuit$,
$Q\clubsuit$, $7\spadesuit$.

$\textbf{ Full house:}$ Three cards of one rank and two of another.

Example: $3\spadesuit$, $3\diamondsuit$, $3\clubsuit$,
$9\heartsuit$, $9\diamondsuit$.

$\textbf{ Flush:}$ Five cards in the same suit that are not in sequence.

Example: $3\clubsuit$, $4\clubsuit$, $5\clubsuit$,
$6\clubsuit$, $8\clubsuit$.

$\textbf{ Straight:}$ Five cards in sequence that are not all in the
same suit.

Example: $6\clubsuit$, $7\clubsuit$, $8\diamondsuit$,
$9\spadesuit$, $10\clubsuit$.

$\textbf{ Three of a kind:}$ Three cards of the same rank; the others of
different rank.

Example: $J\clubsuit$, $J\diamondsuit$, $J\spadesuit$,
$7\diamondsuit$, $K\heartsuit$.

$\textbf{ Two pairs:}$ Two pairs of cards.

Example: $5\heartsuit$, $5\spadesuit$, $8\diamondsuit$,
$8\clubsuit$, $A\spadesuit$.

$\textbf{ Pair:}$ A single pair of cards.

Example: $3\clubsuit$, $3\diamondsuit$, $5\spadesuit$,
$9\diamondsuit$, $Q\diamondsuit$.

$\textbf{ Bust:}$ A hand with none of the above.

Example: $2\clubsuit$, $4\spadesuit$, $6\diamondsuit$,
$8\heartsuit$, $10\clubsuit$.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
 
 
9-10
 
11-12
13-14

Counting zeroes used in counting to 333,333,333

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Circles and Pythagoras

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$ and
to the line that lies in the area enclosed by them.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Diagonals in a dodecahedron

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Pool table bounces

A pool table is $4$ feet wide and $8$ feet long, and is
arranged in a coordinate system where $1$ unit is $1$ foot so that
one 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)$ so
that its first bounce is against the wall at $y = 4$, in how many
places can you hit that wall so that the ball goes into the pocket
at $(8,0)$ after exactly $11$ total bounces against the walls
$y=0$ and $y=4$? It doesn't matter how many times the ball
bounces against the walls at $x=0$ and $x=8$. Assume the ball
always bounces so that it's angle of incidence is equal to it's
angle of reflection.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Area of a flower

A "flower" pattern is made as follows. A regular hexagon is
inscribed in a circle of radius $1$. A circle is drawn with each
of the edges of the hexagon as diameter. The flower consists of
everything inside the original circle or inside any of the six
smaller circles. What is the area of the flower?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Radius of circle circumscribed around three smaller ones

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Radius of circles in a tangent ring

Arrange $n$ circles or radius $r$, in a ring such that
each is tangent to its two neighbors, with the points of tangency
all lying on a circle of radius $1$. What is $r$?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Counting diagonals

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Alternating sum of binomial coefficients

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Find a nice formula for the sum:
\[ {n \choose 0}^2 + {n \choose 1}^2 + {n \choose 2}^2 + \cdots + {n \choose n}^2. \]

Find a nice formula for the sum:
\[ {n \choose 0}^2 + {n \choose 1}^2 + {n \choose 2}^2 + \cdots + {n \choose n}^2. \]

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Show that if $m > k$ and $n > k$ then:
\[\sum_{j=0}^k {n \choose j}{m \choose k-j} = {n+m \choose k}. \]

Show that if $m > k$ and $n > k$ then:
\[\sum_{j=0}^k {n \choose j}{m \choose k-j} = {n+m \choose k}. \]

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Prove that for any $n > 0$:
\[1^2 + 4^2 + 7^2 + 10^2 + \cdots
+ (3n-2)^2 = n(6n^2 - 3n - 1)/2. \]

Prove that for any $n > 0$:
\[1^2 + 4^2 + 7^2 + 10^2 + \cdots
+ (3n-2)^2 = n(6n^2 - 3n - 1)/2. \]

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Arbelos tangent radius

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' $\textit{Book of Lemmas}$).

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
7-8
9-10
11-12
13-14

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.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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.

EasyModerateChallengingPerplexing
1-2
3-4
 
 
 
 
5-6
 
 
7-8
9-10
11-12
13-14

Sum of cubes - proof without words

``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.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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 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$.

EasyModerateChallengingPerplexing
1-2
3-4
 
 
 
5-6
 
 
7-8
 
9-10
11-12
13-14

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.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
 
9-10
11-12
13-14

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.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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?)

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
 
 
 
13-14
 
 

Tile space with circles

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
 
 
13-14
 

Recognizing decimals

``Name That Number''

a.) 3.162277660168379331998893544432718533720

b.) 2.718281828459045235360287471352662497757

c.) 1.618033988749894848204586834365638117720

d.) 1.570796326794896619231321691639751442099

e.) 0.707106781186547524400844362104849039284

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
 
9-10
11-12
13-14

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
 
11-12
13-14

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.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Two rooks on a chessboard

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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.?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Inaccessible squares for three-dimensional knight

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.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
 
 
7-8
9-10
11-12
13-14

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Sum of geometric series by induction

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}. \]

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Sum of cubes formula by induction

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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 $nk-1$.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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$.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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$.)

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
 
 
9-10
 
 
11-12
13-14

$\cos x\cdot\cos 2x\cdot\cos 4x\cdots
\cos 2^{n-1}x = \frac{\sin 2^nx}{2^n \sin x}$

Show that if $\sin x \ne 0$ and $n$ is a natural number, then:
\[ \cos x\cdot\cos 2x\cdot\cos 4x\cdots
\cos 2^{n-1}x = \frac{\sin 2^nx}{2^n \sin x}. \]

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

$\sum_{k=0}^n {n+k \choose k}\frac{1}{2^k} = 2^n$

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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.

EasyModerateChallengingPerplexing
1-2
3-4
 
 
5-6
 
 
7-8
9-10
11-12
13-14

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
 
11-12
13-14

Two kings on a chessboard

How many ways to put a white and black king on a
chessboard so that neither attacks the other? (A king attacks only
those squares adjacent to it, so a king away from the edge of the
board attacks the 8 adjacent squares.)

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Trigonometry and the 17-gon

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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$.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Counting regions when the plane is cut by "zig-zags"

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Counting distinct words

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Constructible numbers and the 17-gon

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}}$

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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$?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Rearranging letters

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.)

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Primes dividing $a^2 + 1$

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$.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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$?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Eight rooks on a chessboard

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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$.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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$.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Combinatorics of assigning people to rooms

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Summing geometric series, inverse problem

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Counting numbers with repeated digits

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Finite geometric series exercise

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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 second-to-last person to be dismissed.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Two queens on a chessboard

How many ways can you put 2 queens on a chessboard so that
they don't attack each other? (Queens attack both on the rows
and on the diagonals of a chessboard.)

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Infinite geometric series exercise

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Counting routes

If $A$, $B$, and $C$ are cities
If there are 4 roads from $(A \Longrightarrow B)$ and 3 from
$B \Longrightarrow C$, how
many ways are there from $A \Longrightarrow C$? (Assume that
all roads are one-way, in the direction of the arrows.)

If, in addition, there are 6 roads from $C\Longrightarrow D$, how many
ways from $A \Longrightarrow D$?

As in the problem above, but 4($A\Longrightarrow B$),
3($B\Longrightarrow C$), 5($A\Longrightarrow D$), 5($D\Longrightarrow
C$). How many ways from $A \Longrightarrow C$?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
 
9-10
11-12
13-14

Solving a recurrence

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}$

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Number of ways to pair $2n$ people

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Sum of $\frac{n}{2^n}$

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Recursive divisibility test for 7

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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$.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Marriage problem

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Summing a Fibonacci-geometric series

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

All horses are the same color fallacy

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Combinations exercise

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Archimedes lemma for tangent circles

If two circles are tangent at $A$, and if $\overline {BD}$,
$\overline{EF}$ are parallel diameters in the circles,
then $A$, $D$, and $F$ are collinear. (This is Proposition 1 in Archimedes' $\textit{The Book of Lemmas}$).

EasyModerateChallengingPerplexing
1-2
3-4
5-6
 
7-8
 
9-10
11-12
13-14

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

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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)^{ d-1 } a_1 + (-2)^{ d-2 } a_2 + \dots + a_d$ is.

EasyModerateChallengingPerplexing
1-2
3-4
 
5-6
7-8
9-10
11-12
13-14

AM-GM 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$
for all positive $x_i$.
a)By setting $x_n = \displaystyle\frac{x_1 + x_2 + \cdots + x_{n-1}}{n-1}$, prove that $P(n)$ implies $P(n-1)$ for all $n > 1$.
b)Show that $P(n)$ and $P(2)$ imply $P(2n)$.
c)Explain why this proves $P(n)$ is true for all $n$.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Combinations and pairings

One student has 6 books and another has 8. In how many ways
can they exchange 3 books of the first student for 3 books of the
second?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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)}$.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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)^{ d-1 } a_1 + (-5)^{ d-2 } a_2 + \dots + a_d$ is.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
 
9-10
11-12
13-14

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Combinations and forming teams

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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)}$.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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^{ d-1 } a_1 + 2^{ d-2 } a_2 + \dots + a_d$ is.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
 
9-10
11-12
13-14

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.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Triangles formed by 10 points in the plane

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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)}$.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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$?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Choosing teams with specified roles

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Arctan identity

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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 { 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)$?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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$.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Triangles formed by points on parallel lines

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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
$ 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.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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$.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
 
9-10
11-12
13-14

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.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Placing checkers

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Binomial theorem and approximating cube roots

Find $\sqrt[3]{1729}$ to 4 decimal places in 40 seconds. (Hint 1: recall that
1729 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$ with $k\in \mathbb{R} $

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
 
9-10
11-12
13-14

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$.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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$.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Counting numbers by sum of digits

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Difference of cubes, solving equations

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Choosing team captains

How many ways can you choose a captain and co-captain of
a football team with 11 members?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Lottery combinations

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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}+
\frac{1}{22}+\frac{1}{26}+\frac{1}{28}+\cdots$.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
 
9-10
11-12
13-14

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$.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
 
9-10
11-12
13-14

Difference of fourth powers, solving equations

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Counting subsets - dinner party model

A person has 10 friends. Over several days he invites some
of them to a dinner party in such a way that he never invites
exactly the same group of people. How many days can he keep
this up, assuming that one of the possibilities is to ask
nobody to dinner?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Solving recursion for Fibonacci-like 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$.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Polynomials, sum of fifth powers

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

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Counting subsets - staircase model

There are 7 steps in a flight of stairs (not counting the
top and bottom of the flight). When going down, you can jump
over some steps if you like, perhaps even all 7. In how
many different ways can you go down the stairs?

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

Sum of reciprocals of squares of odd numbers

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}$.

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
9-10
11-12
13-14

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}$).

EasyModerateChallengingPerplexing
1-2
3-4
5-6
7-8
 
9-10
11-12
13-14
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.