YOU WERE LOOKING FOR: 100 Locker Problem Answer
When you deal with square numbers there are an odd number of factors because one of the pairs is a repeated number. When a person walks through the lockers and changes their positions, they represent a factor of the number. For instance person 4...
You can put this solution on YOUR website! There is no real formula for this type of problem. You need to break this problem down into smaller parts, and then generalize a bigger picture from those parts. Lets say we only have 10 people and 10...
These factors dont cancel so it stays open. It turns out that every number, except the perfect squares, has an even number of factors. All of these factors are paired up, which means there are an even number of factors. So there are only 3 factors in this number. This is true for all perfect squares, since there's always a repeated factor of the square root value. So every perfect square locker number will remain open because they have an odd number of factors. This makes it easier to count the number of open lockers since we only have to find perfect squares. So here's the list of perfect squares and open lockers : 1.
He wanted to leave all of his money to you, but he knew that if he did, your relatives would pester you forever. So he is banking on the fact that he taught you everything you need to know about riddles. Your uncle left the following note in his will: "I have created a puzzle. If all of you answer it together, you will share the money evenly. However, if you are the first to find the pattern and solve the problem without going through all of the leg work, you will get the entire inheritance all to yourself. Good luck. He explains: Every relative is assigned a number from 1 to Heir 1 will open every locker. Heir 2 will then close every second locker. Heir 3 will change the status of every third locker, specifically if it's open, she'll close it, but if it's closed, she'll open it.
This pattern will continue until all of you have gone. The words in the lockers that remain open at the end will help you crack the code for the safe. Before cousin Thaddeus can even start down the line, you step forward and tell the lawyer you know which lockers will remain open. But how? Pause the video now if you want to figure it out for yourself! Answer in: 3 Answer in: 2 Answer in: 1 The key is realizing that the number of times a locker is touched is the same as the number of factors in the locker number. For example, in locker 6, Person 1 will open it, Person 2 will close it, Person 3 will open it, and Person 6 will close it. The numbers 1, 2, 3, and 6 are the factors of 6. So when a locker has an even number of factors it will remain closed, and when it has an odd number of factors, it will remain open. Most of the lockers have an even number of factors, which makes sense because factors naturally pair up. In fact, the only lockers that have an odd number of factors are perfect squares because those have one factor that when multiplied by itself equals the number.
For Locker 9, 1 will open it, 3 will close, and 9 will open it. Therefore, every locker that is a perfect square will remain open. You know that these ten lockers are the solution, so you open them immediately and read the words inside: "The code is the first five lockers touched only twice. So the code is The lawyer brings you to the safe, and you claim your inheritance. Too bad your relatives were always too busy being nasty to each other to pay attention to your eccentric uncle's riddles.
We hope you enjoyed and learned from the problem. For those who missed it, here was the challenge problem: Imagine lockers numbered 1 to with students lined up in front of those lockers: The first student opens every locker. The second student closes every 2nd locker. The 4th student changes every fourth locker. The 5th student changes every 5th locker. That same pattern continues for all students. Cool, huh? We hope you realized that lockers are only touched by students who are factors of that locker number, i. Student 1 opens it and student 5 closes it. In fact, because factors come in pairs, the first student factor will open it and the corresponding factor student closes it.
At first, maybe you thought every locker would be closed because factors come in pairs. But there was a twist… Here are a couple of ways you could have gotten there: Method 1: Solve a Simpler Problem Start with just 20 lockers and try to find a pattern. They are all open. Of the first 20 lockers, locker s 1, 4, 9, and 16 are left open. Those are perfect squares. You can extend that pattern to identify the remaining open lockers. Lockers 1, 4, 9, 16, 25, 36, 49, 64, 81, and are left open! Method 2: Who Touches Which Lockers Identifying which students touch which lockers is a little less of a brute-force approach and would likely have gotten you to the solution a little more quickly. The only student who touches locker 1 is student 1. Student 1 opens the locker, and since no one else touches it, it will be left open at the end. Consider locker 2. Student 1 opens the locker, and student 2 closes it. No one else touches the locker, so it will be closed.
Consider locker Students 1 opens the locker. Student 2 closes it. Students 3 and 4 skip right by it. Student 5 opens it. Students 6, 7, 8, and 9 skip right by it. And student 10 closes it. Locker 10 will be closed. Mental Milestone 1: After looking at several lockers, you should notice that lockers are only changed by student numbers that are factors of the locker number. In other words, locker 12 is changed by students 1, 2, 3, 4, 6, and Mental Milestone 2: You should also have noticed that factors always come in pairs. This means that for every student who opens a locker, there is another student who closes it.
For locker 12, student 1 opens it, but student 12 closes it later. Student 2 opens it, but student 6 closes it later. Student 3 opens it, but student 4 closes it later. By this logic, every locker would be closed. But there are exceptions! Student 1 opens it. Student 5 closes it. Student 25 opens it.
The locker will be left open, but why? In this case, the factors do not come in pairs. One and 25 are a pair, but five times five is also Five only counts as one factor. This causes the open-close pattern to be thrown off. Locker 25 is left open. This means that only perfect square lockers will be left open. Locker s 1, 4, 9, 16, 25, 36, 49, 64, 81, and are left open! Her solution was simple, precise, and just as important, correct. In fact, I like her solution better than the explanations I provided above.
You can put this solution on YOUR website! There is no real formula for this type of problem. You need to break this problem down into smaller parts, and then generalize a bigger picture from those parts. Lets say we only have 10 people and 10 lockers. If person 1 opens all of the lockers, they're all open. Now person 2 goes, and all of the even numbered lockers are shut. Now it's 3's turn: locker 3 is shut, locker 6 is open again, and 9 is shut. Four takes a shot and locker 4 and 8 are reopened. Students 6, 7, 8, and 10 only shut locker 6, 7,8, and 10 respectively; while person 9 opens locker 9.
So if we look at say locker 6, person 1 opens it, person 2 closes it, person 3 opens it, and finally person 6 closes it. So there are 4 people who interact with it notice how its an even number. While with locker 4, only students 1,2,4 touch it, and it stays open. So by this reasoning, if an even number of people touch it, it stays closed. If an odd number of people touch it, it stays open. To find out how many people touch it, we simply find the number of factors the number has. With 6 there are 4 factors: 1,2,3,6. The four factors simply cancel each other out one action of opening is undone by another action of closing.
While the number 4 has 3 factors: 1,2,4. These factors dont cancel so it stays open. It turns out that every number, except the perfect squares, has an even number of factors. All of these factors are paired up, which means there are an even number of factors. So there are only 3 factors in this number. This is true for all perfect squares, since there's always a repeated factor of the square root value. So every perfect square locker number will remain open because they have an odd number of factors. This makes it easier to count the number of open lockers since we only have to find perfect squares.
The Locker Problem and Unique Factorization Posted by gtmath Wednesday, May 6, 2 comments There is a hallway with lockers, numbered 1 through They are all closed to begin with. There are also kids, numbered 1 through Which lockers remain open at the end? I've heard that this one is actually an interview question, though no one has ever asked it to me So kid 1 runs down the hallway and opens all multiples of 1 i. Kid number 2 then goes and closes 2, 4, 6, etc.
Now, kid 3 visits 3, 6, 9, etc. So he'll close 3 which kid 1 opened , open 6 opened by 1 then closed by 2 , close 9 opened by 1 , etc. It's not going to be fast to go through each kid and write it out, though that would get you the answer. The answer's the same in each case, and it's pretty cool. To get there, start by considering a given locker- let's look at 48 as an example.
Kids 1, 2, 3, 4, 6, 8, 12, 16, 24, and 48, or all the factors of 48, are going to visit this locker. Since there are 10 factors, the door will end up closed and it will be opened then closed again 5 times in the process. Now, this is where it gets good. You can see from the example, or any other example you work through, that a locker will end up closed if it has an even number of visitors, or an even number of factors. Almost all the lockers have an even number of factors, because almost every factor has a "buddy. Which factors don't have a buddy? It's the ones where the buddy is itself. Take locker 64 as an example. The factors are 1, 2, 4, 8, 16, 32, and So this locker will end up open. It will get opened and closed again 3 times, but will be opened one additional time and remain open at the end. The only numbers with an odd number of factors like this are the perfect squares, i.
So we got the answer; it's the perfect squares. Good job. If you want to read the real nerdy stuff, go on; otherwise, thanks for reading. Unique Prime Factorization The solution to the problem above relied on the fact that any positive integer can be written as the product of two factors, sometimes in multiple ways. A prime number is a positive integer that has no factors other than 1 and itself. Any other positive integer is a composite number and can be written as a product of factors other than 1 and itself. The first few primes are 1, 2, 3, 5, 7, 11, 13, 17, etc. There are infinitely many primes. This isn't news- the proof outlined above is allegedly a modification of a proof by Euclid. Ok, back to business. We were talking about the locker problem and factoring. However, once we break it down to powers of primes, there is only one way to do it, called a prime factorization. Remember these? This discussion is bringing us to the Fundamental Theorem of Arithmetic.
I'm going to show the proof below and then leave you a little food for thought about how this relates to the number of visitors at our lockers above. Theorem Fundamental Theorem of Arithmetic : Every positive integer greater than 1 can be factored into a product of powers of primes. Furthermore, this prime factorization is unique i. Proof: We have to prove that such a prime factorization exists, and then that it is unique. Luckily, it's already been done on Wikipedia, so I'll regurgitate their proof below. Existence: This part can be proved by induction. Uniqueness: There is a more intuitive way to do this that uses Euclid's Lemma, but I'll show the way that doesn't assume this lemma. We know now that every positive integer greater than 1 has at least one prime factorization.
September 16, This is probably one of the best math problems I give my fifth grade students. It goes like this: There are lockers in the long front hall of our school. Each August, the custodians add a fresh coat of paint to the lockers and replace any of the broken number plates. The lockers are numbered from 1 to When the students arrive on the first day, they decide to celebrate the start of the school year with our school tradition. The first student inside runs down the hall opening all of the lockers. The second student runs down the hall closing every second locker, beginning with locker number 2. The third student reverses the position of ever third locker, beginning with locker number 3.
If the locker is open, she closes it. The fourth student changes the position of every fourth locker, beginning with number 4. This continues until the th student has a turn, changing the position of the th locker. At the end of this ritual, which locker doors are open? Why are the open lockers left open? Which patterns emerged in your work? After a week of working on this problem with their partner, they write up what they discovered on posters. I have them include these four sections: 1. Restate the problem 3. Answer 4. Also, students ask comments or give feedback to the groups that present. Here are some of their posters.
I have often told people that, believe it or not, they could find the answer by searching the Ask Dr. But I prefer to give them a reference to one of the answers in which we gave only hints, because this is a fun problem to discover the answer for yourself. Tiny hints Here is a question from , which asked about two problem, the first of which is our subject: Word Problem Hints 1 There are lockers numbered 1 - Suppose you open all of the lockers, then close every other locker. Then, for every third locker, you close each opened locker and open each closed locker. You follow the same pattern for every fourth locker, every fifth locker, and so on up to every thousandth locker.
No comments:
Post a Comment