Here's a Hard One!(?)

Student 1 obviously start at locker 1,

Do student 2 start at 1 or 2? That is 1, 3, 5 . . . . or 2, 4 , 6 . . . . .

There are one thousand lockers and one thousand students in the school. The principal asks the first student to go to every locker and open it. Then he has the second student go to every second locker and close it. The third goes to every third locker and, if it is closed, he opens it, and if it is open, he closes it. The fourth student does this to every fourth locker, and so on. After the process is completed with the thousandth student, how many lockers are open?

43

I get 31

I did the following pascal program

var a : array [1..1000] of boolean;

z,t :Integer;

begin

fillchar (a,sizeof(a),0);

for z:= 1 to 1000 do

for t:= z to 1000 do if t mod z = 0 then a[t] := not a[t];

z:=0;

for t:= 1 to 1000 do if a[t] then inc(z);

writeln (z);

end.

I THINK the answer is ZERO. With Student #1, all 1000 are open, but by the time you get to Student #500, only 1 locker is open. The number remains 1 until 999, but the last Student ... #1000 closes it.

Just my assumption ... I'm anxious to know the answer.

Open Student

1000 1

500 2

333 3

250 4

200 5

166 6

142 7

125 8

111 9

100 10

90 11

83 12

76 13

71 14

66 15

62 16

58 17

55 18

52 19

50 20

47 21

45 22

43 23

41 24

40 25

38 26

37 27

35 28

34 29

33 30

32 31

31 32

30 33

29 34

28 35

27 36, 37

26 38

25 39, 40

24 41

23 42, 43

22 44, 45

21 46, 47

20 48, 49

19 50, 51, 52

18 53, 54, 55

17 56, 57, 58

16 59, … 62

15 63, … 66

14 67, … 71

13 72, … 76

12 77, … 83

11 84, … 90

10 91, … 99

9 100, … 111

8 112, … 124

7 125, … 142

6 143, … 166

5 167, … 199

4 200, … 249

3 250, … 333

2 334, … 499

1 500, … 999

0 1000

If every student start at locker no 1 the total opened after 1000 students will still be 31.

The answer can never be zero. Consider locker 2 (start at 1 option) - It is opened by student 1 and nobody else can touch it again.

Student 2 must go to 1, 3, 5, 7, 9 ,11, 13, 15 . . . . . .

Student 3 must go to 1,4,7,10,13,16 . . . . . . .

Student 4 must go to 1, 5, 9, 13, 17 . . . . . .

Student 5 must go to 1, 6, 11, 16, . . . . .

from the above it can be seen that box 2 and 5 will be open and 3, 4, 6 will be closed.

Always starting at 1 the open boxes will be 2, 5, 10 , 17, 26 . . . . .

Starting at the box with students number the open boxes will be 1, 4, 9, 16, 25 . . .

Hi,

You are ABSOLUTELY CORRECT !!!

Damn ... that's why its WISE to COLABORATE

Thanks,

... and more ...

the open 31 lockers are numbers:

1, 4, 9, 16, 25, 36 ... 961

How cool is that

Have you noticed that the gap is increasing by 2 every interval?

HI guys!

Hmmm...

1000 lockers

1000 students

1) The first student Opens all the lockers.(all lockers will be opened)

2) The second student will go to EVERY 2nd locker and CLOSES IT.(50% of the lockers are closed)

3) The third student will go to EVERY 3rd locker and, if its closed, he opens it, and if its open, he will close it.(the problem starts here )

4) The fourth student will go to EVERY 4th locker and, if its closed, he opens it, and if its open, he will close it.(confusion starts here )

5) all the remaining students will do the same reffering the position of locker( where they are going to start) to the student's position(5th, 6th,...etc)

(Nose bleeding starts here )

Take care!

Hi Optimusprime!

Sorry! Fell asleep at 783.

Mark

Let me repeat my answer as in post 4

Number of open lockers 31

The open lockers are
Locker no 1
Locker no 4 Closed 2
Locker no 9 Closed 4
Locker no 16 Closed 6
Locker no 25 Closed 8
Locker no 36 Closed 10
Locker no 49 Closed 12
Locker no 64 Closed 14
Locker no 81 Closed 16
Locker no 100 Closed 18
Locker no 121 Closed 20
Locker no 144 Closed 22
Locker no 169 Closed 24
Locker no 196 Closed 26
Locker no 225 Closed 28
Locker no 256 Closed 30
Locker no 289 Closed 32
Locker no 324 Closed 34
Locker no 361 Closed 36
Locker no 400 Closed 38
Locker no 441 Closed 40
Locker no 484 Closed 42
Locker no 529 Closed 44
Locker no 576 Closed 46
Locker no 625 Closed 48
Locker no 676 Closed 50
Locker no 729 Closed 52
Locker no 784 Closed 54
Locker no 841 Closed 56
Locker no 900 Closed 58
Locker no 961 Closed 60

An odd number of factors will indicate an open locker

I made a report on 25 students /lockers to explain

Number of lockers / students = 25

Locker 1 touched by 1, Open - odd no of factors
Locker 2 touched by 1, 2, Closed - even no of factors
Locker 3 touched by 1, 3, Closed - even no of factors
Locker 4 touched by 1, 2, 4, Open - odd no of factors
Locker 5 touched by 1, 5, Closed - even no of factors
Locker 6 touched by 1, 2, 3, 6, Closed - even no of factors
Locker 7 touched by 1, 7, Closed - even no of factors
Locker 8 touched by 1, 2, 4, 8, Closed - even no of factors
Locker 9 touched by 1, 3, 9, Open - odd no of factors
Locker 10 touched by 1, 2, 5, 10, Closed - even no of factors
Locker 11 touched by 1, 11, Closed - even no of factors
Locker 12 touched by 1, 2, 3, 4, 6, 12, Closed - even no of factors
Locker 13 touched by 1, 13, Closed - even no of factors
Locker 14 touched by 1, 2, 7, 14, Closed - even no of factors
Locker 15 touched by 1, 3, 5, 15, Closed - even no of factors
Locker 16 touched by 1, 2, 4, 8, 16, Open - odd no of factors
Locker 17 touched by 1, 17, Closed - even no of factors
Locker 18 touched by 1, 2, 3, 6, 9, 18, Closed - even no of factors
Locker 19 touched by 1, 19, Closed - even no of factors
Locker 20 touched by 1, 2, 4, 5, 10, 20, Closed - even no of factors
Locker 21 touched by 1, 3, 7, 21, Closed - even no of factors
Locker 22 touched by 1, 2, 11, 22, Closed - even no of factors
Locker 23 touched by 1, 23, Closed - even no of factors
Locker 24 touched by 1, 2, 3, 4, 6, 8, 12, 24, Closed - even no of factors
Locker 25 touched by 1, 5, 25, Open - odd no of factors

Report on open lockers
Locker no 1
Locker no 4 Closed 2
Locker no 9 Closed 4
Locker no 16 Closed 6
Locker no 25 Closed 8

Number of open lockers out of 25 = 5

Optimusprime please indicate where I am wrong.

Locker 1 touched by 1, Open - odd no of factors
Locker 2 touched by 1, 2, Closed - even no of factors
Locker 3 touched by 1, 3, Closed - even no of factors
Locker 4 touched by 1, 2, 4, Open - odd no of factors

...

It seems as a bit of magic that numbers which are perfect squares have odd number of factors (including 1 and the number itself as you seem to assume above), but it is not!

If a N number is a prime, then it has even number of factors (1 and N). If it is not, then there will be a divisor, say x, which when multiplied by another integer y (x<=N and y<=N) will produce the number: N=xy. Then y is also a divisor, as it also holds: N=yx. This makes factors even EXCEPT, when x=y, i.e. N=x², in which case we take the x,y pair only once.

Concluding, as all perfect squares have odd number of factors, the number of "flips" of the locker doors will be odd and consequently doors will be open on locations 1, 4, 9, 16, ... n²

Hi tkot

I was a bit slow in realising the link to squares but eventually also got it at post 15.

Do You agree with the solution at #15?

Open lockers = integer part of the square root of the number of lockers

Would 320 open for 102400 lockers be true?

Is there a situation where this can be used?

Is there an answer for Mark at #16?

Hi Hendrik

What I wanted to say in my post is that the locker doors at locations constituting perfect squares will experience odd number of flips, so eventually will result being open.

Let me rephrase it: As you already mentioned in a previous post, locker 2 will be touched only be student No2 and nobody else. Lets generalize: The n-th locker will have its final status after n-th student has tampered with it, and will stay this way for ever. Therefore, however many the students are, or however many the doors are, we just need to see how many divisors correspond to each door index number, to see how many students will visit it, and consequently how many flips will suffer. If these flips are odd, then the door will stay open, however long the "ritual" may last thereafter. As it appears, only perfect squares have odd number of divisors, so...

Now, back to your question, which is the original question: " how many door are open?". In #15 you are right. Indeed, how many perfect squares we can fit up to number N? These are the numbers: 1²=1, 2²=4, 3²=9, ... (√N)²=N . So the number of those numbers is √N. We assume that √N is integer, otherwise we crop it down to the closest integer so that (√N)² won't exceed N.

AND (or however ), it only works for the final answer when the number of students and the number of doors are the same, right?

Indeed, in order for this analysis to be true, we need at least n students to know the final configuration of the n-th door. So in order to know the final configuration of the 1000th door we need at least 1000 students. If we add the assumption that no student should remain idle (there must be at least a door to play with), then the numbers of doors and students must be equal.

First student opens all lockers.

Second student closes all even numbered lockers.

Third student closes all lockers with odd numbers evenly divisible by 3, and opens the even numbered lockers with numbers also evenly divisible by 3.

Fourth student opens all even numbered lockers with numbers evenly divisible by 4, unless the number is also evenly divisible by 3, then he closes it.

Fifth student goes only to those lockers ending with 0 or 5. Here's where it starts to get complicated, for a while.

The higher the student's number is, the lower the number of lockers he will have to open or close. Students 500 through 1000 have only one locker to open or close.

More to come...

It is actually very easily calculated.

Take the integer part of the square root of the number.

The square root of 1000 = 31.6227 = 31

Only numbers with exact square roots will have an odd number of factors. (up to 1000 at least)

Hi, Hendrik!

What is the rule of calculation that you are using to decide on this formula? Sorry, I'm not a statistician and am only familiar with a few basic rules for calculating combinations and permutations. Is it a rule, or just a logical process you derived from the challenge?

Mark

Hi Mark

No Rule that I can think of. The question don't seem to have a real world application.

I started by simulating the situation with a small program at #4.

Because of no response the computer prepared a report at #13.

Looking at the data made me realize the solution.

PS Students will devise something like that. There were 2 fire hoses on each floor. On the way to dinner the first student passing will open the valve a bit. the next closes it. Open close . . . The result was usually water cascading down the steps.

answer is 31 if every student starts with 1st locker

rule:

no of open lockers X = sq.root (no of total lockers - 1) (round figure)

open locker numbers: sq(1 to X) + 1

for example:

for 1000 lockers

X = sq.root(1000- 1) = sq. root 999 = 31

open locker no: sq(1) +1 = 2

sq(2) +1 = 5 and so on.......

Hello, sanimisra!

Great! Now it can be done for any number of repetitive actions provided the actors are the same number as the items acted upon, and we can always count the perfect squares as having been acted upon an uneven number of times.

For example, 673 students and 673 lockers acted upon means that √(N-1) = √(673 - 1) = √672 = 25.92 = 25 will be the number of lockers acted upon an uneven number of times, and the actual numbers of the lockers acted upon an uneven number of times will be the perfect squares #1,#4,#9,#16,#25, etc. up to and including #625. The remainder have all been acted upon an even number of times.

Right?

Mark

yes. just that 1, 4, 9 , 16 will be the answer if 1st student starts from locker 1, 2nd student from locker 2 and so on..

formulae will be then directly the square of row no.

that is, sq(1), sq(2), .........

2,5,10, 17... will be locker no if every student starts from 1st locker.

same formulae may not be applicable to both cases, but if you draw a Matrix, u l find that it follows all diagonal elements in both cases.

this is applicable to any no of student- locker system provided no of student = no of locker.

glad to see your reply.. i thought no body will reply as this question was posted 2 years back.

yes. just that 1, 4, 9 , 16 will be the answer if 1st student starts from locker 1, 2nd student from locker 2 and so on..

formulae will be then directly the square of row no.

that is, sq(1), sq(2), .........

2,5,10, 17... will be locker no if every student starts from 1st locker.

same formulae may not be applicable to both cases, but if you draw a Matrix, u l find that it follows all diagonal elements in both cases.

this is applicable to any no of student- locker system provided no of student = no of locker.

glad to see your reply.. i thought no body will reply as this question was posted 2 years back.

yes. just that 1, 4, 9 , 16 will be the answer if 1st student starts from locker 1, 2nd student from locker 2 and so on..

formulae will be then directly the square of row no.

that is, sq(1), sq(2), .........

2,5,10, 17... will be locker no if every student starts from 1st locker.

same formulae may not be applicable to both cases, but if you draw a Matrix, u l find that it follows all diagonal elements in both cases.

this is applicable to any no of student- locker system provided no of student = no of locker.

glad to see your reply.. i thought no body will reply as this question was posted 2 years back.