Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
I'm pretty sure Warp is referring to C1-continuity (continuous and once differentiable) as "smooth"; the functions defined above in Warp's post, even for the same exponent, are not C2-continuous (continuous and twice differentiable).
I'm assuming that what Warp means is that the function defined on [0,0.5] must be a scaling (horizontal and/or vertical) of y=xn, and that it is not allowed to be transformed in any other way. And similarly the function defined on [0.5,1] is defined as above, but rotated 180 degrees around the point (0.5,0.5). Warp's question is: for given exponents, what is the y value of the point where these two segments meet (when x=0.5), so that the resulting curve is continuous and once differentiable?
Note that scaling y=xn horizontally and vertically gives y=C(Dx)n, which we can rewrite as y=(CDn)xn. So we can assume that the function f is defined as y=Axm on [0,0.5], y=1-B(1-x)n on [0.5,1].
Then f must be continuous and differentiable at 0.5. That gives the two equations:
A(0.5)m = 1-B(0.5)n
Am(0.5)m-1 = Bn(0.5)n-1
Solving this (I leave this to the reader) gives B=m2n/(m+n), A=n2n(m+n). So at x=0.5, y=n2n-m/(m+n).
By the way, my first thought of an "easing function" was the sine curve 0.5+0.5sin(π(x-0.5)).
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Actually, horizontal flip doesn't correspond to negation, but negation of complex conjugation. (Negation is 180-degree rotation.) Your point still stands though.
In the general case zn+1=znk+c, there is actually rotational symmetry (by multiples of 2π/(k-1)) combined with vertical reflection symmetry (complex conjugation).
rhebus wrote:
Admittedly saying this proof doesn't work isn't the same as saying that there definitely isn't horizontal symmetry. I'm pretty sure this is only one or two steps away from proving that though.
For zn+1=zn2+c, let c=1. Then the sequence is 0,1,2,5,26,... so 1 is not in the Mandelbrot set. On the other hand, for c=-1, the sequence is 0,-1,0,-1,... and so -1 is in the set.
Same kind of argument for even powers greater than 2.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
OmnipotentEntity wrote:
thatguy wrote:
Here's a more interesting twin prime problem: prove that the only Fibonacci numbers that are also twin primes are 3, 5 and 13.
(I can remember the result, and I have been shown a proof, but I can't remember the details and Google isn't helping. But I think it relies pretty heavily on recurrence formulas for the Fibonacci numbers, and for Fn+-2, that enable you to factorise them.)
While looking for other ways to prove this, I found a nice formula involving the Fibonacci and Lucas numbers.
Recall that Fibonacci numbers are defined as F0=0, F1=1, Fn+2=Fn+1+Fn. The first few numbers are 0,1,1,2,3,5,8,13,21,34,... , and it can even be extended backward to negative indices: ...,-8,5,-3,2,-1,1,0,1. Note that F-n = (-1)n+1Fn.
Lucas numbers are related similarly, and are defined as L0=2, L1=1, Ln+2=Ln+1+Ln. The first few numbers are 2,1,3,4,7,11,18,29,47,... , and it can be extended backward: ...,18,-11,7,-4,3,-1,2,1. Note that L-n = (-1)nLn.
Then the entire problem above can be solved just with the following identity, which applies for all integers m,n.
FmLn + FnLm = 2Fm+n. (*)
Proof is by induction, which I will omit.
Replacing n in (*) with -n gives:
FmLn - FnLm = (-1)n2Fm-n, (**)
because of F-n = (-1)n+1Fn and L-n = (-1)nLn. Taking (*)+(**) and (*)-(**) and dividing by 2 give:
FmLn = Fm+n + (-1)nFm-n, (***)
FnLm = Fm+n - (-1)nFm-n. (****)
@ Setting m=n in (***) gives F2n = FnLn. So F2n is prime only for n=2, which gives the twin primes 3,5.
@ Setting m=n+3 in (***) gives F2n+3 + (-1)nF3 = F2n+3 + (-1)n2 = Fn+3Ln. So F2n+3 + (-1)n2 is prime only for n=1, which gives the twin primes 3,5 again.
@ Setting m=n+3 in (****) gives F2n+3 - (-1)nF3 = F2n+3 - (-1)n2 = FnLn+3. So F2n+3 - (-1)n2 is prime only for n=1 and 2, which give two pairs of twin primes, 5,7 and 11,13.
So the only Fibonacci primes that are part of a pair of twin primes are 3,5, and 13.
Note that you can also prove that, for example, the only primes that are one away from a Fibonacci number are 2,3, and 7. (Hint: set m=n+1 and m=n+2 in both (***) and (****).)
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
The furigana マドーキング (Madō Kingu) is placed entirely over the kanji 魔動王, so according to Japanese convention, the 魔動王 in the title is supposed to be pronounced Madō Kingu and not anything else.
You can choose whichever title you feel is appropriate for this site. I'm just pointing out that Japanese convention on furigana is weird enough that one can just impose any pronunciation one wants on any written script for stylistic reasons. This happens with a few other Japanese titles out there.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Nice improving the former TAS (can't believe it only took you 13791 rerecords).
I did give this a thought that making a TAS of this game could be (mostly) automated in some way. However, no matter how easy MrWint makes it look, setting up automation for a game is not even remotely easy.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
I forgot to mention until now. This game is actually supposed to be called "Madō King Granzort", not "Madouou/Madoo Granzort". Because Japanese is weird.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
OmnipotentEntity wrote:
Warp wrote:
In other words is the derivative of "(1/2)*x*f(x) + (1/4)*sinh-1(2x)" "f(x)"?
No, absolutely not.
I think Warp meant to ask "Do there exist any functions f(x), other than sqrt(4x2+1), such that the derivative of (1/2)*x*f(x) + (1/4)*sinh-1(2x) is f(x)?"
The answer to that is yes. But it's not that impressive. The family of solutions to the differential equation ((1/2)*x*f(x) + (1/4)*sinh-1(2x))' = f(x) (■) is sqrt(4x2+1) + Cx, for all real numbers C. Note that (■) is a first-order linear differential equation. So you can rewrite it as:
f'(x) - (1/x)*f(x) = -(1/x)*(1/sqrt(4x2+1)).
Multiplying both sides by 1/x (the factor to apply reverse product rule to the left-hand side):
((1/x)*f(x))' = -(1/x2)*(1/sqrt(4x2+1)),
(1/x)*f(x) = int(-(1/x2)*(1/sqrt(4x2+1))) = sqrt(4x2+1)/x + C,
where the integral can be solved with, for example, x=(1/2)*tan(u). So
f(x) = sqrt(4x2+1) + Cx.
Note: Because (■) is a linear differential equation and we already know that sqrt(4x2+1) is a solution, we can just solve the homogeneous system ((1/2)*x*h(x))' = h(x) (solution family is Cx). Then every solution to (■) is a solution to the homogeneous system (Cx) plus the particular solution sqrt(4x2+1).
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Warp wrote:
Is the same true for any possible replacement for sqrt(4x2 + 1), or does it have to be precisely that?
If you're asking whether the antiderivative of sqrt(a+bx2) is similar, the answer is yes.
By integration of parts (int means integral/antiderivative):
int(sqrt(a+bx2)) = x*sqrt(a+bx2) - int(bx^2/sqrt(a+bx2)
= x*sqrt(a+bx2) - ( int(sqrt(a+bx2)) - int(a/sqrt(a+bx2)) )
So
2*int(sqrt(a+bx2)) = x*sqrt(a+bx2) + int(a/sqrt(a+bx2))
int(sqrt(a+bx2)) = (1/2)*x*sqrt(a+bx2) + (a/2)*int(1/sqrt(a+bx2))
So you just have to find the antiderivative of 1/sqrt(a+bx2) and that is:
● (1/sqrt(b))*sinh-1(sqrt(b/a)x) if a>0, b>0,
● (1/sqrt(-b))*sin-1(sqrt(-b/a)x) if a>0, b<0,
● (1/sqrt(b))*cosh-1(sqrt(-b/a)x) if a<0, b>0.
(After this, add a constant C at the end.)
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
If you only need a few points (as in, ~10 to 1000 or so, not billions) on the curve y=x2 that are equally spaced by arclength, you can just use Newton's Method. In this case:
xi+1 = xi - (f(xi)-C)/f'(xi),
where
f(x) = (1/2)*x*sqrt(4x2 + 1) + (1/4)*sinh-1(2x),
f'(x) = sqrt(4x2 + 1),
and C ranges from 0 to 1.48 (or whatever) with step-size 0.01 (or whatever). The initial value x0 can be anything reasonably close, e.g. x0=sqrt(C). Five or six iterations of Newton's Method should be enough to converge to 15 decimal places.
Edit: For example, if you let C range from 0.1 to 1.5 with step-size 0.1, the values of the coordinates would be:
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
OmnipotentEntity wrote:
I was looking into continued fractions, and I found this OEIS wiki page on the subject.
It lists the basic continued fraction [0, 1, 2, 3, 4, 5]... as I_1(2)/I_0(2) where I_n is the modified Bessel Function of the 1st kind.
This is the last place I expected to see the Bessel function crop up. Any insight on why this is? I have been unable to find a proof.
This page should explain why. Unfortunately it is somewhat complicated and I can't really say any more on the topic.
Warp wrote:
I suppose the only way is to approximate by recursively subdividing and measuring distances along straight lines. That's a bit surprising. One wouldn't think of x2 to be that complicated.
Arclength is complicated in most cases.
I don't think there is a way to express inverse of arclength of x2 in elementary functions. Would giving a Taylor series instead be acceptable?
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Well obviously if ∑an converges to π and f:{0,1,...}→{0,1,...} is an increasing function, then so does ∑bn where by=af-1(y) if y is in the range of f and by=0 otherwise. So we can take f(n) to be as fast-increasing as we can conceive and ∑bn would converge as slowly.
But that's cheating. To make things a little less trivial, let's assume the sequence {|an|} is always decreasing (but not zero). We can rewrite cn=1/|an| where {cn} is always increasing.
Now if the terms an are always positive, then ∑an=∑1/cn is absolutely convergent. The corresponding sequence {cn} can't increase too slowly or else the sum would diverge. At least cn would need to go to ∞, but that's not enough; for example the harmonic series (1+1/2+1/3+...) diverges. In fact, cn would have to grow faster than linearly in n for the same reason the harmonic series diverges. So already it cannot converge slower than the Leibniz formula if it is absolutely convergent.
So another obvious approach is to allow an to alternate in sign, so that ∑an=∑(-1)n/cn. In this case, cn can grow as slowly as possible (since in this case, all that is required for convergence is cn→∞). For example, cn=ln(ln(n+1)+1) would cause the summation to converge extremely slowly, cn=ln(ln(ln(n+1)+1)+1) slower still, and so on. Unfortunately, we know very little about what these series converge to.
These series (when cn grows linearly or slower) are obviously conditionally convergent. The Riemann Series Theorem says that you can rearrange a conditionally convergent series to converge to any real number you choose or even diverge. Thus there is a rearrangement of ∑(-1)n/cn that converges to π, and would converge very slowly. The problem is that we have no clue what this rearrangement is.
So other than the Leibniz formula, I can't think of another formula that converges to π that is slower with {|an|} always decreasing. I thought of the Dirichlet eta function (alternating Riemann zeta function) but don't know any rational numbers in (0,1) that would make it converge to anything related to π.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
thatguy wrote:
All this e-chat reminded me of a relatively obscure property of e which turns up in the following problem:
A cheeky monkey is stealing bananas from a market stall. At the market, bananas come in boxes of a specific size. The monkey is very clever, and knows the vendor leaves his market stall unattended for a few minutes at the same time every day to pray, leaving a partially full box of bananas. At this time the monkey dashes to the box and takes it back to his lair, where he has his own box of the same size that he has also stolen from the vendor. He does this every day until his box is full of bananas. Show that, on average, it takes e days to fill the box.
I'll assume the problem is one about selecting and adding values from a uniform distribution on [0,1] until their sum is greater than 1.
Given n variables x1, x2, ..., xn whose values are randomly selected from [0,1], what is the probability that x1+x2+...+xn<1? (*)
The answer to (*) is 1/n!. There are a few ways to show this. One is that the question is equivalent to finding the volume of an n-dimensional simplex whose vertices are (0,0,...,0), (1,0,...,0), (0,1,...,0), ..., (0,0,...,1). Using the determinant formula for simplex volume thus gives 1/n!. (Or you could just use integration.) Another way which doesn't require this formula, or calculus, is as follows: The answer to (*) is the same as answering the following question:
Given n variables y1, y2, ..., yn whose values are randomly selected from [0,1], what is the probability that y1<y2<...<yn? (**)
This is because the probability for (*) is formed by taking x1 in ［0,1］, x2 in ［0,1-x1］, x3 in ［0,1-x1-x2］, ..., and the probability for (**) is formed by taking y1 in ［0,1］, y2 in ［y1,1］, y3 in ［y2,1］, ..., where y1 corresponds to x1, y2 to x1+x2, y3 to x1+x2+x3, and so on. For (**), the probability must be 1/n!, since the particular ordering of y1<y2<...<yn is one of n! possible orderings of y1,y2,...,yn , each of which have the same probability.
So now that we know the answer to (*) is 1/n!, the probability that n values were selected by the time their sum is greater than 1 is 1/(n-1)! - 1/n! = (n-1)/n!. The expected number is then:
Sum{n from 1 to infinity} n(n-1)/n! = Sum{n from 2 to infinity} 1/(n-2)! = 1+1+1/2!+1/3!+... = e.
------------------------------------------------------------
By the way, about the Riddler problem of filling out the long division below with digits 0 to 9:
It can be solved as follows:
● c must be 0, since no subtraction takes place when its digit is brought down.
● www is 7 times uuu
● xxx, which is a multiple of uuu, is greater than www, since xxx plus yy is a 4-digit number, but www plus a 3-digit number is a 3-digit number. However xxx is less than vvvv and zzzz, also multiples of uuu.
● It follows that xxx is 8 times uuu and vvvv=zzzz is 9 times uuu. So b=8 and a=d=9.
● Since xxx which is 8 times uuu is a 3-digit number, then uuu is between 112 and 124.
● So yy is less than 13.
● But xxx+yy is a 4-digit number.
● So xxx which is 8 times uuu is between 988 and 999.
● Only possibility is uuu=124.
The unique solution is thus:
I like this problem because the fact that it has a unique solution is not so obvious, yet all the necessary information is based on the structure of the long division presented.
The other Riddler problem wasn't so fun. I took the solution here from yesterday's Riddler column. No claim (let alone proof) is given that this rearrangement into a square here is unique:
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
thatguy wrote:
Depends what you consider the definition of e. Most people are introduced to it through the following identity:
lim(n -> inf) (1+1/n)n = e
However, from an analytical standpoint, the really fundamental property is:
d/dx(ex) = ex
There is a link between the two definitions when it comes to learning calculus. It comes in when establishing the derivative of logarithms.
The general logarithm is defined as: logb(x) is the value y such that by=x, b positive and not 1. Using the limit definition of the derivative:
d/dx logb(x) = lim[h→0] (logb(x+h)-logb(x))/h
= lim[h→0] (1/h)*logb(1+h/x)
= lim[h→0] logb((1+h/x)1/h)
= logb(lim[h→0] (1+h/x)1/h)
= (1/x)*logb(lim[h→0] (1+h/x)x/h)
= (1/x)*logb(lim[k→∞] (1+1/k)k),
where k=x/h. Now lim[k→∞] (1+1/k)k is defined to be e, and so
d/dx logb(x) = (1/x)*logb(e),
and defining ln(x) to be loge(x) gives
d/dx ln(x) = 1/x.
The derivative of ex now comes from the chain rule: Taking derivative of both sides of x=ln(ex) gives
1=(d/dx ex)*(1/ex),
which implies d/dx ex = ex.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
p4wn3r wrote:
y'(u) = (1-u)e-uy(u)
By induction you can prove that
y(n)(u) = Pn(u)e-uy(u) [*],
where Pn(u) is an n-th degree polynomial.
I'm not sure about this. For example, I'm getting for y''(u):
y''(u) = -e-uy(u) + (u-1)e-uy(u) + (1-u)e-uy'(u)
= (u-2)e-uy(u) + (1-u)2e-2uy(u),
which isn't in the form written above (y(n)(u) = Pn(u)e-uy(u)).
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
OmnipotentEntity wrote:
(d^n x^(1/x))/(dx^n) = x^(-n + 1/x) (1 - n + 1/x)_n for (n element Z and n>=0 and x!=1/x)
Where (x)_n is the Pochhammer symbol and represents (x)(x+1)(x+2)...(x+n-1)
That would be true if 1/x didn't have an x in it. Unfortunately d/dx xk= kxk-1 is only valid when k does not depend on x.
Regarding dn/dxn x1/x, I'm not sure how to prove that it has n simple zeroes (obviously everything has to be positive since it is only defined for x>0). I do know that something like this can be proven for dn/dxn e-x2 as follows:
The function y=e-x2 satisfies the differential equation y'=-2xy. Using this, we can show that y(n)=p(x)y, where p(x) is a polynomial of degree n. That means:
● y is infinitely differentiable everywhere.
● Since y has no zeroes, that means y(n)=0 only when p(x)=0, so y(n) has no more than n zeroes counting multiplicity.
● lim[x→-∞] y(n) = lim[x→∞] y(n) = 0 for all n.
Clearly y' has exactly one simple zero at x=0. Now suppose y(n) has n simple zeroes at x1, x2, ..., xn. Because they are simple zeroes, they cannot be zeroes of y(n+1). By the mean value theorem, there exists a zero of y(n+1) between each pair xi, xi+1. There also exists a zero less than x1 (mean value theorem on x0→-∞ and x1) and a zero greater than xn (mean value theorem on xn and xn+1→∞), which gives at least n+1 zeroes of y(n+1). Since there are no more than n+1 zeroes counting multiplicity, then these n+1 zeroes are the only zeroes and they are all simple.
I haven't figured out if this process works for dn/dxn x1/x yet.
----
By the way, there are a couple interesting problems on The Riddler this week.
Riddler Classic: Fill all the * entries with digits from 0 to 9 to make this long division correct. Numbers can't start with 0. There is only one solution and it can be done with pen and paper.
That is the easy problem. The hard problem is Riddler Express below.
Riddler Express: Cut the shape below into three pieces and reassemble them into a square.
I have a solution for Riddler Classic but I still haven't figured out Riddler Express yet.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
thatguy wrote:
2) Let's stick specifically to positive real numbers here - raising a negative number to a fractional power leads us into the murkier waters since these functions are multi-valued, and can only be defined via somewhat artificial branch cuts.
xy > eylnx implies:
eylnx > exlny
ylnx > xlny
lnx/x > lny/y
So the easiest way to visualise this is to draw a graph of f(x) = lnx/x, and then substitute in x and y. If f(x) > f(y), then xy > yx. Interestingly, this gives the relation a transitive property: If xy > yx, and yz > zy, then you can guarantee that xz > zx.
To add to this, the graph of f(x) = ln(x)/x is as follows:
So the equation ln(x)/x = c has two solutions x1, x2 whenever 0 < c < 1/e (the maximum of ln(x)/x is at x=e with a value of 1/e; this is proved with calculus; ln(x)/x → 0 as x → ∞ as well), with 1 < x1 < e, and x2 > e. For example, when c = ln(2)/2, the two solutions are x1=2 and x2=4.
In fact, these two solutions are given exactly by x1 = e-W(-c) and x2 = e-W-1(-c), respectively, where W(x) and W-1(x) are branches of the Lambert W function; W(x) is the inverse of xex on -1 to ∞, and W-1(x) is the inverse of xex on -∞ to -1. This is because:
ln(x)/x = c
→ z/ez = c where x=ez
→ -ze-z = -c
→ -z = W(-c) or W-1(-c)
→ z = -W(-c) or -W-1(-c)
→ x = e-W(-c) or e-W-1(-c).
To answer the question, xy > yx for positive x,y if and only if at least one of the following is true:
@ y < x ≤ e,
@ e ≤ x < y,
@ y ≤ 1 < x,
@ 1 < x < e and y > e-W-1(-ln(x)/x),
@ x > e and y < e-W(-ln(x)/x).
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
ruadath, if you need to use a debugger for SNES games, you can use Geiger's Snes9x Debugger. I tend to use that whenever I need to understand some functions that are hard to understand otherwise.
Edit: Fixed link.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
link_7777 wrote:
The route from the NES version doesn't work here for some reason?
It should work in SNES as well, but you have to set CPU difficulty to easiest.
I think I have a video uploaded somewhere but I don't remember where. In any case, it should be reproducible by any competent TASer.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
I gave TAStudio a try at one point (since Hetfield90 was very supportive of it) but it crashed a few too many times (taking all the greenzones with it) and I eventually stopped using it.
I may use it later when I try working on a new Mega Man 7 100% TAS, but not until then.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
r57shell wrote:
Each of corner tends to starting corners. It's easy proovable:
Fix n
The intention was not to fix n, but to consider the set of all (infinite) corners as a whole.
Then:
r57shell wrote:
But total distance: ac0 + ac1 + ac2 + ... + acn = a(1 - c^(n+1))/(1 - c)
When a->0, this is zero.
● The total distance is an infinite sum: ac0 + ac1 + ac2 + ... + acn+ ..., which equals a/(1-c).
● c depends on a; c=sqrt(a2+b2)=sqrt(a2+(1-a)2)=sqrt(2a2-2a+1).
● a/(1-c)=a/(1-sqrt(2a2-2a+1))=(1+sqrt(2a2-2a+1))/(-2a+2); when a→0, the limit is 2/2=1.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
r57shell wrote:
FractalFusion wrote:
Since the motion vectors always form 45-degree angles to the radial displacement (from the center of the square), radial velocity is always 1/sqrt(2) inward and tangential velocity is always 1/sqrt(2) clockwise (and we also know that tangential velocity is equal to radial distance times angular velocity).
Can you explain in details?
Because of 90-degree rotational symmetry around the center of the square, the four animals always form the corners of a square at any given time. The velocity vector of the top-left animal is shown in the diagram above but this applies similarly to all of them. Because the animals form the corners of a square at all times, θ is always 45 degrees, and so |vr|=(sqrt(2)/2)*|v| and |vt|=(sqrt(2)/2)*|v|.
For simplicity, I assumed that |v| was always 1 (unit speed). However, it doesn't actually matter what |v| is, as long as all four animals have the same speed at the same time (so that it always remains a square). For example if instead we let speed be a function of t, so that we use |v(t)| instead of unit speed, then:
dr = (-1/sqrt(2))*|v(t)| dt
r*dθ = (-1/sqrt(2))*|v(t)| dt = dr
and the rest is the same.
r57shell wrote:
FractalFusion wrote:
Suppose that four animals are placed at the corners of the unit square and each animal walks at unit speed directly toward the one on its left.
In the end: can you prove that this task is same/related?
The side length of the first square inside the outer (unit) square is sqrt((1-a)2+a2)=sqrt(2a2-2a+1), which we call c. Also, the diagram is self-similar, so a rotation and scaling maps the first square to the second, the second to the third, and so on. The corners of the squares can thus be modelled by:
@ Four animals are placed at the corners of the unit square.
@ 1st step: Each of them faces the one on the left and moves distance a.
@ 2nd step: Each of them faces the one on the left and moves distance ac.
@ 3rd step: Each of them faces the one on the left and moves distance ac2.
...
@ nth step: Each of them faces the one on the left and moves distance acn-1.
...
Each step generates all the corners of the squares. Letting a→0 causes all the distances above to go to 0, so the corners converge to a curve, and this curve is the one formed where each animal walks directly toward the one on its left (continuously).
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
thommy3 wrote:
(4 choose 3)*8/52*1/51*6/50*1/49*4/48*1/47 = 1 in 19 million
thommy3 wrote:
Four possible ways to chosse three players from the four who get dealt KQ suited.
That number overcounts the cases though (since it counts the case when all four players have KQs four times).
For (1), the number I have is:
(I ignore the order of the two cards in each hand, but I specify the four players. I choose the three players that get KQs, then the three suits, then order them among the players, then give the fourth player any two cards. I subtract the cases where the fourth player also has KQs.)
[C(4,3)C(4,3)3!C(46,2)-4*4!] / [C(52,2)C(50,2)C(48,2)C(46,2)], or about 5.23435×10^-8 (1 in 1.91046×10^7).
If you allow the fourth player to have KQs (and count it only once) then:
[C(4,3)C(4,3)3!C(46,2)-3*4!] / [C(52,2)C(50,2)C(48,2)C(46,2)], or about 5.23561×10^-8 (1 in 1.91000×10^7).
For (2), I assume that the fourth hand has been folded and plays no further part. I assume that the fourth player could have had the last KQs, or anything else other than the other kings or queens that the other players hold, and so is no different from being randomly dealt two cards. If all four players have KQs, it is counted four times (once for each player that folds).
(I also ignore the order of the five cards on the board.)
At a minimum, AJT is on the board. Then it is impossible to have a full house or four of a kind. The only higher hands possible are flushes and straight/royal flushes. Since three players hold KQs, there can't be three cards of those suits on the board. The board also can't have all cards being the fourth suit.
So the cases for the ranks of the cards on the board are:
(x and y denote ranks below ten (T), z denotes K or Q, u and v denote A or J or T)
@ AJTxy, C(8,2) * [4^5 - C(3,1)[C(5,3)3^2+C(5,4)3+C(5,5)] - 1] = 19740
@ AJTxx, C(8,1) * [4^3C(4,2) - C(3,1)[6+3*9]] = 2280
@ AJTzx, C(2,1)C(8,1) * [4^4 - C(3,1)[C(4,3)3+C(4,4)] - 1] = 3456
@ AJTKQ, 1 * [4^3 - C(3,1) - 1] = 60
@ AJTux, C(3,1)C(8,1) * [4^3C(4,3) - C(3,1)[6+3*9]] = 3768
@ AJTuz, C(3,1)C(2,1) * [4^2C(4,2) - C(3,1)3] = 522
@ AJTuv, C(3,2) * [4C(4,2)^2 - C(3,1)3^2] = 351
@ AJTuu, C(3,1) * [4^2C(4,3) - C(3,1)3] = 165
Total: 30342
So the probability is thommy3's answer times 30342 / C(46,5), which is about 1.15976×10^-9 (1 in 8.62249×10^8).
Now, you might argue that, for example, having AJTKQ on the board violates the spirit of the problem, because that means everyone's KQs is useless for making an A-high straight. So I'll look at the extreme: suppose that we require that not only do all three players have nut hands (hands which can never lose from their standpoint), but also that each player is guaranteed to win but for another player having KQ (this is the most exciting scenario, and the one which Warp saw as indicated by the screenshot, which I will post here again).
Warp wrote:
That means the only permissible board layout is AJTxy with no three cards of the same suit. In that case there are C(8,2) * [4^5 - C(4,1)[C(5,3)3^2+C(5,4)3+C(5,5)]] = 16800 possibilities, and so the probability is thommy3's answer times 16800 / C(46,5), which is about 6.42144×10^-10 (1 in 1.55728×10^9).
Edit: Fixed the denominator for (2). Obviously it's supposed to be C(46,5), not C(44,5), since we were discarding consideration of the fourth player's hand.
OmnipotentEntity wrote:
This is known as the "curve of pursuit." Also known as the "mice problem."
I don't know the solution to the curve, but it should be rather easy to set up the parametric differential equations. I'll leave that to someone else though.
Seeing this as a pursuit problem is very useful. For example, this blog discusses square pursuit, and an image of square pursuit from that blog is shown below:
Suppose that four animals are placed at the corners of the unit square and each animal walks at unit speed directly toward the one on its left. Since the motion vectors always form 45-degree angles to the radial displacement (from the center of the square), radial velocity is always 1/sqrt(2) inward and tangential velocity is always 1/sqrt(2) clockwise (and we also know that tangential velocity is equal to radial distance times angular velocity). In terms of differential equations:
r=distance from center, t=time, θ=angle
dr = -1/sqrt(2) dt
r*dθ = -1/sqrt(2) dt = dr
Solving the last equation:
dθ = 1/r dr
θ+C = ln(r)
r = eθ+C = Aeθ.
Therefore each of the four animals traces a logarithmic spiral with polar equation r = Aeθ for some A depending on which one of the four is considered.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Bobo the King wrote:
And that's as far as I've gotten. Based on this very short trend (75 --> 70.83 --> 68.33), it appears that the success rate crashes fairly rapidly toward 50 percent as the deck size increases. In this sense, 52 would be "closer to infinity than to 2". Can anyone confirm this? What is the approximate probability of success using this strategy on a deck of 52 cards?
There is an exact probability, and it is 3724430600965475 / 6446940928325352 (about 57.7705%).
The exact formula for 2n cards (n red and n black) is 1/2 + (4n/C(2n,n) - 1)/(4n). The first few values of n agree with Bobo the King's calculations. Approximations for various n based on this formula, showing that this approaches 1/2 as n approaches infinity:
Plugging in the asymptotic formula C(2n,n)~4n/sqrt(pi*n) gives the approximation 1/2 + (sqrt(pi*n) - 1)/(4n) for large n, which is another way to show that the limit is infinity.
The long explanation for this is as follows:
The best strategy is: for each card, choose the color which has more cards remaining; since you make a choice at each stage, the aim is to maximize the expected number of cards guessed correctly for each card alone. When there are an equal number of red and black cards, it doesn't matter what you choose; the long-term success probability will not be affected. For simplification purposes, I will assume that in this case you choose red and black with equal probability (1/2 each).
It turns out that there is a combinatorial approach to this problem. Model the deck as a path of up and right steps starting from (0,0) and ending at (n,n) (such as shown in https://i.stack.imgur.com/vGlBj.gif for n=1 to 3) where you go through the deck and go up if the card is red and right if the card is black. Then there is a surprising relation between the expected number of correct guesses (and thus the long-term success probability) and the number of times this path contacts the line y=x (henceforth called "the diagonal").
Following the strategy above, consider each time the path goes between contact points on the diagonal, say, from (a,a) to (b,b). At (a,a), the random choice of red or black adds 1/2 to the expected number of correct guesses so far. After this card, you choose black (if it was red) or red (if it was black) until the path reaches (b,b); this adds b-a correct guesses. Thus, from (a,a) to (b,b), the expected number of correct guesses so far is increased by b-a + 1/2.
Summing over the whole path gives as the expected number of correct guesses n + E/2, where E is the average number of contacts with the diagonal, other than at (n,n), over all such paths from (0,0) to (n,n). So the long-term success probability is (n + E/2)/(2n) = 1/2 + E/(4n). The problem then becomes one of calculating E.
Generating functions
A Dyck path is an up-right path from (0,0) to (n,n) that never goes below the diagonal. The generating function for Dyck paths is D(x)=(1-sqrt(1-4x))/(2x). I will define a "strict Dyck path" as a Dyck path which never contacts the diagonal except at (0,0) and (n,n). A strict Dyck path is just a Dyck path from (0,1) to (n-1,n), with an additional up-step added to the beginning and an additional right-step at the end. I also allow the strict Dyck path to acquire two orientations: one where it is above the diagonal and one where it is reflected so as to be below the diagonal. The generating function for strict Dyck paths on two orientations is 2xD(x) = 1-sqrt(1-4x).
Thus an unrestricted up-right path from (0,0) to (n,n) can be viewed as a sequence of k≥1 strict Dyck paths on two orientations, and the number of contacts is k. Normally, we take the generating function 1/[1-(1-sqrt(1-4x))] = 1/sqrt(1-4x), which indeed is the generating function for the sequence C(2n,n). On the other hand, we can take the bivariate generating function F(x,z)= 1 / [1 - (1-sqrt(1-4x))z], which in addition counts the number of the diagonal contacts other than (n,n) in the variable z.
To calculate the average number of contacts E, we first take the sum total of contacts, which we do by taking the derivative of F(x,z) in z and then setting z=1. Since d/dz F(x,z) = (1-sqrt(1-4x))/[1 - (1-sqrt(1-4x))z]2, this gives (1-sqrt(1-4x))/(1-4x) = 1/(1-4x) - 1/sqrt(1-4x). The coefficient of xn of this generating function is 4n - C(2n,n). Thus the average number of contacts E is 4n/C(2n,n) - 1. Substituting into 1/2 + E/(4n) gives the formula 1/2 + (4n/C(2n,n) - 1)/(4n), as above.
Warp wrote:
Thus it becomes somewhat of a surprise that the answer to the question of whether there are infinitely many Mersenne primes is actually unknown, an unsolved problem in mathematics. Why wouldn't there be infinitely many of them?
But, of course, as long as you can't prove there are, you can't say so. Assertions in mathematics cannot be made based on intuition and gut feeling.
Math is full of stuff like that.
Possible reasoning based on heuristics for why there could be infinitely many Mersenne primes (and finitely many Fermat primes) is given here: http://math.stackexchange.com/questions/838678/intuitively-what-separates-mersenne-primes-from-fermat-primes . Of course not a valid proof of anything, but one of the reasons that people use heuristics is because we know so little about some things in math.
Warp wrote:
1) In a four-player game of Texas Hold'em, what are the odds that three of them will get King-Queen suited as their hand cards?
2) What are the odds that, in addition to the above, they all get ace-high straights (iow. 10, J and A hit the table; the two other cards don't matter). No straight flush (nor full houses), though, so those situations don't count.
I'll answer this later if no one else does, but I have some questions. For (1), does it matter what the fourth hand is? Can it be anything, including the last King-Queen suited? For (2), do we ignore the fourth hand completely, as in, we can assume that it has been folded and plays no further part in the deal?
Also, as a question of interest, in the deal that you mentioned (three players with King-Queen suited, 10, J, A and two others on the table), do you remember if all three players have nut hands? That is, from their point of view, they all had a hand which from their point of view could never lose no matter what anybody else had? If so, that would have been very interesting. The usual result being that all three players go all-in and a huge amount of excitement is generated, only to end in a split pot anyway. :D
The furigana マドーキング (Madō Kingu) is placed entirely over the kanji 魔動王, so according to Japanese convention, the 魔動王 in the title is supposed to be pronounced Madō Kingu and not anything else.
You can choose whichever title you feel is appropriate for this site. I'm just pointing out that Japanese convention on furigana is weird enough that one can just impose any pronunciation one wants on any written script for stylistic reasons. This happens with a few other Japanese titles out there.
It can be solved as follows:
I have a solution for Riddler Classic but I still haven't figured out Riddler Express yet.
So the equation ln(x)/x = c has two solutions x1, x2 whenever 0 < c < 1/e (the maximum of ln(x)/x is at x=e with a value of 1/e; this is proved with calculus; ln(x)/x → 0 as x → ∞ as well), with 1 < x1 < e, and x2 > e. For example, when c = ln(2)/2, the two solutions are x1=2 and x2=4.
In fact, these two solutions are given exactly by x1 = e-W(-c) and x2 = e-W-1(-c), respectively, where W(x) and W-1(x) are branches of the Lambert W function; W(x) is the inverse of xex on -1 to ∞, and W-1(x) is the inverse of xex on -∞ to -1. This is because:
ln(x)/x = c
→ z/ez = c where x=ez
→ -ze-z = -c
→ -z = W(-c) or W-1(-c)
→ z = -W(-c) or -W-1(-c)
→ x = e-W(-c) or e-W-1(-c).
To answer the question, xy > yx for positive x,y if and only if at least one of the following is true:
@ y < x ≤ e,
@ e ≤ x < y,
@ y ≤ 1 < x,
@ 1 < x < e and y > e-W-1(-ln(x)/x),
@ x > e and y < e-W(-ln(x)/x).
Because of 90-degree rotational symmetry around the center of the square, the four animals always form the corners of a square at any given time. The velocity vector of the top-left animal is shown in the diagram above but this applies similarly to all of them. Because the animals form the corners of a square at all times, θ is always 45 degrees, and so |vr|=(sqrt(2)/2)*|v| and |vt|=(sqrt(2)/2)*|v|.
For simplicity, I assumed that |v| was always 1 (unit speed). However, it doesn't actually matter what |v| is, as long as all four animals have the same speed at the same time (so that it always remains a square). For example if instead we let speed be a function of t, so that we use |v(t)| instead of unit speed, then:
dr = (-1/sqrt(2))*|v(t)| dt
r*dθ = (-1/sqrt(2))*|v(t)| dt = dr
and the rest is the same.
The side length of the first square inside the outer (unit) square is sqrt((1-a)2+a2)=sqrt(2a2-2a+1), which we call c. Also, the diagram is self-similar, so a rotation and scaling maps the first square to the second, the second to the third, and so on. The corners of the squares can thus be modelled by:
@ Four animals are placed at the corners of the unit square.
@ 1st step: Each of them faces the one on the left and moves distance a.
@ 2nd step: Each of them faces the one on the left and moves distance ac.
@ 3rd step: Each of them faces the one on the left and moves distance ac2.
...
@ nth step: Each of them faces the one on the left and moves distance acn-1.
...
Each step generates all the corners of the squares. Letting a→0 causes all the distances above to go to 0, so the corners converge to a curve, and this curve is the one formed where each animal walks directly toward the one on its left (continuously).
Suppose that four animals are placed at the corners of the unit square and each animal walks at unit speed directly toward the one on its left. Since the motion vectors always form 45-degree angles to the radial displacement (from the center of the square), radial velocity is always 1/sqrt(2) inward and tangential velocity is always 1/sqrt(2) clockwise (and we also know that tangential velocity is equal to radial distance times angular velocity). In terms of differential equations:
r=distance from center, t=time, θ=angle
dr = -1/sqrt(2) dt
r*dθ = -1/sqrt(2) dt = dr
Solving the last equation:
dθ = 1/r dr
θ+C = ln(r)
r = eθ+C = Aeθ.
Therefore each of the four animals traces a logarithmic spiral with polar equation r = Aeθ for some A depending on which one of the four is considered.
