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 "2020 INMO Problems/Problem 6"

(Created page with "==Problem== A stromino is a <math>3 \times 1</math> rectangle. Show that a <math>5 \times 5</math> board divided into twenty-five <math>1 \times 1</math> squares cannot be co...")
 
(→‎Solution)
 
Line 41: Line 41:
 
So there will exactly one unit square covered exactly once.
 
So there will exactly one unit square covered exactly once.
  
−
Contradiction ! And we are done.
+
Contradiction ! And we are done. ~ftheftics

Latest revision as of 12:55, 5 November 2020

Problem

A stromino is a $3 \times 1$ rectangle. Show that a $5 \times 5$ board divided into twenty-five $1 \times 1$ squares cannot be covered by $16$ strominos such that each stromino covers exactly three squares of the board, and every square is covered by one or two strominos. (A stromino can be placed either horizontally or vertically on the board.)

Solution

At first of all let assigne a $5\times 5$ matrix with $a_{ij} = (i+j)$.

Now notice that $\sum_{i=1} ^ 5 \sum_{j=1}^5 a_{ij} \equiv 0 \pmod{3}$.


Now notice that , For each trominoes sum of the numbers that it cover is $0$ modulo $3$.

Now let's assume that there are are$x$ unit square covered exactly once and $25-x$ unit square covered twice . So, $x+2(25-x) =16\times 3=48$.

So there are only $2$ unit square coverd exactly once.

Let assume that $a_{xy}$ and $a_{zw}$ are the unit squares that covered exactly once.

Since, I have assume that the colouring is possible that's why 

, $2(\sum_{i=1} ^ 5 \sum_{j=1}^5  a_{ij})-a_{xy} -a_{zw} \equiv 0 \pmod{3}$.

\[\implies (x+y)\equiv 2(z+w) \pmod{3} \cdots (1)\]

again assign another kind of coloring , $a_{ij} = (i-j)$.

In this case we also get, $2(\sum_{i=1} ^ 5 \sum_{j=1}^5 a_{ij})-a_{xy} -a_{zw} \equiv 0 \pmod{3}$.

\[\implies x-y\equiv 2(z-w) \pmod{3}\cdots (2)\].

From equation (1 )and (2) we should get, \[x\equiv 2z \implies x+z \equiv 0 \pmod{3}\].

\[\implies x+z \equiv y+w \equiv 0 \pmod{3}\].

Similarly we have $x-z \equiv y-w \equiv 0\pmod{3}$.

So , only possibility is $x=y=z=w=3$.

So there will exactly one unit square covered exactly once.

Contradiction ! And we are done. ~ftheftics

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2020_INMO_Problems/Problem_6&oldid=136617"