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

Latest revision as of 23:07, 24 December 2024

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

In the grid, you can make a rectangle and construct a parallelogram, notice how you can always make a parallelogram so long as the rectangle that was chosen was not a square, the ammount of ways to pick a rectangle is $\binom{7}{2}\binom{5}{2}=210$ since there are 7 horizontal lines and you choose 1, and there are 5 vertical lines and you choose 2, and the total ammount of squares are $6\cdot 4+5\cdot 3+4\cdot 2+3\cdot 1=50$ , so the total ammount of rectangles you can make are $210-50=160$ , also for each rectangle there are 2 parallelograms you can make, one of them is fliped, so myltiply the total ammount of rectangles by 2 which is $160\cdot 2=\boxed{320}$

2013 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"

Latest revision as of 23:07, 24 December 2024

Problem

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.
+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.
-==Solution==
+<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));
-We will prove that <math>n</math> is even and that <math>n</math> is nonnegative separately because each part has its own specific [[casework]].
-<br>
+</asy>
-'''Lemma 1: <math>n</math> is nonnegative'''<br>
-* If <math>a</math> and <math>b</math> are [[relatively prime]], then <math>n = ab + 1 - a - b = (a-1)(b-1)</math>.  Since <math>a,b \ge 1</math>, we know that <math>n \ge 0</math>, making <math>n</math> nonnegative.
-* If <math>a</math> and <math>b</math> are not relatively prime, then let <math>g</math> be the [[GCD]] of <math>a</math> and <math>b</math>.  Since <math>\mathrm{LCM}(a,b) \cdot \mathrm{GCD}(a,b) = ab</math>, we find that <math>\mathrm{LCM}(a,b) = \tfrac{ab}{g}</math>.  This means that <math>n = \tfrac{ab}{g} + g - a - b = (\tfrac{a}{g} - 1)(b - g)</math>.  Because <math>a,b \ge g</math>, we know that <math>\tfrac{a}{g} - 1 \ge 0</math> and <math>b \ge 0</math>, making <math>n</math> nonnegative.
-<br>
+==Solution==
-'''Lemma 2: <math>n</math> is even'''<br>
-* If <math>a</math> and <math>b</math> are even, then <math>\mathrm{LCM}(a,b)</math> and <math>\mathrm{GCD}(a,b)</math> are both even since <math>a</math> and <math>b</math> share a factor of 2.  That means <math>n</math> must be even as well since only even numbers are being added or subtracted.
-* If <math>a</math> is even and <math>b</math> is odd, then <math>\mathrm{LCM}(a,b) \equiv 0 \pmod{2}</math> because <math>a</math> has a factor of 2 and <math>\mathrm{GCD}(a,b) \equiv 1 \pmod{2}</math> because <math>b</math> does not have a factor of <math>2</math>.  That means <math>n \equiv 0 + 1 - 0 - 1 \equiv 0 \pmod{2}</math>, making <math>n</math> even once again.  By [[symmetry]], <math>n</math> is even when <math>a</math> is odd and <math>b</math> is even.
-* If <math>a</math> and <math>b</math> are odd, then <math>\mathrm{LCM}(a,b)</math> and <math>\mathrm{GCD}(a,b)</math> are both odd since <math>a</math> and <math>b</math> do not have a factor of 2.  That means <math>n \equiv 1 + 1 - 1 - 1 \equiv 0 \pmod{2}</math>, making <math>n</math> even.
-<br>
+In the grid, you can make a rectangle and construct a parallelogram, notice how you can always make a parallelogram so long as the rectangle that was chosen was not a square, the ammount of ways to pick a rectangle is <math>\binom{7}{2}\binom{5}{2}=210</math> since there are 7 horizontal lines and you choose 1, and there are 5 vertical lines and you choose 2, and the total ammount of squares are <math>6\cdot 4+5\cdot 3+4\cdot 2+3\cdot 1=50</math>, so the total ammount of rectangles you can make are <math>210-50=160</math>, also for each rectangle there are 2 parallelograms you can make, one of them is fliped, so myltiply the total ammount of rectangles by 2 which is <math>160\cdot 2=\boxed{320}</math>
-By combining Lemmas 1 and 2, we find that for all scenarios, <math>n</math> is nonnegative and even.
 ==See Also==
-{{Indonesia MO box|year=2012|before=First Problem|num-a=2}}
+{{Indonesia MO box|year=2013|before=First Problem|num-a=2}}
 [[Category:Intermediate Number Theory Problems]]