Wikipedia has this elegant image "proving" that max(a,b) > QM > AM > GM > HM > min(a,b), where the middle quantities are the quadratic, arithmetic, geometric, and harmonic means of a and b:
(Of course, we can imagine max(a,b) as the "infinity-mean" and min(a,b) as the "-infinity-mean", naturally extending these definitions. Also, this isn't really a proof, but it does very quickly guide a viewer toward a proof.)
My question concerns the side HG, which is not labeled as any mean. We have two formulas for HG, evident from the figure:
HG^2 = r^2 - (AM-HM)^2
HG^2 = GM^2 - HM^2
Setting these two equal to each other yields the relation:
r^2 - (AM-HM)^2 = GM^2 - HM^2
which can be used as the last of seven equations relating the quantities. This is good enough on its own and requires no further explanation, but we can add those negative terms to both sides to make the equation more... "hypotenuse-like" (?):
r^2 + HM^2 = GM^2 + (AM-HM)^2
What I'm curious about, which may be very easy or very difficult (I'm not sure), is whether this new equation can be represented geometrically. Is there some way to swing these sides around on this figure such that the equation above is what is represented? It may be a silly question and may reveal how lazy I am, as it might be a simple step. I just don't see it immediately and don't care to rigorously investigate it.
Edit: Bonus points if you can provide a geometric justification for the version where we cancel HM^2 from both sides:
r^2 + 2*AM*HM = GM^2 + AM^2
I assume your actual question is why is the side HC the harmonic mean HM. (AM and GM are obvious.)
There is no need to find or use side HG in the diagram. Triangles OGC and GHC are similar so GM/AM = HC/GM
---> HC = GM2/AM = (ab) / ((a+b)/2) = 2ab / (a+b), which is the harmonic mean.
Arcorann wrote:
A secret society would like to poll their 60 members on some yes/no question. They are only interested in the parity of the number of yes votes. However, they will only allow a given pollster to interview 50 members, and each pollster may only report back a number between 0 and 50 inclusive. It is believed that up to one pollster may lie or make a mistake in reporting.
* Find the smallest number of pollsters required (easy).
I can't answer the other questions as I don't understand what they are asking. However, for this, it seems the answer is 18: Group the 60 members in 6 groups of 10: A,B,C,D,E,F. Assign three pollsters each for six blocks as follows: ABCDE (x3), ABCDF (x3), ABCEF (x3), ABDEF (x3), ACDEF (x3), BCDEF (x3). You need to do x3 for each block to get the correct value. Then add up the results (# of yes votes) of the correct values for the six blocks and divide by 5 to get the total number of yes votes, and therefore the correct parity. (I don't know if the answer is changed just by only being interested in the parity.)
I assume your actual question is why is the side HC the harmonic mean HM.
Not what I was after, although the geometry you point out is interesting.
I'm wondering whether there's some special way to use the diagram I posted to construct two right triangles adjoined by their hypotenuse like so:
This seems especially difficult because radius r and line HC (the HM) don't appear to "communicate" with each other on the figure, nor do lines GC (the GM) and OH (AM minus HM). But maybe I'm missing something obvious.
A secret society would like to poll their 60 members on some yes/no question. They are only interested in the parity of the number of yes votes. However, they will only allow a given pollster to interview 50 members, and each pollster may only report back a number between 0 and 50 inclusive. It is believed that up to one pollster may lie or make a mistake in reporting.
* Find the smallest number of pollsters required (easy).
I can't answer the other questions as I don't understand what they are asking. However, for this, it seems the answer is 18: Group the 60 members in 6 groups of 10: A,B,C,D,E,F. Assign three pollsters each for six blocks as follows: ABCDE (x3), ABCDF (x3), ABCEF (x3), ABDEF (x3), ACDEF (x3), BCDEF (x3). You need to do x3 for each block to get the correct value. Then add up the results (# of yes votes) of the correct values for the six blocks and divide by 5 to get the total number of yes votes, and therefore the correct parity. (I don't know if the answer is changed just by only being interested in the parity.)
Let me try to clarify a few points then (looking at what I wrote again it seems I skipped a step when transferring things over):
* The pollsters don't have to interview 50 people, they can interview fewer. As a result, we only need 6 pollsters if we want the exact number of yes votes, but since we're only interested in parity the lower bound is smaller than that.
* The first question should have been "find a lower bound on the number of pollsters required". That was a mistake on my part.
* The pollsters don't necessarily have to report the number of yes votes; they may report an integer based on some other function of the votes they received (again, one pollster may report an incorrect result). The lower bound of pollsters can't be attained if they have to report the number of yes votes (why?), but can with some other function.
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
Arcorann wrote:
FractalFusion wrote:
Arcorann wrote:
A secret society would like to poll their 60 members on some yes/no question. They are only interested in the parity of the number of yes votes. However, they will only allow a given pollster to interview 50 members, and each pollster may only report back a number between 0 and 50 inclusive. It is believed that up to one pollster may lie or make a mistake in reporting.
* Find the smallest number of pollsters required (easy).
I can't answer the other questions as I don't understand what they are asking. However, for this, it seems the answer is 18: Group the 60 members in 6 groups of 10: A,B,C,D,E,F. Assign three pollsters each for six blocks as follows: ABCDE (x3), ABCDF (x3), ABCEF (x3), ABDEF (x3), ACDEF (x3), BCDEF (x3). You need to do x3 for each block to get the correct value. Then add up the results (# of yes votes) of the correct values for the six blocks and divide by 5 to get the total number of yes votes, and therefore the correct parity. (I don't know if the answer is changed just by only being interested in the parity.)
Let me try to clarify a few points then (looking at what I wrote again it seems I skipped a step when transferring things over):
* The pollsters don't have to interview 50 people, they can interview fewer. As a result, we only need 6 pollsters if we want the exact number of yes votes, but since we're only interested in parity the lower bound is smaller than that.
* The first question should have been "find a lower bound on the number of pollsters required". That was a mistake on my part.
* The pollsters don't necessarily have to report the number of yes votes; they may report an integer based on some other function of the votes they received (again, one pollster may report an incorrect result). The lower bound of pollsters can't be attained if they have to report the number of yes votes (why?), but can with some other function.
For the first question, the answer seems to be 4. We can divide the 60 members in 5 groups of 12 and split the pollsters as ABCD / BCDE / ABDE / ACE. Each pollster can report the parity of each group as their answer has more than 4 bits.
For the others questions, by 'correct result' do you mean the exact quantity of yes votes? Are we supposed to find the smallest amount of required pollsters? And for the third question, is that constrained on such minimum amount of pollster? It's not clear what those are asking.
Edit: perhaps some word is missing? Did you mean each pollster can report a different number or something like that?
For fun:
If S is an empty set, show that inf S = +infinity, and sup S = -infinity
Is there a non-empty subset S of the reals such that inf S > sup S?
Because S is empty, every extended real number is a lower bound of S, and the largest of them is +∞ and so inf S = +∞. Likewise, every extended real number is an upper bound of S, and the smallest of them is -∞ and so sup S = -∞.
Of course there is no non-empty subset S of the reals such that inf S > sup S: given a real number b in S, inf S ≤ b ≤ sup S.
This one is not really a challenge, but a dissertation, and I wanna know what people here think about it.
I came across a post that asked the "correct" value of 8 / 2 * 4
Of course, the way we all learn about this is that division and multiplication are two different operations that have the same precedence, and the way to resolve the ambiguity in the expression is to compute the operations from left to right, and the result is 16. Learning this way makes you question why it has to be left to right. Why not right to left? And also, why not have one operation have precedence over the other.
I think there's a reason why lots of people discuss this, and we should do a better job teaching this. One clear tendency in mathematics is abstraction and minimalism. This principle says that the less axioms we need to assume the better, because the more general our thought process becomes. If we understand multiplication like this, if we want to keep expressions to a minimum, avoiding the use of parentheses, there's clearly a way that's more minimal, and in my opinion, the reason for the left-to-right rule.
The better way to teach this, for me, would be to say that multiplication and division are not distinct operations, but there's in fact only one "fundamental" operation, which is of course multiplication. It turns out that it has some very useful properties. For example, it is associative (for real numbers, also commutative, although that's not important for my argument here), it has a unit element, namely 1, such that a * 1 = 1 * a = a, and every nonzero element a has an inverse, you can always find an element a-1 such that a * a-1 = 1. Division is merely a consequence of these properties, when we write a / b, what we really mean is a * b-1.
Why is it better to think this way? Because it's clear that an expression like 8 / 2 * 4 should have a "canonical" result. When we write 8 / 2 * 4, what we really mean is 8 * (1/2) * 4. From this point of view, there's no reason to group the numbers with parentheses, because there's no need to do that, since multiplication is associative! We only treat division and multiplication as separate operations and apply the left-to-right rule because it always gives the same result as this more complicated explanation.
Anyway, what do you guys think? Do you agree with me?
I came across a post that asked the "correct" value of 8 / 2 * 4
This reminds me of one of the first things my teacher said to our class when we were taught fractions:
"From now on you are not allowed to use / anymore. Only use ― now."
After this we would be reminded of it each time we would make that "mistake", and eventually a simple reminder turned into a real mistake like a wrong calculation and we would lose points.
And indeed, this resolves the ambiguity, as this:
8
― * 2
4
is simply not the same as this:
8
――
4 * 2
In retrospect, that's a neat solution here. You can't really explain the intricacies of mathematics about divisions being a side-effect of multiplications having inverses coming from the multiplicative identity or something like that. Division makes intuitive sense because you have objects, and then you give equal amounts of objects to multiple people. That's a practical application of dividing, and how it's taught from the very beginning. It'd be very difficult to tell people division doesn't exist. Making people avoid writing something ambiguous, that's a lot easier.
But of course, this division-rewriting idea doesn't solve the problem of what people think a "correct" value of 8 / 2 * 4 is.
Whenever people personally asked me what I think the correct solution is (which apparently people care about), I always answer that the term is ill-formed. Then I give an ambiguity in something more familiar: language. "John saw the man on the mountain with a telescope." (Who was on the mountain, who had the telescope, etc.). I say that it's the same in this math situation.
People who are more comfortable with ambiguities in language because well humans invented it and humans aren't perfect, but want math to be this rigorous ideal because math just exists.
Those people forget humans also invented math notation.
Warning: Might glitch to creditsI will finish this ACE soon as possible
(or will I?)
Why is it better to think this way? Because it's clear that an expression like 8 / 2 * 4 should have a "canonical" result. When we write 8 / 2 * 4, what we really mean is 8 * (1/2) * 4. From this point of view, there's no reason to group the numbers with parentheses, because there's no need to do that, since multiplication is associative! We only treat division and multiplication as separate operations and apply the left-to-right rule because it always gives the same result as this more complicated explanation.
Anyway, what do you guys think? Do you agree with me?
I agree that it makes sense to know the relationship between x / 2 and x * (1/2), and that this relationship should probably be at least mentioned when teaching division. But I don't think it's necessary to always conceptualize division in this way.
That said, this conversion comes up a lot in higher-level math, at least in my experience. Especially so when you start dealing with calculus, as we have rules that can separate constant co-efficients out of an equation. (Simple example): Say we had a problem that said we need to derive f(x) = (x^2) / 2. While there are tricks to deriving a "fractional" equation, it's much simpler if we know that we can show this function like so: f(x) = (1/2)*(x^2). Even more so if 'x' was in the denominator too, besides just a constant. And same if we were to integrate the equation instead.
Also, this relationship between division and multiplication, parallels the relationship between subtraction and addition. Like we've established, you can represent a division as multiplication, so too you can (and do often) represent subtraction as simply adding a negative number (3 = 5 - 2 == 3 = 5 + -2). At least in my schooling, both relationships were explicitly taught, but not until higher-level math (think it was in algebra?). I think it's pretty normal that as we advance in math subjects, we learn the reasons why we were previously taught something "just works that way".
I’m not sure if any of this really answers the question, but here are some random thoughts.
I’ve always found questions like ‘what is the value of 8 / 2 * 4?’ a bit artificial. I think the problem is that, after a certain point, these kinds of expressions don’t really occur in the mathematics we usually do in school or beyond. When I (and I assume this is true for most people) actually sit down and do numerical or algebraic calculations by hand, I never use symbols like / or ÷. Instead, I tend to write everything using fractions and, if necessary, parentheses. Since a fraction is written vertically, there’s no ‘horizontal ambiguity’ when reading an expression from left to right; it’s clear that the top and bottom of the fraction are on equal terms and I never need to think about the order of operations (which, to be honest, I don’t remember anyway).
When I see a question like ‘what is 8 / 2 * 4?’, my first reaction is something like ‘tell me what language you’re speaking first and then I’ll do the calculation for you’. I may even ask for clarification: 'do you mean (8/2) * 4 or 8/(2*4)?'. Like with Masterjun’s English sentence example, I don’t think it’s the responsibility of the listener to have to resolve ambiguities in the message they receive. It should be the responsibility of the speaker to produce a clear, unambiguous message in the first place. I suppose that someone might respond by saying 'the expression is already unambiguous if you follow the standard order of operations'.
The only scenario I can think of where an expression like 8 / 2 * 4 would occur in my life is in computer code (or writing a message on a forum I suppose). In this case, given a particular programming language, we can appeal to the rules of the language to parse the expression unambiguously. I don’t have a lot of experience with different languages, but I assume these rules are consistent across most mainstream languages and also align with the order of operations we learn in school. As for why the rules should be as they are, I think for me the main reason is that the alternative seems confusing. If a division sign were to incorporate more than the numbers or expressions immediately before or after it, then things like 1 / 3 + 4 / 2 would quickly become very confusing for me. In practice, I get a bit paranoid about fractions as they are and I’m not afraid of redundant parentheses. If I need to write a fraction with something other than just numbers, I tend to write things like ()/() before filling in the contents of the parentheses, safe knowing that anything else I write in my line of code isn’t going to be affected by this particular use of the / sign.
To summarise, I guess I don't really care about the question in the context of mathematics, as it's one I haven't had to worry about in over 20 years. I'd be happy to go with either result depending on what the person asking the question prefers, but I may heavily caution them against interpreting 8 / 2 * 4 as 8 /(2 * 4), as I think they are likely to run into problems doing more complicated calculations. In the context of computer programming, well just stick it into Python and see what comes out.
Joined: 10/27/2004
Posts: 1978
Location: Making an escape
I feel that a question like this is important to understand when you have to know how to enter information into a calculator.
I work as an HVAC tech, and bless their hearts, for most of my coworkers, the ability to subtract x from both sides is considered god tier mathematics*. One calculation that we routinely do involves entering the information into a calculator as a/b/c. The problem is, in more formal settings, like in a textbook, it's presented as
a
b*c
And I've known some to get confused about why the multiplication symbol disappears. I think at least one of them asked, shouldn't that mean you type it in as a/b*c? And as much as I would love to sit down with some of them to explain where the discrepency is, I usually just resort to, "I watch math videos for fun, trust me on this one."
*not saying they are dumb, but they are certainly the kind people that only paid enough attention in high school algebra in order to get a C- before forgetting about the subject entirely
A hundred years from now, they will gaze upon my work and marvel at my skills but never know my name. And that will be good enough for me.
This problem is pretty hard to solve by hand, but there's a way to solve it using freely available software and math tables.
For which natural numbers n is the sum of the first n perfect squares also a perfect square?
This problem is pretty hard to solve by hand, but there's a way to solve it using freely available software and math tables.
For which natural numbers n is the sum of the first n perfect squares also a perfect square?
Just the answer: n=1 and n=24 only. This is the Cannonball Problem (link here), whose results are already known for over 100 years. Now before p4wn3r starts talking about elliptic curves, I would like to mention that there are elementary proofs. For example, this proof by Anglin (pdf can be downloaded here for those who are interested).
----
This week's Riddler Classic is an interesting geometric problem. I'll restate it here as follows:
You have a light source that is polarized in the vertical direction, and an unlimited number of polarizers which can be oriented at any rotation angle. The direction can be changed by passing the light through polarizers; however, only the component of light that is in that direction of the polarizer will pass through. Ex: If the polarizer is vertical, all light will pass through. If it is horizontal, no light will pass through. If it is at a 45-degree angle, 1/sqrt(2) of the light will pass through.
Now it is possible to use the polarizers to re-orient the polarity of the light in the horizontal direction, but at a cost. Ex: If two polarizers are used, the best that can be done is half of the original light (this diagram is from the Riddler page):
Of course, with an unlimited number of polarizers, you could just use an arbitrarily large number of polarizers to make a "circular turn" to orient the polarity of the light horizontally while keeping a fraction of the light that is arbitrarily close to 1.
This is where Riddler Classic throws a twist: each polarizer is only 99% effective. So, only 0.99 of the light that is supposed to pass through each polarizer actually passes through.
With this in mind, what number of polarizers should be used to orient the polarity of the light horizontally while keeping the largest possible fraction of light? And what is the largest possible fraction?
(You may wish to use WolframAlpha to help out with this.)
The solution to the cannonball problem using elliptic curves, which is pretty awesome, consists in writing down the sum of squares formula for n, and equating it to a perfect square. We obtain:
n*(n+1)*(2n+1) = 6k^2
Now, if we change the variable names we have:
6y^2 = 2x^3 + 3x^2 + x
This looks like an elliptic curve, because it's y^2 equals a cubic polynomial in x, and just by looking at it we know the number of integer solutions is finite. Why? Well, we can change it to a curve in Weierstrass so to solve it we need to put it in Weierstrass form, so that if we find an integer solution to this curve, we have a candidate for an integer solution to our curve. There's a theorem by Siegel that states that the number of integer points in an elliptic curve is always finite. Since we have a finite number of candidates, we must have a finite number of solutions to this as well.
Now, the hard part is to actually convert it to Weierstrass form. There are several ways to do it. The easiest is to write it in homogeneous form (essentially just put Z's in every monomial until it reaches degree 3) and feed it to sage, together with a rational point, which we can derive from the solution x=1, y=1. From Sage you can find the minimal model and if you read its information well, you find that you arrive at the curve y^2 = x^3 -36x, the morphisms are:
Scheme morphism:
From: Projective Plane Curve over Rational Field defined by 2*x^3 + 3*x^2*z - 6*y^2*z + x*z^2
To: Elliptic Curve defined by y^2 = x^3 + 18*x^2 + 72*x over Rational Field
Defn: Defined on coordinates by sending (x : y : z) to
(-x : -6*y : -1/12*z)
Generic morphism:
From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 18*x^2 + 72*x over Rational Field
To: Abelian group of points on Elliptic Curve defined by y^2 = x^3 - 36*x over Rational Field
Via: (u,r,s,t) = (1, -6, 0, 0)
What this means is: first Sage does (ignore the signs) y' = 6y and z' = z/12. This scaling on z is equivalent to multiplying x and y by 12, which means y' = 72y and x' = 12x
Also, to get to the minimal model it does y' = Y and x' = X - 6. At the end of the day, the rational transformation Y = 72y and X = 12x + 6 brings us to the curve Y^2 = X^3 - 36X, and for every integer we have a candidate integer solution to the original problem.
Now, if you remember, that's exactly the same elliptic curve we used for the congruent number problem from some time ago! Isn't that cool? Anyway, you can simply look it up or just use sage again! Try putting the following code here to see the magic:
Whatever method you use you will find X = 294 and Y = 5040, which correspond to x = 24 and y = 70, which are the only integral solutions beside x=y=1. And there you go, by relying on very general theorems about structure of elliptic curves you managed to solve a classic number theory problem using your computer and no need to understand convoluted elementary proofs. Isn't modern math amazing?
----
FractalFusion wrote:
This week's Riddler Classic is an interesting geometric problem.
This one looks like a simple optimization for me. Suppose you want to do it using n steps. You want to maximize a product of cosines whose argument sums to a given number. To do this you can apply Jensen's inequality for the function log(cos(x)). Since it's concave for 0 < x < pi/2, we find that cos(x/n)^n >= prod_n cos(x_n), when the sum of all x_n is x, and equality happens when each x_n = x/n.
Essentially, what all this means is that to maximize the product of cosines given that all angles sum to some fixed amount, you must choose the arguments of the cosines to divide the interval evenly.
So essentially you want to find the maximum of a^n*cos(pi/2n)^n, for a = 0,99. This sequence has a maximum because it's decreasing for large n.
This one looks like a simple optimization for me. Suppose you want to do it using n steps. You want to maximize a product of cosines whose argument sums to a given number. To do this you can apply Jensen's inequality for the function log(cos(x)). Since it's concave for 0 < x < pi/2, we find that cos(x/n)^n >= prod_n cos(x_n), when the sum of all x_n is x, and equality happens when each x_n = x/n.
Essentially, what all this means is that to maximize the product of cosines given that all angles sum to some fixed amount, you must choose the arguments of the cosines to divide the interval evenly.
So essentially you want to find the maximum of a^n*cos(pi/2n)^n, for a = 0,99. This sequence has a maximum because it's decreasing for large n.
Despite being a physics problem, I actually didn't bother to do this week's Riddler Classic. It seemed too "easy" to me (either literally easy or at least too straightforward to provide any interesting results).
What I assumed was that with each polarizer, some amount of light is lost to inefficiency and some amount is lost to the polarization itself. It stands to reason (I think...) that the number of polarizers is optimized when these two losses are equal. More polarizers means more loss to inefficiency, fewer polarizers means more loss to polarization. Thus, we expect cos(theta) = 0.99.
(By the way, light intensity is proportional to the cosine squared, but whatever. Don't learn your physics from mathematicians.)
I get cos-1(0.99) = 8.11 degrees. That's 90/8.11 = 11.098 polarizers, which we can round off to 11. I guess you'd want to check 12 as a possible solution, but that would require the function to have a very large third or higher derivative, making it asymmetric.
Is this reasoning sound? Does it match your solution? We differentiate [a*cos(pi/2n)]n with respect to n to obtain [a*cos(pi/2n)]n*[ln[a*cos(pi/2n)] + pi/2n*tan(pi/2n)]. (To my great shame, I just had Wolfram Alpha take the derivative, although I see now I should have taken the log of the initial function and differentiated implicitly.) The first term is never zero and we're therefore left with ln[a*cos(pi/2n)] + pi/2n*tan(pi/2n) = 0. I'm sort of stuck here. We can assume n is large, leading to a few simplifications, but more importantly, I'm not able to massage this into a form reducing to a = cos(pi/2n), which would match my guess. Graphing the original function shows that there is indeed a maximum at n = 11.135, a bit higher than my own answer of 11.098 no doubt due to whatever approximation leads to this result, but they're clearly in agreement with each other.
So having more or less given up on the problem at this point, I'm kicking this question back to everyone else: Why does my intuitive answer (light lost to inefficiency equals light lost to polarization) closely match the exact answer (a transcendental equation based on the derivative of the function)? As is often the case, I suspect I'm overlooking something obvious here.
I didn't mention this, but it should be clear (p4wn3r proved it, and there are many other ways to prove it as well) that the angles have to divide the interval evenly.
So we are finding the n that maximizes (a*cos(pi/(2n)))^n. Or equivalently, by taking logs, the n that maximizes n*ln(a*cos(pi/2n)). If we treat n as a real number variable, it turns out that the second derivative of this function is precisely (-pi^2/4)*sec^2(pi/(2n)) which is always negative when n>1, and so n*ln(a*cos(pi/2n)) is always concave down (when n>1) so if there is a maximum to (a*cos(pi/(2n)))^n, the function must increase to this maximum (when n>1) and decrease after that.
So for a=0.99 it suffices to check n=10, n=11 and n=12 which give (0.99*cos(pi/(2n)))^n = 0.799008..., 0.800042..., and 0.799549, respectively. This confirms that the function is maximized when n=11 and the maximum fraction of light is 0.800042...
Bobo the King wrote:
Why does my intuitive answer (light lost to inefficiency equals light lost to polarization) closely match the exact answer (a transcendental equation based on the derivative of the function)?
Take the derivative equation you wrote above: ln[a*cos(pi/2n)] + pi/2n*tan(pi/2n) = 0, and assume n is large. (We'll assume that we need to find "a" as a function of n.) Set x=pi/2n so we have ln(a*cos(x))+x*tan(x)=0, where x is small. Now it turns out that x*tan(x)≈-2*ln(cos(x)); this is because x*tan(x) = x(x+O(x^3)) = x^2+O(x^4), whereas -2*ln(cos(x)) = -2*ln(1- x^2/2 +O(x^4)) = -2(-x^2/2 +O(x^4)) = x^2+O(x^4). So 2*ln(cos(x))+x*tan(x)≈0 and so ln(cos^2(x))+x*tan(x)≈0. So we can make a≈cos(x), or in other words, a≈cos(pi/2n).
Actually I wasn't sure about your intuitive answer since it wasn't so intuitive to me. But it works out somehow! (at least as an approximation)
Bobo the King wrote:
(By the way, light intensity is proportional to the cosine squared, but whatever. Don't learn your physics from mathematicians.)
Yes, that's true. Mathematicians don't always know what they are talking about. Though I'm sure someone would have let Riddler know about Malus's Law at some point; we'll see when the Riddler solutions come out on Friday.
Actually I wasn't sure about your intuitive answer since it wasn't so intuitive to me. But it works out somehow! (at least as an approximation)
Thinking out loud, I'm wondering about your original characterization of the problem as geometric. Let's scrap the idea of inefficiency, which is a little harder to work with geometrically, and just assume any light lost is due to polarization. The inefficiency is modeled as a polarizer set to 8.11 degrees relative to the previous polarizer, allowing 99 percent of the light to pass through (again, ignoring Malus's law). The new problem is to put together these pairs of polarizers such that the the maximum amount of light goes through subject to the constraint that the angles between them sum to 90 degrees. Assuming they're equally spaced, we're actually dividing up 180 degrees with 2n polarizers, agreeing with my solution. (Actually, now I'm wondering why this doesn't involve logarithms anymore. I must have made an approximation somewhere along the way...)
On further thought, let's try to use the same strategy to get rid of those extra angles. The arccosine of 0.995 is 5.73 degrees, so let's have one polarizer whose angle we set followed by another polarizer that's back 5.73 degrees, followed by a third polarizer ahead the same 5.73 degrees, each with 100% efficiency. Now we have one object (three polarizers) that polarize light along their orientation while allowing 99% of the light to pass through. (Yes, I'm aware that 0.995^2 is not exactly 0.99. It's very close, and the actual angle for the second and third polarizers is 5.74 degrees.) We want to divide up 90 degrees with these objects, maximizing the amount of light passing through. I'm sort of visualizing this as three right triangles joined together as one sheet of paper folded back over itself twice to make a right triangle with one loose corner corresponding to the last polarizer. We can fill up our 90 degrees with these objects, then "unfold" the paper (physically corresponding to having the second and third polarizers both set forward 5.73 degrees) and ask what angle maximizes the length of the final edge of the paper. I don't see how this intuitively arrives at 8.11 degrees since the only angle I'm explicitly working with is now 5.73 degrees, but I must be on the right track if my reasoning is sound.
I dunno. I'm often tempted to say that there are no coincidences in math and that every elegant answer has an elegant proof. Godel's incompleteness theorems tell me this isn't true, but it's still hard to assume otherwise and I find that in practical applications, it tends to be true more often than not.
Your intuition is essentially perturbation theory.
If we look at the formula (a*cos(pi/2n))^n, and noticing that a = 1 - d for a small d, we can expand the functions (1-d)^n -> 1 - nd and cos(pi/2n)^n -> 1 - pi^2/8n, provided that both nd and pi^2/8n remain small. Since this is actually true for the solution, we can approximate the expression as 1 - nd - pi^2/8n.
Now, if we call x = nd the loss due to extra polarizations and y = pi^2/8n the loss due to cosines, notice that the product xy = d*pi^2/8 is a constant, and we are interested in minimizing their sum. From AM-GM, this happens when x=y, exactly as you claimed. However, this should not be expected to give the exact result, because of the linearizations in the formula. Doing x=y gives the same result as a=cos(pi/2n) for small arguments. Just notice that 1 - d = 1 - pi^2/8n^2 => n = pi/sqrt(8d).
This estimate of the value of n from this method is 11.1072, a bit different from yours since the equation you solved is a bit different. If you expand more powers in perturbation theory, you can get a better result, at the cost of making the equation harder to solve, so it's probably better to use other numerical methods to solve the transcendental equation.
Perturbation theory does give us some nice information about the limit d -> 0 (or equivalently, a -> 1). I think I would have to be more rigorous to prove this, but by plugging the formula for n, we get that the wave amplitude (which is different from the intensity, and does decay with a cosine) decays by 1 - sqrt(d)*(pi/sqrt(2)). It definitely looks like that in the limit d -> 0, the wave amplitude decreases asymptotically with an sqrt(d) dependency, and the proportionality factor is pi/sqrt(2).
Here's something pretty cool I stumbled on recently.
I was watching some Digimon Adventure episodes recently and in one of them, some code is shown on Koushiro's laptop, and it's actually a pretty interesting algorithm.
As the internet is a very large place, other people had already seen and analyzed this, some guy ported it to Java here.
In any case, the comment and the name of the function pretty much give away what this thing does, it prints a coastline using a fractal.
To analyze it better, it helps to see which BASIC dialect this thing is, and it's actually X-BASIC, a programming language for the Sharp X86000, a home computer released only in Japan during the 80s. The functions are documented in this page: http://ww3.enjoy.ne.jp/~zoomark/ip/xb/xb_frm.html
Essentially, sqr() is the square root function, line() draws a line on the screen. The first four arguments are x and y of first point, and x and y of the second point. The fifth is some code that represents the color palette, and the sixth the line style (they are not important to understand the algorithm), and finally rnd() returns a random floating point number, uniformly distributed in the interval [0,1)
So, the challenge today is: reverse engineer the function and explain why you expect this thing to be a good approximation for a coastline.
This week's Riddler Classic is about Fibonacci-like sequences (re-explained here as follows):
Consider finite sequences of positive integers where, except for the first two terms, each term is the sum of the two terms before it. For example, the Fibonacci sequence ending at 13: (1, 1, 2, 3, 5, 8, 13). Or the Lucas sequence ending at 7: (2, 1, 3, 4, 7).
We are looking for such sequences of maximum length ("maximal sequences") ending in a specific number. For example, for 7, there are some such sequences terminating in 7, such as (4,3,7), (1,3,4,7), (2,1,3,4,7), etc. The maximal sequence ending in 7 is (2,1,3,4,7).
What is the maximal sequence ending in 81? What about for 179? In general, given a positive integer n, how do we find such maximal sequence(s) ending in n?
Sorry for not posting the solution to my problem earlier. I've been busy at work.
To see what the Digimon code is doing, it's convenient to think in terms of vectors. What it does is: it picks two points P1=(x1,y1) and P2=(x2,y2) in the grid, rotates the vector (P2 - P1) 90 degrees counter-clockwise ,displaces the midpoint by a random amount times this perpendicular vector, then calls itself recursively at (P1,displaced_point) and (displaced_point,P2), stopping when it called itself too many times or the length of the segment is too small, in this case, it just prints a straight line. This is a variant of random midpoint displacement, a technique commonly used to generate fractals, which are known to model coastlines well.
If we look at the randomness in the digimon algorithm, it's specially controlled, it takes an input variable to control the intensity of the displacement, at the minimum the algorithm prints just a straight line. And also, since it's summing three rnd() calls, the distribution function is the Irwin-Hall distribution for n=3, which is already very close to a Gaussian, the mean is -1/2 and the variance is 1/4 (standard deviation 1/2). This means that it chooses a negative value approximately 84% of the time. That means it actually displaces the midpoint more in the clockwise direction. In the end, you're likely to end up with a random fractal between a variant of the dragon curve and the Koch snowflake, which are commonly used to approximate coastlines. Quite advanced math for a children anime!
---------
Now, for the Riddler problem. There are two key pieces of information to notice. The first is that the Fibonacci-like sequence consists of positive integers, and the second is that two consecutive Fibonacci numbers completely determine a sequence, both at positive infinity and negative infinity. We can combine these two facts to solve the problem.
Lemma 1: if a Fibonacci-like sequence has two consecutive positive integers, then all further numbers a_n as n goes to positive infinity are positive integers as well.
We prove this by induction. Suppose we have a tuple (m,n) of consecutive numbers of the sequence. The next tuple is just (n, m+n). Notice that if m and n are positive integers, then so are n and m+n. Applying this inductively, all elements of the sequence are positive integers.
Lemma 2: let an be an element of a Fibonacci-like sequence and assume an <= 0. Then, for every tuple (am-1,am) for m <= n, at least one of am-1 and am is nonpositive.
This comes from an application of Lemma 1. Assume both elements of the tuple are positive. Then, by Lemma 1, every other element of the sequence in the positive infinity direction is also positive, this includes an. We reached a contradiction, so that means our assumption is false.
Lemma 2 suggests an algorithm to find all valid Fibonacci-like sequences that start at a tuple (m,n) where both m and n are positive. We simply pick a tuple and go back using (m,n) -> (n-m,m). If at any point we reach 0 or a negative number, we know it's impossible to find a tuple further down satisfying the conditions of the problem, so we stop. This suggests a solution using dynamic programming, which we can do using O(n^2) memory and time, where n is the number we want to compute the maximal sequence. I wrote some quick and dirty C++ code for this problem:
Language: cpp
#include <stdio.h>
#include <stdlib.h>
struct rep {
int m,n,q;
};
const int MAXN = 1000;
rep dp[MAXN][MAXN];
rep compute(int m, int n) {
rep r = dp[m][n];
if (r.q != -1) {
return r;
}
if (m >= n) {
dp[m][n].m = m;
dp[m][n].n = n;
dp[m][n].q = 0;
return dp[m][n];
}
r = compute(n-m,m);
dp[m][n].m = r.m;
dp[m][n].n = r.n;
dp[m][n].q = r.q + 1;
return dp[m][n];
}
int main(int argc, char* argv[]) {
if (argc < 2) {
printf("Usage: %s [number]\n",argv[0]);
return 1;
}
int n = strtol(argv[1], NULL, 10);
if (n <= 0) {
printf("number must be positive!\n");
return 1;
}
if (n > MAXN - 1) {
printf("too large!\n");
return 1;
}
for (int i=0; i<=n; i++) {
for (int j=0; j<=n; j++) {
dp[i][j].q = -1;
}
}
rep ans;
ans.q = -1;
for (int i=1; i<=n; i++) {
rep r = compute(i,n);
if (r.q > ans.q) {
ans = r;
}
}
printf("(m,n,q) = (%d,%d,%d)\n",ans.m,ans.n,ans.q);
}
We can verify that these representations work:
2,1,3,4,7 (7 is the third number after the initial 2,1)
3,2,5,7,12,19,31,50,81 (81 is the 7th number after the initial 3,2)
11,7,18,25,43,68,111,179 (179 is the 6th number after the initial 11,7)
I had a lot of fun solving this! Thanks, Fractal!
EDIT: I played around with this code for a while, and it's clear to me now that this thing is just maximization of a function f(m,n) where n is fixed. For all the large numbers of n I tested, it's true that you need to pick the value of m such that n/m is the best rational approximation to the golden ratio. I don't see how to prove this, but if true it could simplify the computation a lot.
EDIT 2: I managed to prove it! And doing so found a much simpler solution! It's much more efficient than dynamic programming, and can work for ridiculously large numbers as long as the precision of the machine's floating point numbers can handle that.
If you look at my previous code, I've reduced the problem to the evaluation of the function:
g(m,n) = 0, if m>=n
g(m,n) = 1 + f(n-m,m), otherwise
It turns out that I can relate g(m,n) to something with number theoretical properties. First, let's introduce the function:
f(x) = (x+1)/x
Notice that when we give f a rational number, we get another rational number: f(n/m) = (m+n)/n. Also, notice that it's related to the Fibonacci tuple iteration (m,n) -> (n,m+n). What's happening is that if we give f a rational approximation to the golden ratio, it gives us a better one. The explanation for this is simple. f is what is commonly known as a loxodromic Möbius transformation. Loxodromic transformations have a repulsive and an attractive fixed point. It turns out that phi=(1+sqrt(5))/2 is the attractive fixed point and its conjugate (1-sqrt(5))/2 is the repulsive one, we can find these values by solving the fixed point equation f(x) = x.
Now, a property of Möbius transformations is that they map circles to circles in the complex plane. For loxodromic transformations, this can be visualized by placing a small circle around the repulsive fixed point and iterating it through the transformation. What's going to happen is that the circle will become larger away from the repulsive fixed point and then will start shrinking around the attractive one. That means that, for intervals close enough to the attractive fixed point, loxodromic transformations are in fact contraction mappings. Since the golden ratio is the attractive fixed point of f(x), iterating f will give us better and better rational approximations to it.
To solve this, we don't need the full theory of Möbius transformations because the coefficients of f are all real, and also because f(x) = 1 + 1/x is monotonic for the intervals we need (1/x is decreasing for positive x). Because of this, we can ditch all machinery of circles in the complex plane and work with intervals in the real line, which is much easier!
Let's start. The values where g is fixed at 0 are the ones for m >= n, which means x in the interval [0,1]. Plugging these values in f, we get that [0,1] -> [2,infty]. Doing this again, we have: [1,3/2] -> [5/3,2] -> [3/2, 8/5] -> [13/8, 5/3] -> ...
We see some very interesting patterns here. First, starting from the [1,3/2] interval, we see that this infinite family completely partitions the range [1, 5/3]. A given number cannot be in the intersection of two of them (except for the ones who are made of Fibonacci numbers, but we can treat this case separately). Also, the first, third, fifth, etc. intervals are all strictly smaller than the golden ratio, while the second, fourth, sixth, etc. are larger. This pattern tells us that, the better a rational number approximates the golden ratio, the larger its position in the interval family, and therefore more times you need to apply f to get to it.
After all of this we find a ridiculously simple solution. Since we need to treat the case where the approximation is larger and smaller than phi separately, for a given n, we find an m such that n/(m+1) < phi < n/m. It should be noted that m = floor(n/phi). Then, we simply test the Fibonacci-like sequences ending with (m,n) and (m+1,n) and pick whichever is larger. Code is given below:
Language: cpp
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
struct rep {
int m,n,q;
};
rep g(int m, int n) {
rep r;
if (m >= n) {
r.m = m;
r.n = n;
r.q = 0;
return r;
}
r = g(n-m,m);
r.q++;
return r;
}
int main(int argc, char* argv[]) {
if (argc < 2) {
printf("Usage: %s [number]\n",argv[0]);
return 1;
}
int n = strtol(argv[1], NULL, 10);
if (n <= 0) {
printf("number must be positive!\n");
return 1;
}
double phi = (1+sqrt(5))/2;
int m = (int)floor(n/phi);
rep a = g(m,n);
rep b = g(m+1,n);
rep ans;
if (a.q < b.q) {
ans = b;
} else {
ans = a;
}
printf("(m,n,q) = (%d,%d,%d)\n",ans.m,ans.n,ans.q);
}
EDIT 3: To Masterjun, below:
For one of your examples, the code above generates
That gives the sequence [10946, 2584, 13530, 16114, 29644, 45758, 75402, 121160, 196562, 317722, 514284, 832006, 1346290, 2178296, 3524586, 5702882, 9227468, 14930350, 24157818, 39088168, 63245986, 102334154], which has one more element than the one you provide.
Haha, this was too much fun, wow.
My solution only has to check the fibonacci numbers downwards starting from the biggest one smaller than the number we aim for.
I can't really write it down mathematically, but my three key insights were these:
An equation for a number in position j of a sequence starting with a and b can be written as F(j-1)*a + F(j)*b where F is the fibonacci sequence. This means checking from above going down you can't miss an optimal solution.
Subsequent numbers in fibonacci sequences are always coprime.
The modular multiplicative inverse of a fibonacci number to the modulus of its following fibonacci number is always another fibonacci number.
I'm not even sure if all these are needed or if this is a good solution, but I like it.
Language: Python
def check(n):
# generate fibonacci sequence, stop when bigger than n
fib = [0,1]
while fib[-1]<n: fib.append(fib[-1]+fib[-2])
# start at biggest fibonacci number smaller than n and iterate down
for j in range(len(fib)-2,1,-1):
res = (fib[j-1-(j%2)]*n)%fib[j] # magic
if fib[j-1]*res<=n: break # a solution was found
a = int(res)
b = int((n-(res*fib[j-1]))/fib[j])
if b==0: # we dont allow 0 solutions, even if I enjoy those
b=a
j-=2
assert(n==a*fib[j-1]+b*fib[j]) # it really is a solution
seq = [a,b]
for i in range(j-1): seq.append(seq[i]+seq[i+1])
return seq
If 0 were allowed, the sequence starting with 9349, 9349, ..., could be rewritten as starting with 9349, 0, 9349, 9349, ..., easily adding two extra sequence entries! :D
Warning: Might glitch to creditsI will finish this ACE soon as possible
(or will I?)
I'll make another post because I got to the solution by a very convoluted method, and my edits give the impression that it's more difficult than it actually is.
We take a function f(x) = 1 + 1/x. Let us look at a fixed diagram of it:
To converge to the fixed point, one iteration is to go in the vertical direction and next on the horizontal direction. Doing this, you will converge to the fixed point, which is the golden ratio. Now, the problem of finding a sequence terminating on N is equivalent to:
1) Start at a rational x between 0 and 1.
2) Hop through the fixed point diagram until you land on a rational number N/m for some m.
3) Out of all m, choose the one that gives you more hops.
That's it, basically. It turns out that if we look at intervals instead of points, this iteration is much more predictable.
This image says it all:
What's happening here is: when you are in the red interval (0,1), and apply f, you end up on the blue one (2,infinity).
If you are on the blue one, and apply f, you end up on the purple one (1,3/2). If you are on the purple and apply f, you go to the black one (5/3,2). If you are on black and apply f, you go the yellow one (3/2,8/5). The points that divide these intervals are always fractions of consecutive Fibonacci numbers: 1, 2, 3/2, 5/3, 8/5 and so on.
Because of this, counting the number of iterations starting from the red interval is very simple, we can actually assign a number to each color.
red -> 0
purple -> 2
yellow -> 4
black -> 3
blue -> 1
As we get closer and closer to the golden ratio, which is the fixed point, this number starts to blow up. Because of this, if we want to maximize this number, notice the two properties:
If we denote the golden ratio by phi, and we have two numbers a and b, such that a < b < phi, it's always better to pick b, because it's impossible for the number of iterations for b to be smaller. Similarly, if we have phi < a < b, it's better to pick a, again because it's impossible for the number of iterations for a to be smaller.
For any sufficiently large number N, we can always find an m such that N/(m+1) < phi < N/m. Since N/(m+1) and N/m are the ones closest to phi, from below and above, we can find the solution by only looking at these two guys, so we only need to check the Fibonacci sequences ending in tuples (m,N) and (m+1,N).
I hope this explanation is better.
(Of course, we can imagine max(a,b) as the "infinity-mean" and min(a,b) as the "-infinity-mean", naturally extending these definitions. Also, this isn't really a proof, but it does very quickly guide a viewer toward a proof.)
My question concerns the side HG, which is not labeled as any mean. We have two formulas for HG, evident from the figure:
HG^2 = r^2 - (AM-HM)^2
HG^2 = GM^2 - HM^2
Setting these two equal to each other yields the relation:
r^2 - (AM-HM)^2 = GM^2 - HM^2
which can be used as the last of seven equations relating the quantities. This is good enough on its own and requires no further explanation, but we can add those negative terms to both sides to make the equation more... "hypotenuse-like" (?):
r^2 + HM^2 = GM^2 + (AM-HM)^2
What I'm curious about, which may be very easy or very difficult (I'm not sure), is whether this new equation can be represented geometrically. Is there some way to swing these sides around on this figure such that the equation above is what is represented? It may be a silly question and may reveal how lazy I am, as it might be a simple step. I just don't see it immediately and don't care to rigorously investigate it.
Edit: Bonus points if you can provide a geometric justification for the version where we cancel HM^2 from both sides:
r^2 + 2*AM*HM = GM^2 + AM^2
This seems especially difficult because radius r and line HC (the HM) don't appear to "communicate" with each other on the figure, nor do lines GC (the GM) and OH (AM minus HM). But maybe I'm missing something obvious.
Of course, with an unlimited number of polarizers, you could just use an arbitrarily large number of polarizers to make a "circular turn" to orient the polarity of the light horizontally while keeping a fraction of the light that is arbitrarily close to 1.
This is where Riddler Classic throws a twist: each polarizer is only 99% effective. So, only 0.99 of the light that is supposed to pass through each polarizer actually passes through.
With this in mind, what number of polarizers should be used to orient the polarity of the light horizontally while keeping the largest possible fraction of light? And what is the largest possible fraction?
(You may wish to use WolframAlpha to help out with this.)
To converge to the fixed point, one iteration is to go in the vertical direction and next on the horizontal direction. Doing this, you will converge to the fixed point, which is the golden ratio. Now, the problem of finding a sequence terminating on N is equivalent to:
1) Start at a rational x between 0 and 1.
2) Hop through the fixed point diagram until you land on a rational number N/m for some m.
3) Out of all m, choose the one that gives you more hops.
That's it, basically. It turns out that if we look at intervals instead of points, this iteration is much more predictable.
This image says it all:
What's happening here is: when you are in the red interval (0,1), and apply f, you end up on the blue one (2,infinity).
If you are on the blue one, and apply f, you end up on the purple one (1,3/2). If you are on the purple and apply f, you go to the black one (5/3,2). If you are on black and apply f, you go the yellow one (3/2,8/5). The points that divide these intervals are always fractions of consecutive Fibonacci numbers: 1, 2, 3/2, 5/3, 8/5 and so on.
Because of this, counting the number of iterations starting from the red interval is very simple, we can actually assign a number to each color.
red -> 0
purple -> 2
yellow -> 4
black -> 3
blue -> 1
As we get closer and closer to the golden ratio, which is the fixed point, this number starts to blow up. Because of this, if we want to maximize this number, notice the two properties:
If we denote the golden ratio by phi, and we have two numbers a and b, such that a < b < phi, it's always better to pick b, because it's impossible for the number of iterations for b to be smaller. Similarly, if we have phi < a < b, it's better to pick a, again because it's impossible for the number of iterations for a to be smaller.
For any sufficiently large number N, we can always find an m such that N/(m+1) < phi < N/m. Since N/(m+1) and N/m are the ones closest to phi, from below and above, we can find the solution by only looking at these two guys, so we only need to check the Fibonacci sequences ending in tuples (m,N) and (m+1,N).
I hope this explanation is better.