Problem I. 203. (January 2009)
I. 203. Suppose that a monkey is hitting letters randomly on a typewriter keyboard. If we wait long enough, then those random letters might produce meaningful words, even the complete works of William Shakespeare. The aim of the following experiment is to examine whether monkeys can produce a given text (being at most 3 characters long).
Description of the experiment. Take a monkey and a keyboard containing only the capital letters of the English alphabet. Choose a string, for example OR. In each experiment, wait for 50000 keystrokes, then determine the first position after which the chosen word completely appeared. (For example, if the monkey typed GJFORSFFX, then OR appeared after the 5th keystroke.) Save this value. (If the monkey did not type the given string, set that counter to 60000.)
Your task is to devise a suitable model to simulate the above experiment in a spreadsheet application. You can assume that the monkey hits each letter with equal probability. Experiment with the words FA, BOT, ORR (meaning TREE, STICK and NOSE in English), and with XP, PDF, PPT and MMM (which would be harder for a monkey to understand). However, your solution should be able to handle other words as well. Results of these experiments should be stored in the sheet ``measurements''. (These numbers are read off and entered by you.) No other data can be present on this sheet.
The translation of the text in cell A1 in the example is ``The actual string to be examined'', while cell A3 says ``String MMM in cell A2 appears after the 17719th keystroke on the average'', finally, the Hungarian word ``kísérlet'' is experiment. (These figures are only for illustration.)
The worksheet ``monkey'' should contain the characters typed by the monkey. (You can use an arbitrary format to store characters, but try to choose a layout that helps data processing.) Auxiliary computations (if necessary) can be stored in sheet ``aux''. The more experiments you make the better.
The compressed file i203.zip containing file i203.xls (or i203.ods) should be submitted together with a text file (i203.txt, i203.pdf, ...) specifying the version numbers of the programs applied. The text file should also contain your conjecture about the following question: which string of the form XYZ, XYX, XXY and XXX is the most probable to appear first and last in the monkey's text?
Deadline expired on February 16, 2009.
8 students sent a solution. 9 points: Balla Attila, Pap 999 Dávid. 8 points: 3 students. 5 points: 2 students. 3 points: 1 student.