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)$$
Thursday, April 22, 2010
Critical Height
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:
http://dharmath.blogspot.com/2010/04/solution-1-critical-height.html
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:
http://dharmath.blogspot.com/2010/04/solution-1-critical-height.html
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.
Happy Saint Math Trick's Day
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: http://dharmath.blogspot.com/2010/03/solution-happy-saint-math-tricks-day.html
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: http://dharmath.blogspot.com/2010/03/solution-happy-saint-math-tricks-day.html
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$
Which jug is poisoned?
You have 1000 jugs of wine, one of which has been poisoned. You have access to rats that would die within 23 hours of drinking that poison. You need to determine which jug is poisoned within 24 hours. How many rats do you need at minimum?
Thursday, March 18, 2010
Which stack has counterfeit coins?
Credit to this problem goes to MIT Technology Review Puzzle Corner, November/December 2009 Edition.
Given thirteen stacks each containing four coins, we are told that exactly one stack contains all counterfeit coins. A counterfeit coin weighs less than a good coin by an amount not exceeding 5 grams, and all good coins weigh an integral number of grams.
We are given a precision scale with a very wide area to put the coins on. We need to answer all these three questions all in two weighings:
1. What is the weight of a good coin?
2. What is the weight of a counterfeit coin?
3. Which stack has the counterfeit coins?
Given thirteen stacks each containing four coins, we are told that exactly one stack contains all counterfeit coins. A counterfeit coin weighs less than a good coin by an amount not exceeding 5 grams, and all good coins weigh an integral number of grams.
We are given a precision scale with a very wide area to put the coins on. We need to answer all these three questions all in two weighings:
1. What is the weight of a good coin?
2. What is the weight of a counterfeit coin?
3. Which stack has the counterfeit coins?
Subscribe to:
Posts (Atom)