Problem 4. Triangle has circumcircle and circumcenter . A circle with center intersects the segment at points and , such that , , , and are all different and lie on line in this order. Let and be the points of intersection of and , such that , , , , and lie on in this order. Let be the second point of intersection of the circumcircle of triangle and the segment . Let be the second point of intersection of the circumcircle of triangle and the segment .
Suppose that the lines and are different and intersect at the point . Prove that lies on the line .
Problem 5. Let be the set of real numbers. Determine all functions that satisfy the equation
for all real numbers and .
Problem 6. The sequence of integers satisfies the conditions:
(i) for all , (ii) for all . Prove that there exist two positive integers and for which
for all integers and such that .
Problem 1. We say that a finite set of points in the plane is balanced if, for any two different points and in , there is a point in such that . We say that is center-free if for any three different points , and in , there is no points in such that .
(a) Show that for all integers , there exists a balanced set having points.
(b) Determine all integers for which there exists a balanced center-free set having points.
Problem 2. Find all triples of positive integers such that are all powers of 2.
Problem 3. Let be an acute triangle with . Let be its cirumcircle., its orthocenter, and the foot of the altitude from . Let be the midpoint of . Let be the point on such that and let be the point on such that . Assume that the points and are all different and lie on in this order.
Prove that the circumcircles of triangles and are tangent to each other.
This is a solution to problem D from the International Collegiate Programming Contest. The list of the problems can be found here. This is one of the problems which was really appealing for me, from the start. The idea is the following: suppose you have a Swiss cheese cube of (the units are centimeters). This cheese cube has multiple holes in it, and for the sake of simplicity, we assume they are spheres. Suppose also that their centers and their radii are known. The problem is how to cut this piece of cheese into horizontal slices having equal weights (that is equal volumes). The holes are supposed to be contained in the cube, and non-intersecting.
The problem is really simple if you don’t have any holes. Just cut at evenly distributed points along the height of the cheese cube. Things change if you add holes, because cutting at evenly distributed points may lead to slices of different weights, since the holes may be not evenly distributed in the cube.
The approach I had in mind was to forget about the slices for a moment. Working with slices means that you may need to cut two caps off a sphere, and that leads to complications. Instead of finding the slices, we could search for the planes dividing the cheese cube into two pieces of given volume ratio. That is, given a proportion of the volume, find the height of the cut, such that that proportion is below the cut. To do this, we only need to be capable to find the volume of the pierced cube which lies under a plane of height .
In order to find this volume, it suffices to subtract from the volumes of the portions of the spheres which lie under the plane of height . Thus, we only need the formula for the volume of a spherical cap, which is , where is the radius of the sphere, and is the height of the cap. Such a function, which computes the volume under a plane of height can be easily vectorized, and implemented in Matlab.
Once we have the function which computes the volume under a certain height, it suffices to do a binary search, in order to find the heights which give volumes . Once we have the heights, we can find the widths of the slices. I implemented the algorithm in Matlab below. I don’t have some complicated test cases, but in the ones I have, the division into slices takes seconds.
function Prob3_2015 n = 2; %number of spheres s = 100; %number of slices r = [10000 40000]; %radii of the spheres %coordinates of the centers %the box is parametrized as 100000^3 %and the real dimensions are 100^3 mm^3 ct = [10000 20000 20000; 40000 50000 60000]; %total volume of the spheres totalv = 4*pi/3*sum(r.^3); %actual volume of the cheese cube actualv = 100000^3-totalv; slices = zeros(1,s); for i = 1:s-1 target = i*actualv/s; m = 0; M = 100000; while M-m>1e-6 mid = (m+M)/2; amid = slice_vol(mid,ct,r); if amid>target M = mid; else m = mid; end end fprintf('Cumulative slice %d : %9.6f mm\n',i,mid/1000); slices(i) = mid; end slices(end)= 100000; slices = [0 slices]; disp(' '); for i = 1:s fprintf('Width slice %d : %9.6f mm\n',i,(slices(i+1)-slices(i))/1000); end % function calculating volume under a plane function res = slice_vol(h,ct,r) if isempty(ct) pars = 0; else pars = min(max(h-(ct(:,3)-r(:)),0),2*r(:)); end; res = h*10^10-sum(pi*pars.^2.*r(:)-pi*pars.^3/3);
This the the solution to Problem B from the International Collegiate Programming Contest. The list of problems can be found here. The idea is to find the maximal area of the intersection of two moving polygons. The inputs give the initial positions of two convex polygons and the vectors giving their speed in the plane.
One idea of a solution is as follows: take a maximal time and a discretization of the interval by dividing it into parts. Iterate over the translations at times given by this discretization, compute at each step the area of the intersection of the two polygons (if there is any intersection at all), and in the end find the time for which this area is maximized. Now, even if the discretization step is large (greater than the demanded precision of ), we can conclude that is an approximation of the final time with an error smaller than . This is due to the fact that the function representing the area of the intersection has two monotonicity intervals, as a consequence of the fact that the polygons are convex. On the first interval, the intersection area is increasing, on the second one it is decreasing. Thus, once we have a discrete maximum, we are close to the real maximum.
Now, all we are left to do in order to achieve any desired precision is to refine the search near this discrete maximum, find a new, better approximation, and refine again, until we have enough precision. Of course, one first problem with this algorithm is the initial search using a maximal time . It is possible that if or are not large enough, then we do not detect any intersection of the two polygons. Thus, an initial guess, based on a mathematical argument is needed in order to reduce the search of the optimal time to an interval which is small enough to have enough initial precision to detect the discrete maximum.
The algorithm presented below, uses Matlab’s predefined function polybool which can compute the intersection of two polygons. Of course, this is an overkill, since dealing with intersections of convex polygons is not that complicated (but still, I didn’t have enough time to play with the problem, in order to provide a more optimized version). I do not treat the search for the initial time interval. As I think about it, I guess a n argument based on finding some line intersections should give us a narrow enough time interval (with some care for the case when the two speed directions are collinear). The algorithm presented below solves the sample cases, but could fail in more general situations.
function Prob1_2015(p1,p2) % choose initial polygons; see the text of the problem p1 = [6 3 2 2 4 3 6 6 6 7 4 6 2 2 2]; p2 = [4 18 5 22 9 26 5 22 1 -2 1]; %p1 = [4 0 0 0 2 2 2 2 0 1 1]; %p2 = [4 10 0 10 2 12 2 12 0 -1 1]; np1 = p1(1); np2 = p2(1); cp1 = p1(2:1+2*np1); cp2 = p2(2:1+2*np2); vp1 = p1(end-1:end); vp2 = p2(end-1:end); cp1 = cp1(:); cp1 = reshape(cp1,2,np1); xp1 = cp1(1,:); yp1 = cp1(2,:); cp2 = cp2(:); cp2 = reshape(cp2,2,np2); xp2 = cp2(1,:); yp2 = cp2(2,:); %set precision prec = 1; %here there should be a clever initial choice of %the starting time and stopping time %this choice works well in this case start = 0; stop = 5; while prec>1e-6 n = 100; timex = linspace(start,stop,n); areas = zeros(size(timex)); for i = 1:n t = timex(i); xt1 = xp1+t*vp1(1); yt1 = yp1+t*vp1(2); xt2 = xp2+t*vp2(1); yt2 = yp2+t*vp2(2); [x,y] = polybool('intersection',xt1,yt1,xt2,yt2); areas(i) = polyarea(x,y); end [m,I] = max(areas); if m<1e-6 % if no polygonal intersection is detected % there is nothing further to do display('never'); break end tapp = timex(I); fprintf('Precision %f | Time %f\n',prec,tapp); start = tapp-prec; stop = tapp+prec; prec = prec/10; end clf %this draws the final position of the polygon %as well as their intersection fill(xt1,yt1,'blue') axis equal hold on fill(xt2,yt2,'red') fill(x,y,'green') axis equal hold off
>> Prob1_2015 res = 4.193548
This is the solution to Problem A from the International Collegiate Programming Contest. The list of problems can be found here. This first problem consists simply of reading the parameters of the function defined below, and computing its values on the set . Then, you need to find the maximum decrease in the function values.
The inputs are parameters , the function is
and the values to be considered are . Below is a Matlab code which works, at least for the given Sample Inputs. This should be optimized by removing the for loop. It is instant for but it should be modified to work until .
function res = Prob1_2015(p,a,b,c,d,n) dis = 1:n; vals = p*(sin(a*dis+b)+cos(c*dis+d)+2); mat = zeros(n,1); for i = 1:n mat(i) = vals(i)-min(vals(i:end)); end res = max(mat)
The sample outputs are:
>> Prob1_2015(42,1,23,4,8,10) 104.855110477394
>> Prob1_2015(100,7,615,998,801,3) 0
>> Prob1_2015(100,432,406,867,60,1000) 399.303812592112
New version which works for large . It suffices to eliminate the computation of the min at each of the phases of the iteration. This solves the problem in 0.2 seconds for
function res = Prob1_2015(p,a,b,c,d,n) dis = 1:n; vals = p*(sin(a*dis+b)+cos(c*dis+d)+2); mat = zeros(n,1); lastmax = vals(1); for i = 1:n lastmax = max(lastmax,vals(i)); mat(i) = lastmax-vals(i); end res = max(mat)
Problem 1. If and are positive real numbers, prove that
Problem 2. Let be a scalene triangle with incentre and circumcircle . Lines intersect for the second time at points , respectively. The parallel lines from to the sides intersect at points , respectively. Prove that the points are collinear. (Cyprus)
Problem 3. A committee of film critics are voting for the Oscars. Every critic voted just an actor and just one actress. After the voting, it was found that for every positive integer , there is some actor or some actress who was voted exactly times. Prove that there are two critics who voted the same actor and the same actress. (Cyprus)
Problem 4. Prove that among consecutive positive integers there is an integer such that for every positive integer the following inequality holds
where by denotes the fractional part of the real number . The fractional part of the real number is defined as the difference between the largest integer that is less than or equal to to the actual number . (Serbia)
A triangulation algorithm often gives as output a list of points, and a list of triangle. Each triangle is represented by the indexes of the points which form it. Sometimes we need extra information on the structure of the triangulation, like the list of edges, or the list of boundary points. I will present below two fast algorithms for doing this.
Finding the list of edges is not hard. The idea is to go through each triangle, and extract all edges. The algorithm proposed below creates the adjacency matrix in the following way: for each triangle we set the elements (and their symmetric correspondents) to be equal to .
In order to find the points on the boundary (in two dimensions), it is enough to look for the edges which are sides to only one triangle. We can do this using the adjacency matrix. Note that if is the adjacency matrix, then stores the number of paths of length (two sides) between two points of the triangulation. Note that any edge which is not on the boundary will contain the starting and ending point of two paths of length . If is a triangle such that points are on the boundary, then (there is one path of length going through . We also have . Conversely, if and then are connected, and there is a unique path of length going from to . Thus, is an edge on the boundary. Therefore, we just need to identify the indexes such that there exists with .
Below are two short Matlab codes doing these two algorithms. I guess they are close to being optimal, since only sparse and vectorized operations are used.
%p is the list of points %T is the list of triangles, ap is the number of points %this computes the adjacency matrix A = min(sparse(T(:,1),T(:,2),1,ap,ap)+sparse(T(:,2),T(:,3),1,ap,ap)+sparse(T(:,3),T(:,1),1,ap,ap),1); A = min(A+A',1); % this finds the boundary points, whose indexes are stored in Ibord B = A^2.*A==1; Ibord = find(sum(B,2)>0);