\documentclass[hyperref=pdftex, presentation]{beamer}
% Replacing 'presentation' with 'handout' in the above line
% will produce 4 slides per page.
% The hyperref option makes it possible to include hyperlinks.

\mode<presentation> {
\usetheme{Boadilla}
\setbeamercovered{transparent}
}

\usepackage[english]{babel}
\usepackage[latin1]{inputenc}
\usepackage{times}
\usepackage[T1]{fontenc}

\mode<handout>{
\usepackage{pgfpages}
\pgfpagesuselayout{4 on 1}[letterpaper,landscape,border shrink=5mm]
\setbeamercolor{background canvas}{bg=black!10} }

\setbeamertemplate{footline}
{
\leavevmode%
\hbox{%
\begin{beamercolorbox}[wd=.333333\paperwidth,ht=2.25ex,dp=1ex,center]{author
	in head/foot}%
	\usebeamerfont{author in head/ foot}\insertshortauthor%&\approx& (\insertshorti
\end{beamercolorbox}%
\begin{beamercolorbox}[wd=.333333\paperwidth,ht=2.25ex,dp=1ex,center]{title
	in head/foot}%
	\usebeamerfont{title in head/foot}\insertshorttitle
\end{beamercolorbox}%
\begin{beamercolorbox}[wd=.333333\paperwidth,ht=2.25ex,dp=1ex,right]{date in
	head/foot}%
	\usebeamerfont{date in head/foot}\insertshortdate\hspace*{2em}
	\insertframenumber / \inserttotalframenumber\hspace*{2ex}
\end{beamercolorbox}}%
\vskip0pt%
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\title[Puzzled?]{Puzzled?}
	%\titlegraphic{\includegraphics[width=0.3\textwidth]{coffee_cup_1}}
	\titlegraphic{\includegraphics[height=0.4\textheight]{coffee_cup_1}}
	\subtitle{Is a ``fun'' talk in Beamer possible?}

\author{Sho Uemura}
%\institute{SLAC}
\date[October 10, 2012]

\begin{document}

\begin{frame}
	\titlepage
\end{frame}

%\begin{frame}{Abstract}
%
%Mechanical puzzles are intuitive, fun, and exist in wide variety. 
%Some puzzles test your spatial reasoning.
%Some puzzles test your intuition and imagination. 
%Some puzzles test your patience.
%Some puzzles are impossible, and some are even undecidable.
%A talk about toys where you don't get to play with toys! This will be terrible.
%\end{frame}

\begin{frame}{Here's a useless outline}
	\begin{itemize}
		\item Some cute puzzles
		\item Some tricky puzzles
		\item Four equivalent boring puzzles
		\item Some annoying puzzles
		\item An infinite unsolvable puzzle
	\end{itemize}
\end{frame}

\begin{frame}{Puzzle boxes}
	\begin{itemize}
		\item ~200 years old (Japan)
	\end{itemize}
	\begin{center}
		\includegraphics[height=0.5\textheight]{Yosegi_1}
		\includegraphics[height=0.5\textheight]{Yosegi_5}
	\end{center}
\end{frame}

\begin{frame}{Art puzzles}
	\begin{itemize}
		\item Inspired by puzzle boxes but with a much wider variety of design elements
		\item Annual competitions: \url{http://www.puzzleworld.org/designcompetition/}
	\end{itemize}
	\begin{center}
		\includegraphics[height=0.5\textheight]{coffee_cup_1}
		\includegraphics[height=0.5\textheight]{bad_radio_1}
	\end{center}
\end{frame}

\begin{frame}{Six-piece burrs}
	\begin{itemize}
		\item ~200 years old
		\item Demo: \url{http://www.research.ibm.com/BurrPuzzles/B6JM9.html}
	\end{itemize}
	\begin{center}
		\includegraphics[height=0.3\textheight]{burr1}
		\includegraphics[height=0.3\textheight]{burr2}
		\includegraphics[height=0.3\textheight]{burr3}

		\includegraphics[height=0.3\textheight]{burr4}
		\includegraphics[height=0.3\textheight]{burr5}
		\includegraphics[height=0.3\textheight]{burr6}
	\end{center}
\end{frame}

\begin{frame}{Disentanglement}
	\begin{itemize}
		\item Spatial reasoning puzzles
		\item These pictures are boring
	\end{itemize}
	\begin{center}
		\includegraphics[height=0.4\textheight]{tavernpuzzles_2229_6679713}
		\includegraphics[height=0.4\textheight]{holey_bolt_1}
		\includegraphics[height=0.4\textheight]{double_w_1}

		\includegraphics[height=0.3\textheight]{hedgehog}
	\end{center}
\end{frame}

\begin{frame}{Chinese rings}
	\begin{itemize}
		\item ~2000 years old (China)
		\item Design enforces these rules:
			\begin{itemize}
				\item Can only manipulate rings up to the first ring on the handle, or the one after it
				\item Cannot manipulate a ring if the previous ring is off the handle
			\end{itemize}
	\end{itemize}
	\begin{center}
		\includegraphics[height=0.5\textheight]{JiuLianHuan2+copy}
	\end{center}
\end{frame}

\begin{frame}{Equivalent puzzles}
	\begin{itemize}
		\item Equivalent to staircase puzzle and Spinout; similar to Tower of Hanoi
			\begin{itemize}
				\item Spinout demo: \url{http://www.puzzles.com/products/SpinOut/PlayOnline.htm}
			\end{itemize}
	\end{itemize}
	\begin{center}
		\includegraphics[width=0.8\textwidth]{spinout}

		\includegraphics[height=0.3\textheight]{staircase}
		\includegraphics[height=0.3\textheight]{hanoi}
	\end{center}
\end{frame}

\begin{frame}{Recursion and Gray codes}
	\begin{columns}
		\column{0.7\textwidth}
		\begin{itemize}
			\item Puzzle is recursive (to solve the $n$-ring puzzle, first solve the $n-1$-ring puzzle)
			\item Gray codes: sequences of binary numbers where successive numbers differ by one bit
				\begin{itemize}
					\item Usually generated recursively: coincidentally this means Gray codes correspond to solutions of Chinese rings puzzle
				\end{itemize}
			\item Relationship between Chinese rings and binary numbers discovered by \'Edouard Lucas (inventor of Tower of Hanoi)
		\end{itemize}
		\begin{center}
			\includegraphics[height=0.25\textheight]{gray}
		\end{center}
		\column{0.3\textwidth}
		\includegraphics[width=\textwidth]{lucas}
	\end{columns}
\end{frame}

\begin{frame}{Jigsaw puzzles}
	\begin{itemize}
		\item Traditional jigsaws are $O(n^2)$ search problems (each edge has a unique match)
			\begin{itemize}
				\item Boring unless you're the government (DARPA Shredder Challenge)
			\end{itemize}
		\item Tetravex is hard (many matches $\to$ nonlocal) --- NP-complete
			\begin{itemize}
				\item ``Eternity II'' puzzle (16x16 Tetravex puzzle, rotations allowed) remains unsolved (despite \$2M prize July 2007---end of 2010)
			\end{itemize}
		\item ``Tetravex tiles'' were originally called Wang tiles in formal logic
		\item Tiling problem: given an finite set of Wang tiles and infinite supply of each can you tile an infinite plane?
			\begin{itemize}
				\item Undecidable: equivalent to halting problem for a Turing machine
			\end{itemize}
	\end{itemize}
	\begin{center}
		\includegraphics[width=0.35\textwidth]{tetravex}
	\end{center}
\end{frame}

\begin{frame}{Aperiodic tiling}
	\begin{itemize}
		\item This implies there must exist ``aperiodic tile sets'' that can tile the plane, but can't form periodic patterns (otherwise you could search for periodic tilings)
		\item Below: aperiodic Wang tiles, Penrose tiles
		\item 2011 Nobel in chemistry awarded for discovery of quasicrystals
	\end{itemize}
	\begin{center}
		\includegraphics[height=0.2\textheight]{wang}
		\includegraphics[height=0.2\textheight]{wang_tesselation}

		\includegraphics[height=0.2\textheight]{penrose}
		\includegraphics[height=0.2\textheight]{penrose2}
		\includegraphics[height=0.2\textheight]{quasicrystal}
	\end{center}
\end{frame}

\begin{frame}{Links}
	\begin{itemize}
		\item \url{http://www.research.ibm.com/BurrPuzzles}
		\item \url{http://www.johnrausch.com/PuzzlingWorld/}
		\item \url{http://visualiseur.bnf.fr/CadresFenetre?O=NUMM-3943&I=188&M=tdm}
		\item \url{http://www.tavernpuzzle.com/}
		\item \url{http://www.puzzleworld.org/PuzzleWorld/}
		\item \url{http://www.puzzles.com/products/spinout.htm}
	\end{itemize}
\end{frame}

\end{document}