[math-fun] Wilson's grid problem
D Wilson: Let G1 = Z^2 be the grid of integer points in the plane R^2. Let G2 be the grid of points in R^2 gotten by rotating G1 by 45 degrees about the origin. What is the smallest c for which there exists bijection f: G1 <--> G2 with |P-f(P)| <= c for all P? WDS: It is superior to consider general Lp norm. Wilson chose the p=infinity norm, but L1, L2, whatever. It also is superior to consider general rotation and translation of G2, not just "translate by (0,0) and rotate by 45 degrees." If we restrict to some finite ball containing N points of G1 and N of G2, then using any Lp norm the optimum solution can be found algorithmically by: Solve a graph min-weight matching problem on the complete bipartite graph with N red and N blue vertices, edge costs are pth powers of distances. This will run in time polynomial in N [in fact O(N^2.5) or less, I believe with Dinic algorithm?]. (Actually p=infinity requires "bottleneck matching" not usual sum-of-weights matching, a slight extra programming hassle -- you make the weights infinite if >threshold, and 1 if <threshold, ask if min-weight matching has finite weight, do outer binary search to find the min allowable threshold. It is possible to combine the binary search with the matching algorithm in such a way no overhead is paid. This is all known.) Re some earlier posters muttering about "fundamental domains," octagons, and so on, I do not understand what they meant. It seems to me, sqrt(2) is irrational. Therefore, there is no domain tiling the plane by translation, that works for both G1 and G2 simultaneously. And there is no octagon that tiles the plane. And there is no 2D crystal group with 8-fold symmetry. Here is a SIMPLER PROBLEM than Wilson's, but I think very rich and of great interest: consider an infinite "slab" (rectangle of width 1, infinite in 1 direction but not bi-infinite). Place it on the grid Z^2 in some generic rotated and translated way. Let F(x) then be the number of grid points lying within distance x of the end of the rectangle. Obviously F(x) is asymptotic to x. The question is what is the error term. If we could prove the additive error is bounded by a constant, that would immediately solve Wilson's problem in the sense of proving his c is finite. (It would not find the minimum c, but would prove it is finite.) It might be that quadratic irrationals (as in Wilson's original problem) behave better than general irrational numbers. F(x) is the counting function for a "1 dimensional quasicrystal." This also is a counting version of classic diophantine approximation problem. So that is 3 reasons why F(x) should be important. A related but harder problem is "Gauss's circle problem" of counting the grid points in the area-A circle centered at (0,0). Obviously this count is asymptotic to A. But what is the error term? k1*A^(1/4) <= |count - A| <= k2*A^(131/416) for positive constants k1 and k2, is the best currently known result; these exponents are 0.25 and 0.314904. Returning to our F(x) problem, The points within the slab can be viewed as the corners of an "infinite stairstep." Whenever the next stairstep would have been outside the slab, you take two steps up, not 1 (or whatever) to correct for that. You never get more than a constant distance outside the slab that you need to correct. There is an infinite sequence of bounded integers (the step-type sequence) that thus arises from any irrational number. For quadratic irrational slopes these sequences have nicer properties than for general irrational slopes. (This also indicates connection to the problem of "pixelized stairstep" approximations to lines, in computer graphics, e.g. see Hanna Uscka-Wehlou: Digital lines with irrational slopes, Theoretical Computer Science 377,1-3 (May 2007) 157-169 http://www.sciencedirect.com/science/article/pii/S0304397507001181 .) For quadratic irrational line slopes these stairstep sequences obey some kind of "approximate self similarity" property. That is, if you hop along a distance corresponding to a best rational approximation to the quadratic approximation, and restart from there, then you are going to get the same sequence back again for quite a while, in fact it should be the same sequence up to some bounded number of edits. And then for quadratic irrationals since they have periodic continued fraction expansion, the best approximants form an exponential sequence roughly (like the fibonacci ratios for golden ratio) which means this "self similarity" works at all scales. Edward T.H. Wang: On Double-Free Sets of Integers, Ars Combinatorica 28 (1989) 97-100 considered one such sequence (I think?) and showed the |error| was bounded by O(logX). See http://mathworld.wolfram.com/Double-FreeSet.html . I may be confused. OEIS and this do not discuss any connection of this to quasicrystals and irrational numbers, and does not seem to explicitly discuss any kind of "stairstep sequence for irrational number" but Wang's sequence clearly is connected to the golden ratio and/or sqrt(2). Anyhow, I think in view of the self similarity thing, log(X) error behavior makes sense and is presumably what one should conjecture is the answer for any quadratic irrational slope in my F(x) error problem. So... I conjecture that whenever the slope is quadratic irrational, |F(X)-X| = O(logX). That conjecture would solve Wilson's original problem but with a logarithmically infinite c, that is, the max distance between a point of G1 and its mate in G2 (within ball of radius R) can be upper bounded by O(logR). I am confident stronger results are true, because Peter W. Shor showed if G2 is random points in an RxR square, then the max distance needed in a matching of G2 to the grid points G1 in same square, is O( (logR)^(3/4) ) with high probability. Wilson's problem must have a better upper bound than this. P W Shor: The average case analysis of some on line algorithms for bin packing, Combinatorica 6 (1986) 179-200. T Leighton & P Shor: Tight bounds for minimax grid matching with applications to the average case analysis of algorithms, Combinatorica 9 (1989) 161-187. About "digital lines," if only the pixels corresponding to the points in the slab in my F(x) problem, were colored, then you would draw a line with the correct brightness (i.e. brightness essentially invariant under generic rotations). This is in contrast to every(?) graphics program I ever saw, which always draws lines in a way whose brightness is NOT invariant under rotations. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
A hierarchical strategy for solving Wilson grid problem in Lp norms with p finite: Slice up the plane using a square grid of side L. Within each grid square, use the best G1-G2 matching. The result will leave unmatched, up to N points per square, where N>0 if the number of points of G1 in that square is unequal to the number of G2 points, and N=O(L) is easy to see. Now, erase all the matched points from consideration. Do it again using grid of side sqrt(L) times larger. Keep going in this way. Intuitively speaking each stage in this process gets rid of all but a fraction O(1/L) of the unmatched points, and increases the length scale by factor sqrt(L). Therefore, in any Lp norm, the total cost of the matching it produces, should be finite per point (geometric series converges). This suggests that in any Lp norm with p finite, Wilson's problem has a solution with finite c. This however does not solve the p=infinity case he wanted, and there will be arbitrarily far-separated mates produced (they just are rare). Actually, I think this "suggestion" could actually be turned into a "proof" because the grids at each stage can be randomly translated, and then the unmatched points counting bound will necessarily hold in expectation at each stage, and hence there must exist translations which do better than expectation, and hence there must exist suitable scaled and translated grids that make this argument work. I have not worked thru the details of that, though.
Oho, in this paper: Kinjal Basu, Art B. Owen: Low discrepancy constructions in the triangle http://arxiv.org/abs/1403.2649 it is shown in theorem 5 that in any integer lattice rotated by an angle with quadratic-irrational tangent, the number N of lattice points in a square of side L, obeys |N - L^2| = O( logN ). Their theorem is based on thm1 in WWL Chen and G Travaglini: Discrepancy with respect to convex polygons, J of Complexity 23,4-6 (2007) 662-672. https://rutherglen.science.mq.edu.au/wchen/researchfolder/prj14.pdf Excellent. This should be highly useful for Wilson's problem. It also demonstrates that my F(x) problem about "digital lines", has logarithmic error bound |F(X)-X| = O(logX) proving the conjecture I'd made, in the case of lines with quadratic-irrational slope. FInally, I remark about the "hierarchical solution method" I'd proposed for Wilson problem, as I said, it did not work in Linfinity norm, only in Lp norms with p finite. But it occurs to me that a modification of the method looks suitable for Linfinity norm. Namely, at some large scale L, you do not just stupidly draw matchup lines long distance from A to B. Instead, you find the least cost "alternating path" from A to B (meaning containing edges alternately not in, and in, the set of matchup line segments drawn so far) and switch it, i.e. make the line segments previously used, be not used, and vice versa. ("Cost" is the length of the longest edge thus introduced.) This approach plausibly will solve Wilson's problem with finite c, or very slow-growing c. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
On May 28, 2015, at 10:36 AM, Warren D Smith <warren.wds@gmail.com> wrote:
Re some earlier posters muttering about "fundamental domains," octagons, and so on, I do not understand what they meant. It seems to me, sqrt(2) is irrational. Therefore, there is no domain tiling the plane by translation, that works for both G1 and G2 simultaneously. And there is no octagon that tiles the plane. And there is no 2D crystal group with 8-fold symmetry.
Take a look at this: http://arxiv.org/pdf/1305.1798.pdf Figure 4 shows such a bijection-generating fundamental domain. The diameter is given in equation (1), which, after you divide by 2, gives the bound 0.92 … on c (for the L_infinity norm). This is actually a very good bound, considering the fact that 1/sqrt(2) = 0.707 is a lower bound. Exercise: Prove that c >= 1/sqrt(2). -Veit
Veit Elser Take a look at this: http://arxiv.org/pdf/1305.1798.pdf Figure 4 shows such a bijection-generating fundamental domain. The diameter is given in equation (1), which, after you divide by 2, gives the bound 0.92 ... on c (for the L_infinity norm). This is actually a very good bound, considering the fact that 1/sqrt(2) = 0.707 is a lower bound. Exercise: Prove that c >= 1/sqrt(2). WDS: Wow!! Well, this is not an "octagon", it is a very strange fractalish set, but it does have 8-way symmetry, and it tiles the plane, and it has bounded diameter, so I think Veit is correct. That's amazing!!! However, before you get too excited, note this solution is very special to Wilson's specific problem, and will not solve the general-rotation, general-translation version of it. Re VE's exercise, the usual square grid with square-centers G1 will necessarily contain some squares containing zero members of G2. (Expected membership=1, but nonzero variance.) Hence c>1/2. In fact, a square with side s arbitrarily near sqrt(2) will be empty and will be translatable to anyplace mod G2 with arbitrarily small error, thus proving c>=sqrt(1/2).
So the current state of the art is that the minimum possible c is between 0.707... and 0.92... ? I wonder if a computer search on a reasonably-sized piece of Z^2 could give any insights. Also: having settled on a bijection F, make the following visual aid: show the points of Z^2, with an edge drawn between points P and Q if F(P) and F(Q) are adjacent in *their* grid. On Thu, May 28, 2015 at 2:44 PM, Warren D Smith <warren.wds@gmail.com> wrote:
Veit Elser Take a look at this: http://arxiv.org/pdf/1305.1798.pdf Figure 4 shows such a bijection-generating fundamental domain. The diameter is given in equation (1), which, after you divide by 2, gives the bound 0.92 ... on c (for the L_infinity norm). This is actually a very good bound, considering the fact that 1/sqrt(2) = 0.707 is a lower bound. Exercise: Prove that c >= 1/sqrt(2).
WDS: Wow!! Well, this is not an "octagon", it is a very strange fractalish set, but it does have 8-way symmetry, and it tiles the plane, and it has bounded diameter, so I think Veit is correct. That's amazing!!!
However, before you get too excited, note this solution is very special to Wilson's specific problem, and will not solve the general-rotation, general-translation version of it.
Re VE's exercise, the usual square grid with square-centers G1 will necessarily contain some squares containing zero members of G2. (Expected membership=1, but nonzero variance.) Hence c>1/2. In fact, a square with side s arbitrarily near sqrt(2) will be empty and will be translatable to anyplace mod G2 with arbitrarily small error, thus proving c>=sqrt(1/2).
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I can give a slightly better lower bound than v2/2. Again, let G1 be the grid Z^2 in R^2. Let G3 be G1 translated by (1/2, 0), then rotated 45° The two points of G3 nearest the origin O are A = (x, x) and B = (-x, -x), where x = v2/4. Consider a bijection f:G3 <=> G1. We must have either f(A) != O or f(B) != O. If f(A) != O, the closest possible point is f(A) = (1, 0) or f(A) = (0, 1). Either gives |A-f(A)| = d = v(5-2v2)/2 = .7368128+ By symmetry, if f(B) != O, |B -f(B)| = d as well. I claim that for the original G1 and G2, we can find a point P of G1 such that the closest points of G2 to P are arbitrarily near P+A and P+B. We have either f(P+A) = P or f(P+B) = P. If f(P+A) = P, then |P+B - f(P+B)| is arbitrarily close to d. Similarly If f(P+B) = P, then |P+A - f(P+A)| is arbitrarily close to d. This means d = v(5-2v2)/2 = .7368128+ is a lower bound of the required distance, slightly better than v2/2 = 0.7071067+
For s in [0,1], define an s-median of a triangle (ABC in counterclockwise order) from vertex A to be the line segment connecting A to the point P of the opposite side BC such that BP : PC = s : (1-s) . (E.g., an ordinary median is a (1/2)-median.) A / \ / \ / \ / \ / \ B------P---------C Old math puzzle: Suppose we draw all three s-medians of an equilateral triangle ABC, where s = 1/3. Let delta be the triangle bounded by segments of the three s-medians. Find the ratio area(delta) / area(ABC). New math puzzle: Suppose we draw the r-, s- and t-medians of an equilateral triangle ABC for r, s, t in [0,1], again assuming ABC go counterclockwise around the perimeter. Let delta be the triangle bounded by segments of the three "medians". Find the ratio area(delta) / area(ABC) . ——Dan
Ratios of lengths and ratios of areas are invariant under affine transformations, so the answer should hold for arbitrary triangles, not just equilateral ones. -- Gene From: Dan Asimov <asimov@msri.org> To: math-fun <math-fun@mailman.xmission.com> Sent: Friday, May 29, 2015 9:10 AM Subject: [math-fun] Triangle puzzle For s in [0,1], define an s-median of a triangle (ABC in counterclockwise order) from vertex A to be the line segment connecting A to the point P of the opposite side BC such that BP : PC = s : (1-s) . (E.g., an ordinary median is a (1/2)-median.) A / \ / \ / \ / \ / \ B------P---------C Old math puzzle: Suppose we draw all three s-medians of an equilateral triangle ABC, where s = 1/3. Let delta be the triangle bounded by segments of the three s-medians. Find the ratio area(delta) / area(ABC). New math puzzle: Suppose we draw the r-, s- and t-medians of an equilateral triangle ABC for r, s, t in [0,1], again assuming ABC go counterclockwise around the perimeter. Let delta be the triangle bounded by segments of the three "medians". Find the ratio area(delta) / area(ABC) . ——Dan
Let the triangle be the intersection of the plane x+y+z=1 with the positive octant, so that its vertices are X=(1,0,0), Y=(0,1,0), Z=(0,0,1). The r-median joins X to R=(0,r,1-r). The s-median joins Y to S=(1-s,0,s). The t-median joins Z to T=(t,1-t,0). The r-median consists of the convex linear combination XR = (1-u)X + uR. The s-median consists of the convex linear combination YS = (1-v)Y + vS. Their intersection C = XR.YS can be found with a little algebra. C = XR.YS = ((1-r)(1-s), rs, (1-r)s) / (1-r+rs). By cyclically permuting both (r,s,t) and the coordinates (x,y,z) we also have A = YS.ZT = ((1-s)t, (1-s)(1-t), st) / (1-s+st), B = ZT.XR = (tr, (1-t)r, (1-t)(1-r)) / (1-t+tr). The 3-space linear transformation L that takes X to A, Y to B, and Z to C is the matrix whose columns are the coordinates of A, B, and C The problem asks for Area(ABC)/Area(XYZ). Since the volume of a pyramid is (1/3)base*height, this equals Vol(OABC)/Vol(OXYZ). But this latter quantity equals det(L). Cranking out the determinant, we get for the area ratio a fraction with numerator ((1-r)(1-s)(1-t) - rst)^2, and denominator (1-r+rs)(1-s+st)(1-t+tr). -- Gene From: Eugene Salamin via math-fun <math-fun@mailman.xmission.com> To: math-fun <math-fun@mailman.xmission.com> Sent: Friday, May 29, 2015 11:06 AM Subject: Re: [math-fun] Triangle puzzle Ratios of lengths and ratios of areas are invariant under affine transformations, so the answer should hold for arbitrary triangles, not just equilateral ones. -- Gene From: Dan Asimov <asimov@msri.org> To: math-fun <math-fun@mailman.xmission.com> Sent: Friday, May 29, 2015 9:10 AM Subject: [math-fun] Triangle puzzle For s in [0,1], define an s-median of a triangle (ABC in counterclockwise order) from vertex A to be the line segment connecting A to the point P of the opposite side BC such that BP : PC = s : (1-s) . (E.g., an ordinary median is a (1/2)-median.) A / \ / \ / \ / \ / \ B------P---------C Old math puzzle: Suppose we draw all three s-medians of an equilateral triangle ABC, where s = 1/3. Let delta be the triangle bounded by segments of the three s-medians. Find the ratio area(delta) / area(ABC). New math puzzle: Suppose we draw the r-, s- and t-medians of an equilateral triangle ABC for r, s, t in [0,1], again assuming ABC go counterclockwise around the perimeter. Let delta be the triangle bounded by segments of the three "medians". Find the ratio area(delta) / area(ABC) . ——Dan
Yes! Same as what I got. But with a much shrewder and concise derivation. ((( Because of the invariance of area ratios, and length ratios along any single line, I had used a 1, 1, sqrt(2) right triangle to find the intersection points of the r-, s-, and t-medians, and then used a determinant formula to get the area of the central triangle. Way hairier expressions involved. ))) The formula where r = s = t is g(s), where g(s) := f(s,s,s) = (1 - 2s)^2 / (s^2 - s + 1) And ask some questions whose answer I have no idea about so far: * Why is g(s) the ratio of two quadratic polynomials? * Why is f(r,s,t) the ratio of two sextic polynomials? * Is it even obvious a priori that the formulas should be rational functions? Also: It may be amusing in g(s) to take s = 1/N, N = 1,2,3,.... One gets an interesting sequence of fractions in lowest terms: N: 1 2 3 4 5 6 7 8 9 10 --------------------------------------------------------------------------------------- g(1/N): 1 0 1/7 4/13 3/7 16/31 25/43 12/19 49/73 64/91 N: 11 12 13 14 15 16 17 18 19 20 --------------------------------------------------------------------------------------- g(1/N): 27/37 100/133 121/157 48/61 169/211 196/241 75/91 256/307 289/343 108/127 . . . Seems to me the denominators are more often prime numbers than most fractions in lowest terms. Is this true as N -> oo ??? Which, free associating, makes me wonder: ----- PROBLEM: Find an asymptotic expression for the frequency of primes among denominators of fractions — say as we take all fractions K/L that are already in lowest terms, with sqrt(K^2 + L^2) <= R, as R -> oo. ----- ——Dan
On May 30, 2015, at 11:45 AM, Eugene Salamin via math-fun <math-fun@mailman.xmission.com> wrote:
Let the triangle be the intersection of the plane x+y+z=1 with the positive octant, so that its vertices are X=(1,0,0), Y=(0,1,0), Z=(0,0,1). The r-median joins X to R=(0,r,1-r). The s-median joins Y to S=(1-s,0,s). The t-median joins Z to T=(t,1-t,0). The r-median consists of the convex linear combination XR = (1-u)X + uR. The s-median consists of the convex linear combination YS = (1-v)Y + vS. Their intersection C = XR.YS can be found with a little algebra. C = XR.YS = ((1-r)(1-s), rs, (1-r)s) / (1-r+rs). By cyclically permuting both (r,s,t) and the coordinates (x,y,z) we also have A = YS.ZT = ((1-s)t, (1-s)(1-t), st) / (1-s+st), B = ZT.XR = (tr, (1-t)r, (1-t)(1-r)) / (1-t+tr). The 3-space linear transformation L that takes X to A, Y to B, and Z to C is the matrix whose columns are the coordinates of A, B, and C
The problem asks for Area(ABC)/Area(XYZ). Since the volume of a pyramid is (1/3)base*height, this equals Vol(OABC)/Vol(OXYZ). But this latter quantity equals det(L). Cranking out the determinant, we get for the area ratio a fraction with numerator ((1-r)(1-s)(1-t) - rst)^2, and denominator (1-r+rs)(1-s+st)(1-t+tr).
-- Gene
From: Eugene Salamin via math-fun <math-fun@mailman.xmission.com> To: math-fun <math-fun@mailman.xmission.com> Sent: Friday, May 29, 2015 11:06 AM Subject: Re: [math-fun] Triangle puzzle
Ratios of lengths and ratios of areas are invariant under affine transformations, so the answer should hold for arbitrary triangles, not just equilateral ones. -- Gene
From: Dan Asimov <asimov@msri.org> To: math-fun <math-fun@mailman.xmission.com> Sent: Friday, May 29, 2015 9:10 AM Subject: [math-fun] Triangle puzzle
For s in [0,1], define an s-median of a triangle (ABC in counterclockwise order) from vertex A to be the line segment connecting A to the point P of the opposite side BC such that
BP : PC = s : (1-s) .
(E.g., an ordinary median is a (1/2)-median.)
A / \ / \ / \ / \ / \ B------P---------C
Old math puzzle: Suppose we draw all three s-medians of an equilateral triangle ABC, where s = 1/3. Let delta be the triangle bounded by segments of the three s-medians. Find the ratio
area(delta) / area(ABC).
New math puzzle: Suppose we draw the r-, s- and t-medians of an equilateral triangle ABC for r, s, t in [0,1], again assuming ABC go counterclockwise around the perimeter. Let delta be the triangle bounded by segments of the three "medians". Find the ratio
area(delta) / area(ABC) .
——Dan
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Neat solution, Gene! [And thanks for explaining what the problem was ...] On 5/30/15, Dan Asimov <dasimov@earthlink.net> wrote:
... The formula where r = s = t is g(s), where
g(s) := f(s,s,s) = (1 - 2s)^2 / (s^2 - s + 1)
And ask some questions whose answer I have no idea about so far:
* Why is g(s) the ratio of two quadratic polynomials?
* Why is f(r,s,t) the ratio of two sextic polynomials?
* Is it even obvious a priori that the formulas should be rational functions? ...
In case r = s = t and equilateral, (s^2 - s + 1) happens to equal the squared length of the s-median. WFL
One more consequence of this formula is that the condition for the medians to be concurrent, that the inner triangle have zero area, is that (1-r)(1-s)(1-t) = rst. Continuing in the notation of my earlier post, we can prescribe the point of concurrency as P = (a,b,c), a+b+c=1. Then XP intersects YZ at (0,b/(1-a),c/(1-a)) = (0,r,1-r). With cyclic permutation we have, r = b/(1-a), s = c/(1-b), t = a/(1-c). -- Gene From: Dan Asimov <dasimov@earthlink.net> To: Eugene Salamin <gene_salamin@yahoo.com>; math-fun <math-fun@mailman.xmission.com> Sent: Saturday, May 30, 2015 12:54 PM Subject: Re: [math-fun] Triangle puzzle Yes! Same as what I got. But with a much shrewder and concise derivation. ((( Because of the invariance of area ratios, and length ratios along any single line, I had used a 1, 1, sqrt(2) right triangle to find the intersection points of the r-, s-, and t-medians, and then used a determinant formula to get the area of the central triangle. Way hairier expressions involved. ))) The formula where r = s = t is g(s), where g(s) := f(s,s,s) = (1 - 2s)^2 / (s^2 - s + 1) And ask some questions whose answer I have no idea about so far: * Why is g(s) the ratio of two quadratic polynomials? * Why is f(r,s,t) the ratio of two sextic polynomials? * Is it even obvious a priori that the formulas should be rational functions? Also: It may be amusing in g(s) to take s = 1/N, N = 1,2,3,.... One gets an interesting sequence of fractions in lowest terms: N: 1 2 3 4 5 6 7 8 9 10 --------------------------------------------------------------------------------------- g(1/N): 1 0 1/7 4/13 3/7 16/31 25/43 12/19 49/73 64/91 N: 11 12 13 14 15 16 17 18 19 20 --------------------------------------------------------------------------------------- g(1/N): 27/37 100/133 121/157 48/61 169/211 196/241 75/91 256/307 289/343 108/127 . . . Seems to me the denominators are more often prime numbers than most fractions in lowest terms. Is this true as N -> oo ??? Which, free associating, makes me wonder: ----- PROBLEM: Find an asymptotic expression for the frequency of primes among denominators of fractions — say as we take all fractions K/L that are already in lowest terms, with sqrt(K^2 + L^2) <= R, as R -> oo. ----- ——Dan
On May 30, 2015, at 11:45 AM, Eugene Salamin via math-fun <math-fun@mailman.xmission.com> wrote:
Let the triangle be the intersection of the plane x+y+z=1 with the positive octant, so that its vertices are X=(1,0,0), Y=(0,1,0), Z=(0,0,1). The r-median joins X to R=(0,r,1-r). The s-median joins Y to S=(1-s,0,s). The t-median joins Z to T=(t,1-t,0). The r-median consists of the convex linear combination XR = (1-u)X + uR. The s-median consists of the convex linear combination YS = (1-v)Y + vS. Their intersection C = XR.YS can be found with a little algebra. C = XR.YS = ((1-r)(1-s), rs, (1-r)s) / (1-r+rs). By cyclically permuting both (r,s,t) and the coordinates (x,y,z) we also have A = YS.ZT = ((1-s)t, (1-s)(1-t), st) / (1-s+st), B = ZT.XR = (tr, (1-t)r, (1-t)(1-r)) / (1-t+tr). The 3-space linear transformation L that takes X to A, Y to B, and Z to C is the matrix whose columns are the coordinates of A, B, and C
The problem asks for Area(ABC)/Area(XYZ). Since the volume of a pyramid is (1/3)base*height, this equals Vol(OABC)/Vol(OXYZ). But this latter quantity equals det(L). Cranking out the determinant, we get for the area ratio a fraction with numerator ((1-r)(1-s)(1-t) - rst)^2, and denominator (1-r+rs)(1-s+st)(1-t+tr).
-- Gene
From: Eugene Salamin via math-fun <math-fun@mailman.xmission.com> To: math-fun <math-fun@mailman.xmission.com> Sent: Friday, May 29, 2015 11:06 AM Subject: Re: [math-fun] Triangle puzzle
Ratios of lengths and ratios of areas are invariant under affine transformations, so the answer should hold for arbitrary triangles, not just equilateral ones. -- Gene
From: Dan Asimov <asimov@msri.org> To: math-fun <math-fun@mailman.xmission.com> Sent: Friday, May 29, 2015 9:10 AM Subject: [math-fun] Triangle puzzle For s in [0,1], define an s-median of a triangle (ABC in counterclockwise order) from vertex A to be the line segment connecting A to the point P of the opposite side BC such that
BP : PC = s : (1-s) .
(E.g., an ordinary median is a (1/2)-median.)
A / \ / \ / \ / \ / \ B------P---------C
Old math puzzle: Suppose we draw all three s-medians of an equilateral triangle ABC, where s = 1/3. Let delta be the triangle bounded by segments of the three s-medians. Find the ratio
area(delta) / area(ABC).
New math puzzle: Suppose we draw the r-, s- and t-medians of an equilateral triangle ABC for r, s, t in [0,1], again assuming ABC go counterclockwise around the perimeter. Let delta be the triangle bounded by segments of the three "medians". Find the ratio
area(delta) / area(ABC) .
——Dan
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Nice point, Gene. Also, I hadn't been sure of the symmetry group of f(r,s,t) before getting its formula. Was it generated by the cyclic permutation (r, s, t) -> (s, t, r) and the involution (r, s, t) -> (1-r, 1-s, 1-t) ??? No. Only by the cyclic permutation and the involution (r, s, t) -> (1-s, 1-r, 1-t), both of which preserve orientation of [0,1]^3. —-Dan
On May 31, 2015, at 11:19 AM, Eugene Salamin via math-fun <math-fun@mailman.xmission.com> wrote:
One more consequence of this formula is that the condition for the medians to be concurrent, that the inner triangle have zero area, is that (1-r)(1-s)(1-t) = rst.
Continuing in the notation of my earlier post, we can prescribe the point of concurrency as P = (a,b,c), a+b+c=1.
Then XP intersects YZ at (0,b/(1-a),c/(1-a)) = (0,r,1-r).
With cyclic permutation we have, r = b/(1-a), s = c/(1-b), t = a/(1-c). -- Gene
From: Dan Asimov <dasimov@earthlink.net>
Yes! Same as what I got.
But with a much shrewder and concise derivation.
((( Because of the invariance of area ratios, and length ratios along any single line, I had used a 1, 1, sqrt(2) right triangle to find the intersection points of the r-, s-, and t-medians, and then used a determinant formula to get the area of the central triangle. Way hairier expressions involved. )))
The formula where r = s = t is g(s), where
g(s) := f(s,s,s) = (1 - 2s)^2 / (s^2 - s + 1)
And ask some questions whose answer I have no idea about so far:
* Why is g(s) the ratio of two quadratic polynomials?
* Why is f(r,s,t) the ratio of two sextic polynomials?
* Is it even obvious a priori that the formulas should be rational functions?
Also: It may be amusing in g(s) to take
s = 1/N, N = 1,2,3,....
One gets an interesting sequence of fractions in lowest terms:
N: 1 2 3 4 5 6 7 8 9 10 --------------------------------------------------------------------------------------- g(1/N): 1 0 1/7 4/13 3/7 16/31 25/43 12/19 49/73 64/91
N: 11 12 13 14 15 16 17 18 19 20 --------------------------------------------------------------------------------------- g(1/N): 27/37 100/133 121/157 48/61 169/211 196/241 75/91 256/307 289/343 108/127
. . .
Seems to me the denominators are more often prime numbers than most fractions in lowest terms.
Is this true as N -> oo ???
Which, free associating, makes me wonder:
----- PROBLEM: Find an asymptotic expression for the frequency of primes among denominators of fractions — say as we take all fractions K/L that are already in lowest terms, with
sqrt(K^2 + L^2) <= R,
as R -> oo. -----
——Dan
On May 30, 2015, at 11:45 AM, Eugene Salamin via math-fun <math-fun@mailman.xmission.com> wrote:
Let the triangle be the intersection of the plane x+y+z=1 with the positive octant, so that its vertices are X=(1,0,0), Y=(0,1,0), Z=(0,0,1). The r-median joins X to R=(0,r,1-r). The s-median joins Y to S=(1-s,0,s). The t-median joins Z to T=(t,1-t,0). The r-median consists of the convex linear combination XR = (1-u)X + uR. The s-median consists of the convex linear combination YS = (1-v)Y + vS. Their intersection C = XR.YS can be found with a little algebra. C = XR.YS = ((1-r)(1-s), rs, (1-r)s) / (1-r+rs). By cyclically permuting both (r,s,t) and the coordinates (x,y,z) we also have A = YS.ZT = ((1-s)t, (1-s)(1-t), st) / (1-s+st), B = ZT.XR = (tr, (1-t)r, (1-t)(1-r)) / (1-t+tr). The 3-space linear transformation L that takes X to A, Y to B, and Z to C is the matrix whose columns are the coordinates of A, B, and C
The problem asks for Area(ABC)/Area(XYZ). Since the volume of a pyramid is (1/3)base*height, this equals Vol(OABC)/Vol(OXYZ). But this latter quantity equals det(L). Cranking out the determinant, we get for the area ratio a fraction with numerator ((1-r)(1-s)(1-t) - rst)^2, and denominator (1-r+rs)(1-s+st)(1-t+tr).
-- Gene
From: Eugene Salamin via math-fun <math-fun@mailman.xmission.com> To: math-fun <math-fun@mailman.xmission.com> Sent: Friday, May 29, 2015 11:06 AM Subject: Re: [math-fun] Triangle puzzle
Ratios of lengths and ratios of areas are invariant under affine transformations, so the answer should hold for arbitrary triangles, not just equilateral ones. -- Gene
From: Dan Asimov <asimov@msri.org> To: math-fun <math-fun@mailman.xmission.com> Sent: Friday, May 29, 2015 9:10 AM Subject: [math-fun] Triangle puzzle
For s in [0,1], define an s-median of a triangle (ABC in counterclockwise order) from vertex A to be the line segment connecting A to the point P of the opposite side BC such that
BP : PC = s : (1-s) .
(E.g., an ordinary median is a (1/2)-median.)
A / \ / \ / \ / \ / \ B------P---------C
Old math puzzle: Suppose we draw all three s-medians of an equilateral triangle ABC, where s = 1/3. Let delta be the triangle bounded by segments of the three s-medians. Find the ratio
area(delta) / area(ABC).
New math puzzle: Suppose we draw the r-, s- and t-medians of an equilateral triangle ABC for r, s, t in [0,1], again assuming ABC go counterclockwise around the perimeter. Let delta be the triangle bounded by segments of the three "medians". Find the ratio
area(delta) / area(ABC) .
——Dan
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (8)
-
Allan Wechsler -
Dan Asimov -
Dan Asimov -
David Wilson -
Eugene Salamin -
Fred Lunnon -
Veit Elser -
Warren D Smith