You may also like

problem icon

Multiplication Magic

Given any 3 digit number you can use the given digits and name another number which is divisible by 37 (e.g. given 628 you say 628371 is divisible by 37 because you know that 6+3 = 2+7 = 8+1 = 9). The question asks you to explain the trick.

problem icon

Transposition Fix

Suppose an operator types a US Bank check code into a machine and transposes two adjacent digits will the machine pick up every error of this type? Does the same apply to ISBN numbers; will a machine detect transposition errors in these numbers?

problem icon

Check Codes

Details are given of how check codes are constructed (using modulus arithmetic for passports, bank accounts, credit cards, ISBN book numbers, and so on. A list of codes is given and you have to check if they are valid identification numbers?

Knapsack

Age 14 to 16 Challenge Level:
knapsack

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?