Fun and Creative Problem Solving
in Mathematics and Computer Science

(A Workshop in NYGH)
28 January 2010

by Leong Hon Wai
Department of Computer Science
National University of Singapore
email,MSN,FB: leonghw@comp.nus.edu.sg

This mini-site is used to distribute the slides I used for my workshop on Thursday, 28 January 2010. The workshop is on "Fun and Creative Problem Solving in Mathematics and Computer Science" and the audience includes about 40 NYGH students (S2-S4) who opt to do Mathematics Research Project (MRP) in 2010, 15 teachers and 4 parents.

About the Workshop: here

Feedback: I did not give out any feedback form on that day, but I would like to have your informal feedback from you. Please feel free to write.

The "Challenge Problem"

The Lucky Prisoner's Problem: In a country X, there is a prison with n prisoners, each held in an individual cell, numbers 1, 2, 3,..., n. There is a light in each cell and the light switch is controlled only by the prison guards.

On his birthday, the King of country X wants to set free some lucky prisoners. He announces the following procedure to decide the prisoners that he will pardon and set free.

  1. On day 1, turn ON the lights in every cell.
  2. Then, on day 2, 3, 4,..., n, the prison guard does the following: on day k, the prison guard will “toggle” the light switch of cells whose numbers are multiples of k.
    (To “toggle” mean that if the light is ON, then turn it OFF, but if the light is OFF, then turn it ON.)
  3. At the end of n days, the King releases the prisoners in cells whose lights are ON.

The Question: Determine which prisoners will be freed. Give a proof.

Hurry up and solve this problem and mail it to Prof Leong. The first correct answer gets a prize.

Leong Hon Wai, School of Computing, NUS.

Total Accesses: 1895 hits since 21-Jan-10. (Over 751 days, from 425 hosts)
Accesses today: 2nd. (Complete statistics.)