Newsletter #43 - Solution

Problem

Find the number of ordered pairs <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">(</mo><mi>x</mi><mo separator="true">,</mo><mi>y</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(x,y)</annotation></semantics></math>(x,y) of positive integers that satisfy

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mi>x</mi><mo>≤</mo><mn>2</mn><mi>y</mi><mo>≤</mo><mn>60</mn><mo separator="true">,</mo><mspace width="1em"/><mi>y</mi><mo>≤</mo><mn>2</mn><mi>x</mi><mo>≤</mo><mn>60.</mn></mrow><annotation encoding="application/x-tex">x \leq 2y \leq 60, \quad y \leq 2x \leq 60.</annotation></semantics></math>x≤2y≤60,y≤2x≤60.

Solution - by Bethany (Texas)

The solution set of these inequalities is the quadrilateral with vertices at <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">(</mo><mn>0</mn><mo separator="true">,</mo><mn>0</mn><mo stretchy="false">)</mo><mo separator="true">,</mo><mo stretchy="false">(</mo><mn>15</mn><mo separator="true">,</mo><mn>30</mn><mo stretchy="false">)</mo><mo separator="true">,</mo><mo stretchy="false">(</mo><mn>30</mn><mo separator="true">,</mo><mn>30</mn><mo stretchy="false">)</mo><mo separator="true">,</mo><mo stretchy="false">(</mo><mn>30</mn><mo separator="true">,</mo><mn>15</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(0,0), (15,30), (30,30), (30,15)</annotation></semantics></math>(0,0),(15,30),(30,30),(30,15). Since this quadrilateral has vertices at integer points, we use Pick's theorem, which states that <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>A</mi><mo>=</mo><mi>n</mi><mo>−</mo><mfrac><mi>b</mi><mn>2</mn></mfrac><mo>−</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">A = n - \frac{b}{2} - 1</annotation></semantics></math>A=n−2b−1, where <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>A</mi></mrow><annotation encoding="application/x-tex">A</annotation></semantics></math>A is the area of the quadrilateral, <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math>n is the number of integer points in it (both boundary and interior), and <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>b</mi></mrow><annotation encoding="application/x-tex">b</annotation></semantics></math>b is the number of integer points on the boundary.

The quadrilateral can be constructed as a <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>30</mn><mo>×</mo><mn>30</mn></mrow><annotation encoding="application/x-tex">30 \times 30</annotation></semantics></math>30×30 square (area <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>900</mn></mrow><annotation encoding="application/x-tex">900</annotation></semantics></math>900) with two triangles removed that each have an area of <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mfrac><mrow><mn>15</mn><mo>⋅</mo><mn>30</mn></mrow><mn>2</mn></mfrac><mo>=</mo><mn>225</mn></mrow><annotation encoding="application/x-tex">\frac{15 \cdot 30}{2}=225</annotation></semantics></math>215⋅30=225, so the quadrilateral has area <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>450</mn></mrow><annotation encoding="application/x-tex">450</annotation></semantics></math>450.

In addition to the vertices, the slanted sides that meet at <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">(</mo><mn>0</mn><mo separator="true">,</mo><mn>0</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(0,0)</annotation></semantics></math>(0,0) have integer points at <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">(</mo><mi>k</mi><mo separator="true">,</mo><mn>2</mn><mi>k</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(k,2k)</annotation></semantics></math>(k,2k) and<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">(</mo><mn>2</mn><mi>k</mi><mo separator="true">,</mo><mi>k</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(2k,k)</annotation></semantics></math>(2k,k) for <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math>k from <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn></mrow><annotation encoding="application/x-tex">1</annotation></semantics></math>1 to <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>14</mn></mrow><annotation encoding="application/x-tex">14</annotation></semantics></math>14, and the short sides that meet at <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">(</mo><mn>30</mn><mo separator="true">,</mo><mn>30</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(30,30)</annotation></semantics></math>(30,30) have integer points at<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">(</mo><mi>j</mi><mo separator="true">,</mo><mn>30</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(j,30)</annotation></semantics></math>(j,30) and <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">(</mo><mn>30</mn><mo separator="true">,</mo><mi>j</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(30,j)</annotation></semantics></math>(30,j) for <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>j</mi></mrow><annotation encoding="application/x-tex">j</annotation></semantics></math>j from <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>16</mn></mrow><annotation encoding="application/x-tex">16</annotation></semantics></math>16 to <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>29</mn></mrow><annotation encoding="application/x-tex">29</annotation></semantics></math>29, evaluating to a total of <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>60</mn></mrow><annotation encoding="application/x-tex">60</annotation></semantics></math>60 integer points on the boundary.

Therefore we have <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi><mo>=</mo><mi>A</mi><mo>+</mo><mfrac><mi>b</mi><mn>2</mn></mfrac><mo>+</mo><mn>1</mn><mo>=</mo><mn>450</mn><mo>+</mo><mn>30</mn><mo>+</mo><mn>1</mn><mo>=</mo><mn>481</mn></mrow><annotation encoding="application/x-tex">n = A + \frac{b}{2} + 1 = 450 + 30 + 1 = 481</annotation></semantics></math>n=A+2b+1=450+30+1=481, and since we are only considering positive integer solutions we remove <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">(</mo><mn>0</mn><mo separator="true">,</mo><mn>0</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(0,0)</annotation></semantics></math>(0,0) which leaves us with <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>480</mn></mrow><annotation encoding="application/x-tex">480</annotation></semantics></math>480 ordered positive integer pairs.

Thank you!

Huge thanks to Joan Llobera (Lleida, Catalonia), Mark Spindler (Maryland), Ibrahim (California), Kurt Wynn (Brockton Bay), David J. Webb (Hawaii), Darko L (Serbia), Martin Masson (France), Bethany (Texas), jc (New York), and Aayush Rath (India) for submitting solutions to this challenge problem.