Prove that there are infinitely many prime numbers $p$ such that there are exactly $p^2$ integer triples $(x,y,z)$ such that $0 \leq x,y,z < p$ and $x^2+y^2 - 2010z^3$ is divisible by $p$.
Solution
We will first show that any prime that has form $p = 6k-1$ and does not divide 2010 satisfies the given condition.
First, let $p$ be such prime. Suppose there are $a,b \in \{ 1, \dots, p-1 \}$ such that $a^3 \equiv b^3 \mod p$.
Since $b^{p-1} \equiv 1 \mod p$ then let $c \equiv ab^{p-2} \mod p$, so that we have $bc \equiv a \mod p$.
Then $b^3c^3 \equiv a^3 \equiv b^3 \mod p$ which means $b^3c^3 \equiv b^3 \mod p$ which then means $c^3 \equiv 1 \mod p$ (since $(b,p) = 1$).
Because $c^{p-1} = c^{6k-2} \equiv 1 \mod p$ and $c^{6k-3} = c^{3(2k-1)} \equiv 1 \mod p$, then we must have $c \equiv 1 \mod p$, which means $a \equiv b \mod p$.
In summary, we've shown that $a^3 \equiv b^3 \Rightarrow a \equiv b \mod p$. This means that the set $\{1^3, \dots, p^3 \} \mod p$ is the same as set $\{ 1, \dots, p \} \mod p$. So given any arbitrary $x$ and $y$, we can find exactly one $z$ such that $z^3 \equiv 2010^{-1} (x^2+y^2) \mod p$. Since there are $p^2$ possible pairs for $(x,y)$, then there are also $p^2$ possible triples for $(x,y,z)$.
Now we show that there are infinitely many primes of the form $6k-1$ which would mean that there must be infinitely many primes of the form $6k-1$ that do not divide 2010.
Note that any prime above 3 must have form $6k+1$ or $6k-1$. If there are only finite number of primes of the form $6k-1$, say $p_1, p_2, \dots, p_n$, consider the number $N = 6p_1p_2 \dots p_n - 1$.
For each $i$, $p_i$ does not divide $N$ because otherwise $p_i$ would also have to divide 1, a contradiction. So $N$ is not divisible by any of the $p_i$s, which means all prime factors of $N$ must be of the form $6k+1$. That means, $N \equiv 1 \mod 6$, a contradiction.
Showing posts with label Solution. Show all posts
Showing posts with label Solution. Show all posts
Monday, August 9, 2010
Friday, July 23, 2010
a,b,c integers and cubic number
Suppose $a,b,c$ are positive integers such that $\frac{a}{b} + \frac{b}{c} + \frac{c}{a}$ is an integer. Prove that $abc$ is a cubic number.
Solution
We have $ab^2 + bc^2 + ca^2 = kabc$ for some k.
Let $d = \gcd(a,b,c)$. We can replace $a,b,c$ by $a/d, b/d, c/d$ respectively and the problem does not change. Thus, without loss of generality, we may assume that $d = 1$.
Let $p$ be a prime that divides $abc$, which means $p$ divides at least one of $a,b,c$. We also know that $p$ cannot divide all three, since $d = 1$.
If $p$ divides exactly one of $a,b,c$, for example $a$, then $ab^2, ca^2, kabc$ are all divisible by $p$, but not $bc^2$. Impossible. Thus, $p$ must divide exactly two of $a,b,c$.
Suppose $p$ divides $a$ and $b$. Furthermore, let $x$ be the largest integer such that $p^x$ divides $a$. Likewise, let $y$ be the largest integer such that $p^y$ divides $b$.
Since $ab^2, bc^2, kabc$ are all divisible by $b$, then so is $ca^2$. Thus $y \leq 2x$.
Since $ab^2, ca^2, kabc$ are all divisible by $a$, then so is $bc^2$, Thus $y \geq x$, which means $x \leq y \leq 2x$.
Now, since $ab^2, ca^2, kabc$ are all divisible by $p^{2x}$, then so is $bc^2$, which means $y \geq 2x$.
Therefore, $y = 2x$, which means that the degree of $p$ in the factorization of $abc$ is $x+y = 3x$.
For each prime $p$ that divides $abc$, it must occur as a cubic number in its prime factorization. Thus $abc$ is a cubic number.
A non-trivial example is $a=1,b=2,c=4$.
Solution
We have $ab^2 + bc^2 + ca^2 = kabc$ for some k.
Let $d = \gcd(a,b,c)$. We can replace $a,b,c$ by $a/d, b/d, c/d$ respectively and the problem does not change. Thus, without loss of generality, we may assume that $d = 1$.
Let $p$ be a prime that divides $abc$, which means $p$ divides at least one of $a,b,c$. We also know that $p$ cannot divide all three, since $d = 1$.
If $p$ divides exactly one of $a,b,c$, for example $a$, then $ab^2, ca^2, kabc$ are all divisible by $p$, but not $bc^2$. Impossible. Thus, $p$ must divide exactly two of $a,b,c$.
Suppose $p$ divides $a$ and $b$. Furthermore, let $x$ be the largest integer such that $p^x$ divides $a$. Likewise, let $y$ be the largest integer such that $p^y$ divides $b$.
Since $ab^2, bc^2, kabc$ are all divisible by $b$, then so is $ca^2$. Thus $y \leq 2x$.
Since $ab^2, ca^2, kabc$ are all divisible by $a$, then so is $bc^2$, Thus $y \geq x$, which means $x \leq y \leq 2x$.
Now, since $ab^2, ca^2, kabc$ are all divisible by $p^{2x}$, then so is $bc^2$, which means $y \geq 2x$.
Therefore, $y = 2x$, which means that the degree of $p$ in the factorization of $abc$ is $x+y = 3x$.
For each prime $p$ that divides $abc$, it must occur as a cubic number in its prime factorization. Thus $abc$ is a cubic number.
A non-trivial example is $a=1,b=2,c=4$.
Wednesday, May 12, 2010
Solution: Passengers Boarding Airplane
Credit goes to Ed Kao, Vallent Lee and Laurence Tai for helping with the second solution.
Original problem: http://dharmath.blogspot.com/2009/10/passengers-boarding-airplane.html
2009 passengers are waiting in a line to board an airplane with 2009 seats. Each passenger has a boarding pass that has his/her seat number on it. The first passenger, however, was oblivious and chose a random seat to sit on.
For each subsequent passenger, he/she will try to sit on his/her assigned seat first. If that seat is taken by someone else, he/she will choose a random empty seat to sit on.
What is the probability that the last passenger would sit on his assigned seat?
Answer: $\frac{1}{2}$
First Solution
We generalize the problem to $n$ passengers boarding an airplane with $n$ seats.
The probability that the first passenger sits in his seat is $1/n$. We will prove by induction that the probability that the $k$-th ($k > 1$) passenger sits in his seat is $\frac{n-k+1}{n-k+2}$
For $k=2$, it's obvious that the second passenger has probability $\frac{n-1}{n}$ of finding his seat unoccupied. As long as the first passenger chooses something other than his seat, he will find his seat unoccupied and sits there correctly.
For $k>2$, consider the time when $k$-th passenger is about to board. If he finds his seat unoccupied, he will sit there. The only way that he does NOT sit on his correct seat is if it's already occupied by a previous passenger. We will divide this into two cases, depending on who sits at his seat.
Case 1: Passenger $k-1$ sits there. The only way this could happen is if passenger $k-1$ finds her seat occupied by someone else, and then she chooses to sit at passenger $k$'s seat. The probability of passenger $k-1$ finds her seat occupied by someone else is $1-\frac{n-(k-1)+1}{n-(k-1)+2} = \frac{1}{n-k+3}$.
At that point, there are $k-2$ occupied seats total and there are $n-k+2$ empty seats on the plane. The probability that she chooses to sit at this particular seat is $\frac{1}{n-k+2}$
Case 2: Passenger $i (i < k-1)$ sits there (at passenger $k$'s seat). Now we consider the moment where passenger $i$ was about to board. Passenger $k$'s seat was open.
If passenger $k-1$'s seat had been occupied by someone else before $i$, then passenger $i$'s seat would have been open, and passenger $i$ must have sit there correctly.
In order for passenger $i$ to NOT sit on his seat, both passenger $k$ and $k-1$'s seat are both open. That means, the probability that passenger $i$ sits at passenger $k$'s seat is the same as the probability that passenger $i$ sits at passenger $k-1$'s seat, since both choices are equally likely and they're always made with both choices available.
Thus the probability from case 2 is $\frac{1}{n-k+3}$
The total probability that passenger $k$ does not sit at his correct seat is:
$$\frac{1}{n-k+3} \frac{1}{n-k+2} + \frac{1}{n-k+3} = \frac{1}{n-k+2}$$
so the probability that he sits at his seat is:
$$1 - \frac{1}{n-k+2} = \frac{n-k+1}{n-k+2}$$
which completes the inductive step.
From this formula, it's clear that the probability passenger $n$ sits on his correct seat is $\frac{1}{2}$
Second Solution
We make the following observations:
1. In the beginning, both seat #1 and #2009 are both empty.
2. The moment someone chooses to sit on either seat (that is, the moment they stop being both empty), there is no more choices to be made for the rest of the boarding process. The rest of the passengers must thus sit deterministically from that point on.
Indeed, when passenger $k$ sits on seat #2009, then seat $k+1, ..., 2008$ would be empty and the subsequent passengers don't have to choose at all. Passenger #2009 has a random "choice" of 1 seat.
If passenger $k$ sits on seat #1, then the remaining vacant seats match the unboarded passengers perfectly and everyone can sit in their correct seat save for those who've already boarded.
That means, for every event that someone illegitimately sits on seat #2009, that passenger had an equally likely choice of seat #1, and vice versa. The moment this symmetry is broken, there would be no more choices to be made for the rest of the boarding process.
3. When passenger #2009 is about to board, there is only one empty seat. That empty seat is either seat #1 or seat #2009. If there is another seat $k ( 1 < k < 2009)$ empty, then one might ask: why didn't passenger $k$ sit there? A contradiction.
From the observations above, we define two events:
A: an event that passenger #2009 sits at seat #1
B: an event that passenger #2009 sits at seat #2009
These two events are mutually exclusive, and are the only two possibilities. Furthermore, they have equal probability since the moment one event becomes impossible, there is no more choices to be made by the rest of the passengers.
So the probability that passenger #2009 sits at his correct seat is $\frac{1}{2}$
Original problem: http://dharmath.blogspot.com/2009/10/passengers-boarding-airplane.html
2009 passengers are waiting in a line to board an airplane with 2009 seats. Each passenger has a boarding pass that has his/her seat number on it. The first passenger, however, was oblivious and chose a random seat to sit on.
For each subsequent passenger, he/she will try to sit on his/her assigned seat first. If that seat is taken by someone else, he/she will choose a random empty seat to sit on.
What is the probability that the last passenger would sit on his assigned seat?
Answer: $\frac{1}{2}$
First Solution
We generalize the problem to $n$ passengers boarding an airplane with $n$ seats.
The probability that the first passenger sits in his seat is $1/n$. We will prove by induction that the probability that the $k$-th ($k > 1$) passenger sits in his seat is $\frac{n-k+1}{n-k+2}$
For $k=2$, it's obvious that the second passenger has probability $\frac{n-1}{n}$ of finding his seat unoccupied. As long as the first passenger chooses something other than his seat, he will find his seat unoccupied and sits there correctly.
For $k>2$, consider the time when $k$-th passenger is about to board. If he finds his seat unoccupied, he will sit there. The only way that he does NOT sit on his correct seat is if it's already occupied by a previous passenger. We will divide this into two cases, depending on who sits at his seat.
Case 1: Passenger $k-1$ sits there. The only way this could happen is if passenger $k-1$ finds her seat occupied by someone else, and then she chooses to sit at passenger $k$'s seat. The probability of passenger $k-1$ finds her seat occupied by someone else is $1-\frac{n-(k-1)+1}{n-(k-1)+2} = \frac{1}{n-k+3}$.
At that point, there are $k-2$ occupied seats total and there are $n-k+2$ empty seats on the plane. The probability that she chooses to sit at this particular seat is $\frac{1}{n-k+2}$
Case 2: Passenger $i (i < k-1)$ sits there (at passenger $k$'s seat). Now we consider the moment where passenger $i$ was about to board. Passenger $k$'s seat was open.
If passenger $k-1$'s seat had been occupied by someone else before $i$, then passenger $i$'s seat would have been open, and passenger $i$ must have sit there correctly.
In order for passenger $i$ to NOT sit on his seat, both passenger $k$ and $k-1$'s seat are both open. That means, the probability that passenger $i$ sits at passenger $k$'s seat is the same as the probability that passenger $i$ sits at passenger $k-1$'s seat, since both choices are equally likely and they're always made with both choices available.
Thus the probability from case 2 is $\frac{1}{n-k+3}$
The total probability that passenger $k$ does not sit at his correct seat is:
$$\frac{1}{n-k+3} \frac{1}{n-k+2} + \frac{1}{n-k+3} = \frac{1}{n-k+2}$$
so the probability that he sits at his seat is:
$$1 - \frac{1}{n-k+2} = \frac{n-k+1}{n-k+2}$$
which completes the inductive step.
From this formula, it's clear that the probability passenger $n$ sits on his correct seat is $\frac{1}{2}$
Second Solution
We make the following observations:
1. In the beginning, both seat #1 and #2009 are both empty.
2. The moment someone chooses to sit on either seat (that is, the moment they stop being both empty), there is no more choices to be made for the rest of the boarding process. The rest of the passengers must thus sit deterministically from that point on.
Indeed, when passenger $k$ sits on seat #2009, then seat $k+1, ..., 2008$ would be empty and the subsequent passengers don't have to choose at all. Passenger #2009 has a random "choice" of 1 seat.
If passenger $k$ sits on seat #1, then the remaining vacant seats match the unboarded passengers perfectly and everyone can sit in their correct seat save for those who've already boarded.
That means, for every event that someone illegitimately sits on seat #2009, that passenger had an equally likely choice of seat #1, and vice versa. The moment this symmetry is broken, there would be no more choices to be made for the rest of the boarding process.
3. When passenger #2009 is about to board, there is only one empty seat. That empty seat is either seat #1 or seat #2009. If there is another seat $k ( 1 < k < 2009)$ empty, then one might ask: why didn't passenger $k$ sit there? A contradiction.
From the observations above, we define two events:
A: an event that passenger #2009 sits at seat #1
B: an event that passenger #2009 sits at seat #2009
These two events are mutually exclusive, and are the only two possibilities. Furthermore, they have equal probability since the moment one event becomes impossible, there is no more choices to be made by the rest of the passengers.
So the probability that passenger #2009 sits at his correct seat is $\frac{1}{2}$
Thursday, May 6, 2010
Solution: Cyclic quadrilateral
Original Problem: http://dharmath.blogspot.com/2010/05/cyclic-quadrilateral.html
First Solution
Let $AB=AD=x, BC=y$ and $CD=x+z$ with $y < z$.
Let $\theta = \angle ADC$ so $\angle ABC = 180^o-\theta$. It's easy to see that because $CD > BC$ then $\angle ABC > \angle ADC$ thus $0 < \theta < 90^o$
Now $AC^2 = x^2 + y^2 + 2xy \cos \theta = x^2 + (x+z)^2 - 2x(x+z)\cos \theta$, simplify it to get:
$\cos \theta = \frac{(x+z)^2-y^2}{2x(x+y+z)} = \frac{x+z-y}{x}$
But since $\theta$ is an acute angle, $\theta < 60^o \iff \cos \theta > 1/2$
So we need to show
$x+z-y > x$ which is true because $z > y$
Second Solution
Let $R$ be a point on $CD$ such that $CB = CR$ (see the picture).
Since $AB=AD$, then $CA$ is an internal angle bisector, and thus $\triangle ABC$ are congruent to $\triangle ARC$. That means $RD = CD - CR = CD - CB > AB = AD$.
Also, $AD = AB = AR$.
So $\triangle ARD$ is an isosceles where $AD = AR$ and $RD > AD$, which means that $\angle ADR < 60^o$ and thus $\angle ABC > 120^o$
First Solution
Let $AB=AD=x, BC=y$ and $CD=x+z$ with $y < z$.
Let $\theta = \angle ADC$ so $\angle ABC = 180^o-\theta$. It's easy to see that because $CD > BC$ then $\angle ABC > \angle ADC$ thus $0 < \theta < 90^o$
Now $AC^2 = x^2 + y^2 + 2xy \cos \theta = x^2 + (x+z)^2 - 2x(x+z)\cos \theta$, simplify it to get:
$\cos \theta = \frac{(x+z)^2-y^2}{2x(x+y+z)} = \frac{x+z-y}{x}$
But since $\theta$ is an acute angle, $\theta < 60^o \iff \cos \theta > 1/2$
So we need to show
$x+z-y > x$ which is true because $z > y$
Second Solution
Let $R$ be a point on $CD$ such that $CB = CR$ (see the picture).
Since $AB=AD$, then $CA$ is an internal angle bisector, and thus $\triangle ABC$ are congruent to $\triangle ARC$. That means $RD = CD - CR = CD - CB > AB = AD$.
Also, $AD = AB = AR$.
So $\triangle ARD$ is an isosceles where $AD = AR$ and $RD > AD$, which means that $\angle ADR < 60^o$ and thus $\angle ABC > 120^o$
Thursday, April 22, 2010
Solution 1: Critical Height
Original problem: http://dharmath.blogspot.com/2010/04/critical-height.html
You have an infinite supply of crystal balls that you take into a building with 1000 stories.
There is a critical height at which if you drop the ball from there, the ball would break. If the ball is dropped from the floors under that critical height, it would not break, but if it's dropped from the floors above, obviously, it breaks.
How many trials minimum do you need in order to determine the critical height?
Advanced version #1: If you only have a supply of $k$ balls, how many trials minimum do you need?
Advanced version #2: What is the strategy that would minimize the expected number of trials, given that you only have $k$ balls, if we treat the critical height as a random variable drawn uniformly from (1,...,1000)?
Note that the two advanced versions are two different questions and thus beget two different strategies.
Clarification: When I say "how many trials minimum do you need in order to determine the critical height" it formally means: find the smallest integer $N$ such that it's always possible to determine the critical height within $N$ trials, regardless of where the critical height is. Naturally, this $N$ will be expressed in terms of $k$ in the case of advanced version #1.
Solution to advanced version #1
First we make an observation that we only care about the number of floors that are possible candidates, and the actual floor height is irrelevant. For example, if we know that the critical height must be in the floor 10 to 30, or if we know that it must be in the floor 510-530, we can employ the exact same strategy in both of those situations. The number of minimum trials needed to solve both scenarios are the same, and any action we do in one scenario is directly translatable to the other scenario. We consider these two scenarios as equivalent problems.
Our second observation is that the possible candidates are always in the form of one contiguous block of floors. We start with a block of 1000 floors (floor 1 to 1000). Every time we drop a ball from a certain floor, say floor $a$ either it breaks or it doesn't break. If it breaks, then our next candidate is floor 1 to $a$, and if it doesn't, then our next candidate is floor $a+1$ to 1000. Every time we drop a ball, we divide one contiguous block into two (possibly unequal) halves and we eliminate one half, so we establish an invariant that our candidates are always one contiguous block of floors.
From the two observations above, we may define a function $f(n,k)$ as the minimum number of trials needed to solve the case with $n$ floors and $k$ balls. Without loss of generality (and for notational ease), we may assume that the floors are floor 1 to $n$.
Suppose our first drop is at floor $a$. As we described above, if it breaks, then we are left with $k-1$ balls to find the critical height among floor 1 to $a$. We need at least $f(a,k-1)$ trials to do this. Otherwise, we still have $k$ balls to find the critical height among floor $a+1,...,1000$. We need at least $f(1000-a, k)$ trials. So in the worst case, we need at least $f(n,k) = \max ( f(a,k-1) , f(n-a,k) ) + 1$ if our first drop is at floor $a$. However, we can choose $a$ to minimize the number of trials.
So:
$$ f(n,k) = \min_{a} \left( \max ( f(a,k-1) , f(n-a,k) ) \right) + 1$$
For $k=1$, if we only have 1 ball, then the only possible strategy is to drop it sequentially from floor 1,2,... until it breaks. Thus $f(n,1) = n-1$ For example, if we know that the critical height is somewhere between floor 1 to 3, then we drop it at floor 1 and 2. If it doesn't break at floor 2, then we don't need to test floor 3 because it already know it breaks at floor 3.
Consider the case of $k=2$. Let $g(n) = f(n,2)$. From the recursion above, we have:
$$ g(n) = \min_{a} \left( \max ( a-1 , g(n-a) ) \right) + 1$$
Let $T(n)$ be the $n$-th triangular number. That is,
$T(0) = 0$
$T(1) = 1$
$T(2) = 1+2 = 3$
$T(3) = 1+2+3 = 6$
...
$T(n) = n(n+1)/2$
And let $T^{-1}(n)$ be the ceiling of the inverse triangular number.
That is
$T^{-1}(0) = 0$
$T^{-1}(1) = 1$
$T^{-1}(2) = T^{-1}(3) = 2$
$T^{-1}(4) = T^{-1}(5) = T^{-1}(6) = 3$
$T^{-1}(7) = T^{-1}(8) = T^{-1}(9) = T^{-1}(10) = 4$
and so on.
We claim that $g(n) = T^{-1}(n-1)$, which we shall prove by induction.
For small $n$ we can verify by hand that we can solve $n$ floors and that it's the minimal amount. In fact, for small $n$, $T^{-1}(n-1)$ agrees with $\log_2 n$ which is the information theoretic lower bound.
Now we proceed by strong induction.
$$ g(n) = \min_{a} \left( \max ( a-1 , T^{-1}(n-a-1) ) \right) + 1$$
Note that $T$ is a monotonically increasing function, which means $T^{-1}(n)$ is monotonically non-decreasing. But since the argument to the function is $n-a-1$, the second half of the max is actually non-increasing.
We wish to find $a$ that minimizes the max of two function, one of which is increasing and another non-increasing. The minimum must happen when the two functions intersect, that is when $a-1 = T^{-1}(n-a-1)$.
$$T^{-1}(n-a-1) = a-1$$
$$n-a-1 \leq T(a-1) = a(a-1)/2$$
$$n-1 \leq a+ a(a-1)/2 = a(a+1)/2 = T(a)$$
$$n-1 \leq T(a)$$
$$T^{-1}(n-1) \leq a$$
So the $a$ that minimizes is $T^{-1}(n-1)$, and for that value of $a$,
$f(n) = (a-1) + 1 = a = T^{-1}(n-1)$.
This completes our proof for $k=2$. For an example, suppose we have 11 floors and 2 balls, then our first drop should be at floor 4. If it breaks then we resort to the linear approach with our one remaining ball to discover which among floor 1,2,3,4 is the critical height. We can do it in 3 trials. If it doesn't break, then we drop it at floor 7. If it breaks at floor 7, then the critical floor must be floor 5, 6, or 7, which we can find in 2 trials. If it keeps not breaking, we drop it at floor 9, then 10. In any case, we will find it within 4 trials.
For case $k=3$, we do the same thing except we replace $T$ with $P$, the $n$ pyramidal number.
$P(0) = T(0) = 0$
$P(1) = T(1) = 1$
$P(2) = T(1) + T(2) = 4$
$P(3) = T(1) + T(2) + T(3) = 10$
...
$P(n) = n(n+1)(n+2) / 6$
The arguments in the proof still hold to establish feasibility and optimality of this strategy.
For general case $k$, we replace $P$ with $H_k$, the $n$-th hyper-pyramidal number:
$$H_k (n) = n(n+1)...(n+k-1) / k! = \binom{n+k-1}{k}$$
And the minimum number of trials is
$$f(n,k) = H_k^{-1}(n-1)$$
You have an infinite supply of crystal balls that you take into a building with 1000 stories.
There is a critical height at which if you drop the ball from there, the ball would break. If the ball is dropped from the floors under that critical height, it would not break, but if it's dropped from the floors above, obviously, it breaks.
How many trials minimum do you need in order to determine the critical height?
Advanced version #1: If you only have a supply of $k$ balls, how many trials minimum do you need?
Advanced version #2: What is the strategy that would minimize the expected number of trials, given that you only have $k$ balls, if we treat the critical height as a random variable drawn uniformly from (1,...,1000)?
Note that the two advanced versions are two different questions and thus beget two different strategies.
Clarification: When I say "how many trials minimum do you need in order to determine the critical height" it formally means: find the smallest integer $N$ such that it's always possible to determine the critical height within $N$ trials, regardless of where the critical height is. Naturally, this $N$ will be expressed in terms of $k$ in the case of advanced version #1.
Solution to advanced version #1
First we make an observation that we only care about the number of floors that are possible candidates, and the actual floor height is irrelevant. For example, if we know that the critical height must be in the floor 10 to 30, or if we know that it must be in the floor 510-530, we can employ the exact same strategy in both of those situations. The number of minimum trials needed to solve both scenarios are the same, and any action we do in one scenario is directly translatable to the other scenario. We consider these two scenarios as equivalent problems.
Our second observation is that the possible candidates are always in the form of one contiguous block of floors. We start with a block of 1000 floors (floor 1 to 1000). Every time we drop a ball from a certain floor, say floor $a$ either it breaks or it doesn't break. If it breaks, then our next candidate is floor 1 to $a$, and if it doesn't, then our next candidate is floor $a+1$ to 1000. Every time we drop a ball, we divide one contiguous block into two (possibly unequal) halves and we eliminate one half, so we establish an invariant that our candidates are always one contiguous block of floors.
From the two observations above, we may define a function $f(n,k)$ as the minimum number of trials needed to solve the case with $n$ floors and $k$ balls. Without loss of generality (and for notational ease), we may assume that the floors are floor 1 to $n$.
Suppose our first drop is at floor $a$. As we described above, if it breaks, then we are left with $k-1$ balls to find the critical height among floor 1 to $a$. We need at least $f(a,k-1)$ trials to do this. Otherwise, we still have $k$ balls to find the critical height among floor $a+1,...,1000$. We need at least $f(1000-a, k)$ trials. So in the worst case, we need at least $f(n,k) = \max ( f(a,k-1) , f(n-a,k) ) + 1$ if our first drop is at floor $a$. However, we can choose $a$ to minimize the number of trials.
So:
$$ f(n,k) = \min_{a} \left( \max ( f(a,k-1) , f(n-a,k) ) \right) + 1$$
For $k=1$, if we only have 1 ball, then the only possible strategy is to drop it sequentially from floor 1,2,... until it breaks. Thus $f(n,1) = n-1$ For example, if we know that the critical height is somewhere between floor 1 to 3, then we drop it at floor 1 and 2. If it doesn't break at floor 2, then we don't need to test floor 3 because it already know it breaks at floor 3.
Consider the case of $k=2$. Let $g(n) = f(n,2)$. From the recursion above, we have:
$$ g(n) = \min_{a} \left( \max ( a-1 , g(n-a) ) \right) + 1$$
Let $T(n)$ be the $n$-th triangular number. That is,
$T(0) = 0$
$T(1) = 1$
$T(2) = 1+2 = 3$
$T(3) = 1+2+3 = 6$
...
$T(n) = n(n+1)/2$
And let $T^{-1}(n)$ be the ceiling of the inverse triangular number.
That is
$T^{-1}(0) = 0$
$T^{-1}(1) = 1$
$T^{-1}(2) = T^{-1}(3) = 2$
$T^{-1}(4) = T^{-1}(5) = T^{-1}(6) = 3$
$T^{-1}(7) = T^{-1}(8) = T^{-1}(9) = T^{-1}(10) = 4$
and so on.
We claim that $g(n) = T^{-1}(n-1)$, which we shall prove by induction.
For small $n$ we can verify by hand that we can solve $n$ floors and that it's the minimal amount. In fact, for small $n$, $T^{-1}(n-1)$ agrees with $\log_2 n$ which is the information theoretic lower bound.
Now we proceed by strong induction.
$$ g(n) = \min_{a} \left( \max ( a-1 , T^{-1}(n-a-1) ) \right) + 1$$
Note that $T$ is a monotonically increasing function, which means $T^{-1}(n)$ is monotonically non-decreasing. But since the argument to the function is $n-a-1$, the second half of the max is actually non-increasing.
We wish to find $a$ that minimizes the max of two function, one of which is increasing and another non-increasing. The minimum must happen when the two functions intersect, that is when $a-1 = T^{-1}(n-a-1)$.
$$T^{-1}(n-a-1) = a-1$$
$$n-a-1 \leq T(a-1) = a(a-1)/2$$
$$n-1 \leq a+ a(a-1)/2 = a(a+1)/2 = T(a)$$
$$n-1 \leq T(a)$$
$$T^{-1}(n-1) \leq a$$
So the $a$ that minimizes is $T^{-1}(n-1)$, and for that value of $a$,
$f(n) = (a-1) + 1 = a = T^{-1}(n-1)$.
This completes our proof for $k=2$. For an example, suppose we have 11 floors and 2 balls, then our first drop should be at floor 4. If it breaks then we resort to the linear approach with our one remaining ball to discover which among floor 1,2,3,4 is the critical height. We can do it in 3 trials. If it doesn't break, then we drop it at floor 7. If it breaks at floor 7, then the critical floor must be floor 5, 6, or 7, which we can find in 2 trials. If it keeps not breaking, we drop it at floor 9, then 10. In any case, we will find it within 4 trials.
For case $k=3$, we do the same thing except we replace $T$ with $P$, the $n$ pyramidal number.
$P(0) = T(0) = 0$
$P(1) = T(1) = 1$
$P(2) = T(1) + T(2) = 4$
$P(3) = T(1) + T(2) + T(3) = 10$
...
$P(n) = n(n+1)(n+2) / 6$
The arguments in the proof still hold to establish feasibility and optimality of this strategy.
For general case $k$, we replace $P$ with $H_k$, the $n$-th hyper-pyramidal number:
$$H_k (n) = n(n+1)...(n+k-1) / k! = \binom{n+k-1}{k}$$
And the minimum number of trials is
$$f(n,k) = H_k^{-1}(n-1)$$
Tuesday, March 23, 2010
Solution: Happy Saint Math Trick's Day
Original problem: http://dharmath.blogspot.com/2010/03/happy-saint-math-tricks-day.html
This problem is inspired by this comic.
Prove that the trick in the comic always works. In other words, if $p$ is a prime number greater than 3, prove that $p^2 + 14 \equiv 3 \mod 12$
$p^2 + 14 \equiv 3 \mod 12$ means that $p^2+11$ is divisible by 12, which means that $p^2+11-12 = p^2-1$ is divisible by 12.
If $p$ is a prime number greater than 3, then $p$ is odd. This means that $p$ divided by 4 has remainder either 1 or 3. In both cases, $p^2$ divided by 4 has remainder 1, which means $p^2-1$ is divisible by 4.
If $p$ is a prime number greater than 3, then $p$ divided by 3 has remainder either 1 or 2. In both cases, $p^2$ divided by 3 has remainder 1, which again means $p^2-1$ is divisible by 3.
Since $p^2-1$ is divisible by both 3 and 4, it is divisible by 12.
This problem is inspired by this comic.
Prove that the trick in the comic always works. In other words, if $p$ is a prime number greater than 3, prove that $p^2 + 14 \equiv 3 \mod 12$
Solution
$p^2 + 14 \equiv 3 \mod 12$ means that $p^2+11$ is divisible by 12, which means that $p^2+11-12 = p^2-1$ is divisible by 12.
If $p$ is a prime number greater than 3, then $p$ is odd. This means that $p$ divided by 4 has remainder either 1 or 3. In both cases, $p^2$ divided by 4 has remainder 1, which means $p^2-1$ is divisible by 4.
If $p$ is a prime number greater than 3, then $p$ divided by 3 has remainder either 1 or 2. In both cases, $p^2$ divided by 3 has remainder 1, which again means $p^2-1$ is divisible by 3.
Since $p^2-1$ is divisible by both 3 and 4, it is divisible by 12.
Friday, March 19, 2010
Second Solution: Osculating Circle, Ellipse, and Cone
Original Problem: http://dharmath.blogspot.com/2010/03/osculating-circle-ellipse-and-cone.html
An osculating circle of a point on a curve is defined as a circle that:
1. passes through that point
2. whose slope at that point is the same of the slope of the curve at that point
3. whose radius is the same as the radius of curvature of the curve at that point
In other words, it is a second-degree approximation circle of the curve at that point.
http://en.wikipedia.org/wiki/Osculating_circle
Given a cone whose half-angle is $\theta$, we take a cross section with a plane whose incident angle is $\theta$. That is, the plane is perpendicular to one of the cone rays. Naturally, the cross section forms an ellipse.
If O is the intersection of the main axis of the cone and the cross section, and A is the point on the ellipse's major axis that's closest to O, then prove that a circle with center O and radius OA is an osculating circle to the ellipse at A.
Hint: for people without any knowledge of calculus, the radius of osculating circle at A is $b^2/a$ where $b$ is half the length of minor axis and $a$ is half the length of major axis (standard ellipse notation).
The rest of the problem can be done without using calculus.
As given in the hint, the radius of the osculating circle is $b^2/a$. And clearly the circle in the problem passes through A and its tangent at A is perpendicular to the major axis, hence coincides with the ellipse's tangent. We are left to prove that $OA = b^2/a$. However, astute readers will note that $b^2/a$ is exactly the length of semi latus-rectum of the ellipse. So suppose $D$ is the focus that's closest to $A$, and $GG_1$ is the latus rectum passing through $D$, we will show that $DG = OA$.
Let $B$ be the point on the major axis that's farthest to $O$, and let $S$ be the vertex of the ellipse. Let $x = 2 \theta$ be the angle of the cone. We also note that $AO \perp AS$.
Let $\tau$ be the plane that passes through $GG_1$ (and hence through D) and perpendicular to the cone axis. Let $E$ be the point of intersection of the axis and this plane. The cross section of the cone with $\tau$ is a circle with center $E$. Let $F$ be the point on the circle such that $EF$ passes through $D$.
Since $SO$ is an angle bisector, we have $AO:OB = SA:SB = \cos x$, thus
$$AO = \frac{\cos x }{ \cos x+1} AB = \frac{\sin x \cos x }{ \cos x+1} SB$$
Now, $D$ is the point at which the smaller Dandelin Sphere touches the ellipse. If we consider the triangle $SAB$, then $D$ is where the incenter of that triangle touches $AB$. Since $SAB$ is a right angle at $A$, then $DA$ is the radius of that incenter.
$$DA = \frac{AS.AB}{AS+AB+SB} = \frac{\sin x \cos x}{1 + \sin x + \cos x} SB$$
Thus $AO : DA = (1+ \sin x + \cos x) : (1 + \cos x) = 1 + (\sin x) / (1 + \cos x)$
Which means $DO:AD:AO = \sin x : (1 + \cos x) : (1 + \sin x + \cos x)$
Now, looking back at the triangle $SAB$ and the plane that contains it,
$$DF = \frac{AD}{\cos \theta} = \frac{1 + \cos x}{(1 + \sin x + \cos x) \cos \theta} OA$$
and
$$DE = DO \cos \theta = \frac{\sin x \cos \theta}{1 + \sin x + \cos x} OA$$
So
$$DG^2 = EG^2 - DE^2 = EF^2 - DE^2 = (DE + DF)^2 - DE^2 = DF(DF + 2DE)$$
$$ = \frac{OA^2}{(1 + \sin x + \cos x)^2} \frac{1 + \cos x}{\cos \theta} \left(\frac{1 + \cos x}{\cos \theta} + 2\sin x \cos \theta \right)$$
Since $x = 2\theta$, then $1 + \cos x = 2 \cos^2 \theta$
$$(1 + \sin x + \cos x)^2 = (2 \cos^2 \theta + 2 \sin \theta \cos \theta)^2 = 4 \cos^2 \theta (\sin \theta + \cos \theta)^2$$
and
$$ \frac{1 + \cos x}{\cos \theta} + 2\sin x \cos \theta = 2 \cos \theta + 2 \sin x \cos \theta = 2 \cos \theta (1 + \sin x)$$
So
$$DG^2 = \frac{OA^2}{4 \cos^2 \theta (\sin \theta + \cos \theta)^2} \frac{2 \cos^2 \theta}{\cos \theta} 2 \cos \theta (1 + \sin x)$$
$$ = OA^2 \frac{1 + \sin x}{(\sin \theta + \cos \theta)^2}$$
But
$$1 + \sin x = 1 + 2 \sin \theta \cos \theta = \cos^2 \theta + \sin^2 \theta + 2 \sin \theta \cos \theta = (\sin \theta + \cos \theta)^2$$
So $DG^2 = OA^2$ which means $DG = OA$
An osculating circle of a point on a curve is defined as a circle that:
1. passes through that point
2. whose slope at that point is the same of the slope of the curve at that point
3. whose radius is the same as the radius of curvature of the curve at that point
In other words, it is a second-degree approximation circle of the curve at that point.
http://en.wikipedia.org/wiki/Osculating_circle
Given a cone whose half-angle is $\theta$, we take a cross section with a plane whose incident angle is $\theta$. That is, the plane is perpendicular to one of the cone rays. Naturally, the cross section forms an ellipse.
If O is the intersection of the main axis of the cone and the cross section, and A is the point on the ellipse's major axis that's closest to O, then prove that a circle with center O and radius OA is an osculating circle to the ellipse at A.
Hint: for people without any knowledge of calculus, the radius of osculating circle at A is $b^2/a$ where $b$ is half the length of minor axis and $a$ is half the length of major axis (standard ellipse notation).
The rest of the problem can be done without using calculus.
Second Solution
As given in the hint, the radius of the osculating circle is $b^2/a$. And clearly the circle in the problem passes through A and its tangent at A is perpendicular to the major axis, hence coincides with the ellipse's tangent. We are left to prove that $OA = b^2/a$. However, astute readers will note that $b^2/a$ is exactly the length of semi latus-rectum of the ellipse. So suppose $D$ is the focus that's closest to $A$, and $GG_1$ is the latus rectum passing through $D$, we will show that $DG = OA$.
Let $B$ be the point on the major axis that's farthest to $O$, and let $S$ be the vertex of the ellipse. Let $x = 2 \theta$ be the angle of the cone. We also note that $AO \perp AS$.
Let $\tau$ be the plane that passes through $GG_1$ (and hence through D) and perpendicular to the cone axis. Let $E$ be the point of intersection of the axis and this plane. The cross section of the cone with $\tau$ is a circle with center $E$. Let $F$ be the point on the circle such that $EF$ passes through $D$.
Since $SO$ is an angle bisector, we have $AO:OB = SA:SB = \cos x$, thus
$$AO = \frac{\cos x }{ \cos x+1} AB = \frac{\sin x \cos x }{ \cos x+1} SB$$
Now, $D$ is the point at which the smaller Dandelin Sphere touches the ellipse. If we consider the triangle $SAB$, then $D$ is where the incenter of that triangle touches $AB$. Since $SAB$ is a right angle at $A$, then $DA$ is the radius of that incenter.
$$DA = \frac{AS.AB}{AS+AB+SB} = \frac{\sin x \cos x}{1 + \sin x + \cos x} SB$$
Thus $AO : DA = (1+ \sin x + \cos x) : (1 + \cos x) = 1 + (\sin x) / (1 + \cos x)$
Which means $DO:AD:AO = \sin x : (1 + \cos x) : (1 + \sin x + \cos x)$
Now, looking back at the triangle $SAB$ and the plane that contains it,
$$DF = \frac{AD}{\cos \theta} = \frac{1 + \cos x}{(1 + \sin x + \cos x) \cos \theta} OA$$
and
$$DE = DO \cos \theta = \frac{\sin x \cos \theta}{1 + \sin x + \cos x} OA$$
So
$$DG^2 = EG^2 - DE^2 = EF^2 - DE^2 = (DE + DF)^2 - DE^2 = DF(DF + 2DE)$$
$$ = \frac{OA^2}{(1 + \sin x + \cos x)^2} \frac{1 + \cos x}{\cos \theta} \left(\frac{1 + \cos x}{\cos \theta} + 2\sin x \cos \theta \right)$$
Since $x = 2\theta$, then $1 + \cos x = 2 \cos^2 \theta$
$$(1 + \sin x + \cos x)^2 = (2 \cos^2 \theta + 2 \sin \theta \cos \theta)^2 = 4 \cos^2 \theta (\sin \theta + \cos \theta)^2$$
and
$$ \frac{1 + \cos x}{\cos \theta} + 2\sin x \cos \theta = 2 \cos \theta + 2 \sin x \cos \theta = 2 \cos \theta (1 + \sin x)$$
So
$$DG^2 = \frac{OA^2}{4 \cos^2 \theta (\sin \theta + \cos \theta)^2} \frac{2 \cos^2 \theta}{\cos \theta} 2 \cos \theta (1 + \sin x)$$
$$ = OA^2 \frac{1 + \sin x}{(\sin \theta + \cos \theta)^2}$$
But
$$1 + \sin x = 1 + 2 \sin \theta \cos \theta = \cos^2 \theta + \sin^2 \theta + 2 \sin \theta \cos \theta = (\sin \theta + \cos \theta)^2$$
So $DG^2 = OA^2$ which means $DG = OA$
Thursday, March 18, 2010
Solution: Osculating Circle, Ellipse, and Cone
Original Problem: http://dharmath.blogspot.com/2010/03/osculating-circle-ellipse-and-cone.html
An osculating circle of a point on a curve is defined as a circle that:
1. passes through that point
2. whose slope at that point is the same of the slope of the curve at that point
3. whose radius is the same as the radius of curvature of the curve at that point
In other words, it is a second-degree approximation circle of the curve at that point.
http://en.wikipedia.org/wiki/Osculating_circle
Given a cone whose half-angle is $\theta$, we take a cross section with a plane whose incident angle is $\theta$. That is, the plane is perpendicular to one of the cone rays. Naturally, the cross section forms an ellipse.
If O is the intersection of the main axis of the cone and the cross section, and A is the point on the ellipse's major axis that's closest to O, then prove that a circle with center O and radius OA is an osculating circle to the ellipse at A.
Hint: for people without any knowledge of calculus, the radius of osculating circle at A is $b^2/a$ where $b$ is half the length of minor axis and $a$ is half the length of major axis (standard ellipse notation).
The rest of the problem can be done without using calculus.
As given in the hint, the radius of the osculating circle is $b^2/a$. And clearly the circle in the problem passes through A and its tangent at A is perpendicular to the major axis, hence coincides with the ellipse's tangent. We are left to prove that $OA = b^2/a$.
Let B be the point on the major axis that's farthest to O, and let C be the vertex of the ellipse. Let $x = 2 \theta$ be the angle of the cone. We also note that $AO \perp AC$.
Now the length of major axis $2a = AB = BC \sin x \iff \frac{a}{BC} = \frac{\sin x}{2}$.
Since CO is an angle bisector, then $OA/OB = CA/CB = \cos x$
$$\frac{OA}{AB-OA} = \cos x \iff OA = \frac{AB \cos x}{1 + \cos x} = \frac{2a \cos x}{1 + \cos x}$$
Now, let D be the point where the smaller Dandelin Sphere touches the cutting plane.
http://en.wikipedia.org/wiki/Dandelin_spheres
D is the focus that's closest to A. Therefore $DA = a-c$ where $c = \sqrt{a^2-b^2}$ (using the standard ellipse notation). But the center of the Dandelin sphere is also the incenter of the triangle ABC, so DA is the same as inradius of ABC. Using the inradius formula, and since $\angle BAC = \pi/2$
$$DA = \frac{AC.AB}{AC+AB+BC} = \frac{BC \cos x . BC \sin x}{BC \cos x + BC \sin x + BC} = BC \frac{\cos x \sin x}{1+\sin x + \cos x}$$
So
$$a-c = BC \frac{\cos x \sin x}{1+\sin x + \cos x}$$
$$c/BC = a/BC - \frac{\cos x \sin x}{1+\sin x + \cos x} = \frac{\sin x}{2} - \frac{\cos x \sin x}{1+\sin x + \cos x} = \frac{\sin x}{2} . \frac{1 + \sin x - \cos x}{1 + \sin x + \cos x}$$
Thus $$\frac{c}{a} = \frac{1 + \sin x - \cos x}{1 + \sin x + \cos x}$$
Because $a^2 = b^2+c^2$,
$$\left( \frac{b}{a} \right)^2 = 1 - \left( \frac{c}{a} \right)^2 = 1 - \frac{(1 + \sin x - \cos x)^2}{(1 + \sin x + \cos x)^2} = \frac{4(1+\sin x)(\cos x)}{(1 + \sin x + \cos x)^2}$$
But
$$(1 + \sin x + \cos x)^2 = (1 + \sin^2 x + \cos^2 x + 2 \sin x + 2 \cos x + 2 \sin x \cos x)$$
$$= 2(1+\sin x)(1+\cos x)$$
So
$$\frac{b^2}{a^2} = \frac{2 \cos x}{1 + \cos x} = \frac{OA}{a}$$
Which means $OA = b^2/a$
Alternative solution available here: Second Solution
An osculating circle of a point on a curve is defined as a circle that:
1. passes through that point
2. whose slope at that point is the same of the slope of the curve at that point
3. whose radius is the same as the radius of curvature of the curve at that point
In other words, it is a second-degree approximation circle of the curve at that point.
http://en.wikipedia.org/wiki/Osculating_circle
Given a cone whose half-angle is $\theta$, we take a cross section with a plane whose incident angle is $\theta$. That is, the plane is perpendicular to one of the cone rays. Naturally, the cross section forms an ellipse.
If O is the intersection of the main axis of the cone and the cross section, and A is the point on the ellipse's major axis that's closest to O, then prove that a circle with center O and radius OA is an osculating circle to the ellipse at A.
Hint: for people without any knowledge of calculus, the radius of osculating circle at A is $b^2/a$ where $b$ is half the length of minor axis and $a$ is half the length of major axis (standard ellipse notation).
The rest of the problem can be done without using calculus.
Solution
As given in the hint, the radius of the osculating circle is $b^2/a$. And clearly the circle in the problem passes through A and its tangent at A is perpendicular to the major axis, hence coincides with the ellipse's tangent. We are left to prove that $OA = b^2/a$.
Let B be the point on the major axis that's farthest to O, and let C be the vertex of the ellipse. Let $x = 2 \theta$ be the angle of the cone. We also note that $AO \perp AC$.
Now the length of major axis $2a = AB = BC \sin x \iff \frac{a}{BC} = \frac{\sin x}{2}$.
Since CO is an angle bisector, then $OA/OB = CA/CB = \cos x$
$$\frac{OA}{AB-OA} = \cos x \iff OA = \frac{AB \cos x}{1 + \cos x} = \frac{2a \cos x}{1 + \cos x}$$
Now, let D be the point where the smaller Dandelin Sphere touches the cutting plane.
http://en.wikipedia.org/wiki/Dandelin_spheres
D is the focus that's closest to A. Therefore $DA = a-c$ where $c = \sqrt{a^2-b^2}$ (using the standard ellipse notation). But the center of the Dandelin sphere is also the incenter of the triangle ABC, so DA is the same as inradius of ABC. Using the inradius formula, and since $\angle BAC = \pi/2$
$$DA = \frac{AC.AB}{AC+AB+BC} = \frac{BC \cos x . BC \sin x}{BC \cos x + BC \sin x + BC} = BC \frac{\cos x \sin x}{1+\sin x + \cos x}$$
So
$$a-c = BC \frac{\cos x \sin x}{1+\sin x + \cos x}$$
$$c/BC = a/BC - \frac{\cos x \sin x}{1+\sin x + \cos x} = \frac{\sin x}{2} - \frac{\cos x \sin x}{1+\sin x + \cos x} = \frac{\sin x}{2} . \frac{1 + \sin x - \cos x}{1 + \sin x + \cos x}$$
Thus $$\frac{c}{a} = \frac{1 + \sin x - \cos x}{1 + \sin x + \cos x}$$
Because $a^2 = b^2+c^2$,
$$\left( \frac{b}{a} \right)^2 = 1 - \left( \frac{c}{a} \right)^2 = 1 - \frac{(1 + \sin x - \cos x)^2}{(1 + \sin x + \cos x)^2} = \frac{4(1+\sin x)(\cos x)}{(1 + \sin x + \cos x)^2}$$
But
$$(1 + \sin x + \cos x)^2 = (1 + \sin^2 x + \cos^2 x + 2 \sin x + 2 \cos x + 2 \sin x \cos x)$$
$$= 2(1+\sin x)(1+\cos x)$$
So
$$\frac{b^2}{a^2} = \frac{2 \cos x}{1 + \cos x} = \frac{OA}{a}$$
Which means $OA = b^2/a$
Alternative solution available here: Second Solution
Friday, March 12, 2010
Solution: Tennis Tournament
Original problem: http://dharmath.blogspot.com/2010/03/tennis-tournament.html
In a tennis tournament of 100 people, each player plays every other players exactly once. There is no draw in a tennis game, one side always wins.
Given that no player loses all of his games, prove that there is a cycle of exactly 3 players. That is, there are players A,B, and C such that A defeats B, B defeats C, and C defeats A.
First Solution
First we prove that there exists a cycle of any length in the tournament. Indeed, take player A, "mark" him, and take any player that A defeats, say B, and also mark that player.. And take any player that B defeats, say C, mark him, and so on. At each turn, we are guaranteed to find a player that loses to that player. If we ever find a player that we have marked before, we obtain a cycle. But the number of marked players increases steadily while there is only a finite number of players in the tournament. Sooner or later, we will run out of players and we are guaranteed to return to a previously marked player.
If this cycle that we found has length 3, then we are done. Now we establish the following statement via induction:
A cycle of length at least 3 contains a cycle of length 3.
The base case is trivial. Now suppose we have a cycle of length $k: A_1, A_2, \cdots, A_k$ where $A_i$ beats $A_{i+1}$ and $A_k$ beats $A_1$.
If $A_1$ beats $A_{k-1}$ then we have a cycle of length 3: $A_1$ beats $A_{k-1}$ beats $A_k$ beats $A_1$.
If $A_{k-1}$ beats $A_1$ then we have a cycle of length $k-1: A_1, \cdots, A_{k-1}$ which also contains a cycle of length 3 by induction hypothesis.
In a tennis tournament of 100 people, each player plays every other players exactly once. There is no draw in a tennis game, one side always wins.
Given that no player loses all of his games, prove that there is a cycle of exactly 3 players. That is, there are players A,B, and C such that A defeats B, B defeats C, and C defeats A.
First Solution
First we prove that there exists a cycle of any length in the tournament. Indeed, take player A, "mark" him, and take any player that A defeats, say B, and also mark that player.. And take any player that B defeats, say C, mark him, and so on. At each turn, we are guaranteed to find a player that loses to that player. If we ever find a player that we have marked before, we obtain a cycle. But the number of marked players increases steadily while there is only a finite number of players in the tournament. Sooner or later, we will run out of players and we are guaranteed to return to a previously marked player.
If this cycle that we found has length 3, then we are done. Now we establish the following statement via induction:
A cycle of length at least 3 contains a cycle of length 3.
The base case is trivial. Now suppose we have a cycle of length $k: A_1, A_2, \cdots, A_k$ where $A_i$ beats $A_{i+1}$ and $A_k$ beats $A_1$.
If $A_1$ beats $A_{k-1}$ then we have a cycle of length 3: $A_1$ beats $A_{k-1}$ beats $A_k$ beats $A_1$.
If $A_{k-1}$ beats $A_1$ then we have a cycle of length $k-1: A_1, \cdots, A_{k-1}$ which also contains a cycle of length 3 by induction hypothesis.
Tuesday, January 12, 2010
Solution: Coupon drawing
Original problem here: http://dharmath.thehendrata.com/2010/01/12/coupon-drawing/
A container holds $N$ coupons. You draw successive coupons from the container, observe the coupon drawn, and then replace the coupon. What is the expected number of draws needed until all $N$ coupons have been seen at least once?
Challenge: what is the probability that the process ends after exactly $M$ draws?
A container holds $N$ coupons. You draw successive coupons from the container, observe the coupon drawn, and then replace the coupon. What is the expected number of draws needed until all $N$ coupons have been seen at least once?
Challenge: what is the probability that the process ends after exactly $M$ draws?
Thursday, December 17, 2009
Solution: Stones and Marbles
Original problem: here
First, I apologize that the problem was not carefully worded. The problem statement should have been: find all initial conditions where it's always possible for Bob to empty all the three boxes.
There are 3 boxes, and 2010 stones and 2010 marbles are put arbitrarily inside those three boxes.
At each step, Bob is allowed to either:
1. take a stone from one box, a marble from another box, and put them on the third box
2. add or subtract all boxes by the same number of stones
3. add or subtract all boxes by the same number of marbles
Prove or disprove, that by repeating these steps, Bob can empty all three boxes.
First, I apologize that the problem was not carefully worded. The problem statement should have been: find all initial conditions where it's always possible for Bob to empty all the three boxes.
There are 3 boxes, and 2010 stones and 2010 marbles are put arbitrarily inside those three boxes.
At each step, Bob is allowed to either:
1. take a stone from one box, a marble from another box, and put them on the third box
2. add or subtract all boxes by the same number of stones
3. add or subtract all boxes by the same number of marbles
Prove or disprove, that by repeating these steps, Bob can empty all three boxes.
Wednesday, December 2, 2009
Solution: Inequality
Original problem: http://dharmath.thehendrata.com/2009/12/02/inequality/
For positive real number $a,b,c$ prove that
$2\sqrt{ab+bc+ca} \leq \sqrt{3} \sqrt[3]{(a+b)(b+c)(c+a)}$
For positive real number $a,b,c$ prove that
$2\sqrt{ab+bc+ca} \leq \sqrt{3} \sqrt[3]{(a+b)(b+c)(c+a)}$
Monday, November 30, 2009
Solution: 3 Variable Inequality
Original problem: http://dharmath.thehendrata.com/2009/11/24/3-variable-inequality/
For $a,b,c > 0$, prove that:
$! (ab(a+b) + bc(b+c) + ca(c+a))^2 \geq 4abc(a+b+c)(a^2+b^2+c^2)$
For $a,b,c > 0$, prove that:
$! (ab(a+b) + bc(b+c) + ca(c+a))^2 \geq 4abc(a+b+c)(a^2+b^2+c^2)$
Solution: Integer Inequality
Original problem: http://dharmath.thehendrata.com/2009/11/27/integer-inequality/
For any positive real number $t$, prove that there are integers $a,b,c,d$ such that
$! a^3b+b^3c+c^3d < tabcd$
For any positive real number $t$, prove that there are integers $a,b,c,d$ such that
$! a^3b+b^3c+c^3d < tabcd$
Subscribe to:
Posts (Atom)