Math A-lympiad: Final 1989-1990

The battle against the shop thieves

Introduction

For the shop owners in B. the limit has been reached. It's about time to fight shop lifting!
There have always been customers who were a little easy on paying their bill, but nowadays it seems to be trendy to visit a series of shops and try to get away with as much as possible without paying. If they feel observed in one shop they speed to the next one and continue their proletarian shopping there. Especially the next door city feeds B. with a number of shoplifters.

There has been contact with the local police resulting in the plan to develop and design a telefonic warning system. Fifteen shops will participate in this system.
The shop owner who spots a potential shop lifter will immediately ring two colleagues and give a description of the person (for that reason they develop a description guide).
The calling of one shop will take two minutes. After two minutes one of the two colleagues will be reached who in turn will call two colleagues. After four minutes (on average) the second colleague has been warned who in turn starts calling two shops. Etcetera, etcetera.

An example
The scheme below shows the fifteen shops in a calling tree. If shop 1 starts to ring at time = 0 we will have the situation that after 8 minutes some 73% of the shops will be warned.
However a thief will not always start at the top of the calling tree (at shop one). So we need some modification of the tree in order that every shop can be the first one to start the system.
 
The calling tree

Exercise I

Try to develop different versions for the calling tree. Use the following 'criteria' for quality:
     
  • the number of minutes necessary to warn all shops
  • the number of minutes necessary to warn at least half of the shops
The route of the thief
When placing shops into the calling tree we should reckon with the fact that a major role in how attractive the shop will be for a thief is the relative position to other shops and the kind of articles found in the shop. If, for instance a suspect person is spotted in a Record and CD shop we need to warn other music shops and department stores before the clothing shop at the other side of the street.
Look at the map of the city center of B. to see the position of the fifteen shops.

Exercise II

  1. Design and develop a method how to place the shops into the calling tree. Keep in mind the walking distance between shops and also a kind of 'distance' between the shops in regard to 'theft-sensibility'.
  2. Place the fifteen shops into the calling tree that resulted from Exercise I.
  3. Look once more at the tree keeping in mind the new criteria that might result in a completely different structure. Keep in mind that the system has to be user friendly; simple to execute.
  4. Write a documental article to go with the system. It should pay attention to the fact that the local police need a total view of the system but that the shop owners only need to know what exactly to do in his case.
  5. Write a popular story about the system that explains the system and its benefits to shop owners and other interested 'amateurs'.

Appendix

Map of the city center of B.
1 cm equals a 1 minute walking distance.
 
The city center of B.
Overview of the fifteen shops
Shop # Type
1, 7, 14 department stores
5, 10, 12 supermarkets
2, 6, 8 clothing
4, 13, 15 electronics
3 camera
9, 11 CD and Records, books
Walking distance in minutes
from shop #
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1
2 1
3 1 0
4 3 2 2
5 4 3 3 1
6 4 3 3 1 0
7 5 4 4 2 1 1
8 8 7 7 5 4 4 3
9 8 7 7 5 4 4 3 0
10 10 9 9 7 6 6 5 2 2
11 9 10 10 10 9 9 8 5 5 3
12 9 10 10 12 13 13 14 11 11 9 6
13 11 12 12 14 15 15 16 13 13 11 8 8
14 14 13 13 11 10 10 9 6 6 4 5 11 7
15 3 4 4 6 7 7 8 11 11 13 12 12 14 17