%  Spring break puzzles
%  21-110: Problem Solving in Recreational Mathematics, spring 2010
%  Wednesday, March 3, 2010
%  Brian Kell <bkell@cmu.edu>

\pdfpagewidth=8.5truein \pdfpageheight=11truein
\hsize=6truein \vsize=9truein
\pdfhorigin=1.25truein \pdfvorigin=1truein

% MetaPost stuff
\input supp-pdf
\def\fig#1{\convertMPtoPDF{#1}{1}{1}}
\def\midfig#1{{%
	\setbox0=\hbox{\fig{#1}}%
	\dimen0=0.5\ht0%
	\advance\dimen0 by-0.3\ht\strutbox
	\lower\dimen0\box0%
}}

\font\titlefont=cmbx12
\font\smfont=cmr8

\headline={\hfil}
\footline={\hfil}
\topskip=20pt plus2pt

\newcount\pno  \pno=0
\def\problem{\goodbreak\advance\pno by1 \noindent{\bf Problem~\the\pno.} }
\def\problemno#1. {\goodbreak\noindent{\bf Problem~\hbox{#1}.} }
\def\noskiphint#1\par{\nobreak{\hyphenpenalty=10000\noindent{\it Hint:\/}\enspace#1\par}}
\def\hint#1\par{\nobreak\medskip\noskiphint#1\par}
\def\itemhint#1\par{\nobreak\smallskip\item{}{\it Hint:\/}\enspace#1\par}
\def\solution{\nobreak\medskip\noindent{\bf Solution.} }
\def\part#1{\goodbreak\medskip\indent\llap{#1\enspace}\ignorespaces}
\def\firstpart#1{\nobreak\medskip\indent\llap{#1\enspace}\ignorespaces}

% Pilfered from an example on page 106 of the TeXbook
\def\qed{{\unskip\nobreak\hfil\penalty50
	\hskip1em\hbox{}\nobreak\hfil\hbox{\vrule\vbox to6pt{\hrule\hbox to5.2pt{\hss}\vfil\hrule}\vrule}
	\parfillskip=0pt \finalhyphendemerits=0 \par}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\centerline{\titlefont 21-110: Problem Solving in Recreational Mathematics}
\smallskip
\centerline{\bf Spring break puzzles}
\smallskip
\centerline{Wednesday, March~3, 2010}

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (``Threaded Pins,'' {\it Thinking Mathematically}, page~52.)

\medbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (``Leapfrogs,'' {\it Thinking Mathematically}, page~57.)

\medbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (``Cartesian Chase,'' {\it Thinking Mathematically}, page~162.)\enspace
This is a game for two players on a rectangular grid with a fixed number of
rows and columns. Play begins in the bottom left-hand square where the first
player puts his mark. On his turn a player may put his mark into a square

\nobreak\smallskip

\item{} directly above
\item{} or directly to the right of
\item{} or diagonally above and to the right of

\nobreak\smallskip

\noindent the last mark made by his opponent. Play continues in this fashion,
and the winner is the player who gets their mark in the upper right-hand corner
first. Find a way of winning which your great aunt Maud could understand and
use.

\medbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (``Thirty-one,'' {\it Thinking Mathematically}, page~197.)\enspace
Two players alternately name a number from 1,~2, 3, 4,~5. The first player to
bring the combined total of all the numbers announced to thirty-one wins. What
is the best number to announce if you go first?

\medbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem You have an $n\times n$ chessboard and a marker. You begin by marking
an~X through some of the squares of the chessboard. Next, you mark an~X through
all of the squares which share at least two sides with squares already
containing an~X. You continue marking an~X through such squares until there are
no more unmarked squares that share at least two sides with marked squares.
(Note that adding an~X may open the possibility for another~X to be added.)
Sometimes when you do this, every square on the board will be marked with an~X.
Other times, the process will stop with some empty squares left over.

See the picture below for the process on a $5\times5$ chessboard with a certain
four squares initially marked. In the end, a total of eight squares are marked.

In terms of~$n$, what is the minimum number of marked squares you can start
with and still end up with every square on the board marked with an~X?

$$\fig{spring-break-puzzles-x.mps}$$

\medbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (From {\tt http://stanwagon.com/wagon/Misc/bestpuzzles.html}.)\enspace
A tunnel underneath a large mountain range serves as a conduit for
1001~identical wires; thus, at each end of the conduit, one sees
1001~wire-ends. Your job is to label all the ends with labels (\#1,~\#2,
\dots,~\#1001), so that each wire has the same label at its two ends.

You may join together arbitrary groups of wires at either end; they will then
conduct electricity through the join. Then you cross the mountains by a very
expensive and dangerous helicopter ride to the other end, where you can feed
electricity through any wire and check which of the other ends are live, attach
notes to the wires, and make (or unmake) connections as desired. Then you fly
back to the near end, perform the same sort of operations, fly back, and so on
as often as required.

How can you accomplish your task with the smallest number of helicopter
flights?

\medbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (From {\tt http://stanwagon.com/wagon/Misc/bestpuzzles.html}.)\enspace
Suppose we wish to know which windows in a 36-story building are safe to drop
eggs from, and which will cause the eggs to break on landing. We make a few
assumptions:

\nobreak\smallskip

\item{$\bullet$} An egg that survives a fall can be used again.

\item{$\bullet$} A broken egg must be discarded.

\item{$\bullet$} The effect of a fall is the same for all eggs.

\item{$\bullet$} If an egg breaks when dropped, then it would break if dropped
from a higher window.

\item{$\bullet$} If an egg survives a fall, then it would survive a shorter
fall.

\item{$\bullet$} It is not ruled out that the first-floor windows break eggs,
nor is it ruled out that the 36th-floor windows do not cause an egg to break.

\nobreak\smallskip

\noindent If only one egg is available and we wish to be sure of obtaining the
right result, the experiment can be carried out in only one way. Drop the egg
from the first-floor window; if it survives, drop it from the second-floor
window. Continue upward until it breaks. In the worst case, this method might
require 36~droppings. Suppose two eggs are available. What is the least number
of egg-droppings that is guaranteed to work in all cases?

\medbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (``Pancakes,'' {\it Thinking Mathematically}, page~185.)\enspace
When I make pancakes they all come out different sizes. I pile them up on a
plate in the warming oven as they are cooked, but to serve them attractively I
would like to arrange them in order with the smallest on top. The only sensible
move is to flip over the topmost ones (i.e., insert a pancake flipper somewhere
in the pile and flip over the smaller stack of pancakes above the flipper). Can
I repeat this sort of move and get them all in order?

\nobreak\medskip

\noindent[Extension: Suppose I always burn one side of the pancakes when I
cook them, and when I first pile them on the plate I place them burned side
down. Can I sort them in the same way while guaranteeing that the burned sides
will all be facing down when I am done?]

\medbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (``Desert Crossing,'' {\it Thinking Mathematically}, page~165.)\enspace
It takes nine days to cross a desert. A man must deliver a message to the other
side, where no food is available, and then return. One man can carry enough
food to last for 12~days. Food may be buried and collected on the way back.
There are two men ready to set out. How quickly can the message be delivered
with neither man going short of food?

\medbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (Perfect square game.)\enspace
This is a game for two players. Start with a given number (say,~10). On a
player's turn, she finds the greatest perfect square that is no larger than the
current number, and either adds or subtracts this perfect square to the current
number to obtain a new number. The first player to reach~0 wins. What is the
best strategy? (First of all, is it clear that the game will even end?)

\medbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (Grid sums.)\enspace
This is another game for two players. The game is played on an $n\times n$
square grid, with markers on some squares initially. (The way in which these
first markers are laid out is arbitrary; choose an interesting initial
configuration and play with that.) Each player's turn consists of placing one
marker on an empty square. The winner is the person who places the marker that
first causes the sequence of row sums (the numbers of markers in each row) to
be equal to the sequence of column sums, when both are sorted numerically. For
example, the following configuration is a winning configuration, because both
the sequence of row sums and the sequence of column sums, when sorted, are
0,~1, 1, 2,~3.

$$\fig{spring-break-puzzles-grid-sums.mps}$$

\noindent How should you play this game?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bye
