% This template was created by Stephen on 27th March 2000
% Set the document class
\documentclass[12pt,a4paper]{article}
% Resize the page, to save the forests.
\setlength{\topmargin}{-1cm} \setlength{\textheight}{24cm}
\setlength{\textwidth}{15cm} \setlength{\oddsidemargin}{0.5cm}
\setlength{\evensidemargin}{0.5cm}
% Just in case we want to do Black Board Bold letters.
%\input{amssymb.sty}
\usepackage{amssymb}
% So we can do multicolumns
\usepackage{multicol}
\setlength\columnseprule{0pt} % no vertical lines inbetween columns
\setlength\multicolsep{0.5ex} % space preceding a multicolumn
% A command to generate the header text
\newcommand{\myheader}
{\footnotesize December 2005}
% Change the headers and footers
\pagestyle{myheadings} \markboth{\myheader}{\myheader}
% New Commands to make numbered lists easier
\newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}
% New Commands to make in-text displayed math easier
\newcommand{\bdm}{$ \displaystyle}
\newcommand{\edm}{$}
% New Commands to do handle the black board bold sets:
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Q}{\mathbb{Q}}
% New command for conjugates, arguments, etc.
\def\conj#1{\overline{#1}}
\def\arg{\,\mbox{arg}\,}
\def\Arg{\,\mbox{Arg}\,}
\def\cis{\,\mbox{cis}\,}
\def\Cis#1{\cos {#1} + i \sin {#1}}
\def\Re{\, \mbox{Re}\,}
\def\Im{\, \mbox{Im}\,}
\def\cosec{\,\mbox{cosec}\,}
\def\deg{\,\mbox{deg}\,}
% New command for does not divide
\def\notdivide{\!\not|\,}
% New command for the heading
\newcommand{\WorksheetHeading}[1]{{\par\noindent \bf \Large #1}}
% New command to fix spelling
\newenvironment{centre}{\begin{center}}{\end{center}}
% New command for itemised titles
\def\it#1{\item{\bf #1.}}
%--------------------------------------------------------
% Let the document begin!
\begin{document}
\begin{centre}
\bf \Large
Invariants (J)
\end{centre}
\subsection*{Problems}
\begin{enumerate}
\item Suppose the positive integer $n$ is odd. First Alice writes
the numbers $1,2,\ldots,2n$ on the blackboard. Then she picks any
two numbers $a,b$, erases them, and writes $|a-b|$ in their place.
Prove that when there is exactly one number left on the board,
then it is odd.
\item A circle is divided into six sectors. The numbers
$1,0,1,0,0,0$ are written in the sectors, anticlockwise in that
order. You may increase two neighbouring numbers by 1. Is it
possible to equalise all numbers by a sequence of such steps?
\item Three automata $I$, $H$ and $T$ print pairs of positive
integers on tickets. For an input $(a,b)$, $I$ and $H$ give
$(a+1,b+1)$ and $(a/2,b/2)$ respectively. $H$ accepts only even
$a$, $b$ as input. $T$ accepts two pairs $(a,b)$ and $(b,c)$ as
input and yield output $(a,c)$. Starting with $(5,19)$, for which
$n$ can the ticket $(1,n)$ be reached?
\item Each term in a sequence $1,0,1,0,1,0,\ldots$ starting with
the seventh is the sum of the last six terms modulo 10. Prove that
the string $0,1,0,1,0,1$ never occurs in this sequence
\item Two opposite corner squares of an $8\times 8$ chessboard are
deleted. In how many ways can the resulting 62 squares be tiled by
$2\times 1$ dominos?
\item A square chessboard of side length $2^n$ is given with
exactly one square coloured red. Prove that it is possible to tile
the non-red squares exactly using L-shaped trionimos only.
\item In the Parliament of Sikinia, each member has at most three
enemies. Prove that the house can be separated into two houses,
such that each member has at most one enemy in his own house.
\item $2n$ ambassadors are invited to a banquet. Every ambassador
has at most $n-1$ enemies. Prove that the ambassadors can be
seated around a round table in such a way that nobody is sitting
next to an enemy.
\item Start with a sequence $S=(a,b,c,d)$ of positive integers and
find the derived sequence $T(S)=(|a-b|,|b-c|,|c-d|,|d-a|)$. Does
the sequence $S,T(S),T(T(S)),\ldots$ always reach $(0,0,0,0)$?
\item For what $m$ and $n$ can a $m\times n$ rectangle be tiled
with $1\times 4$ tiles?
\end{enumerate}
\end{document}