Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2013 Indonesia MO Problems/Problem 1

Revision as of 23:00, 24 December 2024 by Skill issue7 (talk | contribs) (→‎Problem 1)

Problem

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.

See Also

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2013_Indonesia_MO_Problems/Problem_1&oldid=237771"