"Royal Holloway Department of Computer Science: Scholarship Challenge, 2013

Departmental Undergraduate Scholarships 2013-2014

£1,000 in the first year of study in the Computer Science Department at RHUL.
renewable at the rate of £500 in years two and three.

Please read the Rules of the Challenge.

These are the four questions that you must answer as part of your scholarship entry.

The Four Questions.

These questions can all be solved without the use of a computer. Your answers should be submitted in plain text (txt), Word (doc), pdf, rich text format (rtf) or the Open document format (ODF). You should justify your submission by explaining carefully how you arrived at each of your answers.

1	Tying Shoe Laces You are late for your plane at Heathrow and are running along a long corridor. Unfortunately, your shoe lace has come undone. This does not slow you down, but you are worried about tripping up. There is a moving walkway up ahead. Is it faster to stop now to tie your shoelace, or tie it on the moving walkway or does it not matter. Carefully justify your answer.
2	You have two sets of four numbered wooden blocks. Each set contains blocks with the numbers 1,2,3 and 4. You have to place all eight blocks in a tower so that there is precisely: one block between the two blocks numbered 1; two blocks between the two blocks numbered 2; three blocks between the two blocks numbered 3; four blocks between the two blocks numbered 4. How many ways can you do this?
3	There is a party to which you and your partner are invited. At this party there are twelve couples (including you and your partner). As is conventional you shake some peoples' hands when you meet them for the first time. Of course no-one shakes their partner's hand, nor their own! The number of hands people might shake ranges from none (they met no-one new) to 22 (everyone except their partner was new to them). So, for fun (?) you go around (at the end of the party) asking how many hands people have shaken. You get every possible answer once. That is you ask 23 people and get the 23 answers from 0 to 22. How many hands did your partner shake?
4	Pockets and Tables You are presented with a square table with a covered pocket in each corner. In each pocket (though you cant see it) is a coin. You cannot tell which way up the coin is. It may have heads on top or it may have tails on top. The table is spun around and then it stops. You cannot tell one pocket from another so you do not know which way around it is now. You now pick two pockets. The coins in these two pockets are revealed and you can turn over neither, one, or both of them. The cover is now put back onto these pockets. At this time if all four coins are the same way up then a bell rings. Otherwise the table spins again, you turn over up to two coins,... What sequence of moves will absolutely guarentee that the bell will ring? How many times (at most) will the table need to be spun?