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.

This document, index.html, has been accessed 105 times since 25-Jun-24 11:57:13 +08. This is the 1st time it has been accessed today.

A total of 75 different hosts have accessed this document in the last 268 days; your host, 18.97.9.168, has accessed it 1 times.

If you're interested, complete statistics for this document are also available, including breakdowns by top-level domain, host name, and date.