Urgent help required?

Question

4. Imagine you are at a car dealership that has 1000 vehicles, all locked.
Suppose a salesperson goes along and unlocks every car.
Another salesperson then goes along and locks every other vehicle beginning with vehicle number 2 (yes, the vehicles are all numbered).
A third salesperson changes the state of every third vehicle beginning with vehicle number 3. (If the vehicle is locked the salesperson unlocks it, and if the vehicle is unlocked the salesperson locks it.)
A fourth salesperson changes the state of every fourth vehicle beginning with number 4.
Imagine that this continues until 1000 salespersons have followed the pattern with the 1000 vehicles. At the end, which vehicles will be locked and which vehicles will be unlocked? Which vehicles have been switched the most frequently? How many vehicles, and which ones, were touched exactly five times? Support all of your choices appropriately.

Answer 1

The cars are numbered 1 through 1000. If you imagine any car (say #14), it will be touched by the salespeople that are factors of the number.

So car #14 will be touched by salespeople 1, 2, 7 and 14. Each time the car is touched an *even* number of times, it will end up locked. Four salespeople mean it will end up locked.

QUESTION 1:
At the end, which vehicles will be locked and which vehicles will be unlocked?

A car will only end up unlocked if it has an *odd* number of factors. Since factors usually pair up (e.g. 1 x 14, 2 x 7) you would normally expect a car to end up locked. However, certain numbers, namely the perfect squares will have an *odd* number of factors. These are the cars (1, 4, 9, 16, ..., etc.) that will be unlocked.

Answer: Cars that are perfect squares (1, 4, 9, etc.) will be unlocked, all the rest will be locked.

QUESTION 2
Which vehicles have been switched the most frequently?

This can really be phrased as which number (1-1000) has the most factors. 512 = 2^9 and has lots of factors:
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, but is this the best?

To find a number which has as many factors as possible, you would like to find a number with as many prime factors as possible (to have many terms to multiply) and exponents as large as possible (to have large terms to multiply). Also the prime factors must be as small as possible to keep their product as low as possible; for the same reason the larger exponents must be on the smallest factors. The choices
for the number of prime factors are

a) only one prime factor: you might as well take 2,
b) two prime factors: 2 and 3,
c) three prime factors: 2, 3 and 5,
d) four prime factors: 2, 3, 5 and 7.

This gets us to 210. That is the most prime factors you can have. if you take more factors you exceed 1000.
You'll notice that you still have some space to increase the exponents: you can take 210 x 2 = 420. This gives lots of factors... but what if you multiplied it by 2 again? Hmm... 840 has tons of factors (32 to be exact):

Factors of 840:
1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 15, 20, 21, 28, 30, 35, 40, 42, 56, 60, 70, 84, 105, 120, 140, 160, 168, 210, 320, 420 and 840

That looks pretty good to me.

QUESTION 3
Which vehicles were touched exactly five times?

Here you need only consider perfect squares, since they have an odd number of factors.
1² has only 1 factor
2² has only 3 factors
3² has only 3 factors
4² has 5 factors --> 16
5² has only 3 factors
6² has 5 factors --> 36
etc.

Basically if n has 2 prime factors, then n² will have 5 factors. You can figure this out, right? The last number you have to check is 31² = 961.