My brother's MATH assignment
My brother asked me this morning to help him in his "weird" math assignment. Their teacher is asking them to solve a problem that is more likely to be given in a programming competition than in a high school math exam.
Here's how it goes:
In a class of 100 students, the student to locker ratio is 1:1. Each locker door are numbered from 1 to 100. The students are asked to open or close the lockers based on a given rule.
The rule is simple. All students must line up in a queue. The Nth student must open/close all lockers having a locker number that is a multiple of N. If a locker is initially closed, they should open it, else they should close it. All lockers are closed at the start.
To give you an example. The first student will open all the lockers (since all numbers are divisible by 1). The next student will close all the even numbered lockers. The third student will close locker#3, open locker#6, close locker#9, so on and so forth.
You are to determine how many lockers will be left opened after all the students are finished.
Whoa! It's an Algo problem. After hearing about this, the first thing that came into my mind is to create a program that will simulate the activity. Apparently, my brother did something on paper (which reminded me of the assignment we did when we discussed "Sieve of Erastosthenes" in High School) but he gave up because he lost count. My dad has been trying to solve extract a pattern out of a chart that he's using to simulate the activity (Haha! Saya!), however, I think he missed to open some lockers on some of his iterations(Human Error).
As for me, it's bruteforce time! 5 minutes and i'm done! I was even able to extract a pattern to optimize the algorithm. Thanks to my ACM powers! Hahahah... :)
Here's how it goes:
In a class of 100 students, the student to locker ratio is 1:1. Each locker door are numbered from 1 to 100. The students are asked to open or close the lockers based on a given rule.
The rule is simple. All students must line up in a queue. The Nth student must open/close all lockers having a locker number that is a multiple of N. If a locker is initially closed, they should open it, else they should close it. All lockers are closed at the start.
To give you an example. The first student will open all the lockers (since all numbers are divisible by 1). The next student will close all the even numbered lockers. The third student will close locker#3, open locker#6, close locker#9, so on and so forth.
You are to determine how many lockers will be left opened after all the students are finished.
Whoa! It's an Algo problem. After hearing about this, the first thing that came into my mind is to create a program that will simulate the activity. Apparently, my brother did something on paper (which reminded me of the assignment we did when we discussed "Sieve of Erastosthenes" in High School) but he gave up because he lost count. My dad has been trying to solve extract a pattern out of a chart that he's using to simulate the activity (Haha! Saya!), however, I think he missed to open some lockers on some of his iterations(Human Error).
As for me, it's bruteforce time! 5 minutes and i'm done! I was even able to extract a pattern to optimize the algorithm. Thanks to my ACM powers! Hahahah... :)