Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
p4wn3r wrote:
Prove that no right triangle with integer side lengths can have a leg whose length is a multiple of the other.
Curiously, there is a proof involving only geometric construction.
HINT: Take the proposed triangle and fold the larger leg into the hypotenuse, one of the triangles created is similar to the larger one. What's going on with it?
I didn't expect something like this would have a geometric construction (it's obvious algebraically). But after seeing your hint, I can actually see now what it's like:
Here we have the triangle ABC with the hypotenuse horizontal. B is folded down onto the point D as shown, and it can be seen that ADE is similar to ABC.
Assume that ABC satisfies the property (AB, BC and AC are integers, with BC a multiple of AB).
BC=DC, so AD = BC-DC is an integer. By similarity, DE is a multiple of AD, and so DE is an integer. Also, BE=DE, so AE = AB-DE is an integer. So ADE is a smaller triangle satisfying the property. By infinite descent, this gives us an absurdity.
----
Here's a question that I was thinking some time ago but didn't post until now.
Let c be any real number greater than 1. Prove the following integral:
Ex: For c=2, the LHS is just the limit of tan-1(x) as x goes to infinity. That is pi/2, which is what the RHS works out to be. But how do we do the other values of c?
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
I'd personally write the branch name as "11-fold canon" rather than "repeated input", but that's just me.
Masterjun wrote:
SMW has quite a big number of framerules everywhere. It was practically impossible to know each of the 11 framecounter values I will end up with, before even starting the TAS. So if you just play back the inputs in an emulator, it won't sync. What is mostly needed for it to sync is adjusting the global framecounter (RAM address $0013) once at each syncpoint.
I knew it was too good to be true.
Figures no one is insane enough to actually do it for real, with 11 instances and everything. I would guess it may be possible on a game that is easier to edit input. SMB is the first one that comes to mind.
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
That problem is from a Riddler post back on Mar 19. Their posted solution doesn't actually say too much. As pretty obviously there are a hundred ways to do this question.
I initially did it algebraically (as p4wn3r did, but without using trigonometry). After finding the answer, I tried to find a way to do it geometrically, and came up with the following:
The red line below is a diameter of the circle (since it's subtended by a 90° angle) and so the extension of the lower left edge of the green square is coincident with the bottom-right corner of the bottom square. So it goes through the top-left corner of the bottom square (bottom left corner of the top square), as shown below:
So the diameter of the green square is two-thirds the side length of the top purple square. To complete the problem geometrically, divide the green and purple square as follows:
This divides the purple square into 18 triangles and the green square into 4 triangles. So the ratio is 18/4 = 9/2.
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
p4wn3r wrote:
A) The point to notice is that if x ∈ A and y ∈ A, with x > y, then x - y ∈ A.
Forgot to reply until now, but that's actually a good way to look at this (I thought initially about doing it through continued fractions, but with this it's not necessary). Knowing that x ∈ A and y ∈ A implies |x-y| ∈ A, all we need to do now is use the Euclidean algorithm (least absolute remainder). Since both w (irrational) and 1 are in A, the algorithm never terminates, and you get a sequence of absolute remainders in A that converges to 0.
Anyway, here's a geometric problem that I saw somewhere on the internet:
Two purple squares and a green square are inscribed in a circle as shown in the image above. The top corner of the green square has the same y-coordinate as the top right corner of the upper purple square.
How many times more is the area of one of the purple squares compared to the area of the green square?
(IIRC it can be done geometrically, without algebra.)
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
Ramzi wrote:
Hi. This isn't really a math "challenge", so much as a straightforward math question. I think the answer is some basic linear algebra, but I am ignorant of linear algebra.
https://i.imgur.com/yaFXZzw.png
If anyone can point me to the right vocabulary, I'd appreciate it.
I think it's referred to as perspective. I don't study graphics transformations a whole lot though.
Transforming 3D to 2D, in general, is just called projection.
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
OmnipotentEntity wrote:
r^2 = a^2 + b^2
...
There is probably a more elegant approach, possibly involving the line connecting the left (or right) edge of both segments, which creates a segment that directly has length a^2 + b^2. But I didn't immediately see an easy way to directly relate this with the radius, and my cat sat down on my paper, so I couldn't continue working.
There's a way to see it if you join the left corner of one with the right corner of the other (see diagram below). The line passes through the point of tangency of the two semicircles and is perfectly diagonal, forming a 45-degree angle with the bottom semicircle's flat side as an inscribed angle subtending the left arc (between the left corners). By a well-known inscribed-angle theorem, the central angle subtending the left arc is 90 degrees. Thus the two right triangles formed as below are congruent (one is a rotation of the other). Each triangle has leg lengths of a and b and hypotenuse r, and so r^2 = a^2 + b^2.
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
Speaking of speed-up encodes, [url=
http://tasvideos.org/forum/viewtopic.php?p=109590#109590]I made a speed-up encode 14 years ago[/url] for a TAS of Battle Chess on the hardest difficulty which abuses glitches, which was 7 "moves" and 11.5 minutes long. Unfortunately the encode has been lost, but the movie file and the "moves" concerned are available 3 posts earlier. (You may need to refer to this page if you know nothing about Battle Chess glitches.)
The TASes that are the most in need of an "official speed-up encode" (don't think this has ever been TASVideos policy) are the ones which have the least chance of being accepted on this site in the first place. Your best bet is to attack the Vault rules (no entertainment requirement).
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
Too bad there doesn't seem to be any quick checkmates like the three-move checkmate in The Chessmaster, or something else that exhibits negative IQ in the computer player.
Also, regarding highest difficulty, there really isn't anything special nowadays about a TAS beating a chess video game from 1982 on its highest difficulty. In fact there isn't anything special about a TAS beating any chess program on its highest difficulty, unless the chess program is called "Stockfish".
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
CasualPokePlayer wrote:
The game prevents contraction of Pokerus until you visit Goldenrod the first time.
I never imagined a Pokemon game would be so devious as to artificially restrict a game mechanic in this matter.
Anyway, thanks for making me at least aware that these developers do this kind of stuff (even if RSE or Gen 4+ turn out not to have any such restriction on PKRS).
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
p4wn3r wrote:
This suggests the following procedure. Replace the n-th line of the matrix by the sum of itself plus the lines corresponding to xn/p1p2..., with the corresponding sign. The n-th term of each of these lines is just gcd(xi,xn) = gcd(xn/p1p2...,xn) = xi.
So I noticed that what you're doing is replacing gcd(xi,xn) (which I assume is the (i,n) entry) with:
sumd|xn μ(d)*gcd(xi,xn/d) (*)
where μ is the Möbius function, and you're trying to show (*) is phi(xn) when i=n and 0 otherwise.
Then we can just use Möbius inversion. If in general we fix b and we let g(n)=gcd(b,n), then the f(n) in the Möbius inversion formula is f(n) = phi(n) when n|b and f(n) = 0 otherwise. You can verify that indeed, g(n) = sumd|n f(d) ; nonzero terms only belong to the factors of gcd(b,n) and when you sum their phi function, you get gcd(b,n).
So by Möbius inversion, f(n) = sumd|n μ(d)*g(n/d) = sumd|n μ(d)*gcd(b,n/d). If b≤n, we get the last quantity is phi(n) if b=n, and 0 otherwise. So we replace b with xi and n with xn, and since xi≤xn for all i, this confirms (*) is phi(xn) when i=n and 0 otherwise, as desired.
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
p4wn3r wrote:
A classic.
Let X = (x1,x2,...,xn) be a sequence of distinct positive integers such that, for any integer y that divides some xi, y = xj for some j.
Let M denote the gcd matrix of X, that is, the element mij = gcd(xi,xj).
Prove that det(M) = phi(x1)*phi(x2)*...*phi(xn), where phi is Euler's totient function.
I was curious what you meant by "a classic" and eventually found out this paper basically describes (and solves) the problem you are giving: what is the determinant of a GCD matrix of an ordered distinct factor-closed set of positive integers? I assume this is what you were getting at, although it is difficult to come up with on your own and I wasn't able to solve it this way.
I solved it a different way though, using the Lindström–Gessel–Viennot lemma (henceforth referred as LGV), as follows:
Loosely, LGV is based on: If we have a directed graph with some nodes labelled A1, ... An, B1, ... Bn (not necessarily distinct), and we form an n×n matrix M where the (i,j) entry is the number of distinct paths from Ai to Bj, then the determinant of M is the same as the signed sum of "path systems" (sets of n paths, which collectively begin at A1, ... An and collectively end at B1, ... Bn; the sign being the sign of the permutation from [A1 ... An] to [B1 ... Bn] described by the paths). By cancellation of path systems whose paths intersect at nodes, we only need to consider the signed sum of all "non-intersecting path systems" in order to calculate det(M). LGV further generalizes so you can assign weights on each of the edges in the directed graph, instead of all edges being weight 1.
The primary use of LGV is to provide a way to enumerate the number of non-intersecting path systems just by evaluating a determinant. For example, the number of non-intersecting path systems on the lattice below (A1 must go to B1, A2 to B2 and A3 to B3) is given by the determinant of the matrix:
But LGV can also be used to show that certain combinatorial matrices have a particular determinant (usually 1), by constructing a directed graph for them which has very few non-intersecting path systems. For example, the n×n matrix with entries given by min(i,j) has a determinant of 1, based on the following directed graph (here n=4):
Note that each Ai goes to and each Bj comes from only a central node at the same level or lower; hence the min(i,j). Here there is only one non-intersecting path system: straight across from A1 to B1, A2 to B2, ... So the determinant of the matrix is 1.
I bring up the last example, because there is in fact a directed graph similar to the last one (with modified weights) that proves the determinant of the GCD matrix above, as follows:
Let {A1, ... , An} be nodes that represent the positive integers {x1, ... , xn}, and let {U1, ... , Un}, {V1, ..., Vn} and {B1, ..., Bn} be additional nodes that also represent {x1, ... , xn} in the same order. Without loss of generality, assume x1 ... xn are in increasing order (this is only for visualization similar to the above graph; the order does not change any of the results here). Define the directed edges and their weights as follows:
* Ai goes to each Uk whenever the value of Uk is a factor of the value of Ai. All edges are weight 1.
* Uk goes to Vk. The weight of the edge from Uk to Vk is phi(xk).
* Vk goes to each Bj whenever the value of Vk is a factor of the value of Bj. All edges are weight 1.
We want to show the (i,j) entry of the matrix is gcd(xi,xj). Note that there is a path from Ai to Uk to Vk to Bj, if and only if the value of Uk (and Vk) divides the GCD of the values of Ai and Bj. Because of the special weights on the edges from Uk to Vk, the total weight that marks the (i,j) entry is the sum of phi(k) over all factors k of gcd(xi,xj), which by a result in number theory is equal to gcd(xi,xj) itself. This confirms the (i,j) entry equals gcd(xi,xj), and so the matrix is M.
Then by LGV, det(M) is the signed sum of non-intersecting path systems. Based on the condition that {x1, ... , xn} are distinct and closed under factors, I argue that there is only one such path system. Because all proper factors of xi are among xk where 1≤k≤i-1, any non-intersecting path system starting from {A1, ..., An} must start as Ai → Ui for all i. A symmetric argument shows that the path system must end as Vi → Bi for all i. Finally Ui → Vi for all i (these are the only edges between {U1, ... , Un} and {V1, ..., Vn}).
So there is exactly one non-intersecting path system: Ai → Ui → Vi → Bi for all i. Thus det(M) is just the weight of this path system , which is the product of weights of all the edges: phi(x1)*phi(x2)*...*phi(xn), QED.
Edit: Changed gcd(i,j) to gcd(xi,xj), which is what I meant.
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
I was hoping this TAS wasn't going to be published so fast. Submissions are more likely to get posts when they remain in Workbench!
I enjoyed the strategies used, being different from the normal run using Raikou. And as far as I know, this is the first Pokemon TAS to make use of Pokerus. Looks like it made a difference a few times.
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
NxCy is right that the current (as a fraction of the current through the battery) from a node with k-1 bits to a node with k bits is I(k-1,k) = 1/k * 1/(N choose k). In fact, these are the numbers in the Leibniz harmonic triangle, a triangle which is basically a reciprocal form of Pascal's triangle where the Nth row and kth entry from the left, which we denote L(N,k), is given by 1/k * 1/(N choose k).
Ex: For N=2, the values of the currents through each resistor are: 1/2 1/2. For N=3: 1/3 1/6 1/3. For N=4: 1/4 1/12 1/12 1/4. And so on.
For each N, the equivalent resistance is just the sum of the values in the Nth row. We need to prove that the sum of the Nth row can be written as what p4wn3r said above:
There are two facts about the Leibniz harmonic triangle which we need:
(1) L(N,k) = L(N+1,k)+L(N+1,k+1) (this is reverse of the property in Pascal's triangle)
(2) L(N,1) = L(N,N) = 1/N
These can be proven by using L(N,k) = 1/k * 1/(N choose k)
We also know that Rn as p4wn3r gave, has the following recursive formula:
R1=1
Rn=Rn-1/2 + 1/n
Let SN represent the sum of L(N,k) over all k. Then S1=1 and:
SN-1 = L(N-1,1) + L(N-1,2) + ... + L(N-1,N-1) = (L(N,1)+L(N,2)) + (L(N,2)+L(N,3)) + ... + (L(N,N-1),L(N,N)) = L(N,1) + 2L(N,2) + 2L(N,3) + ... + 2L(N,N-1) + L(N,N) = 2(SN - 1/N)
and so SN = SN-1/2 + 1/N, which is the exact same as the recursive formula for Rn. Therefore they are the same.
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
In case anyone doesn't know what equivalent resistance means in this question: If you join (0,0,...,0) and (1,1,...,1) with a wire and a battery, what is the ratio of the battery's voltage to the current flowing through it? (Thus being equivalent to a single circuit with a battery and a resistor, with that resistor's resistance being the answer.)
It sounds like if you were to use Kirchhoff's laws on each node and circuit, you'd end up with too many equations to solve. However, it looks like some symmetry can be used to simplify the current flows for the edges. I don't have time to look at this right now, but I'll try to figure it out in the next few days.
P.S. Equivalent resistance reminds me of the time we were discussing XKCD and the infinite grid of one-ohm resistors: http://tasvideos.org/forum/viewtopic.php?p=488114#488114
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
Warp wrote:
I would like to repeat the question I already presented some years ago to a somewhat similar response: Do all the math challenges posted here need to be something for which nobody has ever found nor published a proof? Is this thread titled "some math challenges", or is it titled "unsolved problems in math"?
And on that note, googling for the answer isn't much of a "math challenge". The only slightly challenging thing might be to find the correct search terms, but I don't think that's the type of "challenge" this thread is for.
Note that I did not forbid anyone else from sharing their solution(s) if they were so interested. I was only giving my perspective on the question as it was stated.
The vast majority of questions of interest in this topic have been exploration/research type questions, so it is normal to expect a person to use any means necessary to contribute to the question. Now I do recognize "pen-and-paper" questions sometimes, but having read a statement that says only "Prove X", with no way to guess what was meant by the statement, nor a desire to redo a proof of something I have already seen many times, led to my response.
I chose to post a proof without words because that is something I find interesting and unique to this statement. I do know how to prove it using induction; is this something you want me to share?
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
Looks good, though I look forward to a cannonless TAS.
For some reason at least 49 people think that "No W5" is an actual thing. I'm guessing they just got really bored of any% but didn't want to do a category that takes more than 1.5 hours? Whatever, I don't have anything further to comment regarding that.
This is known already and there are probably hundreds of proofs out there (induction, difference of powers formulas, etc.)
I will take this chance to post a proof without words which I found on the internet:
(courtesy of artofproblemsolving.com)
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
Warp wrote:
In Magic: The Gathering the keyword "scry n" means "look at the top n cards of your library (ie. deck). You may put any amount of them on the top of your library in any order, and the rest on the bottom of your library in any order."
For example, "scry 2" means that you look at the top 2 cards of your deck, and then you may choose to put both of them on the top of the deck (in either order), or both of them on the bottom of the deck (in either order), or one of them on the top and the other on the bottom.
If you can get arbitrarily many consecutive "scry 2" effects (there are ways to achieve this), it can be relatively easily proven that you can use them to reorder your entire deck in any order you want.
So my question is: Suppose your deck has currently 50 cards, and you can apply as many "scry 2" operations to it that you want. How many such "scry 2" operations do you need, at most, to reorder your entire deck in a particular order?
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
Link to video
Rockman 7 EP is a new hack by Puresabe (author of Rockman 4 Minus Infinity) that came out about a month ago.
I did a TAS in the meantime. This is my 2nd test TAS of "all items", finishing the game in 52m40s. Can be improved, although I don't think it can get lower than 52m at this point. "any%" is 4-5 minutes faster but I am not interested in any%.
Note: "all items"/"100%" means getting the Proto Shield and upgrading it to the Hero Shield by letting it get hit enough, and getting the Rush Adaptor and buying Nova Adaptor from the Auto Shop. At 1:02:32 in the above video, the credits tells you whether you achieved "100%" by saying "OK" for it.
If you're looking for more information, there is this playthrough by JupiHornet as well as some speedruns; the best speedrun time at this time of writing is 58m11s in the "any%" category.
Two of the three links to VS Mario TASes are literally this submission.
The other one is #5564: KnucklesMaster368's NES VS. Super Mario Bros. "warps" in 10:14.92 .
Apparently VS Mario is different from normal Mario in that there is only one warp pipe to World 6 instead of warp pipes to Worlds 6-8, and some other level arrangements.
Also, the encode lacks sound for some reason.
Here we have the triangle ABC with the hypotenuse horizontal. B is folded down onto the point D as shown, and it can be seen that ADE is similar to ABC.
Assume that ABC satisfies the property (AB, BC and AC are integers, with BC a multiple of AB).
BC=DC, so AD = BC-DC is an integer. By similarity, DE is a multiple of AD, and so DE is an integer. Also, BE=DE, so AE = AB-DE is an integer. So ADE is a smaller triangle satisfying the property. By infinite descent, this gives us an absurdity.
----
Here's a question that I was thinking some time ago but didn't post until now.
Let c be any real number greater than 1. Prove the following integral:
Ex: For c=2, the LHS is just the limit of tan-1(x) as x goes to infinity. That is pi/2, which is what the RHS works out to be. But how do we do the other values of c?
So the diameter of the green square is two-thirds the side length of the top purple square. To complete the problem geometrically, divide the green and purple square as follows:
This divides the purple square into 18 triangles and the green square into 4 triangles. So the ratio is 18/4 = 9/2.
Two purple squares and a green square are inscribed in a circle as shown in the image above. The top corner of the green square has the same y-coordinate as the top right corner of the upper purple square.
How many times more is the area of one of the purple squares compared to the area of the green square?
(IIRC it can be done geometrically, without algebra.)
But LGV can also be used to show that certain combinatorial matrices have a particular determinant (usually 1), by constructing a directed graph for them which has very few non-intersecting path systems. For example, the n×n matrix with entries given by min(i,j) has a determinant of 1, based on the following directed graph (here n=4):
Note that each Ai goes to and each Bj comes from only a central node at the same level or lower; hence the min(i,j). Here there is only one non-intersecting path system: straight across from A1 to B1, A2 to B2, ... So the determinant of the matrix is 1.
I bring up the last example, because there is in fact a directed graph similar to the last one (with modified weights) that proves the determinant of the GCD matrix above, as follows:
Let {A1, ... , An} be nodes that represent the positive integers {x1, ... , xn}, and let {U1, ... , Un}, {V1, ..., Vn} and {B1, ..., Bn} be additional nodes that also represent {x1, ... , xn} in the same order. Without loss of generality, assume x1 ... xn are in increasing order (this is only for visualization similar to the above graph; the order does not change any of the results here). Define the directed edges and their weights as follows:
* Ai goes to each Uk whenever the value of Uk is a factor of the value of Ai. All edges are weight 1.
* Uk goes to Vk. The weight of the edge from Uk to Vk is phi(xk).
* Vk goes to each Bj whenever the value of Vk is a factor of the value of Bj. All edges are weight 1.
We want to show the (i,j) entry of the matrix is gcd(xi,xj). Note that there is a path from Ai to Uk to Vk to Bj, if and only if the value of Uk (and Vk) divides the GCD of the values of Ai and Bj. Because of the special weights on the edges from Uk to Vk, the total weight that marks the (i,j) entry is the sum of phi(k) over all factors k of gcd(xi,xj), which by a result in number theory is equal to gcd(xi,xj) itself. This confirms the (i,j) entry equals gcd(xi,xj), and so the matrix is M.
Then by LGV, det(M) is the signed sum of non-intersecting path systems. Based on the condition that {x1, ... , xn} are distinct and closed under factors, I argue that there is only one such path system. Because all proper factors of xi are among xk where 1≤k≤i-1, any non-intersecting path system starting from {A1, ..., An} must start as Ai → Ui for all i. A symmetric argument shows that the path system must end as Vi → Bi for all i. Finally Ui → Vi for all i (these are the only edges between {U1, ... , Un} and {V1, ..., Vn}).
So there is exactly one non-intersecting path system: Ai → Ui → Vi → Bi for all i. Thus det(M) is just the weight of this path system , which is the product of weights of all the edges: phi(x1)*phi(x2)*...*phi(xn), QED.
Edit: Changed gcd(i,j) to gcd(xi,xj), which is what I meant.
(courtesy of artofproblemsolving.com)