The Challenge Competition consists of three parts, which are three very different challenges or puzzles. The idea is that you enter the competition as a team. A team consists of no more than 10 students from one school or College. One strategy is that each puzzle is taken on by two or three members of the team, but you can share the work however you wish. The teams will be nominated by the Contact Teacher for your school or college.

Each challenge is 'open-ended' and there is often no single right answer. In fact in some cases we do not even know if anyone knows an answer!

Your solutions must be received no later than 4pm on Monday 17th November. The two or three teams with the best submissions will be invited to present some of their answers at the competition 'Finale' at the end of the What's in IT for You? event on the 19th November. There will be feedback from the judges and, at the discretion of the judging panel, the best overall team will win £250 (to be shared among the team) with a further £250 going to the school or college to which the team belongs. Any individual student, or groups of students, may also enter for a single Challenge. Again, if the judging panel consider an entry to be of sufficient merit there will be prizes available for each Challenge individually.

Submissions should be made electronically and should consist of e-mail with attachments in pdf or an image in any standard format. The submission e-mail should be addressed to challenge@dcs.warwick.ac.uk. In cases where you wish to include diagrams or mathematics you may prefer send a photograph or a scanned image by fax. The fax number is 02476 573024 and your fax should be clearly marked 'Challenge Competition entry for attention of Dr M. Jurdzinski'. For entries by e-mail or fax you must include the name of your school and the names of all students in your team as described above.

Challenge 1. A Cyclic Story

(Note that there are five tasks here but Task (iv) and (v) depend only on Task (i), so one person could work on those, while someone else worked on Tasks (ii) and (iii).)

Preamble. You have probably seen the series

1, 1, 2, 3, 5, 8, 13, ...

and you may know that the ratios of consecutive terms behave in an interesting way. (If you don't know what this is about, look up 'Fibonacci' in Wikipedia.) Actually it does not matter what two numbers you start with, you always get this 'interesting' behaviour. So we might have written

a, b, a+b, a+2b, 2a+3b, ...

Try it with any numbers you like for a and b using a calculator, or write a short program to calculate the numbers and their ratios.

Now instead of just adding the previous two terms try using the rule given by

a, b, (b+1)/a, ...

to make the 'next' term after the last two. Apply this same rule, carefully, to the second and third terms here to make the fourth. You might like to try it with numbers first, say for a=2, and b=5. You might be a bit surprised with your sixth and seventh terms. Try it starting with larger numbers, and negative numbers, for a and b. You should find that although the terms start to get complicated they then (usually) come back to the two numbers with which you began. Try with a=1, b= -2. That's why we said 'usually' in the last-but-one sentence.

Task (i). State carefully, with justification, the values of a and b for which the sequence does 'cycle' back to its initial values.

Task (ii). The expression (b+1)/a is an example of a function of two variables. Here it is serving to state a 'rule' for continuing the terms of a sequence. We shall call a function that repeats its values in this way a 'cyclic function'. The number of different terms (in general) for such a function, before it starts repeating, will be called its 'period'. So the function (b+1)/a is of period 5. In particular cases some of the terms might be equal (for example, a and b might have the same value, could all five values ever be equal?) Find a different function of two variables which again has period 5.

Task (iii). Easy bit: find a cyclic function of two variables which has a period of 6. Hard bit: find a cyclic function of two variables with a period of 7 or else prove that there cannot be such a function.

Task (iv). Go back to the first function in Task (i) but write it as:

x, y, (y+1)/x, ...

Think of x and y now as the co-ordinates of a point (x,y) in the plane. Suppose the point (x,y) is transformed into the point (y, (y+1)/x). What will this same transformation do to the point (y, (y+1)/x) itself? Can you now write down an expression in x and y which will have the same value after the transformation x -> y, y -> (y+1)/x as before the transformation (for any given values of x and y)?

Task (v). Let us denote the expression you found in Task (iv) as F(x, y). Then the curve with equation F(x, y) = k, where k is a constant, is called an 'invariant' for the transformation. Points on this curve will generally change position when 'transformed' but always to another point on the same curve. Now consider the x-y plane as horizontal with a vertical z-axis to describe 3-dimensional space with points (x,y,z). Then the equation z = F(x,y) represents a surface with every particular value of z corresponding to an invariant curve for the transformation. (Such a curve is a 'section' parallel to the x-y plane through the surface.) Find the minimum values of the surface z = F(x,y). For which values of x and y do they occur? [This is quite hard to do analytically - that is, by means of co-ordinate geometry and calculus. An alternative way of finding the answers would be using suitable mathematical or graphical software. If you do that, explain in detail what software you were using and how you found the answers.]

If you have successfully got this far, well done! You will now understand why this is called a Cyclic Story.

 

Challenge 2. Bridge Building

You need to obtain a Jenga game. This is a set of 54 small wooden blocks manufactured by Hambros. You have to build a bridge consisting of two 'pillars'. Each pillar begins with a single Jenga block on the 'ground' (such as a table top). This is called the 'base block' of the pillar. Each successive layer of the pillar may contain one or more of the Jenga blocks. There must be no modification, or addition of any material, to the blocks. You may make marks with pencil or pen on the blocks. The two pillars must form a continuous sequence of blocks successively in contact with one another. The aim of the Challenge is make a stable bridge with the largest 'span' you can achieve, where by 'span' we mean the distance between the inner faces of the base blocks. See the accompanying picture illustrating a very simple bridge using ten blocks. The span in this case was 9.6cm, or a multiple of 1.2800 times the block length of 7.5cm. The bridge is 'stable' (our definition!) if it can sustain a weight of 150g placed at the 'middle' of the bridge. You may use any number of blocks up to the maximum of 54.

Your entry for this challenge should consist of

(i) the span you have achieved as an absolute measurement (in cm) and as a multiple of the length of your blocks;

(ii) a digital photograph of your bridge.

[NB There are small cans of H... Baked Beans weighing 150g. A version of the Jenga Game has been on sale recently in the well-known high street store W... for £5.99.]

 

Challenge 3. Electrical Wiring

An electrician arrives at a house to find that his careless apprentice has installed a bunch of identical black wires running from the cellar to the attic but hasn't labelled them. The only things that the electrician can do to sort this out is to go to the attic or the cellar, and then connect some of the wires together or test connectivity between wires (for example, by connecting a battery and a torch-bulb to any two wire ends). How many times must he go up or down the stairs before he can correctly match up the ends of all the wires?

Example 1. Matching up five wires in three trips.

Consider the following example solution, which proves that if there are 5 wires then the electrician can always correctly match up the ends of all wires by going up or down the stairs just 3 times.

In the diagrams below we use boxes with 5 "wires" at the bottom to denote the wire ends in the cellar, and with 5 "wires" at the top to denote the wire ends in the attic. We will use letters (for example: A, B, C, etc.) to label the wire ends in order to record our findings and to arrive at a correct match-up of the wire ends in the cellar and the attic.

Suppose that the electrician is initially in the cellar. The following diagram shows the result of the electrician putting new labels on all wires in the cellar (red letters A, B, or C at the bottom wires), connecting the first two wires in the cellar together (denoted by the red dotted line connecting the wires labelled with the letter A), and connecting the third and the fourth wires in the cellar together (denoted by the red dotted line connecting the wires labelled with the letter B).

 

Now suppose that the electrician goes upstairs to the attic. What he can do there, by checking connectivity of various wire ends, is to identify the only wire that is not connected to any other wire; note that this must be the wire whose cellar end is labelled with the letter C. Suppose that this wire is the second from the left in the attic (we can make this assumption without loss of generality, and not consider other cases, because the electrician can always "reorder" the wire ends by bending them appropriately). The electrician then labels the second wire in the attic with the letter C (see the diagram below). Observe that now the C labels are unique both in the cellar and in the attic (i.e., no other wire end has the label C); the two wire ends have been correctly matched in just one trip up the stairs!

By further connectivity testing in the attic, while the cellar wire ends are connected as depicted in the diagram above, the electrician can establish which are the two pairs of wire ends in the attic that are connected to each other. Assume (again without loss of generality) that the first and last wires are connected, and that the third and the fourth wires are connected. The electrician then labels the first and last wires with the letter D, and the third and the fourth wires with the letter E; see the blue labels in the diagram below. Note that one of the labels D or E must correspond to A and the other to B, but at this stage the electrician does not have a way of establishing which is which! This is why he introduces new labels D and E.

Finally, once all the connectivity testing in the attic has been done, the electrician decides to connect the last two wire ends in the attic (or more generally, one wire labelled with the letter E and one wire labelled with the letter D). This is denoted by the red dotted line in the diagram below. Moreover, he labels those two wires with the letter F (see the red labels in the diagram below).

The blue labels in the diagram below summarise the knowledge that the electrician has gained by performing connectivity testing in the attic, while the wires in the cellar are connected in the way denoted by the red dotted lines in the previous diagram. In all remaining diagrams we will follow the convention that the blue labels denote new knowledge inferred from connectivity testing, and the red labels are the other newly introduced labels (usually reflecting new wire connections introduced by the electrician after testing).

 

To continue with our example solution for the problem with five wires, suppose now that the labels on the wire ends and wire connections are as in the diagram above, and assume that the electrician has made the second trip, this time down the stairs to the cellar again. By checking connectivity he can establish which two wire ends in the cellar are connected in the attic; without loss of generality assume that these are the first and the third wire ends. The electrician then labels those two wire ends with the letter F (see the blue labels in the diagram below). (Note that the only possible pairs of cellar wire ends that could have been connected here are: first and third, first and fourth, second and third, or second and fourth. Can you see why?)

Finally, the electrician decides to connect the fourth and the fifth wire ends in the cellar (red dotted line) and label them both with the letter G; see the diagram below.

Then the electrician walks up the stairs to the attic again. There, by checking electrical connectivity, he establishes that the second and the third wire ends are connected and hence they should be labelled with the letter G; see the blue labels in the diagram below. (Note that the only possible pairs of attic wire ends that could be connected here are: first and second, or second and third. Can you see why?)

At this stage the electrician has amassed just enough information about the wires to know which of the labels A and B correspond to exactly which labels D and E. The only wire in the cellar that has a label C is now connected to a wire with a label B, and the latter wire has just been identified as the wire that has a label E in the attic. It must then be the case that the label E corresponds to the label B, and therefore the label D corresponds to the label A.

 

Now then, after having made three trips up or down the stairs, the electrician has matched up all the five wires: if he erases the labels D and E in the attic and replaces them with the labels A and B, respectively, then every compound label (for example, EF=BF for the fourth wire in the attic, or BF for the third wire in the cellar) in the cellar and in the attic is unique, and the two wire ends of each of the five wires have the same (matching) labels.

 

Example 2. Matching up six wires in four trips.

Now consider another example solution, this time allowing to correctly match up 6 wires in 4 trips up or down the stairs.

The electrician starts from the attic where he connects the first three wires together and labels them all with the letter A.

 

He then goes to the attic, and by testing for connectivity, he identifies the three wire ends in the attic that are connected in the cellar, and he labels them all with the letter A (without loss of generality, assume that they are the first, the third, and the last wire end in the attic). Also, he connects two unlabelled wire ends (say, the fourth and the fifth) to one of the wires labelled with the letter A (say, the sixth), and he labels them all with the letter B.

Back in the cellar, the electrician identifies the three wire ends that are now connected in the attic, and labels them with the letter B. He then decides to connect the only unlabelled wire end in the cellar (in our case it is the fifth wire end) to one of the wire ends with the label B (say, the sixth), and he labels both with the letter C.

After climbing the stairs back to the attic again, the electrician identifies the two connected wires and labels them with the letter C. One of them must be the previously unlabelled wire end (in our case the second wire in the attic) and the other must have the label B (assume, without loss of generality, that it is the fifth wire in the attic). Finally, the electrician decides to connect one of the wires with the label A (say, the third wire in the attic) to the only wire that has only B as a label (i.e., not the wires whose compound labels are AB or BC), and labels them both with the letter D.

 

After the final trip to the cellar, the electrician identifies the two wires that are connected in the attic, and labels them with the letter D. Now a correct match has been found for all the wire ends, because every compound label in the cellar and in the attic is unique, and the two wire ends of each wire have the same labels.

 

 

Your tasks

Task (i). Find solutions to the problem of matching the cellar and the attic wire ends, for the scenarios with five and six wires, that are more efficient than the example solutions presented above. In other words, present strategies of connecting wires and testing for connectivity, such that the electrician needs less than three trips for five wires, and less than four trips for six wires, in order to match up all of the wire ends in the cellar and in the attic.

Task (ii). Analyze the problems of matching the cellar and the attic wire ends for scenarios with three, four, five, six, seven, eight, nine, ten, ..., wires. Describe efficient strategies for matching wire ends for (some or all) of those cases. What are the smallest possible numbers of trips that are sufficient for your strategies?

Task (iii). Try to find as many numbers W, such that you can design a strategy to solve the problem with W wires in just two trips up or down the stairs.

Task (iv). Try to generalize your reasoning so that you can devise efficient strategies for arbitrarily large number of wires. More specifically, can you present an unbounded sequence of numbers w₁ < w₂ < w₃ < w₄< ..., for which there is a (fixed) number T, such that for every number W in the sequence w₁, w₂, w₃, w₄, ..., there is a strategy to correctly match up all the wire ends for the problem with W wires in no more than T trips? Describe such a strategy that works for each numbers of wires w₁, w₂, w₃, w₄, ...? What is the smallest T for which you can achieve the above?

 

 

Deadline extended!

You can enter for a single Challenge.

Prizes are at the discretion of the judging panel.