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

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

(→‎Problem)
(→‎Solution)
 
(2 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
==Problem==
 
==Problem==
−
 
−
===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.
 
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.
Line 36: Line 34:
  
 
</asy>
 
</asy>
−
 
−
[[2013 Indonesia MO Problems/Problem 1|Solution]]
 
  
 
==Solution==
 
==Solution==
  
−
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]].
+
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>
−
 
 
−
<br>
 
−
'''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>
 
−
'''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>
 
−
By combining Lemmas 1 and 2, we find that for all scenarios, <math>n</math> is nonnegative and even.
 
  
 
==See Also==
 
==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]]
 
[[Category:Intermediate Number Theory Problems]]

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}$

See Also

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