# Research Problems

Here is a collection of research problems. Feel free to ponder upon these - perhaps
even write some computer programs, develop pictures, create tables, identify patterns.
Feel free to make conjectures. And then ... try to find proofs to your claims.
E-mail Jim Tanton jamestanton@stmarksschool.org)
to share your thoughts. Have fun!
If you want more puzzles to think about try clicking here. These are our "problems of the week" from the Sunday classes.

ORDERING DILEMMA **
Warm-Up:** Can
you write the numbers 1 through 10 in the boxes below in a way that respects
the inequalities shown? Is there more than one way to do it?

**Challenge:**Prove that problems like these can always be solved, that is, given

*N*boxes with pre-set inequalities between them, there is always at least one way to arrange the numbers 1 through

*N*respecting those inequalities.

**Is it possible to predict how many solutions such a problem will possess? For example, we can be sure that:**

RESEARCH:

RESEARCH:

has only one solution (1 < 2 < 3), and it is possible to deduce, without necessarily listing them, that the following problem has three solutions:

(“1” must be placed in the second to last position, and placement of any one of the remaining three numbers in the ultimate position to determines a solution.) How many different solutions are there for the warm-up problem? How does the arrangement of inequalities determine the number of solutions?

**SURVIVOR**

Co-invented with Charles Adler.**
Warm-Up:** N people, numbered 1 through N, are stranded on an island and play the following variation of the TV game

*Survivor*.Members of the group vote whether person N should survive or be escorted off the island. If 50% or more of the people agree to this person’s survival then the game ends here and the N people all take an equal share of a $10,000,000 cash prize. If, on the other hand, the N-th person is voted off the island, the remaining (N-1) people will take a second vote to determine the survival of the (N-1)th player (again with a quota of 50%). They do this down the line until a vote eventually passes and a person survives. The cash prize is then shared equally among all the folks remaining after the successful vote.Assume that all players are greedy, but rational, thinkers; that they will always vote for their own survival, for example, and will vote for the demise of another player provided it does not lead to their own demise as a consequence. The question here is simple: who survives?

**Think through a game with just two or three players. Build up to a game with four, five, or six players. How about one with eight players, or ten players? Any patterns?**

Hint:

Hint:

**Variation:**How do the results of the game change if players must attain

*strictly more*than 50% of the votes in order to survive?

**OPEN PROBLEM: **

Let q, for “quota,” be a fraction between 0 and 1. Associated to q are two possible survivor games: one that requires a player to attain q% or more of the votes in order to survive, and another that requires strictly more than q%. Both games yield a sequence of “survivor numbers.”For example, in the warm-up puzzle, with q = 50%, games played with 1, 2, 4, 8, 16, 32, … players yield groups that survive. In the variation, groups with 1, 3, 7, 15, 31, … players survive. [Solve the puzzles to see what I mean by this.]Is there a fraction q for which both games yield the same survivor sequence?(Note: If q is irrational, then the two games are identical. Can you see why?)

**For the mathematically inclined: **

One can show that the survivor sequence for the warm-up
puzzle is given by and , and for the
variation and , where is the
value *x* rounded up to the nearest integer (unless *x* is already
an integer) and is the same,
but set equal to *x*+1 if *x* is an integer. The two sequences differ
the first time is an integer.
The open problem can thus be presented:

*
Let R be a rational greater than 1, and consider the sequence:*

* *

*
Must one of the terms of this sequence be an integer?*

(Here we are thinking .)

**For Fun: ** Prove,
in either version of the game, that two different values of q cannot produce
identical “survivor sequences.”

**CANDY SHARING**

N students sit
in a circle and *k* pieces of candy are distributed among them. At the
blow of whistle, any student possessing two or more pieces of candy gives two
pieces of candy away: one to his or her left neighbour and one to his or her
right neighbour. All “abundant” players do this simultaneously. (Note: A student
may be receiving candy as he or she gives candy away.)

Students then regroup their candy piles and the game is played again at the next blow of the whistle. Students keep playing this game until no-one possesses two or more pieces of candy.

**Warm-Up: **

a) Prove that
the game will never stop if *k *> N.

b) A game with k = N pieces of candy might, or might not terminate. Devise an initial distribution of five pieces of candy among five players that leads to a terminating game. Devise a distribution that does not.

c) Will the following game ever terminate?

(**Hint**:
Colour the students’ seats alternately red and green. What do you notice about
the amount of candy possessed in total by the red players as the game is played?)

**HARD CHALLENGE:
**Suppose *k* < N, that is, there is less candy than players. Must
such a game terminate?

**OPEN PROBLEM
1:**

Suppose *k*
= N. Classify all initial distributions of candy that lead to terminating games.

**HARD CHALLENGE
2:**

It turns out,
as you would intuitively expect, that if *k* < N, then the game must
terminate. Now rather than have players pass candy simultaneously, let them
pass candy whenever they feel like it, in whatever order – sequentially, or
simultaneously in parts.

Is the final distribution of candy independent of the order in which students perform the sharing?

**OPEN PROBLEM 2:**

Although the
*k* > N case seems uninteresting, one can still examine the pattern
of candy distributions as the game is played forever. As there are only a finite
number of possible distributions, the patterns must start repeating in some
periodic fashion.

Glenn Iba, of Lexington Massachusetts, wrote a computer program to watch candy games. He observed:

*k *< N: Game halts.

*k *= N:
Game halts, or follows a cycle of candy distributions of a period
dividing N.

N< *k <*2N: The game falls into a cycle of period 2.

*k* = 2N: The game falls into a cycle of period dividing N.

*k *> 2N: The game falls into a steady state: period 1.

Can you verify these observations? Better yet, can you prove any of his claims?

**OPEN PROBLEM
3: **

A finite number of pennies are placed on the cells of an infinite square grid. Any cell possessing four or more pennies “diffuses” four pennies away: one to each neighbour north, south, east and west. Can anything be said about the diffusion patterns that appear? Is it possible to create some nice

computer pictures? Do different diffusion rules lead to different pictures (diffuse eight pennies – diagonal neighbours as well, “lopsided” diffusion: two north, rest one each, etc.)

If pennies are placed in a cluster of “radius” d, can anything be said how far out the distribution will diffuse?

**BASE ONE AND A HALF**

*This problem
was presented by James Propp in a recent Sunday morning Math Circle talk.*

A “machine” consists of a row of boxes extending infinitely to the left. One places in this machine a finite number of pennies in the right-most box. The machine then redistributes the pennies according to a preset rule.

A “ ” machine replaces pairs of pennies in one box, with a single penny in the box one place to the left.

For example, placing six pennies into the machine “fires” four times to yield a final distribution that can be read as “1 1 0.” This, of course, is the machine that converts numbers to their binary representations.

A machine yields ternary representations, a machine the ordinary base 10 representations, and so on.

**Warm-Up: **Show
that these machines terminate with the same final distributions of pennies no
matter in which order the “fires” are performed. (Note, this result is obvious
when thought of in terms of base representations of numbers. Is it “obvious”
in terms of the mechanics of the machine?)

**OPEN PROBLEM:**

Consider a machine.
This replaces three pennies in one box with *two* pennies in the box one
place to the left. In some sense, this is a “base one and a half machine.”

Here is a list of some representations of numbers in this machine.

0 = 0

1 = 1

2 = 2

3 = 2 0

4 = 2 1

5 = 2 2

6 = 2 1 0

7 = 2 1 1

8 = 2 1 2

9 = 2 1 0 0

10 = 2 1 0 1

20 = 2 1 2 0 2

50 = 2 1 2 0 2 2 2

100 = 2 1 2 0 0 1 2 0 1

500 = 2 1 2 0 0 1 0 1 0 2 1 2 2

Notice, for example, that .

**Question: **James
Propp asks: How many representations have *N* digits?

For example, there are three numbers with one-digit representations (0,1,2), three two-digit representations (20, 21, 22), three three-digit representations (210, 211, 212), six four-digit representations, and so on. This gives the sequence:

3, 3, 3, 6, 9, 12, 18, 27, 42, 63, 93, 141, 210, 315, …

What’s the N-th number in this sequence?

PARTITIONS GALORE

**Warm-Up:**
There are four ways to partition the number “3” if order matters:

“3” = 3, 1+2, 2+1, 1+1+1.

Let P(n) equal the number of ordered partitions of n. Find a general formula for P(n).

**Harder Warm-Up:**

Let be the number of ordered partitions of n if the number “1” can be coloured one of two colours, red or blue say. (All other digits can be written only in black.)

For example,

“3” = 3, 1(red) + 2, 1(blue) + 2, 2 + 1(red), 2 + 1(blue),

1(red) + 1(red) + 1(red), 1(red) + 1(red) + 1(blue), etc.

Show that the sequence given by is every second Fibonacci number.

**RESEARCH****:**

Let be the
number of ordered partitions of *n* where with “1” being of any one of
*k* colours. Is there a formula for ?

Arrange the values into a triangle. Any patterns?

Dare to go to higher dimensions? What if both 1’s and 2’s can be different colours? 1’s, 2’s and 3’s?

__Comment: __One
can think of this problem another way: In how many different ways can one tile
a 1 x n board with tiles of any length, where the tiles of length i can come
in one of c(i) different colours?

**CUP TURNING**

*This appears
in *SOLVE THIS: Mathematical Activities for Students and Clubs.**

**Warm-Up: **Forty-five
plastic cups are placed upright on a table top. Turning over six at a time (no
more, no less) can you flip all the cups upside down? (Note: You might have
to invert the same cups multiple times in order to accomplish this feat.)

**RESEARCH:**

One wishes to
invert *a * cups turning *b* over at a time. Classify those pairs

(*a, b*)
for which the task is possible.

**LAYERED TILINGS**

**Warm-Up:**
A region from a checker-board is said to be *double tiled* by dominoes
if it is completely covered with dominoes in such a way that every cell of the
region has two dominoes covering it, and no domino extends beyond the region
under consideration. (We are assuming each domino covers precisely two neighbouring
cells.)

For example, the following picture is a double tiling of a 2 x 3 rectangular region.

Of course this region can also be tiled with a single layer of dominos.

Prove that any region of the checkerboard that is “double tilable” with dominos is necessarily “single tilable” as well.

(**Hint: **Look
at the “loops” formed by chains of layered dominos.)

**HARD CHALLENGE:**
A “k-tiling” of a region is a tiling with dominos such that each cell of the
region is covered by precisely k dominos.

Prove that any region that is “k-tilable” is also single tilable.

(**Note: **I
am being loose with my language. Hopefully what I write here is enough to convey
the nature of the problem.)

**OPEN PROBLEM:**

The domino has the property that the set of k-tilable regions is the same as the set of single-tilable regions. However, not all tile shapes has this property. For example, the bent tromino triple tiles a 2x2 square, which is not itself single tilable with bent trominos.

It is not difficult to prove that the square tetromino, like the domino, has the “layer redundant” property: Any region that can be k-layered tiled with square tetrominos, for some number k, can in fact be single-tiled.

Classify all polyominoes that, like the domino, have this layer-redundant property.

**ODD NEIGHBOURHOODS**

*This results
to the warm-up and challenge problems appear in Leslie Shader's articler in
"The Mathemagician and the Pied Piper." Ed. E. Berlekamb and T. Rodgers, A.K.
Peters, 1999.*

**Warm-Up: **Fill
the sixteen entries of a 4x4 grid with integers so that the entries in any “neighbourhood,”
that is, a cell and its at most four neighbours (north, south, east and west),
sum to an odd total. (Notice, for example, that the corner squares have only
two neighbours.)

**HARD CHALLENGE
1:**

By a “neighbourhood” of a vertex in a graph we mean the set consisting of that vertex and those vertices connected to it by an edge.

Prove that the vertices of any graph with no loops nor multiple edges can be labeled 0 or 1 in such a way that every neighbourhood contains an odd number of 1’s.

**HARD CHALLENGE
2:**

Let G be a graph with vertices arbitrarily labeled 0 and 1. Show that the addition of just one more appropriately labeled vertex (and set of edges to it) is enough to produce a graph with every neighbourhood odd.

**RESEARCH****:**

Develop a theory related to these two challenges about labeling the vertices of finite graphs either 0, 1, 2, ... (n-1), so that the entries in any neighbourhood add to 1 mod n, (or 2 mod n, etc.)

**SAILORS, COCONUTS,
and MONKEYS**

*The following
variations of a classic puzzle are due to David **C.P. LaFrance-Linden:*

Three sailors gather coconuts to be divided in the morning. During the night, one dishonest sailor, wakes up and divides the coconuts into three equal piles. There is one left over which he gives to a monkey looking on nearby. He hides a pile for himself, recombines the other two piles and goes back to bed.

Later, the second sailor does the same thing: divides the pile he sees into three, gives an extra coconut to the monkey, hides a share and recombines the other two piles.

And later still, the third sailor does it too, also finding the need to give an extra coconut to the monkey.

In the morning, they divide the pile into three. Again, there is one left over which they give to the monkey.

What is the least number of coconuts that was in the pile originally? What are all possible answers for the number of coconuts that could possibly work?

**RESEARCH:
**

Suppose there are N sailors, waking up each in turn during the night, dividing the pile into N equal parts giving excess coconuts to the monkey, and stashing away a share. Suppose the k-th sailor gives coconuts away and in the morning another coconuts are given to the monkey.

The problem above deals with three sailors with =1 for all k. David LaFrance-Linden of Boston Massachusetts, suggests that for N sailors, again =1 for all k, the minimum number of coconuts possible in the problem is given by: . Is he correct?

Suppose = k (that is, the k-th sailor gives away k coconuts, and N+1 coconuts are discarded in the morning.) David suggests the minimum number of coconuts possible is: . Again, is this correct?

Explore other possible sequences and closed form expressions for the minimum number of coconuts possible. (e.g. = , or =1 for all k except , or consider a “characteristic sequence” with equal to zero for all but one k. Do these sequences lead to a “basis of solutions”?) There are many interesting patterns to be discovered. (Let a_k = k^n, for n = 0, 1, 2, 3, ... for example.)

Given a infinite sequence , let C(n) be the number of coconuts for puzzle involving n sailors and the first (n+1) terms of the sequence. Can anything be said about the ratio as n becomes large? Is it related

to ?

**OTHER PROBLEMS**

From **SOLVE
THIS: Mathematical Activities for Students and Clubs** (www.maa.org) there
is still the famous "I can't tell which way the bicycle went" puzzle as well
as "Langton's Ant on Complete Graphs" (ball throwing) and many others. I will
write out these puzzles here too as soon as I get the chance.

Also, I have a puzzle about permutations and Fibonacci numbers which I am keeping secret for now. Math Circle students with me this semester will learn all about these tricky numbers and some of their surprising appearances.