Maths Olympiad Prep

Library / /616 of 860

Geometry Difficulty 5.3 AIME, harder Find the answer

Let PP be the set of points {(x,y)0x,y25,x,yZ}\{(x, y) \mid 0 \leq x, y \leq 25, x, y \in \mathbb{Z}\} and let TT be the set of triangles formed by picking three distinct points in PP (rotations, reflections, and translations count as distinct triangles). Compute the number of triangles in TT that have area larger than 300.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Lemma: The area of any triangle inscribed in an aa by bb rectangle is at most ab2\frac{ab}{2}. (Any triangle's area can be increased by moving one of its sides to a side of the rectangle). Given this, because any triangle in TT is inscribed in a 25×2525 \times 25 square, we know that the largest possible area of a triangle is 2522\frac{25^{2}}{2}, and any triangle which does not use the full range of xx or yy-values will have area no more than 25242=300\frac{25 \cdot 24}{2}=300. There are 425=1004 \cdot 25=100 triangles of maximal area: pick a side of the square and pick one of the 26 vertices on the other side of our region; each triangle with three vertices at the corners of the square is double-counted once. To get areas between 25242\frac{25 \cdot 24}{2} and 25252\frac{25 \cdot 25}{2}, we need to pick a vertex of the square ((0,0)\left((0,0)\right. without loss of generality), as well as (25,y)(25, y) and (x,25)(x, 25). By Shoelace, this has area 252xy2\frac{25^{2}-xy}{2}, and since xx and yy must both be integers, there are d(n)d(n) ways to get an area of 252n2\frac{25^{2}-n}{2} in this configuration, where d(n)d(n) denotes the number of divisors of nn. Since we can pick any of the four vertices to be our corner, there are then 4d(n)4 d(n) triangles of area 252n2\frac{25^{2}-n}{2} for 1n251 \leq n \leq 25. So, we compute the answer to be P=100+4(d(1)++d(24))=4k2424k=100+4(24+12+8+6+4+4+3+3+24+112)=436\begin{aligned} |P| & =100+4(d(1)+\ldots+d(24)) \\ & =4 \sum_{k \leq 24}\left\lfloor\frac{24}{k}\right\rfloor \\ & =100+4(24+12+8+6+4+4+3+3+2 \cdot 4+1 \cdot 12) \\ & =436 \end{aligned}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.