lockers math problem


by T@P
Tags: lockers, math
T@P
T@P is offline
#1
Dec23-04, 03:09 PM
P: 270
there are 100 lockers lined up in a row, and for some unknown reason they are unlocked. for a similarly unknown reason there are 100 students lined up outside the hallway containing the 100 lockers. the first student goes and opens all the lockers. the second then goes and closes every second. the third either opens or closes every third locker, (changes the "state" of it) for example, the 6th locker is closed when the 3rd guy comes to it, so he opens it. after all 100 students go by, what lockers are open/closed? please note i dont think that you should list out all 100 lockers and their state, there is a pattern.
Phys.Org News Partner Science news on Phys.org
Simplicity is key to co-operative robots
Chemical vapor deposition used to grow atomic layer materials on top of each other
Earliest ancestor of land herbivores discovered
Bartholomew
Bartholomew is offline
#2
Dec23-04, 03:53 PM
P: 613
The state of each locker is altered a number of times equal to the total number of factors of the locker number. So the lockers with numbers that have an even number of factors (including 1) are closed, and the lockers with numbers that have an odd number of factors are open. (Not counting just prime factors, counting all factors, and numbering the lockers from 1)
NateTG
NateTG is offline
#3
Dec27-04, 12:18 PM
Sci Advisor
HW Helper
P: 2,538
Quote Quote by Bartholomew
...
What do all numbers that have an odd number have in common? It's a pretty well-known property...1,4,9...?

Bartholomew
Bartholomew is offline
#4
Dec27-04, 12:53 PM
P: 613

lockers math problem


That's cool!
Gokul43201
Gokul43201 is offline
#5
Dec28-04, 12:24 PM
Emeritus
Sci Advisor
PF Gold
Gokul43201's Avatar
P: 11,154
What do all numbers that have an odd number of factors have in common?
Bartholomew
Bartholomew is offline
#6
Dec28-04, 02:27 PM
P: 613
Of course, that's what he meant. I'm no expert, but: First you get the prime factorization of the number. Each factor can be generated by choosing some number of each prime factor (a number from 0 to the power of that factor) and multiplying them all together. So the total number of factors is (a + 1) * (b + 1) * (c + 1) ... where a, b, c, ... are the exponents on 2, 3, 5, ... in the prime factorization. So for this product to be odd, all of a + 1, b + 1, c + 1, ... must be odd, so all of a, b, c, ... must be even, so the original number is a perfect square (and vice versa, if it's a perfect square then it has an odd number of factors).
NateTG
NateTG is offline
#7
Dec28-04, 04:51 PM
Sci Advisor
HW Helper
P: 2,538
Quote Quote by Bartholomew
...
Nicely done. Yeah, Gokul I need to be more careful when I type/post.
Gokul43201
Gokul43201 is offline
#8
Dec29-04, 02:04 PM
Emeritus
Sci Advisor
PF Gold
Gokul43201's Avatar
P: 11,154
Quote Quote by Bartholomew
I'm no expert, but...
Me neither, but I believe that's how the experts do it too, but being experts they like to use fancy terms.

[tex]N = \Pi p_i ^{k_i} [/tex]

[tex] \tau (N) = \Pi (k_i + 1) [/tex]

[itex] \tau (N) [/itex], known simply as the tau function, is a multiplicative function that counts the number of divisors of a given number.

So, an "expert" might simply say that for [itex] \tau (N) [/itex] to be odd, all of [itex] k_i [/itex] must be even, or [itex] k_i = 2m_i [/itex]. Which gives [itex] N = \Pi p_i ^{2m_i} = (\Pi p_i ^{m_i} )^2 = M^2 [/itex].
ShawnD
ShawnD is offline
#9
Jan8-05, 02:35 PM
Sci Advisor
ShawnD's Avatar
P: 988
Is the answer 31? My physics teacher gave this problem as a bonus questions, so I made a C++ program to figure out all the perfect squares between 1 and 1000, and the program says the answer is 31.
I'll get an extra 10% on the next lab if I get this right, so it's kind of important that I get confirmation before Monday, January 10, 2005.
jamesrc
jamesrc is offline
#10
Jan8-05, 02:57 PM
Sci Advisor
PF Gold
P: 478
Select to read. (I'm editing to put into spoiler text because that's what other people did.)

Yes, presuming your question was for 1000 lockers (and students) and they all started off closed and they asked which ones were open after the process was over. (The original post was only for 100 lockers.) You didn't really need the progam, though: like the lay version of what Gokul said, any number with an odd number of factors will end up open, meaning all of the perfect square numbered doors will end up open (which you already know). So all you had to do was look at the square root of 1000 and truncate the decimal places (round down to the nearest integer) and that would be the answer (31).
ShawnD
ShawnD is offline
#11
Jan8-05, 03:08 PM
Sci Advisor
ShawnD's Avatar
P: 988
Quote Quote by jamesrc
So all you had to do was look at the square root of 1000 and truncate the decimal places (round down to the nearest integer) and that would be the answer (31).
Thanks for the confirmation. When I get some free time, I will look closer at Goku's stuff to see what it means or at least how he got that.

*edit
that spoiler text is still very visible in a quote box
Gokul43201
Gokul43201 is offline
#12
Jan8-05, 04:52 PM
Emeritus
Sci Advisor
PF Gold
Gokul43201's Avatar
P: 11,154
Quote Quote by ShawnD
When I get some free time, I will look closer at Goku's stuff to see what it means or at least how he got that.
I suggest you read Bart's explanation. It's in a form that's a lot simpler to absorb.


Register to reply

Related Discussions
tricky lockers... Brain Teasers 12