Lockers

[hilbert]

Our local High School posed the following to High School students:

There are 1000 Lockers in a High School with 1000 students.
The first student opens all lockers.
The second student closes all even number lockers (2,4,6,8...)
The third student toggles every third locker. (Toggle= Close if open or Open if closed)
The fourth student toggles every fourth locker. (4,8,12,...)
The fifth student toggles every fifth locker (5,10,15...)
...
The nth student toggles every nth locker (n,2n,3n...)
This continues until all 1000 students have had a turn.
==================================================
Question 1 : How many lockers are open at the end of this excercise?

Question 2: What is the general answer for N lockers and N students?

[AlvaroDíaz]

Answer to question 1, but can't generalize yet, but it is, following Eratostenes, the nearest by the left prime of the square root of the N.

Regards. Alvaro.

[TomGutman]

>>following Eratostenes<<

No. Eratostenes only sieves out primes. The process here uses all numbers, composites as well as primes. Whether a door ends up open or closed depends on wheter it has an even or odd number of divisors.
__________________
� � � � Tom Gutman

[AlvaroDíaz]

For this is for what I only answer the question 1 and make a conjeture about question 2.

Regards. Alvaro.

[AlvaroDíaz]

On 4/1/2010 10:39:26 PM, Tom_Gutman wrote:
>>>following Eratostenes<<
>
>No. Eratostenes only sieves
>out primes. The process here
>uses all numbers, composites
>as well as primes. Whether a
>door ends up open or closed
>depends on wheter it has an
>even or odd number of
>divisors.

This method sieves perfect square numbers.

Regards. Alvaro.

[TomGutman]

AH, yes. Only perfect squares have an odd number of divisors.
__________________
� � � � Tom Gutman

[NormalVector]

I don't know if the OP has moved on or not, but I decided to give it a try. Came up with a similar method and arrived at the same answer as the others. Not sure on question 2 though. : )

[jeanGiraud]

Thanks Stephen,

Looks interesting for spare time. Hard to visualized the entire process.

and especially where it turns recursive. I was wondering [in case you

are not sure of the solutio] if you could plug the first numbers in the

Neil Sloane/Simon Plouffe series. If there is a series, therefore a

solving module, it will find among their ziliion series solutions.

Try that one !

jmG

[IRstuff]

The triangle problem is old and a trivial problem:

The triangles are not similar to the bounding triangle. The "missing " square is the same area as the mismatch between the two small triangles and the bounding triangle.

[jeanGiraud]

" ... old and trivial"

_____________________________________

Old for sure, but your zigzag image tells nothing worth for answer.

jmG

[NormalVector]

Well you guys are going to think I went too far into this problem but it's summer and I have a lot of time on my hands...

Anyway, I plotted out "Open Lockers vs. N" and then did a non-linear least squares regression to find the general function. I was going to whip out my Newton-Raphson solver but that would take up a lot of space and I thought it would be better just to use the "Find" solve block. It ended up matching the data very well. As for JMG's question, désolé mais je ne suis pas familier avec le "Sloane Plouffe Series" et alors je ne peux pas le faire.

Definitely an interesting problem to consider in spare time.

[jeanGiraud]

Stephen Guimond wrote:

Well you guys are going to think I went too far into this problem but it's summer and I have a lot of time on my hands...

Anyway, I plotted out "Open Lockers vs. N" and then did a non-linear least squares regression to find the general function. I was going to whip out my Newton-Raphson solver but that would take up a lot of space and I thought it would be better just to use the "Find" solve block. It ended up matching the data very well. As for JMG's question, désolé mais je ne suis pas familier avec le "Sloane Plouffe Series" et alors je ne peux pas le faire.

Definitely an interesting problem to consider in spare time.

Stepen,

Simon and Neil are world wide authorities in "combinatorics". They have both replied very quick to me. From what I read, it looks like that Simon p

is the sole algorithm in modern computing machinery. An interesting problem, the lockers. I had removed my first replies as the source was all zombie

from spoiled interpretation. Yours and Alvaro do it accordingly to the Java link. You have three choices for the "fit" .

A visit worth the time spent: Neil sloane Simon Plouffe.

Avec cette chaleur, j'espère les tomates environ 2 semaines .

Jean

I was thinking of a 3D patch plot to imitate the java ... RemToDo.

[RichardJ]

Try floor(sqrt(N))

I didn't try to derive that algebraically, but it seems to work.

[NormalVector]

I'm not on a PC with MathCAD to check it right now, but I think that floor(sqrt(N)) matches the data perfectly. Cool!

[jeanGiraud]

Stephen,

Considering that the SQRT(u) is exact for continuous data,

[not your approximation, just SQRT], then apply trunc(SQRT(u))

floor(SQRT(u)) does the same ... either one are worth for the

"state logic" in the range. This kind of "state range logic"

dates back to the very first microprocessor based analog

and logic controller [1971]. There is a lot +++ logic !

Jean

[NormalVector]

Yeah that makes sense. The "noise" (jumps and discontinuities) shifted my approximation away from the actual funciton and floor(sqrt(N)) is a better theoretical fit.