Oct 27, 2023·edited Oct 27, 2023Liked by Zach Wissner-Gross
A slight modification to the sphere-stacking problem makes it really interesting! If you have only N spheres, what's the maximum tower height, as a function of N? (because, as JBL noted, with infinite spheres the tower can be made arbitrarily high.)
Spoilers below to my approach for this modification.
First, we can reduce this to stacking semicircles instead of hemispheres, which is equivalent by symmetry, and easier to work with. Also, set the bottom sphere to have R=1. First, I'll consider N=2: one more semicircle, on top of the R=1 one. Let's set it so that it rests on the lower semicircle at an elevation angle of A, i.e. the coordinates of the intersection point are (cos A, sin A). Clearly the radius of the upper semicircle is cos A, and its parametric form is (cos A cos t, cos A sin t + sin A). This is of the form (r*cos t, r*sin t + y0). This y-coordinate is maximized at t = pi/2 with a value of (cos A + sin A). So to solve this for N = 2, we need to pick A to maximize (cos A + sin A). This is simple to do, but let me dig a bit deeper (it'll be useful later). Maximizing (cos A + sin A) is equivalent to picking the point on the unit circle whose Cartesian coordinates sum to a maximum (since a unit circle is parameterized by (cos A, sin A)). This maximum occurs at A = asin(1/sqrt(2)) = pi/4, with a value of 2/sqrt(2).
Okay, on to N = 3. I'll again form the parametric equations for the stacked semicircles. The angle B will define where on the middle semicircle the top semicircle will be placed. From the previous part, the parametric equation for the middle semicircle is (cos A cos t, cos A sin t + sin A), so the point of intersection is at t = B -> (cos A cos B, cos A sin B + sin A). The new semicircle will clearly have radius cos A cos B, and will be shifted vertically up from the origin by a distance of (cos A sin B + sin A). The parameterized y-coordinate will be (cos A cos B) sin t + (cos A sin B + sin A), which is of the form (r*sin t + y0). Anyway, this is obviously maximized at t = pi/2, so now we need to pick A and B to maximize the following:
cos A cos B + cos A sin B + sin A
Now, this looks a lot like the Cartesian definition of spherical coordinates (just with the sines and cosines flipped, which is an equivalent way to parametrize a sphere, just with shifted bounds on the parameters. Proof left as an exercise for the reader). So now, we need to find the point on the unit sphere that maximizes X + Y + Z. Skipping the formal proof, this occurs when X = Y = Z, and so X = Y = Z = 1 / sqrt(3). Solving for A and B, we have A = asin(1/sqrt(3)) and B = asin(1/sqrt(2)) = pi/4, but more importantly, the value of the maximum, and the height of the highest N = 3 stack, is 3 * 1/sqrt(3); the sum of the Cartesian components of that maximizing point on the unit sphere.
The last step here is to demonstrate that increasing N gives an expression for the height of the stack that's equivalent to finding the maximum sum of the Cartesian coordinates of a point on a (N-1)-sphere. This value is N * 1/sqrt(N), or sqrt(N). This is the highest the stack can be with N semicircles, which grows without bound as N -> infinity.
Less geometrically satisfying, but you can also solve with calculus: let the bottom radius be R and we'll stack radius r on top. The height from the bottom of the larger hemisphere to the bottom of the smaller is sqrt(R^2 - r^2), so the new total height is r + sqrt(R^2 - r^2). Differentiate to get 1 - r / sqrt(R^2 - r^2). Let that equal zero, solving gives r = R/sqrt(2). Plugging that back in, we have a total height of sqrt(2) * R.
The induction step: assume the max we can do with N is sqrt(N) times the radius. Let's maximize with N+1, with the bottom being radius R and the next hemisphere on that being radius r. Again the gap from the bottom of the R hemisphere to the bottom of the r one is sqrt(R^2 - r^2). By induction, the total height is then sqrt(N) * r + sqrt(R^2 - r^2), since once we choose r, we know we can get to sqrt(N) * r height with it.
Differentiate to get sqrt(N) - r / sqrt(R^2 - r^2) = 0, so r = R * sqrt(N) / sqrt(N+1), and the new max height is sqrt(N+1) R.
Oh the extra credit is funny because there's a discontinuity at the upper limit, right? Let's say we take a strategy where we always put the new cap with radius c times the old radius (with 0 < c < 1). Then by similarity we have that the height we get in the end satisfies
f(R) = sqrt(R^2 - c^2 R^2) + f(c * R) = R * sqrt(1 - c^2) + c * f(R),
and hence
f(R) = R * sqrt(1 - c^2) / (1 - c) = R * sqrt( (1 + c) / (1 - c) ).
The thing about this function is that it grows to infinity as c approaches 1 from below. So no fixed strategy like this is optimal; instead, we should keep taking successively smaller ratios, and if we do that then our tower will grow without bound.
A variation is to stop after N steps; then I believe your f(R) is multiplied by (1-c^(N+1)). Now there is a value of c that maximizes f(R); for large N, it is 1-a/N, where a is a number that satisfies a certain transcendental equation. f(R) is then R * b * sqrt(N), where b = 0.9 approximately. This is below Evan's maximum of R * sqrt(N), showing that shrinking by a factor of c each step is not quite optimal.
I computed the median number of minutes to get caught at 7. I think this is a much more meaningful metric in this case than average... but to each their own.
I understand the one chosen by Elephant Party is the Speaker and the other parties do not account for voting in our problem. And if those in Elephant Party choose a majority, is this the most votes or an absolute majority (50% or more)?
Here, majority means more than 50%. (If I were asking for the most votes without necessarily having a majority, I would have used the word "plurality.")
Sorry to butt in—what's the best route to pitch a puzzle? Twitter DM? Off-topic Substack reply like this one? I'm sorry I can't find the best way. This puzzle is about Downton Abbey and maximizing the area of plane figures, btw :]
Then do it! Your puzzle could be the highlight of everyone’s weekend. If you have a puzzle idea, shoot me an email [link in column]. I love it when ideas also come with solutions, but that’s not a requirement.
(I'm a little behind on my email, but will catch up soon.)
at the scale of the elephant party, 221/3 ≈ 74 is so far away from the threshold for a majority (111), we basically won't see one. so, to good approximation, voting will last for (num candidates - 1) rounds. would be interesting in a state senate, or an HOA...
It's too late for me to submit (busy weekend!) but by intuition, the answer should be so close to 2 that the difference is nigh-immeasurable. Hugo Award ballots are instant-runoff voting, and though voting isn't random, it's extremely uncommon not to take all five rounds of runoffs to get a winner. The chance of winning on the first ballot should be 3 * sum(from i = 111 to 221) [(1/3)^i * (2/3)^(221-i) * binomial(221,i)] if I'm thinking correctly. The very first term in that series is about 0.000000025, and the rest are smaller.
Yeah, it's really close to 2. R has a built-in function pbinom for this purpose, but if you use it the wrong way, you will get a result that rounds to 1. You need the other tail in order to get a small result close to 0, which won't round to 0 because of how floating point numbers work. Your approach is basically the same calculation R does if you set lower.tail = FALSE.
What you might be seeing is the "default" R printing (it makes some assumptions for you depending on your expression), but the underlying numbers should be the same. Try sprintf("%.20f", x) for example with 1 - pbinom(..., lower.tail = TRUE) and it should be the same
A slight modification to the sphere-stacking problem makes it really interesting! If you have only N spheres, what's the maximum tower height, as a function of N? (because, as JBL noted, with infinite spheres the tower can be made arbitrarily high.)
Spoilers below to my approach for this modification.
First, we can reduce this to stacking semicircles instead of hemispheres, which is equivalent by symmetry, and easier to work with. Also, set the bottom sphere to have R=1. First, I'll consider N=2: one more semicircle, on top of the R=1 one. Let's set it so that it rests on the lower semicircle at an elevation angle of A, i.e. the coordinates of the intersection point are (cos A, sin A). Clearly the radius of the upper semicircle is cos A, and its parametric form is (cos A cos t, cos A sin t + sin A). This is of the form (r*cos t, r*sin t + y0). This y-coordinate is maximized at t = pi/2 with a value of (cos A + sin A). So to solve this for N = 2, we need to pick A to maximize (cos A + sin A). This is simple to do, but let me dig a bit deeper (it'll be useful later). Maximizing (cos A + sin A) is equivalent to picking the point on the unit circle whose Cartesian coordinates sum to a maximum (since a unit circle is parameterized by (cos A, sin A)). This maximum occurs at A = asin(1/sqrt(2)) = pi/4, with a value of 2/sqrt(2).
Okay, on to N = 3. I'll again form the parametric equations for the stacked semicircles. The angle B will define where on the middle semicircle the top semicircle will be placed. From the previous part, the parametric equation for the middle semicircle is (cos A cos t, cos A sin t + sin A), so the point of intersection is at t = B -> (cos A cos B, cos A sin B + sin A). The new semicircle will clearly have radius cos A cos B, and will be shifted vertically up from the origin by a distance of (cos A sin B + sin A). The parameterized y-coordinate will be (cos A cos B) sin t + (cos A sin B + sin A), which is of the form (r*sin t + y0). Anyway, this is obviously maximized at t = pi/2, so now we need to pick A and B to maximize the following:
cos A cos B + cos A sin B + sin A
Now, this looks a lot like the Cartesian definition of spherical coordinates (just with the sines and cosines flipped, which is an equivalent way to parametrize a sphere, just with shifted bounds on the parameters. Proof left as an exercise for the reader). So now, we need to find the point on the unit sphere that maximizes X + Y + Z. Skipping the formal proof, this occurs when X = Y = Z, and so X = Y = Z = 1 / sqrt(3). Solving for A and B, we have A = asin(1/sqrt(3)) and B = asin(1/sqrt(2)) = pi/4, but more importantly, the value of the maximum, and the height of the highest N = 3 stack, is 3 * 1/sqrt(3); the sum of the Cartesian components of that maximizing point on the unit sphere.
The last step here is to demonstrate that increasing N gives an expression for the height of the stack that's equivalent to finding the maximum sum of the Cartesian coordinates of a point on a (N-1)-sphere. This value is N * 1/sqrt(N), or sqrt(N). This is the highest the stack can be with N semicircles, which grows without bound as N -> infinity.
Less geometrically satisfying, but you can also solve with calculus: let the bottom radius be R and we'll stack radius r on top. The height from the bottom of the larger hemisphere to the bottom of the smaller is sqrt(R^2 - r^2), so the new total height is r + sqrt(R^2 - r^2). Differentiate to get 1 - r / sqrt(R^2 - r^2). Let that equal zero, solving gives r = R/sqrt(2). Plugging that back in, we have a total height of sqrt(2) * R.
The induction step: assume the max we can do with N is sqrt(N) times the radius. Let's maximize with N+1, with the bottom being radius R and the next hemisphere on that being radius r. Again the gap from the bottom of the R hemisphere to the bottom of the r one is sqrt(R^2 - r^2). By induction, the total height is then sqrt(N) * r + sqrt(R^2 - r^2), since once we choose r, we know we can get to sqrt(N) * r height with it.
Differentiate to get sqrt(N) - r / sqrt(R^2 - r^2) = 0, so r = R * sqrt(N) / sqrt(N+1), and the new max height is sqrt(N+1) R.
Oh the extra credit is funny because there's a discontinuity at the upper limit, right? Let's say we take a strategy where we always put the new cap with radius c times the old radius (with 0 < c < 1). Then by similarity we have that the height we get in the end satisfies
f(R) = sqrt(R^2 - c^2 R^2) + f(c * R) = R * sqrt(1 - c^2) + c * f(R),
and hence
f(R) = R * sqrt(1 - c^2) / (1 - c) = R * sqrt( (1 + c) / (1 - c) ).
The thing about this function is that it grows to infinity as c approaches 1 from below. So no fixed strategy like this is optimal; instead, we should keep taking successively smaller ratios, and if we do that then our tower will grow without bound.
A variation is to stop after N steps; then I believe your f(R) is multiplied by (1-c^(N+1)). Now there is a value of c that maximizes f(R); for large N, it is 1-a/N, where a is a number that satisfies a certain transcendental equation. f(R) is then R * b * sqrt(N), where b = 0.9 approximately. This is below Evan's maximum of R * sqrt(N), showing that shrinking by a factor of c each step is not quite optimal.
I computed the median number of minutes to get caught at 7. I think this is a much more meaningful metric in this case than average... but to each their own.
I understand the one chosen by Elephant Party is the Speaker and the other parties do not account for voting in our problem. And if those in Elephant Party choose a majority, is this the most votes or an absolute majority (50% or more)?
Here, majority means more than 50%. (If I were asking for the most votes without necessarily having a majority, I would have used the word "plurality.")
Sorry to butt in—what's the best route to pitch a puzzle? Twitter DM? Off-topic Substack reply like this one? I'm sorry I can't find the best way. This puzzle is about Downton Abbey and maximizing the area of plane figures, btw :]
See the end of each column:
Want to Submit a Puzzle Idea?
Then do it! Your puzzle could be the highlight of everyone’s weekend. If you have a puzzle idea, shoot me an email [link in column]. I love it when ideas also come with solutions, but that’s not a requirement.
(I'm a little behind on my email, but will catch up soon.)
More extra credit solves than the regular puzzle, fun! Does that happen often?
Good catch! Only the second time that's ever happened. (First time was for the very first puzzle.)
Not surprising. I did the extra credit in my head, never got around to doing the nitty-gritty of the regular.
at the scale of the elephant party, 221/3 ≈ 74 is so far away from the threshold for a majority (111), we basically won't see one. so, to good approximation, voting will last for (num candidates - 1) rounds. would be interesting in a state senate, or an HOA...
If anyone does this Fiddler with R, they definitely want to use lower.tail = FALSE. At least, if they don't want to get exactly 2.
It's too late for me to submit (busy weekend!) but by intuition, the answer should be so close to 2 that the difference is nigh-immeasurable. Hugo Award ballots are instant-runoff voting, and though voting isn't random, it's extremely uncommon not to take all five rounds of runoffs to get a winner. The chance of winning on the first ballot should be 3 * sum(from i = 111 to 221) [(1/3)^i * (2/3)^(221-i) * binomial(221,i)] if I'm thinking correctly. The very first term in that series is about 0.000000025, and the rest are smaller.
I think you can submit Monday too
"among those who submit their solution before 11:59 p.m. the Monday after that puzzle was released.'
Yeah, it's really close to 2. R has a built-in function pbinom for this purpose, but if you use it the wrong way, you will get a result that rounds to 1. You need the other tail in order to get a small result close to 0, which won't round to 0 because of how floating point numbers work. Your approach is basically the same calculation R does if you set lower.tail = FALSE.
For the EC you need higher precision it seems.
What you might be seeing is the "default" R printing (it makes some assumptions for you depending on your expression), but the underlying numbers should be the same. Try sprintf("%.20f", x) for example with 1 - pbinom(..., lower.tail = TRUE) and it should be the same