Math Challenge

Toggle sidebar Toggle sidebar
midwestfisherman

midwestfisherman

Diamond Member
Dec 6, 2003
3,564
8
81
Just wondering if anyone can solve this problem...

Imagine you are at a school that still has student lockers. There are 1000 lockers, all shut and unlocked, and 1000 students.

Here's the problem:

1. Suppose the first student goes along the row and opens every locker.

The second student then goes along and shuts every locker divisible by the number 2.

1. The third student changes the state of every third locker divisible by the number 3. (If the locker is open the student shuts it, and if the locker is closed the student opens it.)

2. The fourth student changes the state of every fourth locker divisible by the number 4.

Imagine that this continues until the thousand students have followed the pattern with the thousand lockers. At the end, which lockers will be open and which will be closed? Why?

Good luck! :D
 
O

opticalmace

Golden Member
Oct 22, 2003
1,841
0
0
Originally posted by: minendo
Only the first one.
Click to expand...

No way.

Look at locker number 4 for example:

Opened by student one
Closed by student two
Opened by student four.

So it won't just be the first one.
 
minendo

minendo

Elite Member
Aug 31, 2001
35,560
22
81
Originally posted by: opticalmace
Originally posted by: minendo
Only the first one.
Click to expand...

No way.

Look at locker number 4 for example:

Opened by student one
Closed by student two
Opened by student four.

So it won't just be the first one.
Click to expand...
Yeah, just noticed that. Missed the part about it being opened if closed.

:eek:
 
O

opticalmace

Golden Member
Oct 22, 2003
1,841
0
0
Originally posted by: minendo
Originally posted by: opticalmace
Originally posted by: minendo
Only the first one.
Click to expand...

No way.

Look at locker number 4 for example:

Opened by student one
Closed by student two
Opened by student four.

So it won't just be the first one.
Click to expand...
Yeah, just noticed that. Missed the part about it being opened if closed.

:eek:
Click to expand...

Hehe. :beer: anyway. :D
 
M

marquee

Banned
Aug 25, 2003
574
0
0
lockers with numbers that are perfect squares. since those are the only ones with an odd number of factors
 
U

upsciLLion

Diamond Member
Feb 21, 2001
5,947
1
81
Originally posted by: midwestfisherman
Just wondering if anyone can solve this problem...

Imagine you are at a school that still has student lockers. There are 1000 lockers, all shut and unlocked, and 1000 students.

Here's the problem:

1. Suppose the first student goes along the row and opens every locker.

The second student then goes along and shuts every locker divisible by the number 2.

1. The third student changes the state of every third locker divisible by the number 3. (If the locker is open the student shuts it, and if the locker is closed the student opens it.)

2. The fourth student changes the state of every fourth locker divisible by the number 4.

Imagine that this continues until the thousand students have followed the pattern with the thousand lockers. At the end, which lockers will be open and which will be closed? Why?

Good luck! :D
Click to expand...

I'm pretty sure the prime numbered ones will be open. As for the rest, I'm not completely sure. Little bit sleep still.
 
U

upsciLLion

Diamond Member
Feb 21, 2001
5,947
1
81
Originally posted by: marquee
Originally posted by: minendo
I think I have it now.

All perfect squares?
Click to expand...

beat ya to it, i win ;)
Click to expand...

Certain ones can be changed more than once. E.g. 2^2 = 4^1. The prime ones aren't touched except for the first time through. The primes p^p every pth time will be closed since they are changed once more. This problem has something to do with the prime divisors, but since the numbers n^n are only changed every nth time, it puts a very interesting spin on things.
 
N

notfred

Lifer
Feb 12, 2001
38,241
4
0
These number lockers will be opened:
1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 441, 484, 529, 576, 625, 676, 729, 784, 841, 900, 961

Why?

#!/usr/bin/perl

# Create a list of lockers
my @locker_states;

#Start them out all closed
for(my $ii = 0; $ii < 1000; $ii++){
$locker_states[$ii] = "closed";
}

# Have each student open or close lockers.
for(my $ii = 0; $ii < 1000; $ii++){ # $ii <- person number
for(my $jj = 0; $jj < 1000; $jj++){ # $jj <- locker number

if((($jj+1) % ($ii+1)) == 0){
# Switch states.
if($locker_states[$jj] eq "closed"){
$locker_states[$jj] = "opened";
}
elsif($locker_states[$jj] eq "opened"){
$locker_states[$jj] = "closed";
}
}

}
}

# Print a list of all opened lockers.
for(my $ii = 0; $ii < 1000; $ii++){
if($locker_states[$ii] eq "opened"){
print $ii + 1, ", ";
}
}
 
B

BigJ

Lifer
Nov 18, 2001
21,330
1
81
Originally posted by: notfred
These number lockers will be opened:
1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 441, 484, 529, 576, 625, 676, 729, 784, 841, 900, 961

Why?

#!/usr/bin/perl

# Create a list of lockers
my @locker_states;

#Start them out all closed
for(my $ii = 0; $ii < 1000; $ii++){
$locker_states[$ii] = "closed";
}

# Have each student open or close lockers.
for(my $ii = 0; $ii < 1000; $ii++){ # $ii <- person number
for(my $jj = 0; $jj < 1000; $jj++){ # $jj <- locker number

if((($jj+1) % ($ii+1)) == 0){
# Switch states.
if($locker_states[$jj] eq "closed"){
$locker_states[$jj] = "opened";
}
elsif($locker_states[$jj] eq "opened"){
$locker_states[$jj] = "closed";
}
}

}
}

# Print a list of all opened lockers.
for(my $ii = 0; $ii < 1000; $ii++){
if($locker_states[$ii] eq "opened"){
print $ii + 1, ", ";
}
}
Click to expand...

And this is why one day programmers will rule the earth :)
 
M

marquee

Banned
Aug 25, 2003
574
0
0
Originally posted by: upsciLLion
Originally posted by: marquee
Originally posted by: minendo
I think I have it now.

All perfect squares?
Click to expand...

beat ya to it, i win ;)
Click to expand...

Certain ones can be changed more than once. E.g. 2^2 = 4^1. The prime ones aren't touched except for the first time through. The primes p^p every pth time will be closed since they are changed once more. This problem has something to do with the prime divisors, but since the numbers n^n are only changed every nth time, it puts a very interesting spin on things.
Click to expand...

i dont think it has anything to do with primes. and if you check notfred's results, you'll see they're indeed all the perfect squares
 
A

Argo

Lifer
Apr 8, 2000
10,045
0
0
Here's scientific explanation of notfreds result:

Every value is divisible by even set of numbers. 24 = 24 * 1, 24 = 12 * 2, 24 = 6 * 4, 24 = 8 * 3. Every break down has two values, and hence their sum will be even. So every number's state will be changed even number of times, and thus remain unchanged. The exception being perfect squares, since they'll have one breakdown where the number repeats: 25 = 5 * 5. We can count 5 only once. Hence those lockers will change their state at the end of the procedure. Hope this makes sense.
 
D

d0ofy

Golden Member
Oct 11, 1999
1,404
0
0
Every locker will be open because of step 1.
All of the lockers are unnumbered and only step 1 has an effect.
 
P

przero

Platinum Member
Dec 30, 2000
2,060
0
0
U sure that's correct? Locker #16 is opened by student 1, shut by student 2, and then not touched again.
 
minendo

minendo

Elite Member
Aug 31, 2001
35,560
22
81
Originally posted by: przero
U sure that's correct? Locker #16 is opened by student 1, shut by student 2, and then not touched again.
Click to expand...
Wrong. Student 4 would touch it, as would student 8, and student 16.

 
You must log in or register to reply here.

TRENDING THREADS

COMPANY
RESOURCES
FOLLOW
Top Bottom