Pages

Wednesday, May 18, 2011

Circular Locker Problem

From a friend's brother:

There are 1000 lockers and 1000 students. The lockers are arranged in a circle, all closed. The 1st student opens all the lockers. The 2nd student closes every other locker. The 3rd student goes to every 3rd locker. If it’s open he closes it, if it’s closed, he opens it. When he gets to locker #999, he continues to locker #2 and continues until he reaches a locker that he has already touched. The 4th student goes to every 4th locker: again, if it’s closed, he opens it, if it’s open, he closes it. Every student after that does the same, until student #1000, who will obviously just open or close locker #1000. After they are all finished, which lockers will be open?

Solution


First, let's think about what happens when student $n$ does his turn.

If $n$ is relatively prime to 1000, that is, $n$ does not contain any factor of 2 or 5, then $n$ will touch all the lockers exactly once. For example, student #3 will go touching lockers 3,6,...,999,2,5,...,998,1,4,7,...,997,1000. In this case student $n$ behaves exactly like student #1.

If $n$ is a multiple of $2$ or $5$, then let $d = \gcd(1000,n)$ Student $n$ touches locker $m$ if and only if $d$ divides $m$. For example, if $n=16$, then $d = 8$. Student #16 will go touching lockers 16,32,...,992,8,24,...,1000, which are exactly all multiples of 8. In this case, student $n$ behaves exactly like student #8.

Now, how many students have numbers that are NOT relatively prime to 1000? Such students must have numbers in the form of $n = 2^a 5^b$ We can enumerate the possibilities:

If $b=0$, then the student numbers are: 2,4,8,16,32,64,128,256,512, for a total of 9 students. Remember that students #16,32,...,512 behave exactly like student #8,and there are 6 of them, so it's equivalent to student #8 going 6 extra times. Their effects cancel out pairwise. So we only need to consider the effects of students #2,4,8.

If $b=1$, then the student numbers are: 5,10,20,40,80,160,320,640, for a total of 8 students. Remember that students #80,...,640 behave exactly like student #40,and there are 4 of them, so their effects cancel out pairwise. So we only need to consider the effects of students #5,10,20,40.

If $b=2$, then the student numbers are: 25,50,100,200,400,800, for a total of 6 students. Remember that students #400,8000 behave exactly like student #200, so their effects cancel out. So we only need to consider the effects of students #25,50,100,200.

If $b=3$, then the student numbers are: 125,250,500,1000.

If $b=4$, then the student number is: 625, which behaves like student #125, and thus cancels the effect of student #125.

So in total, there are 9+8+6+4+1 = 28 numbers that are not relatively prime to 1000, so there are an even numbers of students that are relatively prime. Each of these students touches all lockers exactly once, so their effects again cancel out pairwise. Thus, the student numbers that we need to consider are: (grouped by their largest factor of 2):
5,25
2,10,50,250
4,20,100,500
8,40,200,1000

In order to determine if locker $n$ is closed or open, find all numbers above that divides $n$. If there are even such numbers, then the locker is close, otherwise it's open.

For example, 120 = 3 x 5 x 8, so 120 is divisible by 2,4,8, 5,10,20,40. That means locker #120 is open.

For a more explicit list of open lockers, the following are the open lockers:
1. Lockers with numbers (not divisible by 5 or divisible by 25), and (divisible by 2 but not by 4, or divisible by 8).
2. Lockers with numbers divisible by 5 but not 25, and (divisible by 4 but not by 8).

Monday, May 16, 2011

Magician and cards

From IMO 2000, problem 4:

A magician has one hundred cards numbered 1 to 100. He puts them into three boxes, a red one, a white one and a blue one, so that each box contains at least one card. A member of the audience draws two cards from two different boxes and announces the sum of numbers on those cards. Given this information, the magician locates the box from which no card has been drawn.

How many ways are there to put the cards in the three boxes so that the trick works?

Solution

There are 12 possible ways to divide the card:
1. RWWW...WWWB (Card 1 goes to red box, card 2 to 99 go to white box, and card 100 goes to blue box) and all of its permutations, for a total of 6 ways.
2. RWBRWBRWB... and all of its permutations, for a total of 6 ways.

We now show that there are no other ways to put the cards. Consider the placement string (RWB string as in the example above). We will divide into two major cases: those with repeating characters, and those without repeating characters.

First, note that if there is a substring "RW" anywhere in the string, we don't allow substring "RB," for otherwise we can have an ambiguous sum of W+R versus R+B. Likewise, if there is a substring "RW" then we don't allow "BW."

Now, suppose there is a repeating substring "WW." Then we can't have a "RB" or "BR" anywhere in the string because there would be an ambiguous sum of R+W versus B+W.

Note that if we already have a "WW" then we can't have a "BB" because "BB" would mean that no "RW" or "WR" can exist, but we already established that no "RB" or "BR" can exist. So combination of "WW" and "BB" altogether would make it impossible for any "R" to exist in the string, a contradiction.

Consider the last B in the string, and call this B'. There are 4 possibilities of strings that come after B':
1. B'B: contradiction because B' is the last B in the string
2. B'R: contradiction because no BR is allowed
3. B'W
4. B' is the last letter in the whole string.

Consider also the last R in the string, call it R'. As in B', we only have 2 possibilities of strings that come after R':
5. R'W
6. R' is the last letter in the whole string.

Now obviously 4 and 6 cannot both be true, so one of them (possibly both) must be false. WLOG, we can assume that 6 is false, then 5 has to be true. If there's RW, we cannot have BW, so 3 is false, which means 4 is true.

So the last R in the string is followed by a W, and B is the last letter in the whole string. Since there already is an RW, we can't have a BW in the entire string. Also, we can't have BB, or BR, so there's no other place for another B. That means B' is the last and only B in the string.

Now, R' can't be preceded by another R (because no RR is allowed), nor by a B (because no BR is allowed), nor by a W, because a WR and a WB' can't both exist. So R' is the earliest R in the string. Since it's also the last, then R' is the only R in the string.

So we have RWW...WWB (and all of its permutations) as the only solution that allows repetition between characters.

Now, suppose there's no repeated characters. We assert that we cannot have a pattern like "RWR" anywhere in the string. Because the character that comes after "RWR" cannot be B, because "RWRB" gives an ambiguous sum of R+B and W+R. We also cannot have RWRR for there's no repeating characters. So we must have either "RWRW" or the fact that RWR is the ending of the entire string. If it is the ending, then we apply the same argument forward, and conclude that the ending must be WRWR. Either way, an RWR can be extended to RWRW or WRWR. But since there is at least one B in the string, and this B cannot be adjacent to another B, and we can't have BW, WB, BR, or RB either, a contradiction. So there must not be any RWR or its permutations anywhere in the string.

Suppose card 1 goes to R, and card 2 goes to W. Card 3 can go to:
1. R, forming RWR, contradiction
2. W, forming a WW, contradiction
3. B.

So we have RWB as the beginning of the string. Now card 4 can go to:
1. R
2. W, forming a WBW, contradiction
3. B, forming a WBB, contradiction.
So card 4 must go to R.

We can continue this argument inductively to arrive that the entire string must have the form: RWBRWBRWB....

Thursday, May 5, 2011

Function from N to N

Find all functions $ f:\mathbb{N}^{*}\rightarrow\mathbb{N}^{*} $
such that

$f(n)+f(n+1)+f(f(n))=3n+1 (\forall)n\in\mathbb{N}^{*} $