Knapsack
Problem
This problem is based on the idea of Knapsack codes.
You have worked out a secret code with a friend. Every letter in the alphabet can be represented by a binary value that is given in the lookup table below.
You go off on a camping trip with 5 sticks in your knapsack. They have lengths of 1,3,5,10 and 20 centimetres, these will help you decode any message your friend sends.
A coded message arrives. It is the number 31. To decode the message you must work out which sticks you need to make a length of 31cm and convert this information into the binary code that tells you the letter. Decoding will be easy because your sticks form part of a superincreasing series (each stick is longer than the sum of the lengths of all the smaller sticks).
Taking the largest length off first leaves 31-20 = 11 so the coded letter used the 20 cm stick. 11-10 = 1 so the coded letter also involves the 10cm stick. With 1 left the 5-stick and the 3-stick are not used, just the 1-stick.
This gives you a binary code of 10011 (1x1cm+0x3cm+0x5cm+1x10cm+1x20cm).
So using the binary lookup table, the number 31 represents is 10011, which is the letter s.
Lookup Table
Letter
|
Binary Reference
|
Letter
|
Binary Reference
|
a
|
00001
|
n
|
01110
|
b
|
00010
|
o
|
01111
|
c
|
00011
|
p
|
10000
|
d
|
00100
|
q
|
10001
|
e
|
00101
|
r
|
10010
|
f
|
00110
|
s
|
10011
|
g
|
00111
|
t
|
10100
|
h
|
01000
|
u
|
10101
|
i
|
01001
|
v
|
10110
|
j
|
01010
|
w
|
10111
|
k
|
01011
|
x
|
11000
|
l
|
01100
|
y
|
11001
|
m
|
01101
|
z
|
11010
|
Using the sticks in your knapsack decode the message: 33,18, 20, 1, 31, 20, 30, 33.
That was easy, but say your knapsack code involved a non-superincreasing series that used 1,2,3,4,5cm sticks.
Using this knapsack can you decode the message 1, 5, 14, 4, 5, 8, 10, 5, 4, 7, 9?
Can you explain why superincreasing series are so much easier to decode?
Getting Started
There is only one way to make a length of 1cm from your knapsack so the first letter is easy.
Your problem with the superincreasing series is that there can be more than one way to make each of the totals from your knapsack and you need to look at all the possibilities to work out the message
Why can you just subtract the largest length in the case of superincreasing series in order to decode?
The superincreasing series 1, 2, 4, 8, 16, ... allows you to make all numbers but the one given in the question does not. Why doesn't this matter?
Student Solutions
We had a number of solutions to this problem and I would like to mention Karan of Beecroft Primary school and Ross of the Blue Coat School, who both managed to get the first part right but did not quite get to grips with the second.
Below is a very good solution sent by Andrei of School 205 Bucharest. Well done Andrei.
As in the first case I have to deal with a super increasing series, for each coded number there is only one corresponding letter:
Code |
Binary |
Letter |
33 |
01011 |
K |
18 |
01110 |
N |
20 |
00001 |
A |
1 |
10000 |
P |
31 |
10011 |
S |
20 |
00001 |
A |
30 |
00011 |
C |
33 |
01011 |
K |
So, the coded word is "knapsack". For, the second part of the problem, I take each number and write it in all the possible combinations, which gives us several letters to chose from:
Code |
Sum |
Binary |
Letter |
1 |
1 |
10000 |
p |
5 |
2+3 |
01100 |
l |
|
4+1 |
10010 |
r |
|
5 |
00001 |
a |
14 |
2+3+4+5 |
01111 |
o |
4 |
1+3 |
10100 |
t |
|
4 |
00010 |
b |
5 |
2+3 |
01100 |
l |
|
4+1 |
10010 |
r |
|
5 |
00001 |
a |
8 |
1+2+5 |
11001 |
y |
|
1+3+4 |
10110 |
v |
|
3+5 |
00101 |
e |
10 |
1+4+5 |
10011 |
s |
|
1+2+3+4 |
11110 |
- |
|
2+3+5 |
01101 |
m |
5 |
2+3 |
01100 |
l |
|
4+1 |
10010 |
r |
|
5 |
00001 |
a |
4 |
1+3 |
10100 |
t |
|
4 |
00010 |
b |
7 |
1+2+4 |
11-1- |
z |
|
3+4 |
00110 |
f |
|
2+5 |
01001 |
i |
9 |
1+3+5 |
10101 |
u |
|
4+5 |
00011 |
c |
There are many possibilities to make a word. But I need to find one which has sense. The possibilities are written in the following table:
p |
l |
o |
t |
l |
y |
s |
l |
t |
z |
u |
|
r |
|
b |
r |
v |
m |
r |
b |
f |
c |
|
a |
|
|
a |
e |
|
a |
|
i |
|
The only solution that I can find is: "problematic".
Teachers' Resources
Notes:
One of the challenges of this problem is the reading of a mathematical text for understanding
It would be interesting to investigate why superincreasing series are easier to deal with.
There is an article on Knapsack codes.