Player (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
This week's Riddler Express is about coin flips. https://fivethirtyeight.com/features/the-new-national-pastime-competitive-coin-flipping/ It should be intuitively clear that you should bet on the team that chooses head-tails. The reasoning is as follows: The sequences of n flips that have no head-tails total only n+1, since they must be a sequence of tails followed by heads. The ones that lack HH, per the arguments presented before, total the Fibonacci number F(n+2). Fibonacci numbers grow exponentially, while n+1 linearly, so the first team is much more likely to win than the second. However, a computation of the actual expectation value seems quite difficult. My idea was to calculate the probability of winning on the n-th flip, given that you lost at the previous ones: P(Wn|Ln-1) = pn This can be calculated using the usual formula for conditional probability and computing the intersection with combinatorics. For the first team, it's (n-1)/2n. For the second, it's F(n-3)/2F(n-1). Now you can model the problem as follows. For each team, you perform a trial each time with pn chance of succeeding. If you fail, move to the next trial. If all the p's were constant, we would have the geometric distribution for the number of trials, whose mean is just 1/p. In a crude approximation, the pn for the first team would tend to 1/2 for large n, while the second one to 1/2phi^2, where phi ~ 1.6 is the golden ratio. Inverting this, we expect 2 trials for the first and ~5.1 for the second. (Ignore the first flip). The problem is that I don't know how much the initial behavior can change this calculation. I figured out that I can construct the distribution for the trial numbers setting: pn = P(T = n)/P(T >= n), Starting from n=2 and increasing n you can calculate the distribution for all possible values. Perhaps a careful computation will show which one has a larger mean.
Editor, Skilled player (1936)
Joined: 6/15/2005
Posts: 3239
If you want the probabilities, Riddler Express can be modelled using an absorbing Markov chain. If we call the first team (HT) Team 1 and the second team (HH) Team 2, then there are four transient (non-final) states: OO = neither team can win on next flip HO = Team 1 can win on next flip but not Team 2 OH = Team 2 can win on next flip but not Team 1 HH = Both teams can win on next flip and two absorbing (final) states: 1W = Team 1 has won 2W = Team 2 has won You can set up an absorbing Markov chain and compute the final probabilities of ending up in 1W and 2W starting from OO. Alternatively, you can also compute: if poo is the probability of Team 1 winning starting from OO, and so on, then: (image generated from latex2png.com) Computing gives poo=5/8. So probability of Team 1 winning is 5/8 and for Team 2, 3/8.
Player (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
For whoever is interested, I had time to work on this problem today and I managed to solve it using the expected value approach. The trick is the following. Write the expected value for the number of turns X where each team gets the final flip as: E[X] = Pr(X=1) + 2*Pr(X=2) + 3*Pr(X=3) + ... An equivalent form is: E[X] = Pr(X>=1) + Pr(X>=2) + Pr(X>=3) + ... Now, the probability that a team takes n turns or more to win is just the probability of getting an invalid sequence of n-1 flips. For the first (HT) team, it is: pA(X>=n) = n/2^(n-1) For the second (HH) team, it is: pB(X>=n) = F[n+1]/2^(n-1) where F[n] is the n-th Fibonacci number, where we take F[0]=0 and F[1]=1. If you write the Fibonacci numbers in the form F[n] = ((0.5+sqrt(5)/2)^n - (0.5-sqrt(5)/2)^n)/sqrt(5), it is simple to sum the series for both expected values. For the first team, it is an arithmetic-geometric series that sums to 4. For the second, it is two geometric series that total 6. Therefore, the first team will have won after four turns on average, and the second on six turns. This way, you can find the answer without solving a linear system.
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
When trying to prove that a number is not rational, it appears that the most common approach is proof by contradiction (iow. assume that the number is rational, and prove that the assumption leads to a contradiction). Famously, proving that sqrt(2) is irrational is very easy in this way. I was wondering if there are numbers for which that approach doesn't work, and some other form of proof needs to be used. Perhaps even if there are algebraic numbers that are such. (I understand that it's probably not possible to say "proof by contradiction is impossible for this number." I suppose what I'm asking is if there's some number that can be proven to not be rational, but for which there is no known proof by contradiction, or that proof is way too complicated to be feasible and there's a much easier way of proving it.)
Player (36)
Joined: 9/11/2004
Posts: 2623
Warp wrote:
(I understand that it's probably not possible to say "proof by contradiction is impossible for this number." I suppose what I'm asking is if there's some number that can be proven to not be rational, but for which there is no known proof by contradiction, or that proof is way too complicated to be feasible and there's a much easier way of proving it.)
Unfortunately, there is no real way to "access" irrationality directly. An irrational number is simply a number that is not rational, but a rational number is a number that can be expressed as p/q where p and q are integers. Because the definition of an irrational number is in terms of what it is not, then you have to prove that it's not a rational number, which means proof by contradiction. Other related properties of irrational numbers, such as a non-repeating decimal expansion, are consequences of this property and are themselves proven through contradiction (try it!). This means that the other standard argument to prove irrationality for numbers such as the Champernowne constant relies on proof by contradiction as well, albeit indirectly.
Build a man a fire, warm him for a day, Set a man on fire, warm him for the rest of his life.
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
Especially right now there's a lot of talk out there how graphics card A is "n% faster" than graphics card B. For long I have thought about how ambiguous it is to say that something is "n% (comparative)" than something else. What is the correct way of calculating that percentage? Suppose that using some benchmark, graphics card A runs at an average of 120 frames per second, while graphics card B runs at 150 frames per second. How many "% faster" is B compared to A? Is it even unambiguous to ask that question? One approach would be to take the 120 fps, see how much larger the second number is (in this case 30), and calculate what portion of the 120 that number is, and declare that as the "% faster" value. In this case, 30 is 25% of 120, and thus one could say that card B is "25% faster" than card A. (Incidentally, this is the same value you can get more easily by simply dividing 150/120, giving 1.25, meaning that 150 is 125% of 120, ie. 25% more.) On the other hand, we could also approach the situation by looking at what portion that 120 is compared to 150. In other words, 120/150 = 0.8, which we can interpret as card A having 0.2 = 20% less speed than card B. Since card A is capable of 80% of what card B is, we could interpret this as meaning that card B is "20% faster" than card A. So, is card B "25% faster" or "20% faster" than card A? Or something else? This notional difference becomes even more accentuated the higher the difference. Suppose that the difference is exactly double. For example, card A runs at 100 frames per second, while card B runs at 200 frames per second. How many "% faster" is card B?
Player (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
That's pretty much a matter of convention. Pretty much every area I can think of uses the "old" value as reference when calculating the relative difference. So, if you have a card that's 120 and you come up with a new one that does 150, you say the new one is 25% faster. But if you already had one that's 150 and come up with a card that's cheaper you'll say the new one is 20% slower for a better price. The only thing that's meaningful is the ratio between the quantities being compared. The way this ratio is expressed is more a matter of language. The usual convention does have some tricky situations. For example, if you increase a price by 20% and later give a 20% discount, you don't return to the same price, because the percentages act on different basis, but that's usually how it's done. I personally prefer comparing the difference in scales with log(p1/p2). When p1 and p2 are close to each other, it really doesn't matter which one you pick as reference or calculate the logarithm, the value will be approximately the same. But for exact calculations or larger differences, the convention is important.
Skilled player (1530)
Joined: 7/25/2007
Posts: 299
Location: UK
Easy Riddler Classic this week. A typical path can be described as follows: UURUURRURURUUUU etc, where there are 15!/10!5!=3003 permutations. In general, there are (m+n)!/m!n! paths to take.
Player (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
You write all numbers from 1 to 100 on a blackboard. At any point you can choose any distinct numbers a and b, erase them and write a+b+ab on the blackboard. After doing this process 99 times, which number will be left on the blackboard?
Editor, Skilled player (1936)
Joined: 6/15/2005
Posts: 3239
p4wn3r wrote:
You write all numbers from 1 to 100 on a blackboard. At any point you can choose any distinct numbers a and b, erase them and write a+b+ab on the blackboard. After doing this process 99 times, which number will be left on the blackboard?
Let a*b = a+b+ab be the operation. Note that a*b = (a+1)(b+1)-1. Then (a*b)*c = ((a+1)(b+1)-1)*c = (a+1)(b+1)(c+1)-1 = a*((b+1)(c+1)-1) = a*(b*c) and a*b = (a+1)(b+1)-1 = (b+1)(a+1)-1 = b*a So * is associative and commutative, and so we can apply this operation on any numbers in any order and get the same result. So: 1*2*3*...*100 = (2(3)-1)*3*4*...*100 = (2(3)(4)-1)*4*5*...*100 = ... = 2(3)(4)(5)...(101)-1 = 101!-1. The number at the end will always be 101!-1, which is the 160-digit number: 9425947759838359420851623124482936749562 \ 3127947025437683278893534169775993162214 \ 7650308786159180834691162349000354959958 \ 3369706302603263999999999999999999999999 Alternatively, the value resulting from adding one to every number on the board and then multiplying them all together is an invariant (is always the same at every step) that in this case equals 101!; thus when there is one value left, it must be 101!-1. It's a similar idea.
Warp wrote:
Suppose that using some benchmark, graphics card A runs at an average of 120 frames per second, while graphics card B runs at 150 frames per second. ... So, is card B "25% faster" or "20% faster" than card A? Or something else?
There is another issue when using the word "faster". For the most part, it is understood to compare the speeds of the graphics cards in frames per second. 150 fps is 25% more than 120 fps, so in this sense card B is 25% faster than card A. However "faster" is often conflated with "takes less time than" (i.e. the comparison is based on time and not speed). Using your example, card A runs 600 frames in 5 seconds, card B runs 600 frames in 4 seconds. Since 4 is 80% of 5, card B takes 20% less time than card A, so in this sense one could also claim that card B is "20% faster" than card A.
Player (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
OK, now a harder problem. A classic from Gauss. You start with a0 = a and b0 = b. At every step you perform the operation an+1 = (an+bn)/2 bn+1 = sqrt(anbn) That means, you change the two initial real numbers by their arithmetic and geometric means. Prove that this procedure converges to a value 1/L, where L = (2/pi)*\int_0^{pi/2} dx/sqrt(a2cos2x + b2sin2x). There are two ways to solve this: the magical way, where you need to know the answer, and the more brute force way, where you could actually find the function if you're good at summing series. Both are pretty interesting. Bonus: what would happen if we worked with arithmetic and harmonic mean? And what about harmonic and geometric?
Editor, Skilled player (1408)
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
A very successful mathematician has submitted his proof for the Riemann Hypothesis. A lot of people are skeptical about it. I couldn't understand a single thing, but for a RH proof his paper is incredibly short: https://drive.google.com/file/d/17NBICP6OcUSucrXKNWvzLmrQpfUrEKuY/view
My YouTube channel: https://www.youtube.com/channel/UCVoUfT49xN9TU-gDMHv57sw Projects: SMW 96 exit. SDW any%, with Amaraticando. SMA2 SMW small only Kaizo Mario World 3
Player (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
It's very hard to take this paper seriously. He comes up with his Todd function, which seems to have contradictory properties. He states it's analytic on any compact set of C. That should imply it's analytic, but then he says it's not. The function is said to be defined on a previous paper where he claims to derive the fine structure constant mathematically, but that paper just says they are polynomials and is even more puzzling. He claims to derive alpha using techniques from renormalization in quantum field theory to make pi flow to 1/alpha. While that could potentially be possible, renormalization is not a rigorous mathematical technique, and we can only calculate the renormalization flow equations approximately, so if you take his methods seriously he actually solved a much harder problem, which is renormalization in QFT. Besides, lots of technical details are missing. Which specific theory did he use? What's the value of the beta function? It also seems someone in reddit computed his formula for 1/alpha and it's off by a lot. As to how this relates to the Riemann hypothesis, no idea. He does use the function e^-x/(1-e^-x) , whose Mellin transform gives Gamma(s)Zeta(s), but that's about it. I think it's wise to ignore this "proof". It's unfortunately common that many brilliant researchers ignore every piece of evidence against their ideas when they get older and turn to cranky stuff. Dirac was obsessed with the fine structure constant, Schwinger kept writing about cold fusion long after it was discredited, and there's Einstein with his unified theories that never lead anywhere. Atiyah has some great work, but has unfortunately been making ridiculous claims for a long time and people have been listening just to not get in trouble with a Fields medalist saying his work is bad. Now that he claimed a solution to a famous problem people started reading what he's been writing and the result won't be pretty.
Skilled player (1403)
Joined: 10/27/2004
Posts: 1976
Location: Making an escape
I didn't understand much of what he was talking abaout, but I did find it interesting that he admitted that his proof may be weak/incomplete since it requires choice. But yeah, until other mathematicians have had a chance to pick this apart, I will take this with a grain of salt.
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.
Editor, Skilled player (1936)
Joined: 6/15/2005
Posts: 3239
p4wn3r wrote:
OK, now a harder problem. A classic from Gauss. You start with a0 = a and b0 = b. At every step you perform the operation an+1 = (an+bn)/2 bn+1 = sqrt(anbn) That means, you change the two initial real numbers by their arithmetic and geometric means. Prove that this procedure converges to a value 1/L, where ...
I will assume for the rest of this post that a and b are positive real numbers. After thinking about this for a while, I could only prove that they converge to a value, but I couldn't prove what they converge to. But since there is a whole Wikipedia page about this, I'll just link it here as the solution. The value is called the arithmetic-geometric mean. What if we replaced a and b with their arithmetic and harmonic means? That problem is much easier to figure out. Their arithmetic mean (AM) is (a+b)/2 and their harmonic mean (HM) is (((1/a)+(1/b))/2)^(-1), which simplifies as 2ab/(a+b). When you multiply the AM and HM together, you get ab, which is the same as the product of the original numbers. Therefore the product of the two numbers on the board is always the same at every step. Since they converge to a value L (check this), the value L must satisfy L^2=ab, and so L=sqrt(ab). Note that L is the geometric mean! What if we replaced a and b with their geometric and harmonic means? Note that the geometric mean (GM) of a and b is the reciprocal of the GM of 1/a and 1/b. As well, the HM of a and b is the reciprocal of the arithmetic mean of 1/a and 1/b. Thus we just find the arithmetic-geometric mean of 1/a and 1/b, then take the reciprocal to get the answer.
Player (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Nice! The Wikipedia article lists the solution that I call the "magical" one. The trick to find it is to note that the AGM satisfies the functional equation agm(x,y) = agm((x+y)/2,sqrt(xy)) To find a formula for the AGM, one would have to find a function that obeys such law. Once the answer has been given, it's simple. As the Wikipedia article shows, the elliptic integral is an invariant of the AGM iteration, so it should remain constant at every step. When the two numbers are the same, the elliptic integral is just the inverse. Therefore, once it's proven that the sequence converges, comparing the values of the elliptic integral at the beginning and "at infinity" one concludes that the AGM should be the inverse of the elliptic integral of the initial terms. The brute force approach is like this. Observe that the AGM is homogeneous: agm(kx,ky) = k*agm(x,y) Because of this, the function you need to find actually depends on only one variable, not two. In principle, you can expand it in a Taylor series and use the functional equation to compare term by term. It turns out that you can prove this Taylor series is the one from the elliptic integral. The cleanest way I know of doing this expansion is by writing: agm(1+x,1-x) = agm(1,(1-x)/(1+x))/(1+x) = agm(1,sqrt(1-4x/(1+x)²))/(1+x) Now, agm(1+2sqrt(x)/(1+x),1-2sqrt(x)/(1+x)) = agm(1,sqrt(1-4x/(1+x)²)), so you can write the functional equation (1+x)/agm(1+x,1-x) = 1/agm(1+2sqrt(x)/(1+x),1-2sqrt(x)/(1+x)) Now, you can expand 1/agm(1+x,1-x) in a Taylor series. It is simple because since it's an even function the odd exponents vanish. To expand the RHS you need the Taylor series for (1+x)-n, which you can get by expanding 1/(1+x) as a geometric series and deriving the function. After some calculations you can get all coefficients and get the answer as a hypergeometric series. This series is exactly the elliptic integral and you could prove it using well known identities. Elliptic functions are one of my favorite subjects because there are many different approaches to prove things. The variety of answers to this problem is one aspect of this. You can also recast the functional equation for the AGM as the hypergeometric differential equation, and then prove the answer by uniqueness of the IVP. There's even an approach using theta functions. It turns out that the whole AGM sequence can be expressed as a ratio of squares of Jacobi theta functions, and you can infer all the properties from that!
Editor, Skilled player (1936)
Joined: 6/15/2005
Posts: 3239
This week has an interesting Riddler Classic problem, a more conventional one: ---- A farmer owns a circular field with radius R. If he ties up his goat to the fence that runs along the edge of the field, how long does the goat’s tether need to be so that the goat can graze on exactly half of the field, by area? ---- Shouldn't be too hard to figure out.
DrD2k9
He/Him
Editor, Expert player, Judge (2037)
Joined: 8/21/2016
Posts: 1009
Location: US
If the goat's tether can freely travel along the fence around the entire circumference of the field, the goat's tether length (T) can be solved with the following formula. T=R/sqrt2 If the tether can't freely travel around the fence, then I'm not smart enough to figure it out quickly.
Editor, Skilled player (1408)
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
I'm not sure what you meant, but the goat's movement will be restricted by the fence itself. So you are looking for the ratio between the radius of these 2 circumferences, so that the blue area is equal to the red area.
My YouTube channel: https://www.youtube.com/channel/UCVoUfT49xN9TU-gDMHv57sw Projects: SMW 96 exit. SDW any%, with Amaraticando. SMA2 SMW small only Kaizo Mario World 3
DrD2k9
He/Him
Editor, Expert player, Judge (2037)
Joined: 8/21/2016
Posts: 1009
Location: US
BrunoVisnadi wrote:
I'm not sure what you meant, but the goat's movement will be restricted by the fence itself. So you are looking for the ratio between the radius of these 2 circumferences, so that the blue area is equal to the red area.
Yep...that's what I'm not smart enough to figure out quickly...if the tether is anchored to a specific point on the fence (circle). If the tether is not anchored to that specific point, but can freely slide around the circumference of the fence then blue and red are equal area this way. My solution makes the assumption that the fence end of the tether isn't anchored to a set point. The other (probably proper) solution makes the assumption that the tether is anchored to the specific point on the fence.
Editor, Skilled player (1408)
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
FractalFusion wrote:
If he ties up his goat to the fence
I think the 'fence' refers only to the circumference, not to the whole circle. I'll try this problem tomorrow. Probably some arccosines will appear so it'll be hard to solve for the exact value.
My YouTube channel: https://www.youtube.com/channel/UCVoUfT49xN9TU-gDMHv57sw Projects: SMW 96 exit. SDW any%, with Amaraticando. SMA2 SMW small only Kaizo Mario World 3
Tub
Joined: 6/25/2005
Posts: 1377
It is an old problem; the oldest variation I could find was published in 1982. I've tackled it before (on a different forum) and I'll leave two hints: 1) one possible approach is to use formulas from here: https://en.wikipedia.org/wiki/Circular_segment 2) no matter your approach, you'll get a tangled mess of a formula which you cannot solve. Do a numerical approximation.
m00
Player (36)
Joined: 9/11/2004
Posts: 2623
If the numerical approximation is 1.1249976996... then the formula I have isn't too terribly bad after simplification, but you're correct that it's not invertible.
Build a man a fire, warm him for a day, Set a man on fire, warm him for the rest of his life.
Editor, Skilled player (1936)
Joined: 6/15/2005
Posts: 3239
OmnipotentEntity wrote:
If the numerical approximation is 1.1249976996... then the formula I have isn't too terribly bad after simplification, but you're correct that it's not invertible.
Assuming the field has radius 1, I got a value of about 1.15872847302 for the tether. I'll explain how I got this below. Setting up the formula is actually not that hard and no calculus is required. The following diagram shows the field of radius 1, centered at (0,0), and the region that the goat eats if the tether, tied to the fence at (0,-1), has length c: From the diagram above , the area that the goat grazes is 2*(area of light blue + area of yellow). c = sqrt(2 - 2 cos θ) (from cosine law) α = (1/2)(pi - θ) Area of yellow = (1/2)θ - (1/2)(sin θ) = (1/2)(θ - sin θ) Area of light blue = (1/2)αc2 = α(1 - cos θ) = (1/2)(pi - θ)(1 - cos θ) Total area = (θ - sin θ) + (pi - θ)(1 - cos θ) So we need to solve (θ - sin θ) + (pi - θ)(1 - cos θ) = pi/2. This can't be easily done, so we turn to WolframAlpha to solve it and we get: θ ≈ 1.23589692428 (which is about 70.8 degrees) That gives us the value of c: c ≈ 1.15872847302. If the field has radius R, then the length of the tether is about 1.15872847302*R
Tub
Joined: 6/25/2005
Posts: 1377
I'll just leave a couple of links that the riddler omitted. If you're going to turn to wolfram, don't ignore this page: http://mathworld.wolfram.com/GoatProblem.html More decimal places of the solution can be found on http://oeis.org/A133731 Turns out this problem also has a Wikipedia page, which claims that the problem was first published in 1748.
m00