Brain Teaser For Fun

[JohnVB6]

In a recent issue of Games Magazine the following question was posed:

There are 100 closed lockers in a school. Standing in front of each locker is a student. A bell will ring 100 times. At the first ring, all students will toggle their locker (from closed to opened). At the second ring, every other student will toggle his or her locker. At the third ring, every third student will toggle his or her locker, and so on, until the 100th ring where only the 100th student will toggle his/her locker. After the 100th ring, how many lockers will be open?

Now I wrote a program to determine the answer and it is quite intriguing. I'm wondering if anyone knows why the answer (which you'll have to figure out) is what it is, I needed the program but with time, I think I could have figured out the simple solution. I'll post the program in a couple of days unless someone else beats me to it.

[sql_lall]

Yeah, the answer is (look away if you don't want to know)

10 lockers will be open.
In particular, the open lockers will be #1, 4, 9, 16, 25, 36, 49, 64, 81 and 100.

Reasoning:
consider a locker #X. When is it opened/closed?? i.e. when does its state change?? Obviously, the locker is opened on the 1st ring of the bell. Next, on the 2nd ring, if the locker number is even (divisible by two) it will change state. Similarly,on the 3rd ring, if X is divisible by 3 (written as "3|X") then the state of locker X will change.

It is easy from this to see that at the nth ring, the state of X will change if n|X
=> X changes state at every ring (#k) which is a factor of it. (k|X)

i.e. when does #12 change state??
at ring #1, 2, 3, 4, 6 and 12 = 6 times
As it changes state an even number of times, it is closed (easy to verify)

In other words, if an integer X has an Even number of factors, it is closed at the end, if it has an odd number, locker X is open.
So, what numbers have an odd number of factors?? ONLY SQUARES. This can be explained formally, but an easier proof is to say that every factor d of X can be paired up with another factor, X/d, SO LONG AS d <> x/d. (Otherwise, you are counting the same number twice)
=> Every factor can be paired up => A number always has an even numbner of factors, UNLESS there is a number d such that d=X/d. This is easily changed into d²=X, or X is a square number.

Summary:
Q) How many lockers are open?
A) 10, they are the lockers whose number is one of the squares 1 to 100, numbers which have an odd number of factors, and so are open at the end.

[JohnVB6]

Correct answer and excellent explanation

[opus]

I made the code for EXCEL-VBA

Option Explicit
Option Base 1
 
Public Sub Locker()
Dim i As Integer
Dim j As Integer
Dim Locker(100) As String
For i = 1 To 100
    Locker(i) = "CLOSED"
Next i
For i = 1 To 100
    For j = 1 To 100
        If j / i = Int(j / i) Then
            If Locker(j) = "CLOSED" Then
                Locker(j) = "OPEN"
            Else
                Locker(j) = "CLOSED"
            End If
        End If
        ActiveSheet.Cells(i, j).Value = CStr(Locker(j))
    Next j
Next i
ActiveSheet.Cells(101, 1).Value = "Open Lockers:"
For i = 1 To 100
    If ActiveSheet.Cells(100, i).Value = "OPEN" Then
        ActiveSheet.Cells(101, 2).Value = ActiveSheet.Cells(101, 2).Value & "," & CStr(i)
    End If
Next i
End Sub

[JohnVB6]

Yes, that code works. And here is some code in VB, you need a form with a wide listbox, a commandbutton and a textbox. Just enter any number in the text box for the number of lockers you want to check.

Option Explicit
 
Dim aBits() As Boolean
Dim iNum As Integer
Dim sNum As String
 
Private Sub Command1_Click()
  ReDim aBits(txtMax - 1)
  List1.Clear
  GoFigure
End Sub
 
Private Sub GoFigure()
Dim i, j As Integer
  j = 1
LoopAgain:
  'toggle appropriate bits base on j value
  For i = 0 + (j - 1) To txtMax - 1 Step j
    aBits(i) = Not aBits(i)
  Next
  'record bits for display in list
  For i = 0 To txtMax - 1
    If aBits(i) = True Then
      iNum = 1 'open
    Else
      iNum = 0 'closed
    End If
    sNum = sNum & iNum
  Next
  List1.AddItem sNum
  sNum = ""
  'when max is reached reset bits for next calculation and exit sub
  If j = txtMax Then
    For i = 0 To txtMax - 1
      aBits(i) = False
    Next
    Exit Sub
  End If
  'continue calculating
  j = j + 1
  GoTo LoopAgain
End Sub

[sql_lall]

Just noticed something by opus:

If Locker(j) = "CLOSED" Then
   Locker(j) = "OPEN"
Else
   Locker(j) = "CLOSED"
End If

You don't need the else part, cos it will remain "CLOSED" anyway
Also JohnVB6, there are some faster ways to do your stuff too, like using IIF, looping j = 1 to txtMax, and including sNum = sNum & iNum in the IIF statement.

Anyway, Private Sub 'GoFigure()' hehehe

[JohnVB6]

Thanks for the iinfo, I never have used the IIF statement.

[opus]

Thanks for hint sql_lall, however

if Locker(i) is "OPEN" I want it to change to "CLOSE", so I do need the ELSE statement (I think!)

[sql_lall]

So sorry, i get what it means now.
You do need it for that way, but you can also use IIF. I actually had never heard of it for ages until a few months ago. One of those really helpful things that never appears in books for some odd reason. K

[riis]

Originally posted by sql_lall
One of those really helpful things that never appears in books for some odd reason. K

Maybe because it is terribly slow? I once thought it to be a handy function (compact code), but for some reason it is very slow. An if-then-else block is much faster.