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

(Created page with "==Problem== 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...")
 
(→‎Solution)
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
 
==Problem==
 
==Problem==
  
−
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.
+
Suppose <math>p > 3</math> is a prime number and
−
 
+
<cmath>S = \sum_{2 \le i < j < k \le p-1} ijk</cmath>
−
<asy>
+
Prove that <math>S+1</math> is divisible by <math>p</math>.
−
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==
 
==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 <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>
+
if you let <math>j</math> be constant, you can think of it as summing for each <math>i</math>, <math>\sum^{p-1}_{k=j+1}</math>, and since its for all <math>i</math> you can add another sum to get <math>\sum^{j-1}_{i=2}\sum^{p-1}_{k=j+1}</math>, and for all <math>j</math> we can add another sum, to get <math>\sum_{2\leq i<j<k\le p-1}ijk=\sum^{p-2}_{j=2}\sum^{j-1}_{i=2}\sum^{p-1}_{k=j+1}ijk</math>
 +
<cmath>\sum^{p-2}_{j=2}\sum^{j-1}_{i=2}\sum^{p-1}_{k=j+1}ijk</cmath>
 +
<cmath>\sum^{p-2}_{j=2}\sum^{j-1}_{i=2}ij\sum^{p-1}_{k=j+1}k</cmath>
 +
<cmath>\sum^{p-2}_{j=2}\sum^{j-1}_{i=2}ij\left(\frac{(p-j-1)(p+j)}{2}\right)</cmath>
 +
<cmath>\frac{1}{2}\sum^{p-2}_{j=2}\sum^{j-1}_{i=2}i(j(p-j-1)(p+j))</cmath>
 +
<cmath>\frac{1}{2}\sum^{p-2}_{j=2}\frac{(j+1)(j-2)(j(p-j-1)(p+j))}{2}</cmath>
 +
<cmath>\frac{1}{4}\sum^{p-2}_{j=2}(j+1)(j-2)(j(p-j-1)(p+j))</cmath>
 +
<cmath>\frac{1}{4}\sum^{p-2}_{j=2}-j^5+j^3p^2-j^3p+3j^3-j^2p^2+j^2p+2j^2-2jp^2+2jp</cmath>
 +
<cmath>\frac{1}{4}(\sum^{p-2}_{j=2}-j^5+(p^2-p+3)\sum^{p-2}_{j=2}j^3+(-p^2+p+2)\sum^{p-2}_{j=2}j^2-(2p^2-2p)\sum^{p-2}_{j=2}j)</cmath>
 +
<cmath>\frac{1}{4}(-\frac{2n^6+6n^5+5n^4-n^2}{12}+(p^2-p+3)\frac{(p-2)^2(p-1)^2}{4}-(p^2-p+3)+(-p^2+p+2)\frac{(p-2)(p-1)(2p-1)}{6}+(p^2-p-2)-(2p^2-2p)\frac{(p-1)(p-2)}{2}+(2p^2-2p)</cmath>
 +
<cmath>\frac{1}{48}(p^6-7p^5+11p^4+3p^3+12p^2-20p-48)=S</cmath>
 +
<cmath>S+1=\frac{1}{48}(p^6-7p^5+11p^4+3p^3+12p^2-20p-48)+1=\frac{p}{48}(p^5-7p^4+11p^3+3p^2+12p-20)</cmath>
 +
since it has a factor pf <math>p</math>, we need to prove <math>\frac{p^5-7p^4+11p^3+3p^2+12p-20}{48}</math> is always an integer, for prime <math>p>3</math> <math>p\mod 6\equiv 1\text{ or }5</math>, so let <math>p=6k+1</math> and <math>p=6k+5</math>
 +
for the first case, you get <math>\frac{24k(324k^4+108k^3-63k^2+6k+7)}{48}</math> and for the second you get <math>\frac{24(3k+2)(108k^4+252k^3+195k^2+54k+5)}{48}</math>, notice how both of these are always integers, thus it is proven <math>p</math> divides <math>S+1</math>
  
 
==See Also==
 
==See Also==
−
{{Indonesia MO box|year=2013|before=First Problem|num-a=2}}
+
{{Indonesia MO box|year=2013|num-b=3|num-a=5}}
  
 
[[Category:Intermediate Number Theory Problems]]
 
[[Category:Intermediate Number Theory Problems]]

Latest revision as of 06:06, 25 December 2024

Problem

Suppose $p > 3$ is a prime number and \[S = \sum_{2 \le i < j < k \le p-1} ijk\] Prove that $S+1$ is divisible by $p$.

Solution

if you let $j$ be constant, you can think of it as summing for each $i$, $\sum^{p-1}_{k=j+1}$, and since its for all $i$ you can add another sum to get $\sum^{j-1}_{i=2}\sum^{p-1}_{k=j+1}$, and for all $j$ we can add another sum, to get $\sum_{2\leq i<j<k\le p-1}ijk=\sum^{p-2}_{j=2}\sum^{j-1}_{i=2}\sum^{p-1}_{k=j+1}ijk$ \[\sum^{p-2}_{j=2}\sum^{j-1}_{i=2}\sum^{p-1}_{k=j+1}ijk\] \[\sum^{p-2}_{j=2}\sum^{j-1}_{i=2}ij\sum^{p-1}_{k=j+1}k\] \[\sum^{p-2}_{j=2}\sum^{j-1}_{i=2}ij\left(\frac{(p-j-1)(p+j)}{2}\right)\] \[\frac{1}{2}\sum^{p-2}_{j=2}\sum^{j-1}_{i=2}i(j(p-j-1)(p+j))\] \[\frac{1}{2}\sum^{p-2}_{j=2}\frac{(j+1)(j-2)(j(p-j-1)(p+j))}{2}\] \[\frac{1}{4}\sum^{p-2}_{j=2}(j+1)(j-2)(j(p-j-1)(p+j))\] \[\frac{1}{4}\sum^{p-2}_{j=2}-j^5+j^3p^2-j^3p+3j^3-j^2p^2+j^2p+2j^2-2jp^2+2jp\] \[\frac{1}{4}(\sum^{p-2}_{j=2}-j^5+(p^2-p+3)\sum^{p-2}_{j=2}j^3+(-p^2+p+2)\sum^{p-2}_{j=2}j^2-(2p^2-2p)\sum^{p-2}_{j=2}j)\] \[\frac{1}{4}(-\frac{2n^6+6n^5+5n^4-n^2}{12}+(p^2-p+3)\frac{(p-2)^2(p-1)^2}{4}-(p^2-p+3)+(-p^2+p+2)\frac{(p-2)(p-1)(2p-1)}{6}+(p^2-p-2)-(2p^2-2p)\frac{(p-1)(p-2)}{2}+(2p^2-2p)\] \[\frac{1}{48}(p^6-7p^5+11p^4+3p^3+12p^2-20p-48)=S\] \[S+1=\frac{1}{48}(p^6-7p^5+11p^4+3p^3+12p^2-20p-48)+1=\frac{p}{48}(p^5-7p^4+11p^3+3p^2+12p-20)\] since it has a factor pf $p$, we need to prove $\frac{p^5-7p^4+11p^3+3p^2+12p-20}{48}$ is always an integer, for prime $p>3$ $p\mod 6\equiv 1\text{ or }5$, so let $p=6k+1$ and $p=6k+5$ for the first case, you get $\frac{24k(324k^4+108k^3-63k^2+6k+7)}{48}$ and for the second you get $\frac{24(3k+2)(108k^4+252k^3+195k^2+54k+5)}{48}$, notice how both of these are always integers, thus it is proven $p$ divides $S+1$

See Also

2013 Indonesia MO (Problems)
Preceded by
Problem 3 		1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 Followed by
Problem 5
All Indonesia MO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2013_Indonesia_MO_Problems/Problem_4&oldid=237800"