Math Is Fun Forum

naturewild

Member

Registered: 2005-12-04

Posts: 30

Discreet proof help needed

1) Prove that no square integer number can have a remainder of 3 when divided by 5

2) A school has 1000 students, and their lockers, which are numbered from 1 to 1000, are all closed, The first student opens all the lockers. The second student closes every second locker, beginning with her locker #2. The third student CHANGES the state of every third locker, beginning with locker #3, which means a locked locker becomes open and an open locker becomes closed. This carries on until all 1000 students had their turn.

Which lockers are open and why?

After some work, I think the locker with perfect square numbers are open. So locker #1, 4, 9, 16, 25 etc are open. But I dont know how to prove this and it might not work for numbers within 900-1000.

Also, I need help solving the first problem in this thread :

http://www.mathsisfun.com/forum/viewtopic.php?id=2859

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Discreet proof help needed

1. Since we want to show a remainder when dividing by 5, we must first get something that is divisble by 5.  So lets consider the 5 cases:

n = 5k
n = 5k + 1
n = 5k + 2
n = 5k + 3
n = 5k + 4

Note this covers all possible values for n.  Now lets go through them one by one:

n = 5k.  Then n^2 = 25k^2, which has a remainder of 0 when divided by 5.

n = 5k + 1.  Then n^2 = 25k^2 + 10k + 1 = 5(5k^2 + 2) + 1, which has a remainder of 1 when divided by 5.

Go through the others.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

John E. Franklin

Member

Registered: 2005-08-29

Posts: 3,588

Re: Discreet proof help needed

I really like the locker question.  I am so tempted just to program it and get a result, but that's kind of cheating isn't it.  I could show the results graphically after each student inorder to learn.
Wouldn't all the prime numbered doors be shut, and all those with and even number of factors like #2 ( 1 & 2) the door would be closed, and those with an odd number of factors like locker number 9 (1 & 3 & 9) would be open? And the prime numbers would all have an even number of factors (1 & #), so the door would be closed?

---

igloo myrtilles fourmis

John E. Franklin

Member

Registered: 2005-08-29

Posts: 3,588

Re: Discreet proof help needed

I am beginning to think you are right about perfect squares having an odd number of factors, so doors open because the square root factor is only counted once, and all the other factors are paired up.  Nice work!

---

igloo myrtilles fourmis

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: Discreet proof help needed

I've seen a variation of the 2nd puzzle where all the students change the state of the locker, instead of it being a rota of open, close, change, like it is here.

The answer to that was indeed that all the square lockers were open, because they had an odd number of factors, but this one will have a different answer.

If nothing else, the lockers numbered above 500 will have a pattern of open, close, something.

---

Why did the vector cross the road?
It wanted to be normal.