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

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.

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

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?

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

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?

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?

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

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

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

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?

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

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

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

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?

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?

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?

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?

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

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?

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

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

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?

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?

1-2
3-4
5-6

7-8

9-10

11-12

13-14

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

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?

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

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?

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?

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?

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?

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?

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

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?

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?

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

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

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?

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?

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

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?

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

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

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?

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

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

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?

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?

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?

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?

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

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

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

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?

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?

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?

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

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. 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. 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. 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. 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? 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/ 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? 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? 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? 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. 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. 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? 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. 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. 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$. 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! 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$. 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$. 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? 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 \, .$ 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$. 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$. 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$)? 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. 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. 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$. 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? 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? 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$. 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? 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. 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$. 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? 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. 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$.) 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$. 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? 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? 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$. 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? 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. 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$. 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? 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$. 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$. 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)? 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? 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. 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$. 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? 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? 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)$. 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? 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$. 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? 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? 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. 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. 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. 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? 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? 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? 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. 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. 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? 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? 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? 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? 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. 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: ((())), (())(), ()(()), (()()), ()()(). 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? 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. 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. 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? 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. 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? 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? 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? 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.) 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. 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.) 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$. 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? 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. 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.) 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. 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? 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? 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$? 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? 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.$ 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}.$ 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}.$ 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}.$ 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.$ 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}.$ 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}.$ 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$. 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.$ 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}$). 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. 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. 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. 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$. 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. 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. 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? 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?) 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. 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. 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 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? 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. 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. 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? 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? 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.) 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. 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.? 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. 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. 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}.$ 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.$ 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$. 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$. 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. 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$.) 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}.$ 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. 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.$ 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. 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? 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.) 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.$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$. 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? 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? 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}}$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. 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. 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$? 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.) 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$. 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. 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$? 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? 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$. 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. 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$. 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? 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. 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}$? 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. 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? 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}$. 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. 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. 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.) 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}$. 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. 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$? 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}$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? 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}$. 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. 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$. 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? 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. 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. 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? 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? 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}$). 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}$. 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. 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$. 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? 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)}$. 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. 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? 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? 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)}$. 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. 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. 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? 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? 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)}$. 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$? 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? 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}.$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)$? 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$. 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? 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. 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. 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$. 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. 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? 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} $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$. 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$. 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? 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. 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$. 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? 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? 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$. 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$. 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$. 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? 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$. 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$. 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? 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}$. 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}\$).

1-2
3-4
5-6
7-8

9-10
11-12
13-14