Transcript Induction

AE1APS Algorithmic Problem Solving
John Drake

Coursework 4 deadline –
◦ Thursday 29th November at 1pm


Same submission guidelines as before, hardcopy during lectures or soft-copy via e-mail
[email protected]




Invariants – Chapter 2
River Crossing – Chapter 3
Logic Puzzles – Chapter 5
Matchstick Games - Chapter 4
◦ Sum Games – Chapter 4

Induction – Chapter 6
◦ Tower of Hanoi – Chapter 8


Induction is the name given to a problem
solving technique based on using the solution
to small instances of a problem to solve
larger instances of a problem.
In fact we can solve problems of arbitrary size


We need to measure the "size" of an instance
of a problem
E.g. with matchstick problems, we might call
the size the number of matches



It is not always obvious what the size should
be for some types of problems
The size must be non–negative i.e. whole
numbers 0, 1, 2, …
We call these numbers "natural numbers", as
they are naturally used for counting




Note that some mathematicians do not include 0
in the natural numbers
There are good reasons why we should include 0.
Zero has important significance in maths (and the
history of maths)
One reason in when counting the size of sets, the
null set is defined to have size of 0
We will see examples of including 0 later

We solve the problem in two steps

First we solve the problem instance of size 0

This is usually very easy (often called trivial)

Then, we show how to solve, a problem of
size n+1 (where n is an arbitrary natural
number), given we have a solution to a
problem instance of size n.


The first step is called the base case of the
basis of induction.
The second step is the induction step



By this process, we can solve problems of
size 0
We also know how to solve instances of size 1
(as it is one larger than 0)
We can apply the induction step to solve
problems of size 2 and so on.


The induction step allows us to solve
problems of size one greater than the current
size problem
By repeating this process we can solve
problems of any size

Straight lines are drawn across a sheet of
paper, dividing the paper up into regions.
Show that it is possible to colour each region
black or white, so that no two adjacent
regions have the same colour

P120




The number of lines is the size of a problem
We have to show how to solve the problem
when there are zero lines
We have to show how to solve a problem
when there are n+1 lines, assuming we can
solve the problem with n lines
Let us call the situation when no two adjacent
regions have the same colouring "a
satisfactory colouring"

This is trivial.

With 0 lines, there is one region

This can be coloured black or white and will
be a satisfactory colouring.

Assume a number of lines (n) are drawn on
the paper, and the regions have a satisfactory
colouring


Now we add an additional line (i.e. n + 1)
This will divide some existing regions into
two new regions, which will have the same
colour, therefore the colouring is not
satisfactory.

The task is to show how to modify the colouring
so that it does become satisfactory.

Inverting any satisfactory colouring will also
give a satisfactory colouring.
◦ i.e. changing black regions for white, and vice versa
will also be satisfactory

Let us call the two sides of the new line left
and right. Inverting colours in either region
will still give a satisfactory colouring in that
half (left or right)

Hence, inverting the colours in one half will
guarantee a satisfactory colouring for the
whole piece of paper

The algorithm for colouring is non-deterministic
in several ways
◦ The initial colouring is not specified (could be black or
white)
◦ The order in which the lines are added is unspecified
◦ The naming of the left and right regions is not specified
(symmetry)

This means the final colouring can be arrived at
in different ways, but it is guaranteed to be
satisfactory



A square piece of paper is divided into a grid
of size 2n by 2n, where n is a natural number
Individual squares are called grid squares and
a single grid square is covered
E.g. n = 3

A triomino is an "L" shape made of 3 grid
squares. Show that it is possible to cover the
remaining grid squares using triominoes


The obvious size to use is n
The base case is when n=0, and the grid has
size 1 by 1 (i.e. 20 by 20)

This square will of course be covered

The base case is solved



We want to solve a grid of 2n+1 by 2n+1
We know how to cover a 2n by 2n grid, how do
we use this to help us cover a grid size larger
by one
We make the inductive hypothesis that this is
possible



A grid of size 2n+1 by 2n+1 can be divided into
4 grids of size 2n by 2n by drawing horizontal
and vertical lines
These 4 regions can be called bottom-left,
bottom-right, top-left and top-right
One square is already covered, we will
assume this is in the bottom left square, why?

The bottom left grid is of size 2n by 2n , of
which one square has already been covered.
By the induction hypothesis, the remaining
squares in the bottom-left grid can be
covered

The bottom left grid is of size 2n by 2n , of
which one square has already been covered.
By the induction hypothesis, the remaining
squares in the bottom-left grid can be
covered



This leaves us having to cover the remaining
3 grids
None of these have any squares covered
We can apply the inductive hypothesis if just
one of the squares in each of the 3 remaining
grids is covered

This can be done by placing a triomino at the
junction of the 3 grids




What if we had chosen n = 1 to be our base
case?
Our proof would have left out the 0 case, so
we would still need to prove that separately
However including 0 provides a slightly
deeper insight
"Humans" start counting at 1, computer
scientists and mathematicians start counting
at 0 