Difference between revisions of "2013 Indonesia MO Problems/Problem 1"

Revision as of 22:59, 24 December 2024

Problem

Problem 1

In a $4 \times 6$ grid, all edges and diagonals are drawn (see attachment). Determine the number of parallelograms in the grid that uses only the line segments drawn and none of its four angles are right.

$[asy] draw((0,0)--(6,0)--(6,4)--(0,4)--(0,0)); for (int i=1; i<6; ++i) { draw((i,0)--(i,4)); } for (int i=1; i<4; ++i) { draw((0,i)--(6,i)); } draw((0,1)--(1,0)); draw((0,2)--(2,0)); draw((0,3)--(3,0)); draw((0,4)--(4,0)); draw((1,4)--(5,0)); draw((2,4)--(6,0)); draw((3,4)--(6,1)); draw((4,4)--(6,2)); draw((5,4)--(6,3)); draw((0,3)--(1,4)); draw((0,2)--(2,4)); draw((0,1)--(3,4)); draw((0,0)--(4,4)); draw((1,0)--(5,4)); draw((2,0)--(6,4)); draw((3,0)--(6,3)); draw((4,0)--(6,2)); draw((5,0)--(6,1)); [/asy]$

Solution

We will prove that $n$ is even and that $n$ is nonnegative separately because each part has its own specific casework.

Lemma 1: $n$ is nonnegative

If $a$ and $b$ are relatively prime, then $n = ab + 1 - a - b = (a-1)(b-1)$ . Since $a,b \ge 1$ , we know that $n \ge 0$ , making $n$ nonnegative.
If $a$ and $b$ are not relatively prime, then let $g$ be the GCD of $a$ and $b$ . Since $\mathrm{LCM}(a,b) \cdot \mathrm{GCD}(a,b) = ab$ , we find that $\mathrm{LCM}(a,b) = \tfrac{ab}{g}$ . This means that $n = \tfrac{ab}{g} + g - a - b = (\tfrac{a}{g} - 1)(b - g)$ . Because $a,b \ge g$ , we know that $\tfrac{a}{g} - 1 \ge 0$ and $b \ge 0$ , making $n$ nonnegative.

Lemma 2: $n$ is even

If $a$ and $b$ are even, then $\mathrm{LCM}(a,b)$ and $\mathrm{GCD}(a,b)$ are both even since $a$ and $b$ share a factor of 2. That means $n$ must be even as well since only even numbers are being added or subtracted.
If $a$ is even and $b$ is odd, then $\mathrm{LCM}(a,b) \equiv 0 \pmod{2}$ because $a$ has a factor of 2 and $\mathrm{GCD}(a,b) \equiv 1 \pmod{2}$ because $b$ does not have a factor of $2$ . That means $n \equiv 0 + 1 - 0 - 1 \equiv 0 \pmod{2}$ , making $n$ even once again. By symmetry, $n$ is even when $a$ is odd and $b$ is even.
If $a$ and $b$ are odd, then $\mathrm{LCM}(a,b)$ and $\mathrm{GCD}(a,b)$ are both odd since $a$ and $b$ do not have a factor of 2. That means $n \equiv 1 + 1 - 1 - 1 \equiv 0 \pmod{2}$ , making $n$ even.

By combining Lemmas 1 and 2, we find that for all scenarios, $n$ is nonnegative and even.

2012 Indonesia MO (Problems)
Preceded by First Problem	1 • 2 • 3 • 4 • 5 • 6 • 7 • 8	Followed by Problem 2
All Indonesia MO Problems and Solutions

Page

Toolbox

Search

Difference between revisions of "2013 Indonesia MO Problems/Problem 1"

Revision as of 22:59, 24 December 2024

Contents

Problem

Problem 1

Solution

See Also

@@ Line 1: / Line 1: @@
 ==Problem==
-Show that for any positive integers <math>a</math> and <math>b</math>, the number <cmath>n=\mathrm{LCM}(a,b)+\mathrm{GCD}(a,b)-a-b</cmath> is an even non-negative integer.
+===Problem 1===
+In a <math>4 \times 6</math> grid, all edges and diagonals are drawn (see attachment). Determine the number of parallelograms in the grid that uses only the line segments drawn and none of its four angles are right.
+<asy>
+draw((0,0)--(6,0)--(6,4)--(0,4)--(0,0));
+for (int i=1; i<6; ++i)
+{
+draw((i,0)--(i,4));
+}
+for (int i=1; i<4; ++i)
+{
+draw((0,i)--(6,i));
+}
+draw((0,1)--(1,0));
+draw((0,2)--(2,0));
+draw((0,3)--(3,0));
+draw((0,4)--(4,0));
+draw((1,4)--(5,0));
+draw((2,4)--(6,0));
+draw((3,4)--(6,1));
+draw((4,4)--(6,2));
+draw((5,4)--(6,3));
+draw((0,3)--(1,4));
+draw((0,2)--(2,4));
+draw((0,1)--(3,4));
+draw((0,0)--(4,4));
+draw((1,0)--(5,4));
+draw((2,0)--(6,4));
+draw((3,0)--(6,3));
+draw((4,0)--(6,2));
+draw((5,0)--(6,1));
+</asy>
+[[2013 Indonesia MO Problems/Problem 1|Solution]]
 ==Solution==