Transcript for the lecture - Gresham College

Gresham College
John D Barrow
DAMTP
Cambridge
The Maths of
Sorting Things Out
Complexity is All
Around Us
Impossible to Prove
(so far)
Goldbach- Euler 7th June 1742
Every even number can be
written as the sum of
2 prime numbers
4 = 2+2, 6 = 3+3, 8 = 3+5
10 = 3+7, 12 = 5+7, 14 =7+7,…..
…36 = 31+5…etc
known to be true for even numbers up to
61016
389965026819938
=
5569
+
389965026814369
Number of ways an even number can be written as the sum of two primes (4 < n < 1000)
Number of ways an even number can be written as the sum of two primes (4 < n < 106)
Computer-aided Mathematics
Computer Proofs
Experimental mathematics
Is Anything Beyond Computers?
Four Colours Suffice
Tractability
‘Easy’ problems
N parts
Calculation time grows as N
‘Hard’ problems
N parts
Calculation time grows as 2N
Monkey Puzzles
Puzzle
Monkey
Match up the nine cards
Match up 9 cards
9!  49 = 95,126,814,720 possible moves
Matching up 25 cards has 25!  425
takes
533 trillion trillion years
at
1million moves per second
6-city Travelling Salesman
6 – CITY TRAVELLING SALESMAN
6
3
4
8
9
3
4
10
7
7
5
6
3
4
6-city Travelling Salesman
6 – CITY TRAVELLING SALESMAN
6
3
4
8
9
3
4
10
7
7
5
6
4
3
3
7
5
‘Travelling Salesman’ visiting
3038 sites
(Applegate et al 1990)
18 months of computer time
8 years of parallel computing
Some More ‘Hard’ Problems
Where the best solution can’t be predicted by a
general recipe
Packing Problems
Examples







Fitting music tracks on CDs
Fitting packages in boxes
Scheduling computer or
machine tasks
Building shelves
Adverts in TV breaks
Data storage on disk
Fitting your holiday stuff in a
suitcase
The Problem
25 data files to fit onto disks that each hold a maximum of 10 GB
What is the smallest number of disks you could use?
How do you pack these files to do it?
6,6,5,5,5,5,4,3,2,2,3,7,6,5,4,3,2,2,4,4,5,8,2,7,1
Total volume to be fitted on disks is
106
Strategy 1: ‘Next Fit’
6,6,5,5,5,5,4,3,2,2,3,7,6,5,4,3,2,2,4,4,5,8,2,7,1






Put first track on first disk, then
next in the same disk until it
won’t fit.
Then start new disk.
You can’t go back and fill gaps
in earlier disks.
14 disks used. 3 full.
32 out of 140 slots empty
108/140 = 77% filled
55
2
552
4
2
552
4 4 81
553 7 424 87
66553 76424 87
66553376524587
66554376524587
66554376534587
66554276534587
66554276534587
Other Strategies to Try
‘First Fit’
You can go back and put tracks on the first disk in the line that
still has room
 ‘Worst Fit’
Put next track on the disk that currently has most space available
 ‘Best Fit’
Put next track on the disk that leaves the least room on the disk
after it is added

Strategy 2 : ‘First Fit’
6,6,5,5,5,5,4,3,2,2,3,7,6,5,4,3,2,2,4,4,5,8,2,7,1






Put first track on first disk
which has space,
Then start new disk.
You can go back and fill gaps in
earlier disks.
12 disks used. 6 full.
14 slots empty
106/120 = 88% filled
41553 4
43553242
435532424
8
435537424 87
665537624 87
665537654587
665527654587
665527654587
665527654587
665527654587
Sorting Helps
Sort the files into descending size order
8,7,7,6,6,6,5,5,5,5,5,5,4,4,4,4,3,3,3,2,2,2,2,2,1
Now try sorted ‘Next Fit’ and ‘First Fit’ strategies
What was the best strategy?
Is it the best possible for this problem?
Strategy 3: ‘Sorted Next Fit’
8,7,7,6,6,6,5,5,5,5,5,5,4,4,4,4,3,3,3,2,2,2,2,2,1






Put first track on first disk, then
next in the same disk until it
won’t fit.
Then start new disk.
You can’t go back to fill gaps in
earlier disks.
14 disks used. 4 full.
33 slots empty
107/140 = 76% filled
8
877
8 7 76
8 7 76
8 7 76
8 7 76
8 7 76
8 7 76
555
2
555
32
5554432
5554432
665554432
665554432
665554432
665554432
665554432
665554432 1
Strategy 4: ‘Sorted First Fit’
8,7,7,6,6,6,5,5,5,5,5,5,4,4,4,4,3,3,3,2,2,2,2,2,1






Put first track on first with disk
with space
Then start new disk.
11 disks used. 10 full.
4 slots empty. Can’t do better
106/110 = 96% filled
THIS IS THE BEST POSSIBLE
PACKING
2 3 34
2 3 34
8 3 34
8 7 74
8 7 76
8 7 76
8 7 76
8 7 76
8 7 76
8 7 76
445551
445552
445552
445553
6655532
6655532
6655542
6655542
6655542
6655542
Chicken McNugget Numbers
6, 9 and 20
What is the Largest Non-McNugget Number
Any sufficiently large number can me written
as a linear sum of 6s, 9s and 20s
44
45
46
47
48
49
=
=
=
=
=
=
6+9+9+20
9+9+9+9+9
6+20+20
9+9+9+20
6+6+9+9+9+9
9+20+20
Make all larger numbers by adding a 6
to any one of these and so on
The largest non-McNugget number is 43
6s and 9s only make multiples of 3.
Using a 20 or two doesn’t help.
All the non-McNugget numbers are
1,2,3,4,5,7,8,10,11,13,14,16,17,19,22,23,25,28,31,34,37,43.
The Happy Meal 4-McNugget Box (1979)
makes it mathematically far less interesting
!
The numbers {4,6,9,20} now allow only six non-McNugget numbers
1,2,3,5,7 and 11
What’s the smallest total stamp value that can’t fit on the envelope?
The Postage Stamp Problem
An envelope can only hold a maximum number of stamps  h
Stamps have values An = {a1, a2,…..an}
Sort in ascending order so that 1 = a1 < a2 <….. < an
We want the smallest integer that can’t be written as
N(h, An) = F1a1 + F2a2 + …..+ Fnan
where F1 + F2 + …..+ Fn < h
The number of consecutive possible postage amounts that
will fit on the envelope is n(h, An) = N(h, An) - 1
Exact solution only known for n = 2:
n(h, A2) = (h + 3 – a2)a2 – 2 for h  a2 - 2
n(h,2) = [(h2 + 6h +1)/4]
[…] is integer part, so [3.14] = 3
The first values are 2,4,7,10,14,18,23,28,34,40,….
N(h,4) > 2.008  (h/4)4 + O(h3)
The Spare Change Problem
St Gaudens $20 Gold Double Eagle
Smallest set of coins that will make all
amounts of change from 1 to 100
Europe: 1, 2, 5, 10, 20, 50 denominations
USA: 1, 5, 10, 25
Minimum number of coins given by the handy ‘Greedy Algorithm’:
Use as many of the largest value at each step
76 pence = 50 + 20 + 5 + 1 (4 coins)
76 cents = 50 + 25 + 1 (3 coins)
‘Old money’ in the UK didn’t have the handy property
½ , 1 , 3 , 6 , 12 , 24 , 30 old pence
4 shillings = 48d = 30 + 12 + 6 = 24 + 24
This happens when we double a coin value (> 2d) eg with a groat 4d
8d = 4 + 4 = 6 +1 + 1
Shallit’s Improved American System
Average number of coins needed to make 1 to 100 cents with
1, 5, 10, 25 denominations is 4.7
Worst case is with only a 1 cent coin: need 99 coins to make 99c etc
Average number needed is 49.5
18c
What is the best case using only 4 values?
1, 5, 18, 29 and 1, 5, 18, 25 are both better!
They need an average of 3.89 coins to make
all 1  100 cent amounts
Best to use the 1, 5, 18, 25 values
And replace the dime with a new 18c piece
Improved UK or Euro system ?
1, 2, 5, 10, 20, 50, 100, 200p coins
Average number of coins to make all amounts up to 500 is 4.6
Add a 133p or 137p coin and the average number falls to 3.92
133p
137p
A Further Improvement?


Lots of currencies use the pattern of denominations
1,2,5, and 10,20, 50, and 100, 200, 500
They would do (about 6%) better and use less change with
1,3,4, and 10, 30, 40, and 100, 300, 400
68 = 50 + 10 + 5 + 2 +1 = 40 +10 + 10 + 4 + 4
134 = 100 + 20 +10 +2 + 2 = 100 + 30 + 4
243 = 200 + 20 + 20 + 2 +2 = 200 + 40 + 3
279 = 200 + 50 +20 + 5 + 2 +2 = 200 + 40 + 30 + 3 + 3 +3
Greedy algorithm has one failure because 6 = 3+3 is better than 6= 4+1+1

Best to do away with the 1c or 1p coin though!