Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
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, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
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, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
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, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
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, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
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, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
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, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
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, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
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, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
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, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
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, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
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, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
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, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
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, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
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, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
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, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
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.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
You can reference a table key name with a space in it like:
local tbl={}
tbl["P1 A"]="true"
Or whatever. I didn't test this. But any table key name can be used as a string inside square brackets.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
p4wn3r wrote:
Anyway, the problem is: come up with an algorithm, better than plain brute force, to find two single digit 2x2 matrices whose product is obtained by concatenating the base 10 digits of each element.
Note: I will be using the notation [a b / c d] to mean the 2x2 matrix
We want to find A = [a b / c d] and B = [e f / g h] such that AB = [10a+e 10b+f / 10c+g 10d+h], with a,b,c,d from 1 to 9 and e,f,g,h from 0 to 9. Note that AB-10A-B = [0 0 / 0 0], and so by adding 10I to each side (where I is the identity matrix [1 0 / 0 1]) and factoring, we have:
(A-I)(B-10I)=10I
Letting A'=A-I and B'=B-10I we have A'B'=10I. It follows that det(A') must divide 100. Furthermore, let A'= [a' b / c d'], where a'=a-1 and d'=d-1. Then B' is given by:
B' = A'-1 10I = (10/det(A')) [d' -b / -c a']
Note that the signs within B' must be [- + / + -] by restriction (it is impossible for them to be 0 and satisfy the restrictions on e,f,g,h), and so det(A')=a'd'-bc must be negative. Let k = -det(A'). Then we can solve for everything as follows:
a=a'+1 , b=b , c=c , d=d'+1 , e = 10 - 10d'/k , f = 10b/k , g = 10c/k , h = 10 - 10a'/k
Note that since det(A')det(B')=det(10I)=100, we have that k=bc-a'd' must be a positive divisor of 100. This restricts the possibilities greatly and now it is possible to enumerate everything by hand.
It turns out that k can only be 5, 10 or 20, and bc must be greater than k. Furthermore, if k=5, all of b,c,a',d' are between 1 and 4. If k=20, all of b,c,a',d' must be even. Finally, none of b,c,a'd' can be 0, and a' and d' cannot be 9. Because b and c are interchangeable, as well as a' and d', we classify the following according to b>=c and a'>=d', with up to four possibilities for each:
That makes a nice 100 solutions to this problem.
I assume the 101st one that Masterjun is referring to is [0 0 / 0 0][0 0 / 0 0]. But that's not very interesting now, is it.
By the way, p4wn3r mentioned that some of them have the same matrices A and B. There are 20 of them in fact, given by the 5 rows where a'+d'=9.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Here's a diagram showing what the circle looks like:
We only need to consider when x>0, so the curves we need to intersect are:
y=x3
x2+(y-r)2=r2
The intersection point between the two functions is given as a polynomial equation: x6-2rx3+x2=0
Furthermore, there is a multiple zero at that point. So the x-derivative must also be 0: 6x5-6rx2+2x=0
After factoring x2 and 2x, respectively, and removing them (since x>0), we must solve the system of equations:
x4-2rx+1=0
3x4-3rx+1=0
Multiplying the first equation by 3 and subtracting the two equations results in the equation 3rx=2. Plugging that into the second equation and solving gives x=3-1/4 (about 0.759836), and r=2*3-3/4 (about 0.877383). This gives an area of the circle as pi*4*sqrt(3)/9 (about 2.418399).
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
I heard about this game early on (as being possibly the best Uzebox game) when Uzebox was first released in BizHawk.
Obviously it obviously looked like a nightmare to optimize. It's great that you got so many people interested in collaborating to make a TAS for this game. Also TASes on co-op modes are way more than twice as good as a TAS on a single-player mode.
I like this page.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
EZGames69 wrote:
When watching the single screen mode (as is with the temp encode I made), it's watchable for the most part. However when I watched this in emulator with 3D mode turned on, I quickly realized it ISNT watchable because you can't make out what you see in the hallways. I know that youtube has a feature that lets you turn off 3D mode, but unfortunately that isnt a feature in youtube mobile last time I checked. So I have to give this a meh in entertainment because of this.
Last time I checked, Youtube's 3D mode is trash. I don't have 3D glasses, so the only way I can try to see it is with cross-eye view, but I couldn't figure out how to enable it in Youtube or if it was even possible.
At least Bizhawk has cross-eye view there (you can set it in VirtualBoy -> Preferences... -> ThreeDeeMode -> SideBySide) but unless you're trained in cross-eye view it's kind of difficult to do sometimes, and even then who knows about the actual art quality of the game itself.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
I think there should be a program these days that is capable of stitching them together (and keeping them at 60fps). Maybe Avidemux? I normally just use AviSynth because I tend to do a lot of post processing.
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)
We want to find A = [a b / c d] and B = [e f / g h] such that AB = [10a+e 10b+f / 10c+g 10d+h], with a,b,c,d from 1 to 9 and e,f,g,h from 0 to 9. Note that AB-10A-B = [0 0 / 0 0], and so by adding 10I to each side (where I is the identity matrix [1 0 / 0 1]) and factoring, we have:
(A-I)(B-10I)=10I
Letting A'=A-I and B'=B-10I we have A'B'=10I. It follows that det(A') must divide 100. Furthermore, let A'= [a' b / c d'], where a'=a-1 and d'=d-1. Then B' is given by:
B' = A'-1 10I = (10/det(A')) [d' -b / -c a']
Note that the signs within B' must be [- + / + -] by restriction (it is impossible for them to be 0 and satisfy the restrictions on e,f,g,h), and so det(A')=a'd'-bc must be negative. Let k = -det(A'). Then we can solve for everything as follows:
a=a'+1 , b=b , c=c , d=d'+1 , e = 10 - 10d'/k , f = 10b/k , g = 10c/k , h = 10 - 10a'/k
Note that since det(A')det(B')=det(10I)=100, we have that k=bc-a'd' must be a positive divisor of 100. This restricts the possibilities greatly and now it is possible to enumerate everything by hand.
It turns out that k can only be 5, 10 or 20, and bc must be greater than k. Furthermore, if k=5, all of b,c,a',d' are between 1 and 4. If k=20, all of b,c,a',d' must be even. Finally, none of b,c,a'd' can be 0, and a' and d' cannot be 9. Because b and c are interchangeable, as well as a' and d', we classify the following according to b>=c and a'>=d', with up to four possibilities for each:
We only need to consider when x>0, so the curves we need to intersect are:
y=x3
x2+(y-r)2=r2
The intersection point between the two functions is given as a polynomial equation: x6-2rx3+x2=0
Furthermore, there is a multiple zero at that point. So the x-derivative must also be 0: 6x5-6rx2+2x=0
After factoring x2 and 2x, respectively, and removing them (since x>0), we must solve the system of equations:
x4-2rx+1=0
3x4-3rx+1=0
Multiplying the first equation by 3 and subtracting the two equations results in the equation 3rx=2. Plugging that into the second equation and solving gives x=3-1/4 (about 0.759836), and r=2*3-3/4 (about 0.877383). This gives an area of the circle as pi*4*sqrt(3)/9 (about 2.418399).