King Chickens
Variables
K: King Chicken
F: Field Marshal
C: Chicken
1. For each chicken in a flock, count the number of other chickens which that particular chicken pecks.
Formulate a conjecture about the coefficients
of the polynomials
.
Variables
K: King Chicken 1. For each chicken in a flock, count the number of other chickens which that particular chicken pecks.
Formulate a conjecture about the coefficients
of the polynomials
.
Variables
F: Field Marshall 1. For each chicken in a flock, count the number of other chickens which that particular chicken pecks.
Formulate a conjecture about the coefficients
of the polynomials
.
Variables
C: Chicken 2. How can we arrange for a flock (of any size) to have exactly one king?
Variables
K: King Chicken 2. How can we arrange for a flock (of any size) to have exactly one king?
Variables
F: Field Marshall 2. How can we arrange for a flock (of any size) to have exactly one king?
Variables
C: Chicken 3. If a chicken has the barnyard to itself, of course it is king. How many kings will there be in a flock with two chickens?
Variables
K: King Chicken 3. If a chicken has the barnyard to itself, of course it is king. How many kings will there be in a flock with two chickens?
Variables
F: Field Marshall 3. If a chicken has the barnyard to itself, of course it is king. How many kings will there be in a flock with two chickens?
Variables
C: Chicken 4. There are essentially two different possible pecking orders for a flock with three chickens. How many of the three chickens are kings in each case?
Variables
K: King Chicken 4. There are essentially two different possible pecking orders for a flock with three chickens. How many of the three chickens are kings in each case?
Variables
F: Field Marshall 4. There are essentially two different possible pecking orders for a flock with three chickens. How many of the three chickens are kings in each case?
Variables
C: Chicken
1. Suppose that pecking were transitive, meaning that given any three chickens, if C1 -> C2 and C2 -> C3. Show that in this case there must be some chicken who pecks all the others
Variables
K: King Chicken
1. Suppose that pecking were transitive, meaning that given any three chickens, if C1 -> C2 and C2 -> C3. Show that in this case there must be some chicken who pecks all the others
Variables
F: Field Marshall
1. Suppose that pecking were transitive, meaning that given any three chickens, if C1 -> C2 and C2 -> C3. Show that in this case there must be some chicken who pecks all the others
Variables
C: Chicken 2. Find a flock of six chickens in which every chicken is a king.
Variables
K: King Chicken 2. Find a flock of six chickens in which every chicken is a king.
Variables
F: Field Marshall 2. Find a flock of six chickens in which every chicken is a king.
Variables
C: Chicken 3. If a flock has exactly one king, prove that he must peck all the other chickens.
Variables
K: King Chicken 3. If a flock has exactly one king, prove that he must peck all the other chickens.
Variables
F: Field Marshall 3. If a flock has exactly one king, prove that he must peck all the other chickens.
Variables
C: Chicken
4. "Let K be a king which is pecked by some other chicken. Then there must be a king among the field marshalls of K." Is this statement valid for every pecking order? Either prove this assertion or find a counterexample.
Variables
K: King Chicken
4. "Let K be a king which is pecked by some other chicken. Then there must be a king among the field marshalls of K." Is this statement valid for every pecking order? Either prove this assertion or find a counterexample.
Variables
F: Field Marshall
4. "Let K be a king which is pecked by some other chicken. Then there must be a king among the field marshalls of K." Is this statement valid for every pecking order? Either prove this assertion or find a counterexample.
Variables
C: Chicken The arbelos consists of three points
and
which are collinear, together with the semicircles
,
and
as shown in Figure 1. In the figure
has been added to the figure tangent to the two small semicircles.
intersects a small semicircle at
and
intersects the other small semicircle at
.
intersects
at
. Prove the area of the arbelos is equal to the area of the circle with diameter
,
and
bisect each other, and
is tangent to the small semicircles.
Variables
Variables
Write an integer
in terms of its decimal expansion:
. Prove that
is divisible by 8 if and only if
is.
Variables
Variables
Tower of Hanoi: Arrange the three pegs in a circle. Let
be the number of moves it takes to move a tower of
discs from peg A to peg B with all moves being clockwise, and
with all moves being counter-clockwise. Express
and
recursively. Alternatively: prove that
and otherwise
and
.
Variables
Variables
How many ways are there to choose a president, a vice-president, andtreasurer from a club of 15, assuming all three are different people?
Variables
Variables
Construct with proof, the twin circles in a given arbelos with a straightedge and compass.
Variables
Variables
Write an integer
in terms of its decimal expansion:
. Come up and prove a divisibility test for powers of 2.
Variables
Variables
Tower of Hanoi: A double tower consists of two discs of each of
sizes. How many moves does it take to transfer a double tower from peg A to peg B? (As usual, a bigger disc may never be placed on top of a smaller disc, but equal discs may be placed on top of each other.)
Variables
Variables
How many diagonals are there in a convex
-gon?
Variables
Variables
Find the radius of the circle tangent to all three of the semicircles that form the arbelos (See Figure 4) in terms of the radii of these three semicircles. (This is Proposition 6 in Archimedes' \emph{Book of Lemmas}).
Variables
Variables
You can make Venn diagrams using circles that cut the plane into two regions with one circle, four regions with two circles, and eight regions with three circles. Is it possible to make sixteen regions with four circles? (Generalize: how many regions can be made with n circles?)
Variables
Variables
How many ways to put a white and black rook on achessboard so that neither can attack the other? (Rooks can onlyattack along rows and columns -- not along the diagonals.)
Variables
Variables
({\bf Pappus}) The chain of inscribed circles,
, in an arbelos has the following property. The distance from the diameter of the largest semicircle to the center of the
circle in the chain,
, is exactly equal to
, where
is the diameter of
. (Hint: Use inversion in a circle orthogonal to
.)
Variables
Variables
Write an integer
in terms of its decimal expansion:
. Prove that
is divisible by 5 if and only if
is.
Variables
Variables
When you cut the plane with
lines, how many {\em bounded} regions can you make?
Variables
Variables
How many ways to put a white and black king on achessboard so that neither attacks the other? (A king attacks onlythose squares adjacent to it, so a king away from the edge of theboard attacks the 8 adjacent squares.)
Variables
Variables
Let
Compute
Variables
Variables
Write an integer
in terms of its decimal expansion:
. Prove that
is divisible by 10 if and only if
.
Variables
Variables
When you cut the plane with
"zig-zags" (two antiparallel rays joined by a line segment), how many regions can you divide the plane into?
Variables
Variables
If you have an alphabet of 26 letters, how many 3-letterwords can you make? What if the three letters all haveto be different? How many 5 letter words can you make,if you can repeat letters, but can't have 2 in a rowthat are the same?
Variables
Variables
Convince yourself that
is constructible by constructing
Variables
Variables
Write an integer
in terms of its decimal expansion:
. Prove that
is divisible by 3 if and only if
is.
Variables
Variables
Josephus problem:
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
.For what even numbers
is it true that
?
Variables
Variables
How many rearrangements can be made of the letters in the following words:VECTOR, TRUST, CARAVAN, CLOSENESS, MATHEMATICAL? (For example, for``VECTOR'', some possibilities include: VECTRO, OTCEVR, and ROTVEC.)
Variables
Variables
If
is even and
is a prime that is not a factor of
and
(the notation
stands for
divides
), then
for some integer
.
Variables
Variables
Write an integer
in terms of its decimal expansion:
. Prove that
is divisible by 9 if and only if
is.
Variables
Variables
Josephus problem:
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
.For what odd numbers
is it true that
?
Variables
Variables
How many ways can you put 8 mutually non-attacking rookson a standard
chessboard?
Variables
Variables
Let
define the sequence of Fermat numbers. Prove that
for all
.
Variables
Variables
Write an integer
in terms of its decimal expansion:
. Prove that
is divisible by 11 if and only if
is.
Variables
Variables
Josephus problem:
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
.Let
. Show that for any even number
,
.
Variables
Variables
There are 3 rooms in a dormitory, a single, a double,and a quad. How many ways are there to assign 7 peopleto the rooms?
Variables
Variables
What geometric series has a sum of
?
Variables
Variables
Write an integer
in terms of its decimal expansion:
. Prove that
is divisible by 7 if and only if
is.
Variables
Variables
How many 10-digit numbers have at least 2 equal digits?
Variables
Variables
Find
.
Variables
Variables
Write an integer
in terms of its decimal expansion:
. Prove that
is divisible by 11 if and only if
is.
Variables
Variables
Josephus problem:
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
.What is a formula for
, the number of the penultimate survivor? That is, where should Josephus's friend sit? In our example,
since person 3 is the second-to-last person to be dismissed.
Variables
Variables
How many ways can you put 2 queens on a chessboard so thatthey don't attack each other? (Queens attack both on the rowsand on the diagonals of a chessboard.)
Variables
Variables
Find
.
Variables
Variables
Write an integer
in terms of its decimal expansion:
. Prove that
is divisible by 13 if and only if
is.
Variables
Variables
Solve the recurrence
,
,
.Hint:
Variables
Variables
How many ways can you split 14 people into 7 pairs?
Variables
Variables
Find
.
Variables
Variables
Show that
is divisible by 7 if and only if
is.
Variables
Variables
Solve the recurrence
,
,
.
Variables
Variables
N boys and N girls are in a dance class. How many ways arethere to pair them all up?
Variables
Variables
Find
, where
is the
th Fibonacci number.
Variables
Variables
Write an integer
in terms of its decimal expansion:
. Prove that
is divisible by 7 if and only if
is.
Variables
Variables
To show: all horses are the same color.If there's one horse, certainly all horses are the same color.If there are
horses, then by the induction hypothesis horses 1 through
are the same color, and horses 2 through
are the same color, but since horse 2 through
are in both sets, they overlap, so all horses are the same color.What, if anything, is wrong with this logic?
Variables
Variables
How many ways are there to choose a team of 3 students from agroup of 30?
Variables
Variables
Find
.
Variables
Variables
Explain why this proves
is true for all
.
Variables
Variables
One student has 6 books and another has 8. In how many wayscan they exchange 3 books of the first student for 3 books of thesecond?
Variables
Variables
Find
. Find
.
Variables
Variables
In the quadratic
, 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
instead? (How will you judge it if some roots are real and some are complex?)d) What happens when Al says "complex" with this polynomial?
Variables
Variables
How many ways can a group of 10 boys be divided into twobasketball teams of 5 boys each?
Variables
Variables
Find
. Find
.
Variables
Variables
Is it possible that
,
, and
all have real roots?
Variables
Variables
Ten points are marked on the plane so that no three of them arein a straight line. How many different triangles can be formedusing these 10 points as vertices?
Variables
Variables
Find
. Find
.
Variables
Variables
The roots of
are
and
, and the roots of
are
and
. All of the coefficients are nonzero. What are the values of
,
,
, and
?
Variables
Variables
A group of soldiers contains 3 officers, 6 sergeants, and 30privates. How many ways can a team be formed consisting of 1 officer,2 sergeants, and 20 privates?
Variables
Variables
Show
Variables
Variables
Compute the sequence
that gives rise to the generating function
, by looking at the product
. If you look at the result, can you think of a different way to compute
?
Variables
Variables
For a quadratic polynomial
, call the roots
and
. Define
and
.Find formulas for
,
,
, and
in terms of the coefficients
,
, and
.
Variables
Variables
Ten points are marked on a straight line and 11 on anotherline, parallel to the first. How many triangles can be formedfrom these points? How many quadrilaterals?
Variables
Variables
First show
Then show that
, so that
Use the fact that
to calculate
to 10 decimal places.
Variables
Variables
Define a recursive sequence by setting
and
for
. \begin{enumerate}[(a)] \item Conjecture a formula for
by experimenting. \item Now put the sequence
into a generating function
and find a formula for
by utilizing the recursive definition of
. \item Expand your formula for
into partial fractions, and use the result to prove your conjectured formula for
. \end{enumerate}
Variables
Variables
For a quadratic polynomial
, call the roots
and
. Define
and
.Prove that for the polynomial
,
is always an integer not divisible by 5.
Variables
Variables
How many ways can you put 10 white and 10 black checkers onthe black squares of a checkerboard?
Variables
Variables
Find
to 4 decimal places in 40 seconds. (Hint 1: recall that1729 is the famous taxicab number that Ramanujan stated was the smallest integer that can be written as a sum of two cubes in two ways;
and
.) (Hint 2:
\hspace{.1in}
Variables
Variables
Define a recursive sequence by setting
and
for
. Find a formula for
.
Variables
Variables
For a quadratic polynomial
, call the roots
and
. Define
and
.Find a formula for
in terms of
and
.
Variables
Variables
How many 10-digit numbers have the sum of their digits equalto 1? The sum equal to 2? To 3? To 4?
Variables
Variables
Show that
can be made larger than any real number by choosing an appropriate
. Then show that when all the terms with denominators that are not prime are removed, the series diverges. In other words the sum of the reciprocals of the prime numbers diverges. On the other hand, show when all the terms that contain the digit nine are deleted, the series converges. In fact, the sum is less than 90.
Variables
Variables
Given that
is a real number satisfying
, compute
.
Variables
Variables
To win the California lottery, you must choose 6 numberscorrectly from a set of 51 numbers. How many ways are there toto make your 6 choices?
Variables
Variables
Note that
. Find the sum of all the unit fractions that have denominators with only factors from the set
. That is, find the following sum:\\
.
Variables
Variables
The \emph{Fibonacci sequence}
is given by the recursion
![]() |
Show that
![]() |
and use this to derive a closed form for
.
Variables
Variables
Find all solutions (real and complex) of
.
Variables
Variables
A person has 10 friends. Over several days he invites someof them to a dinner party in such a way that he never invitesexactly the same group of people. How many days can he keepthis up, assuming that one of the possibilities is to asknobody to dinner?
Variables
Variables
Compute the generating function
for the sequence
given by the recursion
![]() |
If you feel like it, derive a closed form for
.
Variables
Variables
Find all solutions of
,
.
Variables
Variables
There are 7 steps in a flight of stairs (not counting thetop and bottom of the flight). When going down, you can jumpover some steps if you like, perhaps even all 7. In howmany different ways can you go down the stairs?
Variables
Variables
Euler showed that
. Find
.
Variables
Variables
In the following exercise we study the \emph{binomial coefficients}
. \begin{enumerate} \item First assume that
and
are integers such that
. Suppose you didn't know anything about
, except the relations
![]() |
Compute the generating function
![]() |
and use it to find a formula for
. \item Convince yourself that your computation is identical if we allow
to be any complex number and
to be any nonnegative integer. \item Compute the generating function
![]() |
and use it to find a formula for the generating function
. \end{enumerate}
Variables
Variables
For a quadratic polynomial
, call the roots
and
. Define
and
.Express
in terms of
and
. This is a very popular math contest trick!
Variables
Variables
Find the sum of the first
squares by differentiating the generating function
.
Variables
Variables
If the roots of
are the cubes of the roots of
, compute
in terms of
and
.
Variables
Variables
In how many ways can 12 pennies be put in 5 purses? Whatif none of the purses can be empty?
Variables
Variables
Given a sequence
with generating function
, let
![]() |
Find a formula for
. Use this to prove that the Fibonacci numbers satisfy
![]() |
Variables
Variables
For a cubic polynomial
, the roots
,
, and
come in three symmetric combinations:
,
, and
.Express
,
, and
in terms of the coefficients of the polynomial
,
,
, and
.
Variables
Variables
In how many ways can you put k identical things into n boxes,where the boxes are numbered
? What if you must put atleast one thing in each box (so, of course,
)?
Variables
Variables
Let
denote the number of triangulations of an
-gon, so e.g.,
,
,
, etc. We also set
. \begin{enumerate} \item Find a recurrence relation for
. \item Compute the generating function
and use it to find a closed form for
. \end{enumerate}
Variables
Variables
For a cubic polynomial
, the roots
,
, and
come in three symmetric combinations:
,
, and
.The sum of the
powers of the roots is defined as
.Express
in terms of
,
, and
.
Variables
Variables
A bookbinder must bind 12 identical books using red, green,or blue covers. In how many ways can this be done?
Variables
Variables
Given a graph
and a positive integer
, let
be the number of colorings of
that use at most
colors.Compute
for the following four classes:\begin{itemize} \item The \emph{null graph}
consists of
nodes and no edges. \item The \emph{complete graph}
consists of
nodes with all possible edges between them. \item The \emph{line graph}
consists of
nodes with edges that form a line segment. \item The \emph{cycle}
consists of
nodes with edges that form a circle.\end{itemize}What do you notice about\begin{enumerate} \item the leading coefficients? \item the second leading coefficients? \item the constant term? \item the highest degree?\end{enumerate}
Variables
Variables
For a cubic polynomial
, the roots
,
, and
come in three symmetric combinations:
,
, and
.The sum of the
powers of the roots is defined as
.Find
,
, and
for the polynomial
.
Variables
Variables
A train with
passengers must make
stops. How manyways are there for the passengers to get off the train at thestops? What if we only care about the number of passengers gettingoff at each stop?
Variables
Variables
Given a graph
and a positive integer
, let
be the number of colorings of
that use at most
colors.Experiment with the numbers
for different examples of graphs
. Can you guess what they count? (Hint: look at \emph{acyclic orientations} of
, i.e., give each edge a direction, in such a way that you can't see any coherently oriented cycle.) Try to prove your assertion.
Variables
Variables
For a cubic polynomial
, the roots
,
, and
come in three symmetric combinations:
,
, and
.The sum of the
powers of the roots is defined as
.With
,
, and
, find the three roots in terms of
and
.
Variables
Variables
How many ways are there to arrange 5 red, 5 green, and 5 blueballs in a row so that no two blue balls lie next to each other?
Variables
Variables
Are there any magic
squares? Explain.
Variables
Variables
For a cubic polynomial
, the roots
,
, and
come in three symmetric combinations:
,
, and
.The sum of the
powers of the roots is defined as
.First express
in terms of
,
, and
. Then use that answer to factor
. (By the way, this is an important step in one derivation of the cubic formula. First transform to
, then let
and
.)
Variables
Variables
How many ways are there to represent 100000 as the product of3 factors if we consider products that differ in the order of factorsto be different?
Variables
Variables
How many magic
squares are there?
Variables
Variables
For a cubic polynomial
, the roots
,
, and
come in three symmetric combinations:
,
, and
.The sum of the
powers of the roots is defined as
.a) Prove that
.b) Prove that
.c) Generalize to something that starts with
. Generalize further to polynomials of degree
.
Variables
Variables
There are 12 books on a shelf. In how many ways can you choose5 of them so that no two of the chosen books are next to each otheron the shelf?
Variables
Variables
Find a formula for the magic sum of an
square.
Variables
Variables
Compute the sum of the cubes of the roots of
.
Variables
Variables
In how many ways can a necklace be made using 5 identical redbeads and 2 identical blue beads?
Variables
Variables
We define a \emph{(weak) magic square} to be a square matrix whose entries are nonnegative integers and whose rows, columns, and main diagonals sum to the same number.Let
be a magic
square.\begin{enumerate}[(a)]\item Show that the center term
is the average over all
.\item Show that there are no magic
squares with line sum
, if
is not a multiple of~3.\end{enumerate}
Variables
Variables
Compute the sum of the
powers of the roots of
.
Variables
Variables
How many 6-letter ``words'' contain at least one letter ``A''(if any sequence of letters counts as a word)?
Variables
Variables
Show that, if
has no common factor with 10 other than
(we say that
and 10 are \emph{relatively prime}), then
. Can you see where the exponent 4 comes from? Come up with a similar equation for a general modulus
and think about how you could prove that equation.
Variables
Variables
In general, the key to polynomial division is to recognize that dividing
by
lets you write
, where
is the quotient and
is the remainder. Plugging in clever values of
is almost always a good idea.a) Find the remainder when
is divided by
.b) Find the remainder when
is divided by
.c) Find the remainder when
is divided by
.
Variables
Variables
Given 6 vertices of a regular hexagon, in how many ways canyou draw a path that hits all the vertices exactly once?
Variables
Variables
The code we'll describe in this exercise is due to Diffie and Hellman. It is a \emph{public-key code} because part of the code is known to everyone. Here's how it works: you and your friend choose a prime number
and an integer
between 2 and
. 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
, and your friend \emph{secretely} chooses an integer
. You compute
and tell your friend the result. Your friend computs
and tells you the result. The secret key that you both can use is
![]() |
The last two equalities explain why both you and your friend can easily compute
.You can now use
to encode messages, e.g., using multiplication mod
, and
to decode.Can you see why it's hard to compute
if you know
,
,
, and
? How could you make this cryptosystem safer? Do you see a way to ``break" it?
Variables
Variables
In general, the key to polynomial division is to recognize that dividing
by
lets you write
, where
is the quotient and
is the remainder. Plugging in clever values of
is almost always a good idea.Find the remainder when
is divided by
.
Variables
Variables
Within a table of
rows and
columns a box is marked atthe intersection of the
row and
column.How many of the rectangles formed by the boxes of the tablecontain the marked box?
Variables
Variables
Here's \emph{Euler's
-function}:
counts the numbers between 1 and
that are relatively prime to
.Compute the first couple of values of this function:
Find a formula for
when
is prime. Find a formula for
in terms of
and
in the case that
and
are relatively prime.One of Euler's theorem says that, if
is relatively prime to
, then
.Conclude that, if
, then
.
Variables
Variables
A
cube is formed of small unit cubes.A grasshopper sits in the center
of one of the corner cubes. Ata given moment, it can jump to the center of any of the cubeswhich has a common face with the cube where it sits, as long as thejump increases the distance between point
and the currentposition of the grasshopper. How many ways are there for thegrasshopper to reach the unit cube at the opposite corner?
Variables
Variables
This exercise is about the RSA cryptosystem, named after its discoverers Ron Rivest, Adi Shamir, and Leonard Adleman.Here's how it works: You need two prime numbers
and
, compute their product
, find a number
that is relatively prime to
, and compute an inverse
of
modulo
, i.e.,
.You keep all of this private except for the numbers
and
which you make public (in particular, your friends know
and
). To send you a message
, your friend encodes it as
![]() |
You can decode your friend's message by computing
![]() |
Explain why this decoding works.What makes this cryptosystem safe? How could you make it safer? What would one need to break it?
Variables
Variables
Find the number of integers from 0 to 999999 that have no twoequal neighboring digits in their decimal representation.
Variables
Variables
A \emph{Sudoku square} is a
grid filled with nine symbols (such as the numbers from 1 to 9) in such a way that each row, column, and the nine
subsquares (shown above) contain each symbol exactly once. In a \emph{Sudoku puzzle}, the square contains some entries (called \emph{clues}), and the goal is to complete the Sudoku square. In the classical setting, the clues are chosen such that there is only one way to complete each square. You may try your luck with the two Sudoku puzzles above (caveat: If you've never played a Sudoku puzzle, watch out---these squares are addictive).We will work on two problems regarding Sudoku squares:\begin{enumerate}[(1)]\item How many Sudoku squares are there?\item What is the minimum number of clues that yield a unique solution to a Sudoku puzzle?\end{enumerate}These are hard questions. In fact, (1) was answered only in 2005 (the number of Sudoku squares is
), and (2) remains open (it is conjectured that the minimum number is 17). So we will simplify the problems and work with
Sudoku squares. Experiment with questions (1) and (2) in the
case.
Variables
Variables
How many ways are there to divide a deck of 52 cards into twohalves such that each half contains exactly 2 aces?
Variables
Variables
How many ways are there to place four black, four white, and fourblue balls into six different boxes?
Variables
Variables
In Lotto, 6 numbers are chosen from the set
. In how many ways can this be done such that the chosen subsethas at least one pair of neighbors?
Variables
Variables
Find the sum
. Hint: thesum can be interpreted as the number of ways to choose a committeof at least one that includes a president,vice-president, and treasurer (not necessarily distinct persons) froma set of
people.
Variables
Variables
Given a set of
objects, assume that
areindistinguishable, and the other
are distinct. Show thatwe can choose
objects from this set in
ways.
Variables
Variables
In how many ways can you take an odd number of objects froma set of
objects?
Variables
Variables
persons sit around a circular table. How many of the
arrangements are distinct, i.e., do not have the same neighboringrelations?
Variables
Variables
points are chosen on a circle. In how many ways canyou connect them all in pairs such that none of the segmentsoverlap?
Variables
Variables
In how many ways can you triangulate a convex
-gon usingonly the original vertices?
Variables
Variables
If you have a set of
pairs of parentheses, how many wayscan you arrange them ``sensibly''. For example, if you have3 pairs, the following 5 arrangements are possible:((())), (())(), ()(()), (()()), ()()().
Variables
Variables
Can you arrange the numbers
along a circlesuch that the sum of two neighbors is never divisible by 3, 5, or7?
Variables
Variables
In how many ways can you choose two distinct subsets from acollection of
items? The two subsets together need notinclude all
items.
Variables
Variables
In how many ways can you choose two distinct subsets from acollection of
items? The two subsets together need notinclude all
items.
Variables
Variables
How many subsets of the set
contain notwo successive numbers?
Variables
Variables
How many ways are there to put seven white and two black billiardballs into nine pockets? Some of the pockets may be empty andthe pockets are considered distinguishable.
Variables
Variables
Consider a circular set of
seats, with a different childsitting in each. How many ways can you rearrange the childrenso that no child moves more than one seat to the right or theleft of his/her original position?
Variables
Variables
Can you find a polyhedron with an odd number of faces, where eachface has an odd number of edges?
Variables
Variables
Can you partition the set of positive integers into infinitelymany infinite subsets such that each subset is generated fromany other by adding the same positive integer to each elementof the subset?
Variables
Variables
Consider all
nonempty subsets of the set
.For every such subset, we find the product of the reciprocals of eachof its elements. Find the sum of all these products. (For example,if the set consists of
, the subsets are
,
,
,
,
,
, and
.The products of the reciprocals are 1, 1/2, 1/3, 1/2, 1/3, 1/6, and1/6, respectively. The sum of all of them is 3.
Variables
Variables
How many ways are there to group 4 pieces of luggage? 5 pieces?(Here are the groupings of 3 pieces,
,
, and
:
,
,
,
,
. The vertical barsrepresent divisions into groups.)
Variables
Variables
Find the number of poker hands of each type. For thepurposes of this problem, a poker hand consists of 5 cards chosenfrom a standard pack of 52 (no jokers). Also for the purposes ofthis problem, the ace can only be a high card. In other words, thecard sequence
,
,
,
,
is not a straight, since the ace isa high card only.\par\vskip .2inHere are the definitions of the hands:\vskip .1in{\bf Royal flush:}
through
in the same suit.\par\hskip .3in Example:
,
,
,
,
.\par{\bf Straight flush:} 5 cards in sequence in the same suit, but nota Royal flush.\par\hskip .3in Example:
,
,
,
,
.\par{\bf Four of a kind:} Four cards of the same rank.\par\hskip .3in Example:
,
,
,
,
.\par{\bf Full house:} Three cards of one rank and two of another.\par\hskip .3in Example:
,
,
,
,
.\par{\bf Flush:} Five cards in the same suit that are not in sequence.\par\hskip .3in Example:
,
,
,
,
.\par{\bf Straight:} Five cards in sequence that are not all in thesame suit.\par\hskip .3in Example:
,
,
,
,
.\par{\bf Three of a kind:} Three cards of the same rank; the others ofdifferent rank.\par\hskip .3in Example:
,
,
,
,
.\par{\bf Two pairs:} Two pairs of cards.\par\hskip .3in Example:
,
,
,
,
.\par{\bf Pair:} A single pair of cards.\par\hskip .3in Example:
,
,
,
,
.\par{\bf Bust:} A hand with none of the above.\par\hskip .3in Example:
,
,
,
,
.
Variables
Variables
If you write out all the numbers from
to
how manyzeroes will you need to use?
Variables
Variables
Let
and
be integers. If
is a circle of radius
and
is a circle of radius
, and if
, and
,are tangent to each other and both are tangent to the same line,find the radius of the circle tangent to both
and
andto the line that lies in the area enclosed by them.
Variables
Variables
How many internal three-dimensional diagonals are there in aregular dodecahedron? (A regular dodecahedron is a polyhedronwith 12 identical faces, each of which is a regular pentagon. Adiagonal connects a vertex with another vertex, but other than thevertices, lies entirely within the solid.)
Variables
Variables
A pool table is
feet wide and
feet long, and isarranged in a coordinate system where
unit is
foot so thatone corner is at
and the
-foot side lies along the
-axis. If you strike a ball initially placed at
sothat its first bounce is against the wall at
, in how manyplaces can you hit that wall so that the ball goes into the pocketat
after exactly
total bounces against the walls
and
? It doesn't matter how many times the ballbounces against the walls at
and
. Assume the ballalways bounces so that it's angle of incidence is equal to it'sangle of reflection.
Variables
Variables
A "flower" pattern is made as follows. A regular hexagon isinscribed in a circle of radius
. A circle is drawn with eachof the edges of the hexagon as diameter. The flower consists ofeverything inside the original circle or inside any of the sixsmaller circles. What is the area of the flower?
Variables
Variables
Three mutually tangent circles of radius one are surroundedby a larger circle that is simultaneously tangent to all three.What is the radius of the larger circle?
Variables
Variables
Show that
![]() |
Variables
Variables
Show that
![]() |
Variables
Variables
Show that
![]() |
Variables
Variables
Show that
![]() |
Variables
Variables
Find a nice formula for the sum:
![]() |
Variables
Variables
Show that if
and
then:
![]() |
Variables
Variables
Show that
![]() |
Variables
Variables
Show that
.
Variables
Variables
Prove that for any
:
![]() |
Variables
Variables
Show that if
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
regions.
Variables
Variables
``Sums and Cubes I.'' Find three integers satisfying
and
. Now find a second solution. Next define a \textit{beastly number} as a positive integer which is equal to the sum of its digits plus the sum of the cubes of its digits. Demonstrate that 152 is not beastly. \\ There are precisely six beastly numbers, find as many as you can.
Variables
Variables
warm-up, excercise
Variables
Variables
``Sums and Cubes II.'' The formula for the sum of the first
cubes is:
![]() |
Find a proof by picture of this fact.
Variables
Variables
``Sums and Cubes III.'' The following gem is due to Ross Honsberger. \\ The first
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
, preferably not prime. Then list all the positive divisors of this number, including 1 and
. 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,
.
Variables
Variables
warm-up, excercise
Variables
Variables
``Efron's Dice.'' Present the following four dice having the numbers listed below on their faces.\medskip\centerline{\textbf{A:} \ 0, 0, 4, 4, 4, 4 \hspace{2cm} \textbf{B:} \ 3, 3, 3, 3, 3, 3}\centerline{\textbf{C:} \ 2, 2, 2, 2, 6, 6 \hspace{2cm} \textbf{D:} \ 1, 1, 1, 5, 5, 5}\medskip\noindent Then imagine a game in which two players each pick a die and roll it once, the winner being the person with the higher number. Compute the probability of winning in the games A vs B, B vs C, C vs D, and D vs A.
Variables
Variables
``Points of Intersection'' The goal is to position a prescribed number of lines in the (Euclidean) plane to obtain exactly 100 points of intersection. Begin with 100 lines, then try 29 lines, 21 lines, 19 lines, and finally 15 lines.
Variables
Variables
``A Ladder Locus'' A ladder, originally upright against a vertical wall, slides downward and outward, always in contact with the wall, until it crashes to the ground. What figure is traced out by a hapless painter positioned midway up the ladder?
Variables
Variables
``Mix and Match'' Draw a closed ray and an open ray, such as the sets of points
with
and
for
. Which object contains more points?\\ Challenge: find an explicit bijection between the two sets.
Variables
Variables
``Beguiling Tilings I'' Tile all of space with non-degenerate circles.
Variables
Variables
The arbelos consists of three points
and
which are collinear, together with the semicircles
,
and
as shown in Figure 1. In the figure
has been added to the figure tangent to the two small semicircles.
intersects a small semicircle at
and
intersects the other small semicircle at
.
intersects
at
. Prove the area of the arbelos is equal to the area of the circle with diameter
,
and
bisect each other, and
is tangent to the small semicircles.
Variables
Variables
Suppose we take a 8 x 8 chessboard and cut off two opposite corners. We have some rectangular 2 x 1 dominoes, each of which can cover exactly two adjacent squares. Can we tile the chessboard with these dominoes?
Variables
Variables
On a 5 x 5 grid, we begin with some squares with X's in them and the rest of the squares blank. If any empty square is surrounded on at least 2 sides by squares with X's in them then we draw an X in this empty square as well. We repeat this until every square either has an X in it or shares at most one edge with such a square. \\Show that if we start with a grid with less than five X's in it, then when we finish this process, some squares will still be blank.
Variables
Variables
Show that if five points lie on the surface of a sphere, then there is some hemisphere containing four of them.
Variables
Variables
What is the maximum number of bishops one can place on a 8x8 chessboard such that no bishop can capture any other?
Variables
Variables
Suppose we have a balance (i.e. a scale with two arms, which can only tell us whether the items place on one arm weigh less than or more than the items place on the other arm). We are given 9 coins, one of which is counterfeit and weighs more than its real counterparts. Using only two weighings, is it possible to determine which of the 9 coins is counterfeit? Suppose instead we start with 10 coins; is it now possible to determine which is counterfeit in only two weighings?
Variables
Variables
Suppose we have two drinking glasses, one of which holds 21 oz. and one which holds 13 oz. Is it possible to measure exactly 1 oz. of water using only these two cups? What if our two cups are 8 oz. and 10 oz.?
Variables
Variables
Suppose we begin with a knight sitting at (1,0,0) in three-dimensional space. A \textit{three-dimensional knight jump} is a move where a piece goes
along one axis (i.e. in the
,
, or
-directions),
along a second axis, and
along the remaining axis. For example, our knight at (1,0,0) could make a three-dimensional knight jump to (1,0,0) +(2,-1,3) = (3,-1,3), or perhaps to (1,0,0) + (-1,-3,-2) = (0,-3,-2). Show that it is not possible for our knight to reach (0,0,0) by making a finite number of three-dimensional knight jumps.
Variables
Variables
Assume that any simple (but not necessarily convex)
-gon (where
) has at least one diagonal that lies completely within the
-gon. Show that any
-gon can be subdivided into exactly
triangles so that every triangle vertex is one of the original vertices of the
-gon.
Variables
Variables
Prove by induction the formula for the sum of a geometric series:
![]() |
Variables
Variables
Show that:
| < |
![\[ f_0 = 0 , \ f_1 = 1 , \ f_{ n+2 } = f_{ n+1 } + f_n \ \text{ for } n \ge 0 \, . \]](/files/tex/2b978540745c4a821e1590707f786cab0964b32a.png)
![\[ F(x) := \sum_{ n \ge 0 } f_n \, x^n = \frac{ x }{ 1 - x - x^2 } \]](/files/tex/8aa4f08bcdd73337832cdf7fb3bba1a34600a564.png)
![\[ g_0 = g_{34} = 0 , \ g_{ n+2 } = g_{ n+1 } + g_n \ \text{ for } n \ge 0 \, . \]](/files/tex/65194859cff98b7fe7c32a648d82273631ba7f5a.png)
![\[ \binom n k = \binom{ n-1 }{ k-1 } + \binom{ n-1 }{ k } \qquad \text{ and } \qquad \binom n 0 = 1 \, . \]](/files/tex/61aba397ce6d4335841f71a10fd5877d804d0789.png)
![\[ B_n(x) := \sum_{ k \ge 0 } \binom n k x^k \]](/files/tex/b7793cfc37aa90703c1e6b954c04341b9dc7cb3b.png)
![\[ B(x) := \sum_{ n \ge 0 } \sum_{ k \ge 0 } \binom n k x^k y^n \]](/files/tex/2d0edd2bd2864532aa2783121ed2ee2d3f3f7c61.png)
![\[ B(x) = \sum_{ n \ge 0 } b_n \, x^n = \frac{ A(x) }{ 1-x } \, . \]](/files/tex/5585b741ff024e6af8cdb1d521bad6dffe14d8d6.png)
![\[ f_0 + f_1 + \dots + f_n = f_{ n+2 } - 1 \, . \]](/files/tex/518715143a78563e7d9508c0cc29f5e08af57b0e.png)
![\[ s \equiv g^{ mn } \equiv \left( g^m \right)^n \equiv \left( g^n \right)^m \bmod p \, .\]](/files/tex/c95bf0d49d108fb9e9fd45a791e6be350ded95ca.png)
![\[ e = d^b \bmod m \, .\]](/files/tex/cc9ae0c076e489403d3b69d1fefcf36b6f8628f3.png)
![\[ d = e^c \bmod m \, .\]](/files/tex/db0ecd81d9496c4c00de3ba623cd8d49d421384f.png)
![\[ \sum_{k=0}^n (-1)^k{n \choose k} = 0.\]](/files/tex/afc58417009b9ac5e7f58de1b462a7cc98dbb08e.png)
![\[ {r \choose m}{m \choose k} = {r \choose k} {r-k \choose m-k}. \]](/files/tex/2d913a735b0000debad911c90b165e7a3558a6f1.png)
![\[ \sum_{k=0}^n {k \choose m} = {n+1 \choose m+1}. \]](/files/tex/1c0cc6b062911b64b78e3a476d6a67aad1680840.png)
![\[ \sum_{r=1}^n r{n \choose r} = n2^{n-1}. \]](/files/tex/b8ef4f0ea8c4278ac31a659d3823fdc8a685bb2e.png)
![\[ {n \choose 0}^2 + {n \choose 1}^2 + {n \choose 2}^2 + \cdots + {n \choose n}^2. \]](/files/tex/770a7d506123e609cb9bb3bd0d96fa27637fdf4a.png)
![\[\sum_{j=0}^k {n \choose j}{m \choose k-j} = {n+m \choose k}. \]](/files/tex/4c5b5486613c7874a25e5b13a8fdfdd01c2f32fa.png)
![\[ \sum_{k=0}^n {r+k \choose k} = {r+n+1 \choose n}.\]](/files/tex/5f7473b2b56f2511e140c2b65b7096615e4cbabe.png)
![\[1^2 + 4^2 + 7^2 + 10^2 + \cdots+ (3n-2)^2 = n(6n^2 - 3n - 1)/2. \]](/files/tex/030695bf5c56d83521f5ff6aa17f443b8b30b523.png)
![\[ 1^3+2^3+3^3+\cdots+n^3 = (1+2+3+\cdots+n)^2. \]](/files/tex/9da7c07c3d5b6afd68c4f7a9c2637f2ae0bdd4c2.png)
![\[ a + ar + ar^2 + \cdots + ar^{n-1} =a\frac{r^n-1}{r-1}. \]](/files/tex/7d38930674517edcbf789e61fce374c83a431578.png)