Archive

Archive for the ‘Geometry’ Category

Spherical triangles of area Pi

April 6, 2018 Leave a comment

Recently I stumbled upon this page and found out a very nice result:

If a spherical triangle has area \pi then four copies of it can tile the sphere.

Here we are talking about triangles on the unit sphere whose edges are geodesics. The above result is a simple consequence of the following facts:

  1. If a spherical triangle has angles \alpha,\beta,\gamma then its area is \alpha+\beta+\gamma-\pi. Therefore if a triangle has area \pi, then \alpha+\beta+\gamma = 2\pi.
  2. If ABC is a triangle of area \pi and D is obtained by symmetrizing A with respect to the midpoint of BC on the sphere, then DCB and ABC are congruent triangles.
  3. Using angles and the fact that on the sphere similar triangles are congruent, we obtain that the triangles ABC,BCD,CDA,DAC are all congruent.

Here are a few examples of such partitions:

Advertisements

Mesh a hollow sphere

April 5, 2018 Leave a comment

This is an interesting experiment I’ve done today and I’d like to share it. There are nice software out there which allow you to mesh regular surfaces, like the sphere, torus or other examples.

I needed something different: I wanted to mesh a sphere with a hole and an inner surface. This kind of surfaces may be useful for those who want to design objects for 3D printing. When using 3D printers, the cost is usually proportional to the volume of material used, since this also consumes impression time. If you manage to make a hollow object, the cost goes down immediately (as the resistance of the object…). However, to make a hole, you need to consider an inner parallel surface. I’ll not handle this here, since it’s more complicated. I’ll just mesh a hollow sphere.

I did this in Matlab using the nice library Distmesh, which is free and really easy to use. The whole difficulty was making a function whose zero level set is the hollow sphere. Recall that it is possible to find the union of two shapes using the minimum of two level set function and the intersection using the maximum. This is all that you need to understand what I did below. You can see the details in the Matlab code below.

function [p,t] = Hole_Spher_Mesh(mh)

  R = 0.5;
  r = 0.4;
  rh = 0.1;

  fh=@(p) sqrt(min(p(:,1).^2+p(:,2).^2,ones(size(p(:,1)))));
  fh=@(p) sqrt((p(:,1).^2+p(:,2).^2));
  [p,t]=distmeshsurface(@(x)fd(x,R,r,rh),@huniform,mh,[-1.1,-1.1,-1.1;1.1,1.1,1.1]);
  points = p';
  npt = prod(size(points))/3

clf
patch('Faces',t,'Vertices',p,'FaceColor',[0,0.7,0.9],'EdgeColor','none','FaceAlpha',0.5);

function res = fd(p,R,r,rh)

res1 = sqrt(sum(p.^2,2))-R;
res2 = (rh-sqrt(p(:,1).^2+p(:,2).^2));
res3 = p(:,3);
res2 = max(-res2,res3);
res4 = sqrt(sum(p.^2,2))-r;
res2 = min(res2,res4);
res = max(res1,-res2);

And here is the resulting surface for the parameter mh = 0.01 (if you put a higher precision computations will take longer).

HollowSphere

Romanian Masters in Mathematics contest – 2018

March 9, 2018 Leave a comment

Problem 1. Let {ABCD} be a cyclic quadrilateral an let {P} be a point on the side {AB.} The diagonals {AC} meets the segments {DP} at {Q.} The line through {P} parallel to {CD} mmets the extension of the side {CB} beyond {B} at {K.} The line through {Q} parallel to {BD} meets the extension of the side {CB} beyond {B} at {L.} Prove that the circumcircles of the triangles {BKP} and {CLQ} are tangent .

Problem 2. Determine whether there exist non-constant polynomials {P(x)} and {Q(x)} with real coefficients satisfying

\displaystyle P(x)^{10}+P(x)^9 = Q(x)^{21}+Q(x)^{20}.

Problem 3. Ann and Bob play a game on the edges of an infinite square grid, playing in turns. Ann plays the first move. A move consists of orienting any edge that has not yet been given an orientation. Bob wins if at any point a cycle has been created. Does Bob have a winning strategy?

Problem 4. Let {a,b,c,d} be positive integers such that {ad \neq bc} and {gcd(a,b,c,d)=1}. Let {S} be the set of values attained by {\gcd(an+b,cn+d)} as {n} runs through the positive integers. Show that {S} is the set of all positive divisors of some positive integer.

Problem 5. Let {n} be positive integer and fix {2n} distinct points on a circle. Determine the number of ways to connect the points with {n} arrows (oriented line segments) such that all of the following conditions hold:

  • each of the {2n} points is a startpoint or endpoint of an arrow;
  • no two arrows intersect;
  • there are no two arrows {\overrightarrow{AB}} and {\overrightarrow{CD}} such that {A}, {B}, {C} and {D} appear in clockwise order around the circle (not necessarily consecutively).

Problem 6. Fix a circle {\Gamma}, a line {\ell} to tangent {\Gamma}, and another circle {\Omega} disjoint from {\ell} such that {\Gamma} and {\Omega} lie on opposite sides of {\ell}. The tangents to {\Gamma} from a variable point {X} on {\Omega} meet {\ell} at {Y} and {Z}. Prove that, as {X} varies over {\Omega}, the circumcircle of {XYZ} is tangent to two fixed circles.

Source: Art of Problem Solving forums

Some quick ideas: For Problem 1 just consider the intersection of the circle {(BKP)} with the circle {(ABCD)}. You’ll notice immediately that this point belongs to the circle {(CLQ)}. Furthermore, there is a common tangent to the two circles at this point.

For Problem 2 we have {10\deg P = 21 \deg Q}. Eliminate the highest order term from both sides and look at the next one to get a contradiction.

Problem 4 becomes easy after noticing that if {q} divides {an+b} and {cn+d} then {q} divides {ad-bc}.

In Problem 5 try to prove that the choice of start points determines that of the endpoints. Then you have a simple combinatorial proof.

Problem 6 is interesting and official solutions use inversions. Those are quite nice, but it may be worthwhile to understand what happens in the non-inverted configuration.

I will come back to some of these problems in some future posts.

Regular tetrahedron – computing various quantities in terms of the side-length

February 2, 2018 Leave a comment

Sometimes one needs to find certain quantities related to the regular tetrahedron in {\Bbb{R}^3}, like volume, radius of the circumscribed sphere, radius of inscribed sphere, distance between opposite sides, etc. in terms of the side-length which we’ll note in the following with {a}. In the past I needed to find the angle under which every side is seen when looking from the center of the regular tetrahedron.

Here’s a trick which can help you find rather easily everything you need related to the regular tetrahedron: just embed it into a cube. We can see rather easily that when drawing certain diagonals of the faces of a cube, like in the figure below, we can recover a regular tetrahedron. Now it becomes rather easy to solve all questions above. We note that the ratio between the side of the cube (denoted by {\ell}) and the side of the embedded tetrahedron (denoted by {a}) is {\sqrt{2}}: {a = \ell \sqrt{2}}.

tetra_cube_1

Here are a few ideas:

1. Finding the volume of the tetrahedron in terms of its sides.

The volume of the cube is {\ell^3}. The volume of the tetrahedron can be obtained by cutting four corner pyramids with volumes {\ell^3/6} (recall that volume of a pyramid is (area of base) {\times} (height) {/3}). Therefore the volume of the regular tetrahedron is {2\ell^3/6 = l^3/3}. Replacing {\ell = a/\sqrt{2} } we get that the volume of the tetrahedron is {a^3/(6\sqrt{2})}.

2. Finding the circumradius {R}.

It is not difficult to see that the sphere passing through the vertices of the tetrahedron also passes through the vertices of the cube. Therefore its radius is a long diagonal of the cube divided by {2}. This gives {\ell \sqrt{3}/2}. Replacing {\ell=a/\sqrt{2}} we get that the circumradius is {R = a\sqrt{6}/4}.

3. Finding the inradius {r}.

Once we have the volume and the circumradius, finding the inradius is not that difficult, since the symmetry of the figure shows that {r+R = h}, where {h} is the distance from a vertex to the opposite face, also called the height. We can find the height from the formula of the volume (recalled above), and then find {r = h-R}. Also note that since the center of the tetrahedron is also the centroid, we must have {R=3r}, so we have another quick finish solution.

However, let’s use the cube to do this. We can choose a system of coordinates putting the origin at the center of the cube (and tetrahedron). Put the cube so that its vertices have coordinates {\pm \ell/2,\pm \ell/2,\pm \ell/2} and suppose that the tetrahedron corresponds to the vertices {A(\ell/2,\ell/2,\ell/2)}, {B(-\ell/2,-\ell/2,\ell/2)}, {C(\ell/2,-\ell/2,-\ell/2)}, {D(-\ell/2,\ell/2,-\ell/2)}. All we need to do is to compute the distance from the origin to the plane {(BCD)}. This is immediate if we know the equation of this plane. Fortunately, it is really easy to see that the coordinates of {B,C,D} verify {x+y+z+\ell/2 = 0} (if not, then note that the normal to {(B,C,D)} is the vector {(1,1,1)} and figure out the remaining translation constant). We know that if a plane is defined by the equation {ax+by+cz+d=0} then the distance from {(x_0,y_0,z_0)} to this plane is

\displaystyle \frac{|ax_0+by_0+cz_0+d|}{\sqrt{a^2+b^2+c^2}}.

Apply this to our problem and the distance from the origin to {(BCD)} becomes {\ell/(2\sqrt{3})}. Replace {\ell = a/\sqrt{2}} and we get {r = a/(2\sqrt{6})=a\sqrt{6}/12}.

4. Find distance between opposite sides.

This is particularly easy with the cube. The distance between the opposite sides is exactly the distance between two parallel faces of the cube and that is {\ell = a/\sqrt{2}}.

5. Find angle made by two rays connecting the center with vertices.

Use the coordinate system introduced in 3. and just compute the angle between vectors {\vec u = (\ell,\ell,\ell)} and {\vec v = (-\ell,-\ell,\ell)}, for example. If {\alpha} is the angle between {\vec u} and {\vec v} we get that

\displaystyle \cos \alpha = \frac{\langle \vec u,\vec v\rangle}{\|\vec u\| \|\vec v\|}=\frac{-\ell^2}{3\ell^2} = -\frac{1}{3}.

Therefore {\alpha = \arccos (-1/3)}.

Project Euler – Problem 264

July 28, 2017 Leave a comment

Today I managed to solve problem 264 from Project Euler. This is my highest rating problem until now: 85%. You can click the link for the full text of the problem. The main idea is to find all triangles ABC with vertices having integer coordinates such that

  • the circumcenter O of each of the triangles is the origin
  • the orthocenter H (the intersection of the heights) is the point of coordinates (0,5)
  • the perimeter is lower than a certain bound

I will not give detailed advice or codes. You can already find a program online for this problem (I won’t tell you where) and it can serve to verify the final code, before going for the final result. Anyway, following the hints below may help you get to a solution.

The initial idea has to do with a geometric relation linking the points A, B, C, O and H. Anyone who did some problems with vectors and triangles should have come across the needed relation at some time. If not, just search for important lines in triangles, especially the line passing through O and H (and another important point).

Once you find this vectorial relation, it is possible to translate it in coordinates. The fact that points A, B, C are on a circle centered in O shows that their coordinates satisfy an equation of the form x^2+y^2=n, where n is a positive integer, not necessarily a square… It is possible to enumerate all solutions to the following equation for fixed n, simply by looping over x and y. This helps you find all lattice points on the circle of radius \sqrt{n}.

Once these lattice points are found one needs to check the orthocenter condition. The relations are pretty simple and in the end we have two conditions to check for the sum of the x and y coordinates. The testing procedure is a triple loop. We initially have a list of points on a circle, from the previous step. We loop over them such that we dont count triangles twice: i from 1 to m, j from i+1 to m, k from j+1 to m, etc. Once a suitable solution is found, we compute the perimeter using the classical distance formula between two points given in coordinates. Once the perimeter is computed we add it to the total.

Since the triple loop has cubic complexity, one could turn it in a double loop. Loop over pairs and construct the third point using the orthocenter condition. Then just check if the point is also on the circle. I didn’t manage to make this double loop without overcounting things, so I use it as a test: use double loops to check every family of points on a given circle. If you find something then use a triple loop to count it properly. It turns out that cases where the triple loop is needed are quite rare.

So now you have the ingredients to check if on a circle of given radius there are triangles with the desired properties. Now we just iterate over the square of the radius. The problem is to find the proper upper bound for this radius in order to get all the triangles with perimeter below the bound. It turns out that a simple observation can get you close to a near optimal bound. Since in the end the radii get really large and the size of the triangles gets really large, the segment OH becomes small, being of fixed length 5. When OH is very small, the triangle is almost equilateral. Just use the upper bound for the radius for an equilateral triangle of perimeter equal to the upper bound of 100000 given in the problem.

Using these ideas you can build a bruteforce algorithm. Plotting the values of the radii which give valid triangles will help you find that you only need to loop over a small part of the radii values. Factoring these values will help you reduce even more the search space. I managed to  solve the problem in about 5 hours in Pari GP. This means things could be improved. However, having an algorithm which can give the result in “reasonable” time is fine by me.

I hope this will help you get towards the result.

Balkan Mathematical Olympiad 2017 – Problems

May 10, 2017 Leave a comment

Problem 1. Find all ordered pairs of positive integers { (x, y)} such that:

\displaystyle x^3+y^3=x^2+42xy+y^2.

Problem 2. Consider an acute-angled triangle {ABC} with {AB<AC} and let {\omega} be its circumscribed circle. Let {t_B} and {t_C} be the tangents to the circle {\omega} at points {B} and {C}, respectively, and let {L} be their intersection. The straight line passing through the point {B} and parallel to {AC} intersects {t_C} in point {D}. The straight line passing through the point {C} and parallel to {AB} intersects {t_B} in point {E}. The circumcircle of the triangle {BDC} intersects {AC} in {T}, where {T} is located between {A} and {C}. The circumcircle of the triangle {BEC} intersects the line {AB} (or its extension) in {S}, where {B} is located between {S} and {A}.

Prove that {ST}, {AL}, and {BC} are concurrent.

Problem 3. Let {\mathbb{N}} denote the set of positive integers. Find all functions {f:\mathbb{N}\longrightarrow\mathbb{N}} such that

\displaystyle n+f(m)\mid f(n)+nf(m)

for all {m,n\in \mathbb{N}}

Problem 4. On a circular table sit {\displaystyle {n> 2}} students. First, each student has just one candy. At each step, each student chooses one of the following actions:

  • (A) Gives a candy to the student sitting on his left or to the student sitting on his right.
  • (B) Separates all its candies in two, possibly empty, sets and gives one set to the student sitting on his left and the other to the student sitting on his right.

At each step, students perform the actions they have chosen at the same time. A distribution of candy is called legitimate if it can occur after a finite number of steps. Find the number of legitimate distributions.

(Two distributions are different if there is a student who has a different number of candy in each of these distributions.)

Source: AoPS

Project Euler Problem 285

March 25, 2017 Leave a comment

Another quite nice problem from Project Euler is number 285. The result of the problem depends on the computation of a certain probability, which in turn is related to the computation of a certain area. Below is an illustration of the computation for k equal to 10.

pb285_10

To save you some time, here’s a picture of the case k=1 which I ignored and spent quite a lot of time debugging… Plus, it only affects the last three digits or so after the decimal point…

pb285_1

Here’s a Matlab code which can construct the pictures above and can compute the result for low cases. To solve the problem, you should compute explicitly all these areas.


function problem285(k)

N = 100000;

a = rand(1,N);
b = rand(1,N);

ind = find(abs(sqrt((k*a+1).^2+(k*b+1).^2)-k)<0.5);

plot(a(ind),b(ind),'.');
axis equal

M = k;
pl = 1;

for k=1:M
if mod(k,100)==0
k
end
r1 = (k+0.5)/k;
r2 = (k-0.5)/k;

f1 = @(x) (x<=(-1/k+r1)).*(x>=(-1/k-r1)).*(sqrt(r1^2-(x+1/k).^2)-1/k).*(x>=0).*(x<=1); f1 = @(x) f1(x).*(f1(x)>=0);
f2 = @(x) (x<=(-1/k+r2)).*(x>=(-1/k-r2)).*(sqrt(r2^2-(x+1/k).^2)-1/k).*(x>=0).*(x<=1); f2 = @(x) f2(x).*(f2(x)>=0);

if k == pl
thetas = linspace(0,pi/2,200);
hold on
plot(-1/k+r1*cos(thetas),-1/k+r1*sin(thetas),'r','LineWidth',2);
plot(-1/k+r2*cos(thetas),-1/k+r2*sin(thetas),'r','LineWidth',2);
plot([0 1 1 0 0],[0 0 1 1 0],'k','LineWidth',3);
hold off
axis off
end

A(k) = integral(@(x) f1(x)-f2(x),0,1);

end

xs = xlim;
ys = ylim;

w = 0.01;
axis([xs(1)-w xs(2)+w ys(1)-w ys(2)+w]);

sum((1:k).*A)

%d bloggers like this: