I have a bag of tiles. The tiles can be either blue or yellow, but you do not know how many are blue and how many are yellow. You draw 12 tiles without replacement: 4 blue and 8 yellow.
Is the next tile you draw more likely to be blue or yellow?
Does the answer depend on the number of tiles originally in the bag?
What is the chance that the next tile you draw is blue?
I feel like my answer is way too simple, so I'm very interested in what else it could be. My idea is that you know nothing about the tiles other than they're either blue or yellow, and that you drew twice more yellows than blues. Therefore, you'd think the next tile drawn is more likely to be yellow, independent of how many tiles are in the bag, with the chance of drawing blue next being 4/12.
Based on the information I am given so far, I can only presume that maximum likelihood estimation was intended as the solution method. (After all, we are not allowed to assume anything about the prior distribution ... what else can we possibly do?)
So, with regard to MLE, let n be the total number of tiles and k be the number of blue tiles. The number of ways of choosing 4 blue and 8 yellow tiles is f(k)=C(k,4)C(n-k,8), and we need to find the k that maximizes this. (Here, C(a,b) denotes a choose b.)
Now the ratio of successive terms is f(k+1)/f(k)=[C(k+1,4)C(n-k-1,8)]/[C(k,4)C(n-k,8)] = [(k+1)(n-9-k)]/[(k-4)(n-k)], and so find when f(k+1)/f(k)<1:
[(k+1)(n-9-k)]/[(k-4)(n-k)] < 1
-k^2+(n-10)k+(n-9) < -k^2+(n+4)k-4n
5n-9 < 14k
(5n-9)/14 < k
So f(k+1)/f(k)>1 when k<(5n-9)/14 and f(k+1)/f(k)<1 when k>(5n-9)/14. This implies that the sequence f(0), f(1), ... , f(n-1), f(n) is maximized at the first k value when f(k+1)/f(k)<1 (that is, ceiling((5n-9)/14) ).
For n=100, this value is ceiling(491/14) = 36, so the drawing of 4 blue and 8 yellow is most likely when there are 36 blue and 64 yellow tiles in the bag to begin with. After drawing, this leaves 32 blue and 56 yellow, so the probability the next draw is blue is 32/88 = 4/11.
For n=30, this value is ceiling(141/14) = 11, so 11 blue and 19 yellow. After drawing, 7 blue and 11 yellow are left, so the probability of drawing blue is 7/18.
As the number of tiles goes to infinity, the proportion of blue tiles in the maximum likelihood estimate approaches 5/14, so the limiting probability of drawing blue is 5/14.
MLE is the intended solution, or rather, conditioning on the likelihood. If you collect all of the likelihoods, normalize them as a pmf, then evaluate the expectation value of the given hypergeometric distribution, 5/14 is indeed the result you get for an arbitrary bag of fixed size N, then you'll find for any valid choice of N > 13. Proving this is somewhat tricky though and it involves some more obscure summations involving binomial coefficients.
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.
Nice to see you back, p4wn3r.
I'm guessing this is just calculus?
Edit: Deleted wrong solution. I really should have looked up what the curve looked like first.
So to find critical points of this function we just need to take the derivative. This is (x^2 - x - 6)e^x which factors into (x-3)(x+2)e^x. Set equal to zero and we have critical values of m at y = 0 (from e^x at negative infinity), y=7e^-2 (from the (x+2)), and y = -3e^3 (from the (x-3)). So this function has zero real roots for m < -3e^3, exactly one at m = -3e^3, two on the range -3e^3 < m <= 0, three on the range 0 < m < 7e^-2, two at m = 7e^-2, and finally one for m > 7e^-2.
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.
So to find critical points of this function we just need to take the derivative. This is (x^2 - x - 6)e^x which factors into (x-3)(x+2)e^x. Set equal to zero and we have critical values of m at y = 0 (from e^x at negative infinity), y=7e^-2 (from the (x+2)), and y = -3e^3 (from the (x-3)). So this function has zero real roots for m < -3e^3, exactly one at m = -3e^3, two on the range -3e^3 < m <= 0, three on the range 0 < m < 7e^-2, two at m = 7e^-2, and finally one for m > 7e^-2.
Just to add:
From the derivative, f(x) is continuous and strictly increasing on (-inf,-2], strictly decreasing on [-2,3] and strictly increasing on [3,inf).
Furthermore, lim[x->-inf] f(x) = 0 and lim[x->inf] f(x) = inf.
So f(x) is increasing from (but not including) 0 to 7/e2, then decreasing from 7/e2 to -3e3, then increasing from -3e3 to infinity. A graph of f(x) is shown below:
So the equation (x2-3x-3)ex - m = 0 has:
This one I created myself!
You have a very large array of N white squares. Choose one of them randomly and paint it black. Repeat this process exactly N times. You can paint a square black more than once, but that has no effect in the final result. On average, what's the ratio of squares that will remain white?
This one I created myself!
You have a very large array of N white squares. Choose one of them randomly and paint it black. Repeat this process exactly N times. You can paint a square black more than once, but that has no effect in the final result. On average, what's the ratio of squares that will remain white?
Is there a nice solution to this? It feels like the coupon collector's problem, so I would assume that the answer is 1/e in the limit, but every approach I've considered and that I know to be correct has horrible dependent probability mess.
I'm not completely certain if this approach is kosher but it gives me the answer I'm expecting, and I don't care enough to remind myself of the exact rules about expectations to justify it properly, but consider N squares, the expected number of black squares at the end of the first turn is p1 = 1, then it's p2 = p1 + (1 - 1/N) = 2 - 1/N for the second turn, and p3 = p2 + (1 - p2/N), and so on. Then it's a matter of solving this recursion.
p3 = p2 + (1 - p2/N) = 2 - 1/N + (1 - (2 - 1/N))/N) = 2 - 1/N + 1 - 2/N + 1/N^2) = 3 - 3/N + 1/N^2
p4 = p3 + (1 - p3/N) = 3 - 3/N + 1/N^2 + (1 - (3 - 3/N + 1/N^2)/N) = 3 - 3/N + 1/N^2 + 1 - 3/N + 3/N^2 - 1/N^3 = 4 - 6/N + 4/N^2 - 1/N^3
I could be wrong, but this seems like a Pascal's triangle situation. And again, not caring enough to justify this, let's just move on and assume I'm correct. lol. If we divide both sides by N, then subtract 1 from both sides we will get 1 - pN/N = (1 - 1/N)^N which is e^-1 as N gets large.
pN/N is the ratio of black squares to all squares, so 1 - pN/N is the exact value we were trying to find.
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.
Very nice! I think it does work.
The solution I had in mind uses methods I learned in statistical physics. It goes like this:
Suppose you have n white squares at the end. What's the probability of that happening? The formula is:
(N!/n!(N-n)!) * (1-1/N)^(Nn) * (1 - (1-1/N)^N)^(N-n)
Justification is: first we have to choose the N choose n ways to choose the n squares.
Then, for the n squares, we multiply n times by the probability that each of them are never painted, which is (1-1/N)^N.
Similarly, for the N-n black squares, we multiply N-n times by the probability that they are painted at least once, which is the complement of the previous one: 1-(1-1/N)^N.
What we need to do now is to compute the expected value of n in this distribution. Essentially sum on n, and find the limit when N->inf.
Now the tricks from statistical physics come into play. It turns out that things simplify a lot in the asymptotic limit:
1) The most obvious one is that (1-1/N)^N goes to e as N->inf
2) It often happens that in the large N limit, each individual term has a different exponential growth rate, and the term with the largest growth rate dominates all others
3) You are free to add and remove irrelevant asymptotic terms to simplify solving the problem, because they don't matter in the N->inf limit.
4) When N->inf the ratio r=n/N can be considered a continuous value, and you can use calculus.
Because of these things, the trick here is to take the logarithm of each term, then you compute everything in the asymptotic limit, adding and removing terms which are smaller than O(N), then rewrite it in terms of the ratio r and then use calculus to determine where the maximum of the logarithm happens.
Let's do this step by step. First, we use (1):
(N!/n!(N-n)!) * e^(-n) * (1 - 1/e)^(N-n)
Simplify a little:
(N!/n!(N-n)!)*(1-1/e)^N * (e-1)^(-n)
Now let's take the logarithm. We can use Stirling's approximation up to O(N), which gives log N! = N log N - N
N log N - n log n - (N-n) log (N-n) + N log (1 - 1/e) - n log(e-1)
We want to find the maximum of this expression with respect to n. The constant terms in n are not relevant, so we drop them:
- n log n - (N-n)log(N-n) - n log(e-1)
Now we substitute n = rN:
-rN log(rN) - N(1-r)log((1-r)N) - rNlog(e-1)
Here, we can simplify further. Notice that N is just a constant that multiplies everything and does not affect the maximum, so we can drop it.
-r log(r) - (1-r)log(1-r) + log N - r log(e-1)
The log N term is constant in n and can also be dropped. Anyway, we can differentiate with respect to r to obtain:
- log(r) - 1 + log(1-r) + 1 - log(e-1) = 0
log(1/r - 1) = log (e - 1)
1/r - 1 = e -1
r = 1/e
The reason you don't find this solution in most math books is that, in the way I wrote it, it's not 100% rigorous, but it can be made so, with the theory of asymptotic analysis and, in my opinion, easier than joint probability distributions.
EDIT:
Well, now looking at it, it seems I did not need to take the asymptotic limit at all! The sum on n in the initial formula can be computed exactly using binomial expansion:
sum_n(n*(N!/n!(N-n)!) * (1-1/N)^(Nn) * (1 - (1-1/N)^N)^(N-n)) = N*sum_n((N-1)!/(n-1)!(N-n)!) * (1-1/N)^(Nn) * (1 - (1-1/N)^N)^(N-n)) =
= N*(1-1/N)^N*sum_n((N-1)!/(n-1)!(N-n)!) * (1-1/N)^(N(n-1)) * (1 - (1-1/N)^N)^(N-n))
Reindex the sum: n -> n+1
N*(1-1/N)^N*sum_n((N-1)!/n!(N-1-n)!) * (1-1/N)^(Nn) * (1 - (1-1/N)^N)^(N-1-n)) = N*(1-1/N)^N -> N/e
So the ratio tends to 1/e for large N.
This looks like linearity of expectation.
For i=1,2,...,N, let Xi = 1 if square i is colored white at the end and 0 otherwise.
Then E(Xi) = P(square i is colored white) = (1-1/N)N for all i=1,2,...,N.
So the expected number of white squares is E(X1)+E(X2)+ ... +E(XN) = N(1-1/N)N which approaches N/e in the limit, so the ratio of white squares is 1/e.
The Riddler is dead, long live the Fiddler.
This week's extra credit Fiddler problem has been giving me some issues. I will restate the entire problem first, then explain where I am stuck in spoilers.
I’m continuing to play Digits (will it ever come out of beta?) from The New York Times. Based on personal experience, I recommend it as a fun way to engage kids with whole number operations. If you’re a fan of Digits, the TV show Countdown, or other similar games, then this week’s Fiddler is for you.
You are writing an expression using the whole numbers 1, 2, 3, 4, and 5, and the operations of addition, subtraction, multiplication, and division. Importantly, you must use each number and operation exactly once. Also, you can use as many parentheses as you would like. No concatenation of the digits is allowed (i.e., you can’t combine 2 and 3 to make the number 23). For example, one such number you could generate is 7, since you can write that as (2÷1)×3+5−4.
What is the largest value you can generate in this way, using the five digits and four operations?
Instead of five numbers and four operations, you now have nine numbers and eight operations. This time around, your expression should include the nine whole numbers 1, 2, 3, 4, 5, 6, 7, 8, and 9, each of which must be used exactly once. And the operations are once again addition, subtraction, multiplication, and division, each of which must be used exactly twice. As before, you have unlimited parentheses, while concatenation is not allowed.
What is the largest value you can generate, using the nine digits and eight operations?
(What if you have the numbers from 1 to 4N+1 and each of the four operations must be used exactly N times?)
With a little bit of effort you can find the values for N=1 and N=2 to be 35 and 9900 relatively easily or nearly instantaneously via a computer search, I won't bother doing much exposition on this part.
Here are my thoughts on the final part for arbitrary N:
If you examine the form of the solution for N=2, you'll find that all of the minuses become pluses other than the one targeting the 2, and similarly, all of the divisions become multiplications other than the one targeting 1. So this would seem to suggest that the pattern should be find some combination of the additions that sacrifice the 2 to the minus and the 1 to the division, leaving behind a grand total of 8N^2 + 6n - 4 to be split among 2n terms as evenly as possible to maximize the multiplication at the end. This gives (4N^2 + 3N - 2)/N on average, or between 4N+2 and 4N+3, approaching 4N+3 as N gets large. Using this technique it's possible to, instead of enumerating permutations of digits operations and orders, instead simply enumerate partitions of these integers into exactly 2n terms, and then choose some set of operations that makes it work. Using this approach you can rapidly find N=3, N=4 takes a few hours, but N=5 seem a little bit out of reach computationally still.The reason I want to enumerate the case for N=5, is because I suspect that it might become necessary to also sacrifice 3 once the number of minus operations becomes sufficiently large, in order to split the remaining values more evenly into the multiplication bins, finding if this becomes required, and if so exactly when would be required to begin categorizing a general solution.
Using this technique, the best value for N=3 is (8 - (2 - 3 - 7))/(((1/(6+9))/(5+10)) * (4+11) * 12 * 13 = 13 * 12 * 15^3 * 16= 8424000, and for N=4 it is 17 * 16 * 15 * (11 + 9) * (12 + 8)/((1/(13+7) /(14+6)/(10 - (2 - 5 - 4 - 3))) = 17 * 16 * 15 * 20^5 = 13056000000. For N=5, the search is yet ongoing but a candidate solution is (found by hand): 21 * 20 * 19 * 18 * (17 + 7) * (16 + 9) / ((1 / (15 + 10))/(14 + 11)/(13 + 12)/(8 - (2 - 6 - 5 - 4 - 3)) = 21 * 20 * 19 * 18 * 25^4 * 24^2 = 32319000000000.
One way to measure the "badness" of a particular solution is to find the squared deviation for each multiplication term from the average term, then divide by the number of terms. This roughly captures (or maybe exactly captures, I honestly haven't bothered to try to give a proof either way) how far away the solution is from an unobtainable upper bound. For N=3, this value 1.889, for N=4, it's 4. The candidate solution above has N=5 at 8.8, with just the 18 term at badness 21.16. So attempting to eliminate this term we can rewrite with also a -3 as well and get (not bothering to rewrite *s and /s and +s as -s), 21 * 20 * 19 * (18 + 5) * (17 + 6) * (16 + 7) * (15 + 8) * (14 + 9) * (11 + 10 + 4 - 3) * (13 + 12 - 2) = 21 * 20 * 19 * 23^6 * 22 = 25989180672840, which while this solution only has a badness of 2.95, the fact that there were 3 additional units to work with seems to easily make up for the relatively high badness of the N=5 candidate.If we assume that -3 will never be bigger, then we can come up with product(3N+3..4N+1) * ceil(S/(N+1))^(S mod N+1) * floor(S/(N+1))^(N+1-S mod N+1) where S = sum(3..3N+2) - 2, but I'm still not entirely convinced this is optimal for large enough N.
EDIT: In fact, consider two numbers that sum to 1001, the largest pair of multipliers are 501 * 500 in this case, if we subtract 3 from the total we have 499 * 499, now unbalancing the first, we have to go all of the way down to 461 * 540 before the unbalanced but larger value becomes larger than the balanced smaller one. This is a total "badness" of 3120.5, which is about 3 * 1001. So it seems like the total badness will have to reach very large levels in order to justify removing the 3, roughly 3 times one of the terms. However, they do seem to become bad enough. This would suggest at upper limit where that things become bad enough at N=49 to force using the -3, and perhaps it's better a few (several?) values before.
EDIT: A much more careful analysis of the badness for these two cases suggests a crossover at around n=19, and an analogous formula for the sac 2 and 3 case suggests that the crossover value is exactly n=21: (21, 1858561114113223590154513972642442186649575491096420050912878442728057261260800000, 1861170011681117541222317931520613643629245091916594782109445096734720000000000000, False)
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.
I think I got it, although I don't know if there is a simpler way to do this:
f(xy) gcd(f(x), y) = f(x) f(y) and f(yx) gcd(f(y), x) = f(y) f(x) imply gcd(f(x),y) = gcd(f(y),x) for all x,y.
Two important properties:
[1] If we let f(x)=n, then n=gcd(f(x),n)=gcd(f(n),x) implying n divides x (notation: n|x). That is, f(x)|x for all x.
[2] Note that gcd(f(x),y)|y and gcd(f(y),x)|x. If gcd(x,y)=1, it follows that gcd(f(x),y)=gcd(f(y),x)=1. Then f(xy) gcd(f(x), y) = f(x) f(y) becomes f(xy) = f(x) f(y). Therefore f(x) must be a multiplicative function.
Now we check specific values. First, by property [1], f(1) must be 1.
Then we check f(p) for prime p. By property [1], f(p) is either 1 or p:
Case 1: f(p)=1. Then x=y=p gives f(p2) gcd(f(p),p) = f(p)f(p) ---> f(p2)=1. Likewise, x=p2, y=p gives f(p3)=1, and so on. By induction, f(pn)=1.
Case 2: f(p)=p. Then x=y=p gives f(p2) gcd(f(p),p) = f(p)f(p) ---> f(p2)=p. Likewise, x=p2, y=p gives f(p3)=p, and so on. By induction, f(pn)=p.
Thus, for each prime p, we have a choice whether to assign f(pn)=1 for all n≥1, or f(pn)=p for all n≥1; that is, whether to include p as a prime factor in the output or not. Together with with the multiplicative function property [2], we can summarize possible f as follows: Any function satisfying f(xy) gcd(f(x), y) = f(x) f(y) must be of the form fQ(x), where Q is a (possibly infinite) subset of the primes, and fQ(x) is the product of all prime factors of x that are in Q.
----
There is one other thing: The above reasoning does not actually verify that f=fQ(x) satisfies the equation. To verify it, we need one more thing:
Consider a function f=fQ(x). To check that fQ(xy) gcd(fQ(x), y) = fQ(x) fQ(y), we will look at each prime p:
Case 1: p is not in Q: None of the factors in the equation will contain the factor p then.
Case 2: p is in Q but divides neither x nor y: None of the factors in the equation will contain the factor p then.
Case 3: p is in Q and divides x, but not y: The factors fQ(xy) and fQ(x) will each contain exactly one factor of p, and only these factors.
Case 4: p is in Q and divides y, but not x: The factors fQ(xy) and fQ(y) will each contain exactly one factor of p, and only these factors.
Case 5: p is in Q and divides both x and y: The factors fQ(xy), gcd(fQ(x), y), fQ(x) and fQ(y) will each contain exactly one factor of p.
In all cases, the factors of p are balanced on both sides. Doing this over all primes p shows that the equation holds.
I don't believe that there is a simpler way to do this, I did largely the same approach, but you managed to cut out some of the faffing about I did with x = f(u), y = u. Great job.
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.
Fiddler on the Proof has an interesting question this week that I had coincidentally been thinking about some time ago (at some point in the last year or so, I can't remember).
----
We form a weaving loom pattern in the unit square as follows:
* On the left side from the top-left corner to the bottom-left corner are n equally-spaced points A1, A2, ..., An.
* On the bottom side from the bottom-left corner to the bottom-right corner are n equally-spaced points B1, B2, ..., Bn. Note that B1 = An.
* Draw n line segments: from A1 to B1, A2 to B2, and so on, up to An to Bn.
The figure above shows n=100.
Question: As n goes to infinity, what is the curve formed by the upper edge of the pattern?
----
Fiddler on the proof also has a bonus question ("Extra Credit"). Rotate the above pattern around so it looks like this:
Question: As n goes to infinity, what fraction of the unit square is not covered by the four patterns (that is, what is the area of the central white region)?
Note that the lines that get drawn are from (0, 1-t) to (t, 0) for t rational, with equation y = (1-1/t) x + (1-t).For given x, this is maximised when (some calculus) t = sqrt(x), with y = x + 1 - 2sqrt(x). As a side note, we may rearrange to (y-x-1)^2 = 4x, which we recognise as the standard equation of a parabola. When I was first shown this weaving pattern by a teacher when I was young, they claimed that it was a circle :)
For the area, note that it is 4 times the area between y = 1/2, x = 1/2 and the curve.Solving the quadratic equation shows that this occurs when sqrt(x) = (2-sqrt(2))/2 i.e. x = (3-2sqrt(2))/2.So our area is 4 times the integral from (3-2sqrt(2))/2 to 1/2 of 2sqrt(x) - x - 1/2, which is (8sqrt(2)-10)/3.
EDIT: It is maybe worth noting that the above solution is very handwavy about exactly which lines are drawn and for which n. For those who have a thing for rigour, this can be patched up with a continuity argument using density of the rationals, along with the fact that the "mesh size" is arbitrarily small as n is taken arbitrarily large.
Current TAS:
[SNES] Jelly Boy
[NES] Street Fighter 2010
Fiddler on the Proof has an interesting question this week that I had coincidentally been thinking about some time ago (at some point in the last year or so, I can't remember).
I already knew this one. Actually when I started university a physics professor came to visit me and my friends at our dorm, and he showed this question as a challenge. So I have a bit of nostalgia here and absolutely MUST solve it.
There are two ways to go about it, one is more formal, other more intuitive a la Euler that's harder to formalize. Let's start with the intuitive one.
Consider the continuum limit. In that limit we connect the point (0,1-t) to the point (t, 0). If we add a differential dt, we similarly must connect (0,1-t-dt) to the point (t+dt,0). We can find the intersection point of these two by solving a linear system. The first line is given by y = 1-t - x*(1-t)/t, and the second line is y = 1-t-dt - x*(1-t-dt)/(t+dt).
Equate them and you get -x*(1-t)/t = -dt -x*(1-t-dt)/(t+dt) => x = t(t+dt). Notice that in the limit dt -> 0, we have simply x = t^2. In this limit the intersection point should correspond to a point in the curve. So, substituting y = 1 - t - t(1-t) = (1-t)^2. We know (t^2, (1-t)^2) for t from 0 to 1is a parametrization of the curve. It's easy to express it as y(x) = (1-sqrt(x))^2
Now let's go to the formal way, which you would write in a calculus test.
Suppose y(x) is the curve. The tangent to the curve at x must cross the x and y axes at points (0, 1-t) and (t,0) for some t. This implies that the slope of the tangent is -(1-t)/t. Therefore, y'(x) = -(1-t)/t for some t. However, this condition is not sufficient. The point (x, y(x)) must also be somewhere along the line y = 1-t -x*(1-t)/t, or else the setup won't work. This second condition, though, fixes a value for y given x. So, if we isolate t, we have t = 1/(1-y'(x)), and substituting this in the other equation we get:
y = xy' -y'/(1-y')
Now, if you like to research things, you'd eventually recognize this as Clairaut's equation. If you don't know it, you can still guess you can solve it by noticing that the terms y and xy' combine nicely. Anyway, the basic idea is to simply differentiate it with respect to x:
y' = y' + xy'' - y''/(1-y')^2 => y''(x - 1/(1-y')^2) = 0
Now, y'' = 0 gives functions of the form y = ax + b. The only way to satisfy the boundary conditions y(0)=1 and y(1)=0 is to set y = 1 - x. Although this function satisfies the conditions I set before, it does so in a trivial way, so let's look at the other solution. It is x(1-y')^2 = 1 => y' = 1 +- 1/sqrt(x).
Notice that we want the derivative to be negative for 0<x<1, for this to happen, we need to pick the minus sign. So y' = 1 - 1/sqrt(x). Finally integrate this to find y = x - 2sqrt(x) + c. Setting y(0) = 1, we have c = 1, and we can rewrite y = (1-sqrt(x))^2, the same answer as before.
For the bonus question, we just need to integrate y(x) from 0 to 1 and from 1/2 to 1. That's pretty easy, because y(x) is just a sum of x to the power of an exponent. If we do this, we have that the area from 0 to 1 is 1/6, and from 1/2 to 1 is sqrt(2)/3 - 11/24. If we sum the area of 4 curves around a square, we double count 8 times the area from 1/2 to 1. From this we can compute the free area in the unit square as 1 - 2/3 + 8*sqrt(2)/3 - 11/3, which is approximately 0.4379
Fiddler on the Proof has an interesting question this week that I had coincidentally been thinking about some time ago (at some point in the last year or so, I can't remember).
Consider the continuum limit. In that limit we connect the point (0,1-t) to the point (t, 0). If we add a differential dt, we similarly must connect (0,1-t-dt) to the point (t+dt,0). We can find the intersection point of these two by solving a linear system. The first line is given by y = 1-t - x*(1-t)/t, and the second line is y = 1-t-dt - x*(1-t-dt)/(t+dt).
Equate them and you get -x*(1-t)/t = -dt -x*(1-t-dt)/(t+dt) => x = t(t+dt). Notice that in the limit dt -> 0, we have simply x = t^2. In this limit the intersection point should correspond to a point in the curve. So, substituting y = 1 - t - t(1-t) = (1-t)^2. We know (t^2, (1-t)^2) for t from 0 to 1is a parametrization of the curve. It's easy to express it as y(x) = (1-sqrt(x))^2
That's actually a nice way to get the result.
For a long time, I "knew" that the answer was the quadratic Bezier curve (parabola) formed by the left and bottom sides, but had no idea how to actually prove it. This is about what is known as an envelope, formed by the family of lines y = ((t-1)/t)x + 1-t. Example 2 on that page is in fact the question that is asked and I solved it in that way shortly after posting the question.
OmnipotentEntity wrote:
Show that:
Sum(a=1..inf) Sum(b=1..inf) gcd(a,b)/(a^2 b^2) = (5/2) zeta(3)
My zeta game isn't very good, unfortunately. I might attempt this but don't expect a response from me.
Show that:
Sum(a=1..inf) Sum(b=1..inf) gcd(a,b)/(a^2 b^2) = (5/2) zeta(3)
The trick here is to find an Euler product that will decompose this thing into an infinite product of primes, and then apply the zeta formulas. Notice that the denominator is always the square of an integer. Because of this, we can rewrite the sum as:
S = sum(n=1..inf) f(n)/n^2
What is f(n)? f(n) is the sum of gcd(a,b) for every possible way of writing n=a*b. Another way f expressing it is f(n) = sum(d|n) gcd(d, n/d). Notice that if we have n and m coprime, then f(n*m)=f(n)*f(m), so f is a multiplicative function. Because of this, we only need to evaluate it for prime powers, where things are much simpler.
We have f(p^k) = sum(i=0..k) gcd(p^i,p^(k-i)) = sum(i=0..k) p^(min(i,k-i))
We break it into even and odd:
f(p^(2l)) = p^l + 2(p^l-1)/(p-1)
f(p^(2l+1)) = 2*(p^(l+1)-1)/(p-1)
To set up the Euler product, we need to calculate
T(p) = 1 + f(p)/p^2 + f(p^2)/p^4 + ...
We sum an even plus an odd one divided by p^2 and sum to infinity. With some help from Wofram Alpha, the answer is:
Now sum it and simplify (credit to Wolfram Alpha again):
So, we want calculate the infinite product of T(p) over all primes p. To do that, we can use that prod(1-1/p^s) = 1/zeta(s) and prod(1+1/p^s) = zeta(s)/zeta(2s)
So, our product becomes:
Using zeta(2) = pi^2/6 and zeta(4) = pi^4/90, the factors of pi cancel out and the answer is 90/36 * zeta(3) = 5/2*zeta(3).
By the way, this was a pretty challenging one. I saw the multiplicative property of the gcd in the sum, but had to do a lot of trial and error with some generating functions that led nowhere until I got the Euler product right, and even then it was a lot of algebra that I don't think I could do by hand.
I created a new one today!
Let x and y be two positive real numbers, such that x > y and:
x + y = 6
(x+sqrt(x))(y+sqrt(y)) = 8.25
Find x and y.
This winds up being equivalent to finding the intersection of a parabola with an ellipse*. If you straightforwardly attempt to solve the resulting quartic, you don't get anything that looks reasonable. The quartic I arrived at is 1396 u4 + 296 u3 - 1744 u2 - 192 u + 480 = 0, where u2 = y.
I assume there is a tricky change of variables that makes this possible/reasonable to get a closed form solution, but a numerical approximation is y = 0.9453, and x = 5.0547.
I'll circle back to this when I'm less busy. Seems that if I can rotate the parabola in order to eliminate the + 4u, I might be able to perform a substitution on the ellipse that might make it more amenable to manual calculation. However, I'm not looking forward to dealing with an off-axis ellipse, and it might not wind up being any less complicated.
* the parabola is 37u2 + 4u - 24, and the ellipse is 4 sqrt(6 - u2)
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.
Here's the best explanation I can think of:
(x+sqrt(x))(y+sqrt(y)) = xy + x*sqrt(y) + y*sqrt(x) + sqrt(xy) = 8.25
4x*sqrt(y)+4y*sqrt(x) = 33 - 4xy - 4sqrt(xy)
Square both sides:
16x2y+16y2x + 32xy*sqrt(xy) = 1089 + 16x2y2 + 16xy - 264xy - 264sqrt(xy) + 32xy*sqrt(xy)
16xy(x+y) = 1089 + 16(xy)2 - 248xy - 264sqrt(xy)
Since x+y=6: 0 = 16(xy)2 - 344xy - 264sqrt(xy) + 1089
Substituting z = 2*sqrt(xy): z4 - 86z2 - 132z + 1089 = 0
Now it so happens that z=3 is a solution to the equation above, and so 3 = 2*sqrt(xy), or xy = 9/4
So x+y=6 and xy=9/4, which gives x2 - 6x + 9/4 = 0, or x = 3 ± 3sqrt(3)/2. Now actually one of them is x and the other is y, and since x>y, that gives x = 3 + 3sqrt(3)/2, y = 3 - 3sqrt(3)/2.
----
You may have noticed that I didn't even bother checking that z4 - 86z2 - 132z + 1089 = 0 had no other real solutions. I'm pretty confident that checking this was not part of the original intent of the question. But if you want an explanation: z4 - 86z2 - 132z + 1089 = (z-3)(z3+3z2-77z-363). The cubic factor can be checked to have one real and two complex roots, and the real root is about z≈9, which gives xy≈20. And as it turns out, x+y=6 and xy=c has a solution if and only if c is less than or equal to 9.
Note that you can get the answer to the original question directly just by entering into WolframAlpha:
So the equation (x2-3x-3)ex - m = 0 has:
We form a weaving loom pattern in the unit square as follows:
* On the left side from the top-left corner to the bottom-left corner are n equally-spaced points A1, A2, ..., An.
* On the bottom side from the bottom-left corner to the bottom-right corner are n equally-spaced points B1, B2, ..., Bn. Note that B1 = An.
* Draw n line segments: from A1 to B1, A2 to B2, and so on, up to An to Bn.
The figure above shows n=100.
Question: As n goes to infinity, what is the curve formed by the upper edge of the pattern?
----
Fiddler on the proof also has a bonus question ("Extra Credit"). Rotate the above pattern around so it looks like this:
Question: As n goes to infinity, what fraction of the unit square is not covered by the four patterns (that is, what is the area of the central white region)?
