#770

1

009s

Each cell of an $n \times n$ grid square is colored black or white. We call such a coloring *nice* if every $2 \times 2$ square covers an even number of black cells, and every cross covers an odd number of black cells. Find all $n \ge 3$ such that in each nice coloring the four corner cells have the same color.
![](attached_image_1.png)

[
  "Color row 1 black and rows 2, 3 white. Then extend the coloring periodically with the remaining rows until the entire square is colored. It is immediate that the obtained coloring is nice. If $n \\equiv 0 \\pmod{3}$ or $n \\equiv 2 \\pmod{3}$, the last row is white while the first one is black. So a necessary condition on $n$ is $n \\equiv 1 \\pmod{3}$. We prove that it is sufficient.\n![](attached_image_2.png)\n\nFor $n \\equiv 1 \\pmod{3}$, consider a nice coloring. For convenience write 0 in each white cell and 1 in each black cell. Then each $2 \\times 2$ square covers numbers with even sum, and each cross covers numbers with odd sum. We need the following observations.\n\na. Consider two squares $2 \\times 2$ sharing one corner cell. The sum of the 8 numbers they cover, which is even, equals $a+b+c$ plus the sum of the numbers in the cross with center $b$, which is odd. It follows that $a+b+c$ is odd. By symmetry this holds for every 3 consecutive diagonal cells, in both directions.\n![](attached_image_3.png)\n\nb. Let 4 consecutive diagonal cells cover the numbers $a$, $b$, $c$, $d$ in this order. By a), $a+b+c$ and $b+c+d$ are odd, hence $a$ and $d$ have the same parity. Because both are 0 or 1, they are in fact equal: $a=d$.\n\nc. We claim that the four corner cells of each $4 \\times 4$ squares contain equal numbers. Let them be $a$, $b$, $c$, $d$, and let central four numbers be $e$, $f$, $g$, $h$ as in the figure. The latter are covered by a $2 \\times 2$ square, hence $e+h$ and $f+g$ have the same parity (their sum is even). By a) the parity of $a$ (respectively $b$) is opposite to the one of $e+h$ (respectively $f+g$). It follows that $a$ and $b$ have the same parity. Hence they are equal. In addition $a=d$ and $b=c$ by b), therefore $a=b=c=d$.\n![](attached_image_4.png)\n\nObservation c) is enough to finish the solution. It implies that the coloring is periodic with period 3, horizontally or vertically. Set $n=3k+1$ and consider the numbers in cells 1, 4, 7, ..., $3k+1=n$ of any row. By c) they are equal, in particular so are the numbers in the first and the last cell. By symmetry, the extremal cells in each column have equal numbers. Consequently the four corner numbers in the table are equal.\n\nIn conclusion the numbers satisfying the condition are $n \\equiv 1 \\pmod{3}$."
]

[
  {
    "bytes": "b'\\x89PNG\\r\\n\\x1a\\n\\x00\\x00\\x00\\rIHDR\\x00\\x00\\x00.\\x00\\x00\\x00-\\x08\\x02\\x00\\x00\\x00^O\\xce\\xce\\x00\\x00\\x02\\xcfIDATx\\x9c\\xdd\\x98?k\\xeaP\\x18\\xc6\\xdf\\xd3STR\\x82h\\x04\\xa7R\\x04\\xff\\x8cv\\x10]:TJ\\x05\\xebl\\xfd\\x04\\n\\xe2\\x17\\xa8\\x9f\\xc0\\xceB+\\xc4\\xad\\x8b\\xe8\\xd4\\xa1\\x16\\xb4U\\x17KI;\\t\\x85b\\xed\\xeeb\\x96\\x8a1\\x15B:\\xa4\\xd7\\xdb\\xf1\\xfa\\xfa\\x82\\xe5>c\\xe0y\\xf2\\xcb\\xc9\\xc9{\\x1e\\xc2L\\xd3|}}m6\\x9b\\xb2,_\\\\\\\\\\x00@\\xa1P\\xc8\\xe5r\\xb1X\\x0c\\x00\\x00\\xa0\\\\.+\\x8a\\x92\\xcb\\xe5\\xae\\xae\\xae~^\\x07\\x00EQ\\x00\\xe0\\xe7\\x95\\x7f\\x97\\xa2(\\xba\\xae/39\\xe7`\\x9af:\\x9df\\x8cm\\xad!\\xc6\\x18\\x00\\xa0C\\x00@\\x14\\xc5m\\x8b\\xf1\\xe4\\xe4\\xa4R\\xa9 \\x1e\\xceR>\\x9fo6\\x9b\\x97\\x97\\x97\\xa9TjU\\xefl6\\x8bD\"\\x00\\xf0\\x8d\"\\x08\\xc2\\xee\\xee.\\x1aE\\x10\\x04\\x00\\x90$\\t\\x112\\x9dN\\xad\\x85\\xd9B\\xdf\\x9e\\\\d(\\xe1px\\x7f\\x7f\\x7f\\x9d\\x042\\x94\\xd1h\\xf4\\xf6\\xf6\\xf6+P\\xe6\\xf3\\xf9|>\\xc7y\\xad\\x0f\\x90\\x0c%\\x1a\\x8dF\\xa3Q\\x84\\xd1\\xe1pd\\xb3YJ\\x14EQ\\xac\\x89\\xb7\\xaat]\\x97e\\x99\\x12\\x05-\\xcey \\x10\\xf8\\x15(\\x82 \\x9c\\x9d\\x9d\\x91\\xa1\\x04\\x02\\x01\\xaf\\xd7\\xeb\\xf1x\\x10^\\xc30F\\xa3\\x11\\x19\\xca\\xde\\xde\\xde\\xd1\\xd1\\xd1\\xe1\\xe1!\\xc2\\xabi\\xda\\xf9\\xf99\\x19\\xca\\xfd\\xfd\\xfd\\xf5\\xf5\\xf5\\xed\\xed-\\xc2K\\xbfW\\x82\\xc1`0\\x18D\\x18\\x89\\xf7\\n\\x00\\xb8\\\\.\\x97\\xcb\\xb5N\\x02\\x19J\\xaf\\xd7\\xeb\\xf5z\\x9bG\\xf1\\xfb\\xfd\\x9cs\\x9c\\xd70\\x8c\\xf7\\xf7w2\\x14\\x9f\\xcf\\xc79\\xb7\\x8e\\x92U\\xa5iZ\\xa9T\"C9>>>88\\xc0\\x9dAK\\xd1\\xa0\\xdc\\xdd\\xdd\\xf5\\xfb}\\xdc\\x19d\\xb7\\xdb3\\x99\\x0c,\\x0b\\xe5d2yxx@\\xa3\\xd4j\\xb5\\xc5b1\\x1c\\x0e\\x11!\\xba\\xae\\xb7Z-\\x00\\xf8n\\xfch\\x08*\\xfdm\\xfc\\x1e\\x8f\\'\\x14\\n\\xa1\\x83\\x86\\xc3\\xe1d2\\t\\x85B\\x88c\\xc80\\x8c\\xe7\\xe7g\\x80?\\xab\\x92N\\xa7\\xcd5d\\xadk\\xa3\\xd1@x?>>DQ\\x14Eq\\xf3%a\\xa9_\\x81B\\xdcm\\xd1\\xa2\\xef\\xb6h\\xd1w[I\\x92p-n\\xa9m\\x12\\x8e\\xd3\\xd3S\\xbb\\xdd\\x1e\\x8f\\xc77\\x8f\\xd2\\xe9t\\xc6\\xe3\\xb1\\xaa\\xaa\\x92$\\xad\\xea\\xe5\\x9c\\xfb\\xfd~2\\x14UU;\\x9dN\\xb7\\xdbE\\x0cnA\\x10\\x8a\\xc5\\xa2i\\x9a\\x9b\\xdf\\xb6\\x96\\xaa\\xd5*\\xe5\\x9f\\x84p8\\x8c0~~~\\xd6\\xebu\\xa7\\xd3I\\xf3\\x82\\x00\\xc0\\xedv#6\\n\\x00,\\x16\\x8bv\\xbb\\r\\xb4\\xdd\\xb6\\xdb\\xed\\xe2\\xbc\\xff\\xef\\xb4e\\x8c\\xe1\\xba\\xad5m\\x19cd(\\xc9d2\\x99L\\xa2\\xed\\xd9l\\x96\\x06%\\x93\\xc9\\xb8\\xdd\\xee\\x9d\\x9d\\x1dt\\x82,\\xcb4(\\x89D\\xc2f\\xb3\\xad\\x19B\\x83R\\xaf\\xd7\\x9f\\x9e\\x9e\\x06\\x83\\xc1:!\\xdfsEU\\xd5\\xc7\\xc7GtJ\\xadV{yy\\xb9\\xb9\\xb9\\xd14mU\\xaf\\xa6i\\x86ap\\xce\\xbf\\x00\\x80\\x0cxJ\\n0\\xd0\\x99\\x00\\x00\\x00\\x00IEND\\xaeB`\\x82'",
    "path": "3._NATIONAL_XXX_OMA_2013_p4_data_57f94955ef.png"
  },
  {
    "bytes": "b'\\x89PNG\\r\\n\\x1a\\n\\x00\\x00\\x00\\rIHDR\\x00\\x00\\x003\\x00\\x00\\x005\\x08\\x02\\x00\\x00\\x00c\\x9aD`\\x00\\x00\\x01\\xe4IDATx\\x9c\\xed\\x98\\xbf\\xca\\xea0\\x18\\x87\\xf3\\xd5\\x8f\\xd6\\xa5B\\xc7\\x80\\x08.\\x1dj\\xa7\\xcc^\\x80\\xd0\\xad\\xd0\\xc1\\xd1+pp\\xf4\\n\\x1c\\x04\\x1d\\xbd\\x82\\x80\\x83\\x0e\\xe2=\\xd4E\\n\\x16\\x1c\\x03\\xde\\x80 T\\x88\\x10r\\x86x\\xfe\\x0c\\xdf\\xd1\\xbc=\\x9cs2\\xe4\\x99\\xda\\xf0\\xcb\\xfb>\\x04\\x02/\\xf9\\x90R\"#q\\xfe\\xb7\\xc0o\\xf9\\xac\\xb1\\xa7\\xaa\\xaa~\\xbf_U\\x95f\\xbe\\xd9lRJ{\\xbd\\x1e\\xac\\x8d\\x84s\\xbb\\xdd|\\xdf\\x07u\\xc9\\xb2\\x0c\\xda\\xa5\\xce\\x99)\\x96\\xcb\\xe5`0x\\x1b;\\x1c\\x0e\\xe3\\xf1\\xb8F\\xfd\\xfaf\\x18\\xe30\\x0c\\xdf\\xc6\\xc20\\xdc\\xedv5\\xea\\x9b{\\x03\\xac\\x19\\x1ck\\x06\\xc7\\x9a\\xc1\\xb1fp\\xac\\x19\\x1cs\\xcd>\\x11B\\x8c\\xb1\\xeb\\xf5\\xaa\\xbf\\xe7~\\xbf\\x0b!\\x18c\\xc7\\xe3Q\\'\\xaf\\x8ak\\x86\\x11B\\x8dF#\\x8ec$\\xa5\\xcc\\xb2L_\\xeb\\x1f\\xe0\\xba\\xeed2yNAA\\x10t\\xbb]\\xcd\\x9dB\\x88\\xb2,;\\x9dN\\x10\\x04:y\\xc6\\x18BH\\xbf>cl>\\x9f?\\xcf\\x0c4s\\xaa\\x99v\\xbd^k\\xe6\\xa1\\xf5)\\xa5\\x9e\\xe7\\x99x\\x03\\x92$q]\\xd7D3\\x855\\x83c\\xa2\\xd9\\xe5r\\x11B\\x98hv:\\x9d\\x0c5\\xb

Argentina

NATIONAL XXX OMA

[
  "Discrete Mathematics > Combinatorics > Coloring schemes, extremal arguments",
  "Discrete Mathematics > Combinatorics > Invariants / monovariants"
]

proof and answer

n ≡ 1 (mod 3)

2

00rl

The point $M$ lies on the side $AB$ of the circumscribed quadrilateral $ABCD$. The points $I_1, I_2$, and $I_3$ are the incenters of $\triangle MBC$, $\triangle MCD$, and $\triangle MDA$. Show that the points $M, I_1, I_2$, and $I_3$ lie on a circle.
![](attached_image_1.png)

[
  "Lemma. Let $I$ be the incenter of $\\triangle ABC$ and let the points $P$ and $Q$ lie on the lines $AB$ and $AC$. Then the points $A, I, P$, and $Q$ lie on a circle if and only if\n$$\n\\overline{BP} + \\overline{CQ} = BC\n$$\nwhere $\\overline{BP}$ equals $|BP|$ if $P$ lies in the ray $BA \\rightarrow$ and $-|BP|$ if it does not, and similarly for $\\overline{CQ}$.\n\n*Proof of the lemma.* We shall only consider the case when $P$ and $Q$ lie in the segments $AB$ and $AC$. All other cases are treated analogously.\n![](attached_image_2.png)\nSuppose that $A, I, P$, and $Q$ lie on a circle. Let $D$ and $E$ be the contact points of the incircle of $\\triangle ABC$ with $AB$ and $AC$. We have that $\\angle PIQ = 180^\\circ - \\alpha$, so $\\angle DIP = \\angle EIQ$ and, therefore, $\\triangle DIP \\simeq \\triangle EIQ$. This gives us $DP = EQ$ and $BP + CQ = BD + CE = BC$, as needed.\nThe converse is established by following the foregoing chain of inequalities in reverse. $\\square$\n\nLet the circumcircle of $\\triangle MI_1I_3$ meet the lines $AB, CM, \\text{ and } DM$ for the second time at $P, Q, \\text{ and } R$. By the lemma, $\\overline{BP}+\\overline{CQ} = \\overline{BC}$ and $\\overline{DR}+\\overline{AP} = \\overline{DA}$. Therefore, $\\overline{CQ}+\\overline{DR} = \\overline{BC}+\\overline{DA}-\\overline{BP}-\\overline{AP} = \\overline{BC}+\\overline{DA}-\\overline{AB}$. Since $ABCD$ is circumscribed, this is equal to $CD$, and, by the lemma, the proof is complete.\n![](attached_image_3.png)",
  "Let $\\omega_1, \\omega_2$, and $\\omega_3$ be the incircles of $\\triangle MBC, \\triangle MCD$, and $\\triangle MDA$. The common internal tangent $t_1$ of $\\omega_1$ and $\\omega_2$ equals $[\\text{tangent from } M \\text{ to } \\omega_2] - [\\text{tangent from } M \\text{ to } \\omega_1] = \\frac{1}{2}(MC + MD - CD - MB - MC + BC)$.\nAnalogously, the common internal tangent $t_2$ of $\\omega_2$ and $\\omega_3$ equals $[\\text{tangent from } M \\text{ to } \\omega_2] - [\\text{tangent from } M \\text{ to } \\omega_3] = \\frac{1}{2}(MC + MD - CD - MD - MA + DA)$.\nFinally, the common external tangent $t_3$ of $\\omega_1$ and $\\omega_3$ equals $[\\text{tangent from } M \\text{ to } \\omega_1] - [\\text{tangent from } M \\text{ to } \\omega_3] = \\frac{1}{2}(MB + MC - BC + MD + MA - DA)$.\nSince $ABCD$ is circumscribed, we have $AB + CD = BC + DA$, and, therefore, $t_1 + t_2 = t_3$. It follows from this that $\\omega_1, \\omega_2$, and $\\omega_3$ have a common tangent $s$ (which separates $\\omega_2$ from $\\omega_1$ and $\\omega_3$).\n![](attached_image_4.png)\nLet $\\triangle MKL$ be the triangle formed by the lines $MC, MD$, and $s$. Then, since $I_1I_2$ and $I_2I_3$ are external angle bisectors in it, we have $\\angle I_1I_2I_3 = 90^\\circ - \\frac{1}{2}\\angle KML = 180^\\circ - \\angle I_1MI_3$ and, therefore, $MI_1I_2I_3$ is cyclic. $\\square$"
]

[
  {
    "bytes": "b'\\x89PNG\\r\\n\\x1a\\n\\x00\\x00\\x00\\rIHDR\\x00\\x00\\x02\\xb8\\x00\\x00\\x01\\xfb\\x08\\x02\\x00\\x00\\x00\\xa8\\x86{\\'\\x00\\x00\\xf3cIDATx\\x9c\\xec\\xddu\\\\T\\xd9\\x17\\x00\\xf03I\\x0c\\xdd\\x08\\x08\\x82\\x82\\x08\\x88\\xdd\\x8dk\\xb7\\x80\\xdd\\x9d\\x08\\xba\\xc6\\xda\\xdd\\x8a\\x8a\\xbak\\xa0\\xa0\\xa2\\x0bv\\xaf\\x8a\\xdd\\xba*- \\xdd\\xdd\\x0c\\x0c\\x13\\xbf?.\\xf3~,\\x02\\x123\\xf3&\\xee\\xf7\\xf3\\xfb\\xe3N\\xbdw\\xd6\\x1f<\\xce\\xdcw\\xef9\\x14\\x81@\\x00\\x18\\x86a\\x18\\x86a5\\xa1\\x92\\x1d\\x00\\x86a\\x18\\x86a\\xd2\\x0b\\'\\n\\x18\\x86a\\x18\\x86\\xd5\\n\\'\\n\\x18\\x86a\\x18\\x86\\xd5\\x8aN\\x8c\\xf8|~EE\\x05\\x89\\xa1`\\x18\\x86a\\x18&m\\xfe\\x9f(\\x08\\x04\\x02\\x1e\\x8fGb(\\x18\\x86a\\x18\\x86I\\x1b|\\xeb\\x01\\xc30\\x0c\\xc3\\xb0Z\\xe1D\\x01\\xc30\\x0c\\xc3\\xb0Z\\xe1D\\x01\\xc30\\x0c\\xc3\\xb0Z\\xe1D\\x01\\xc30\\x0c\\xc3\\xb0Z\\xd1\\x7f\\xfd\\x16\\x0c\\x13\\x8f\\x9b7o>y\\xf2\\xe4\\xc6\\x8d\\x1b\\xa6\\xa6\\xa6NNNT*5???66\\xd6\\xd1\\xd1q\\xcd\\x9a5ZZZd\\x07\\x88a\\x18\\x86\\x01\\x85(\\xe1\\xcc\\xe3\\xf1\\xca\\xcb\\xcb\\xc9\\x8d\\x06S4\\xd9\\xd9\\xd9\\xe6\\xe6\\xe6g\\xce\\x9c\\x994i\\x12z\\x86\\xcdf{xx\\xfc\\xfb\\xef\\xbfO\\x9f>USS#7<\\x0c\\xc30\\x0c\\xdfz\\xc0\\xc8\\xf4\\xef\\xbf\\xff\\x02@\\xcf\\x9e=\\x89gTTT\\xbc\\xbc\\xbcJKK}||\\xc8\\x8b\\x0b\\xc30\\x0c\\xab\\x84\\x13\\x05\\x8cLO\\x9f>\\xb5\\xb4\\xb4l\\xde\\xbcy\\xd5\\'i4Z\\xbf~\\xfd\\xfe\\xf9\\xe7\\x1f\\xb2\\xa2\\xc20\\x0c\\xc3\\x088Q\\xc0\\xc8\\xf4\\xfc\\xf9\\xf3~\\xfd\\xfa\\xfd\\xfc<\\x8dFKOO\\x97x8\\x18\\x86aXu8Q\\xc0H\\x93\\x95\\x95\\x15\\x1a\\x1aZc\\xa2\\x90\\x95\\x95\\xa5\\xae\\xae.\\xf1\\x880\\x0c\\xc3\\xb0\\xeap\\xa2\\x80\\x91\\xe6\\xf9\\xf3\\xe7\\x14\\n\\xa5o\\xdf\\xbe\\xd5\\x9e\\xe7p8/^\\xbc\\xb0\\xb1\\xb1!%*\\x0c\\xc30\\xac*\\xbc=\\x12#\\xcd\\xb3g\\xcf\\xec\\xec\\xec\\xf4\\xf4\\xf4\\xaa=\\xff\\xf8\\xf1\\xe3\\xfc\\xfc\\xfc\\x11#F\\xd4\\xf6\\xc1\\xe4\\xe4\\xe4\\x1b7n|\\xfb\\xf6\\x8d\\xc3\\xe1\\xb4i\\xd3f\\xf4\\xe8\\xd1m\\xda\\xb4\\x11s\\xb0\\x18\\x86a\\n\\no\\x8f\\xc4H\\x83\\xfe\\xc6\\xef\\xde\\xbd\\xbb\\xda\\xf3#G\\x8e\\xcc\\xca\\xcaz\\xfb\\xf6-\\x95Z\\xc3\\x8c\\xd7\\xf1\\xe3\\xc77m\\xdaTVVF<C\\xa1P\\x16-Z\\xb4k\\xd7.\\x06\\x83!\\xde\\x881\\x0c\\xc3\\x14\\x0f\\x9eQ\\xc0\\xc8\\x11\\x1f\\x1f\\x9f\\x90\\x90\\xf0\\xf3\\x02\\x85[\\xb7n}\\xfe\\xfc\\xf9\\xf1\\xe3\\xc75f\\t\\'N\\x9cX\\xbdzu\\xb5\\'\\x05\\x02\\xc1\\x89\\x13\\'rss\\xcf\\x9c9C\\xa1P\\xc4\\x140\\x86a\\x98b\\xc2k\\x140r<}\\xfa\\x94N\\xa7W\\xad\\xa0\\x00\\x00\\x7f\\xff\\xfd\\xf7\\xca\\x95+o\\xdc\\xb8aoo\\xff\\xf3Gbbb\\xfe\\xf8\\xe3\\x0f4\\xee\\xd1\\xa3\\x87\\x8f\\x8f\\x8f\\xbf\\xbf\\xff\\xb8q\\xe3\\xd03W\\xae\\\\\\xb9v\\xed\\x9a\\xb8\\xc3\\xc60\\x0cS4xF\\x01\\x93\\xb4\\xb4\\xb4\\xb4W\\xaf^\\x9d<y\\xd2\\xc0\\xc0\\xe0\\xd1\\xa3G\\xe8\\xc9\\xbc\\xbc\\xbcg\\xcf\\x9e5o\\xde\\xfc\\xfd\\xfb\\xf7?\\xafZ@.\\\\\\xb8PQQ\\x01\\x00\\x03\\x06\\x0c\\xf8\\xe7\\x9f\\x7f\\xe8t:\\x00\\xb8\\xb8\\xb8\\xacZ\\xb5\\xea\\xe0\\xc1\\x83\\x00\\xe0\\xed\\xed\\xed\\xec\\xec,\\xa9\\xff\\x0e\\x0c\\xc30\\x85\\x80\\xd7(`\\x92\\x96\\x96\\x96\\x16\\x11\\x11Q\\xedI55\\xb5\\x0e\\x1d:\\xa0\\xbf\\xfd\\xb5\\x19<x\\xf0\\xeb\\xd7\\xaf\\x01\\xe0\\x9f\\x7f\\xfe\\x194h\\x10\\xf1|nn\\xae\\x9e\\x9e\\x9e@ PSS\\xcb\\xc8\\xc8\\x10G\\xcc\\x18\\x86a\\n\\x0b\\xcf(`\\x92flllll\\xdc\\x88\\x0f\\x16\\x16\\x16\\xa2\\x81\\x89\\x89I\\xd5\\xe7\\xb5\\xb4\\xb4\\x98LfyyyIII\\\\\\\\\\\\\\x8b\\x16-D\\x10%\\x86a\\x18\\x06\\x00x\\x8d\\x02&C\\x88=\\x907n\\xdc\\xa8\\xfa\\xfc\\xb3g\\xcf\\xd0d\\x98@ \\xb0\\xb7\\xb7\\xef\\xd3\\xa7\\xcf\\xb1c\\xc7RSSI\\x08\\x11\\xc30L\\xee\\xe0[\\x0f\\x98\\xcc\\xb8}\\xfb6j2\\xa9\\xa2\\xa2\\xe2\\xe3\\xe3\\xe3\\xe2\\xe2\\x02\\x00\\x1f>|\\x18?~|JJJ\\xb57S(\\x94\\x9e={\\xba\\xb8\\xb8\\x8c\\x193\\xa6\\xb6E\\x0f\\x18\\x86a\\xd8/\\xe1D\\x01\\x93\\x19\\x02\\x81\\xc0\\xc9\\xc9\\xe9\\xc3\\x87\\x0f\\xe8\\xa1\\xbe\\xbe\\xbe\\x92\\x92Rrr2z\\xa8\\xa9\\xa9\\xd9\\xb3g\\xcf\\xa7O\\x9fV-\\xb1\\x00\\x00t:\\xbd_\\xbf~\\x13&L\\x18>|\\xb8\\xa6\\xa6\\xa6\\xa4\\x83\\xc60\\x0c\\x93q8Q\\xc0dIzzz\\xd7\\xae]\\xb3\\xb3\\xb3\\xab=\\xa

Balkan Mathematical Olympiad

BMO 2016 Short List Final

[
  "Geometry > Plane Geometry > Triangles > Triangle centers: centroid, incenter, circumcenter, orthocenter, Euler line, nine-point circle",
  "Geometry > Plane Geometry > Quadrilaterals > Inscribed/circumscribed quadrilaterals",
  "Geometry > Plane Geometry > Circles > Tangents",
  "Geometry > Plane Geometry > Miscellaneous > Angle chasing"
]

proof only

3

021o

Problem:

Amanda desenhou a seguinte figura:
![](attached_image_1.png)
Observe que a soma ao longo de qualquer lado do triângulo acima é sempre a mesma, pois, como podemos verificar,
$$
1+3+6=6+2+2=1+7+2
$$
a) Complete os números que faltam nos círculos da figura abaixo de modo que as somas ao longo de qualquer lado do quadrado sejam sempre as mesmas.
![](attached_image_2.png)
b) Encontre uma maneira de colocar os números nos círculos de maneira que as somas ao longo de qualquer linha sejam sempre as mesmas. Há mais de uma solução?
![](attached_image_3.png)
c) $\mathrm{Na}$ figura abaixo, que foi desenhada apenas parcialmente (por falta de espaço!), também vale que a soma ao longo de cada segmento é sempre a mesma. Entretanto, Amanda apagou todos os números exceto os dois números mostrados na figura (3 e 4). Sabe-se que há 40 círculos no desenho. É possível descobrir quais números estavam nos círculos pintados de cinza claro e cinza escuro?
![](attached_image_4.png)

[
  "Solution:\n\na) Na linha inferior a soma \u00e9 $2+3+5=10$. Como as somas ao longo de qualquer lado s\u00e3o iguais, o n\u00famero que falta no canto superior \u00e0 direita do quadrado deve ser igual a 2, como na figura a seguir:\n![](attached_image_5.png)\nFaltam mais dois n\u00fameros a serem preenchidos. Novamente, como a soma deve ser 10 em qualquer lado, os n\u00fameros que faltam s\u00e3o 1 e 3, como na figura a seguir:\n![](attached_image_6.png)\n\nb) Vamos chamar de $x$ e $y$ os n\u00fameros a serem colocados nos cantos superiores do quadrado, como na figura a seguir:\n![](attached_image_7.png)\nAs somas devem ser constantes ao longo de qualquer lado ou diagonal desenhada. A soma ao longo do lado superior \u00e9 $x+9+y$, logo todas as somas devem ser iguais a $x+9+y$. Observando as somas ao longo dos lados verticais, deduzimos que os cantos inferiores devem ser iguais a $y-6$ e $x+3$, como na figura a seguir:\n![](attached_image_8.png)\nFalta verificar a soma ao longo da diagonal desenhada e do lado horizontal inferior. A soma ao longo do lado horizontal inferior \u00e9 igual a\n$$\n(y-6)+12+(x+3)=x+9+y\n$$\nverificando a soma desejada. Verificando a soma ao longo da diagonal desenhada, obtemos\n$$\nx+17+(x+3)=x+9+y\n$$\nde onde conclu\u00edmos que $y=x+11$. Logo, qualquer solu\u00e7\u00e3o ser\u00e1 da forma\n![](attached_image_9.png)\nComo o valor de $x$ ainda n\u00e3o foi fixado, podemos obter muitas solu\u00e7\u00f5es! Por exemplo, tomando $x=0$, obtemos a solu\u00e7\u00e3o:\n![](attached_image_10.png)\n\nc) Chamemos de $x$ e $y$ os n\u00fameros vizinhos aos n\u00fameros 3 e 4, como na figura a seguir:\n![](attached_image_11.png)\nComo a soma ao longo de cada segmento \u00e9 constante, os dois pr\u00f3ximos n\u00fameros devem ser iguais a 3 e 4:\n![](attached_image_12.png)\nComo h\u00e1 40 c\u00edrculos no desenho, h\u00e1 20 c\u00edrculos na linha de cima e 20 c\u00edrculos na linha de baixo. Continuando o processo acima, vamos obter:\n![](attached_image_13.png)\nObserve $\\mathrm{o}\\ x$ no canto superior mais \u00e0 direita. Este $x$ est\u00e1 ligado ao $4\\ \\mathrm{e}$ ao $y$. Como $x+4=x+y$, conclu\u00edmos que $y=4$. Logo, os n\u00fameros nos dois c\u00edrculos cinza s\u00e3o iguais a 4."
]

[
  {
    "bytes": "b'\\xff\\xd8\\xff\\xdb\\x00\\x84\\x00\\x08\\x06\\x06\\x07\\x06\\x05\\x08\\x07\\x07\\x07\\t\\t\\x08\\n\\x0c\\x14\\r\\x0c\\x0b\\x0b\\x0c\\x19\\x12\\x13\\x0f\\x14\\x1d\\x1a\\x1f\\x1e\\x1d\\x1a\\x1c\\x1c $.\\' \",#\\x1c\\x1c(7),01444\\x1f\\'9=82<.342\\x01\\t\\t\\t\\x0c\\x0b\\x0c\\x18\\r\\r\\x182!\\x1c!22222222222222222222222222222222222222222222222222\\xff\\xc0\\x00\\x11\\x08\\x01g\\x01\\x9a\\x03\\x01\"\\x00\\x02\\x11\\x01\\x03\\x11\\x01\\xff\\xc4\\x01\\xa2\\x00\\x00\\x01\\x05\\x01\\x01\\x01\\x01\\x01\\x01\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x01\\x02\\x03\\x04\\x05\\x06\\x07\\x08\\t\\n\\x0b\\x10\\x00\\x02\\x01\\x03\\x03\\x02\\x04\\x03\\x05\\x05\\x04\\x04\\x00\\x00\\x01}\\x01\\x02\\x03\\x00\\x04\\x11\\x05\\x12!1A\\x06\\x13Qa\\x07\"q\\x142\\x81\\x91\\xa1\\x08#B\\xb1\\xc1\\x15R\\xd1\\xf0$3br\\x82\\t\\n\\x16\\x17\\x18\\x19\\x1a%&\\'()*456789:CDEFGHIJSTUVWXYZcdefghijstuvwxyz\\x83\\x84\\x85\\x86\\x87\\x88\\x89\\x8a\\x92\\x93\\x94\\x95\\x96\\x97\\x98\\x99\\x9a\\xa2\\xa3\\xa4\\xa5\\xa6\\xa7\\xa8\\xa9\\xaa\\xb2\\xb3\\xb4\\xb5\\xb6\\xb7\\xb8\\xb9\\xba\\xc2\\xc3\\xc4\\xc5\\xc6\\xc7\\xc8\\xc9\\xca\\xd2\\xd3\\xd4\\xd5\\xd6\\xd7\\xd8\\xd9\\xda\\xe1\\xe2\\xe3\\xe4\\xe5\\xe6\\xe7\\xe8\\xe9\\xea\\xf1\\xf2\\xf3\\xf4\\xf5\\xf6\\xf7\\xf8\\xf9\\xfa\\x01\\x00\\x03\\x01\\x01\\x01\\x01\\x01\\x01\\x01\\x01\\x01\\x00\\x00\\x00\\x00\\x00\\x00\\x01\\x02\\x03\\x04\\x05\\x06\\x07\\x08\\t\\n\\x0b\\x11\\x00\\x02\\x01\\x02\\x04\\x04\\x03\\x04\\x07\\x05\\x04\\x04\\x00\\x01\\x02w\\x00\\x01\\x02\\x03\\x11\\x04\\x05!1\\x06\\x12AQ\\x07aq\\x13\"2\\x81\\x08\\x14B\\x91\\xa1\\xb1\\xc1\\t#3R\\xf0\\x15br\\xd1\\n\\x16$4\\xe1%\\xf1\\x17\\x18\\x19\\x1a&\\'()*56789:CDEFGHIJSTUVWXYZcdefghijstuvwxyz\\x82\\x83\\x84\\x85\\x86\\x87\\x88\\x89\\x8a\\x92\\x93\\x94\\x95\\x96\\x97\\x98\\x99\\x9a\\xa2\\xa3\\xa4\\xa5\\xa6\\xa7\\xa8\\xa9\\xaa\\xb2\\xb3\\xb4\\xb5\\xb6\\xb7\\xb8\\xb9\\xba\\xc2\\xc3\\xc4\\xc5\\xc6\\xc7\\xc8\\xc9\\xca\\xd2\\xd3\\xd4\\xd5\\xd6\\xd7\\xd8\\xd9\\xda\\xe2\\xe3\\xe4\\xe5\\xe6\\xe7\\xe8\\xe9\\xea\\xf2\\xf3\\xf4\\xf5\\xf6\\xf7\\xf8\\xf9\\xfa\\xff\\xda\\x00\\x0c\\x03\\x01\\x00\\x02\\x11\\x03\\x11\\x00?\\x00\\xf7\\xfa(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xac\\xedg\\\\\\xd3<?`\\xd7\\xda\\xb5\\xf4\\x16v\\xeaq\\xbeg\\xc6O\\\\\\x01\\xdc\\xf1\\xd0s@\\x1a4W\\x91?\\xc6[\\xedrv\\xb7\\xf0O\\x84u\\r[\\x0cT\\xddL<\\xb8\\x81\\xed\\xd3=\\x7f\\xdae\\xfaSO\\x88~6\\xb3\\x17_\\x07h\\xca\\x9f\\xc2\\x86e$\\x8f\\xfb\\xff\\x00\\xd7\\xfc\\xe2\\x80=~\\x8a\\xf2\\x03\\xf1s\\xc4^\\x1c\\x93\\x1e4\\xf0M\\xe5\\x9d\\xbf{\\xbb6\\xf3#\\x1e\\x9d~S\\xff\\x00}\\xfe\\x15\\xe8~\\x1c\\xf1f\\x89\\xe2\\xcb#u\\xa2\\xea\\x11\\\\\\xa8\\xc6\\xf4\\xe8\\xf1\\x93\\xd9\\x94\\xf2;\\xfeF\\x807(\\xa4\\x14\\xb4\\x00QE\\x14\\x00QE\\x14\\x00QE\\x14\\x00QE\\x14\\x00QE\\x14\\x00QE\\x14\\x00QE\\x14\\x00QE\\x14\\x00QE\\x14\\x00QE\\x14\\x00QE\\x14\\x00QE\\x14\\x00QE\\x14\\x00QE\\x14\\x00QE\\x14\\x00QE\\x14\\x00QE\\x14\\x00QE\\x14\\x00QE\\x14\\x00QE\\x14\\x00QE\\x14\\x00QE!\\xa0\\x0c?\\x17\\xf8\\xa3N\\xf0\\x7f\\x87\\xe6\\xd5\\xf5\\'\\xc4q\\xfc\\xb1\\xc6\\x0f\\xcd,\\x87\\xee\\xa2\\xfb\\x9f\\xd0\\x02{W\\x98\\xf8_\\xc0\\xfa\\x9f\\xc4[\\xe8\\xbc]\\xe3\\xe7w\\xb5pZ\\xc3I\\x19TD=\\t\\x1dB\\x9c\\x0fv\\xe0\\x93\\x8e\\x0c\\x9a\\xf4\\'\\xe2\\x1f\\xc6\\xcbo\\x0f\\xcewh\\xbe\\x1e\\x88\\\\\\xdcG\\x8c\\xac\\xb2\\x9d\\xa7\\x07\\xb1\\xea\\xa0\\x83\\xd8?\\xad{*\\x0c\\x0e\\x98\\xa0\\x08\\xac\\xed\\xa0\\xb4\\xb5\\x8e\\xde\\xd6\\x08\\xe0\\x821\\x84\\x8e%\\n\\x8a=\\x00\\x1c\\x01S\\xd6\\x17\\x8bu\\xdb\\xcf\\x0e\\xe8\\xbfn\\xb0\\xd1nu\\x8b\\x8f1c[Kl\\xee9\\xef\\xc0<\\x0f\\xa5p~\\x1f\\xf8\\x97\\xe2{\\xdf\\x88\\xbaw\\x86u\\xcf\\x0eA\\xa5\\x0b\\xc8\\x9e`\\xa6B\\xf2\\x04\\x08\\xec\\x0ezuC\\xda\\x80=ZTY\\x10\\xa3\\x80\\xca\\xc3\\x04\\x11\\xc1\\x1e\\x86\\xbc\\x97\\xc5\\xff\\x00\\x0b\\xe7\\xd2\\xaf?\\xe1)\\xf8~\\xed\\xa6\\xea\\xf6\\xea\\xcf-\\xa4C\\xf7w+\\xd4\\xaa\\xaf@N>\\xee6\\x9f@z\\xfa\\xe2\\xfdsA\\xa0\\x0eG\\xe1\

Brazil

[
  "Algebra > Prealgebra / Basic Algebra > Simple Equations"
]

proof and answer

a) The top-right corner is 2; the remaining missing numbers are 1 and 3, yielding equal sums of 10 along each side. b) Let the two top corners be x and y; all sums equal x plus nine plus y, and consistency forces y = x plus eleven, with bottom corners y minus six and x plus three, giving infinitely many solutions parameterized by x. c) Both highlighted gray circles have the value 4.

4

03nj

Problem:
A circle is inscribed in a rhombus $A B C D$. Points $P$ and $Q$ vary on line segments $\overline{A B}$ and $\overline{A D}$, respectively, so that $\overline{P Q}$ is tangent to the circle. Show that for all such line segments $\overline{P Q}$, the area of triangle $C P Q$ is constant.

![](attached_image_1.png)

[
  "Solution:\nLet the circle be tangent to $\\overline{P Q}$, $\\overline{A B}$, $\\overline{A D}$ at $T$, $U$, and $V$, respectively. Let $p = P T = P U$ and $q = Q T = Q V$. Let $a = A U = A V$ and $b = B U = D V$. Then the side length of the rhombus is $a + b$.\n\n![](attached_image_2.png)\n\nLet $\\theta = \\angle B A D$, so $\\angle A B C = \\angle A D C = 180^{\\circ} - \\theta$. Then (using the notation $[XYZ]$ for the area of a triangle of vertices $X, Y, Z$)\n$$\n\\begin{aligned}\n& [A P Q] = \\frac{1}{2} \\cdot A P \\cdot A Q \\cdot \\sin \\theta = \\frac{1}{2}(a-p)(a-q) \\sin \\theta \\\\\n& [B C P] = \\frac{1}{2} \\cdot B P \\cdot B C \\cdot \\sin (180^{\\circ} - \\theta) = \\frac{1}{2}(b+p)(a+b) \\sin \\theta \\\\\n& [C D Q] = \\frac{1}{2} \\cdot D Q \\cdot C D \\cdot \\sin (180^{\\circ} - \\theta) = \\frac{1}{2}(b+q)(a+b) \\sin \\theta\n\\end{aligned}\n$$\nSo\n$$\n\\begin{aligned}\n[C P Q] & = [A B C D] - [A P Q] - [B C P] - [C D Q] \\\\\n& = (a+b)^2 \\sin \\theta - \\frac{1}{2}(a-p)(a-q) \\sin \\theta - \\frac{1}{2}(b+p)(a+b) \\sin \\theta - \\frac{1}{2}(b+q)(a+b) \\sin \\theta \\\\\n& = \\frac{1}{2}\\left(a^2 + 2 a b - b p - b q - p q\\right) \\sin \\theta\n\\end{aligned}\n$$\nLet $O$ be the center of the circle, and let $r$ be the radius of the circle. Let $x = \\angle T O P = \\angle U O P$ and $y = \\angle T O Q = \\angle V O Q$. Then $\\tan x = \\frac{p}{r}$ and $\\tan y = \\frac{q}{r}$.\n\n![](attached_image_3.png)\n\nNote that $\\angle U O V = 2x + 2y$, so $\\angle A O U = x + y$. Also, $\\angle A O B = 90^{\\circ}$, so $\\angle O B U = x + y$. Therefore,\n$$\n\\tan (x + y) = \\frac{a}{r} = \\frac{r}{b}\n$$\nso $r^2 = a b$. But\n$$\n\\frac{r}{b} = \\tan (x + y) = \\frac{\\tan x + \\tan y}{1 - \\tan x \\tan y} = \\frac{\\frac{p}{r} + \\frac{q}{r}}{1 - \\frac{p}{r} \\cdot \\frac{q}{r}} = \\frac{r(p+q)}{r^2 - p q} = \\frac{r(p+q)}{a b - p q}.\n$$\nHence, $a b - p q = b p + b q$, so $b p + b q + p q = a b$. Therefore,\n$$\n[C P Q] = \\frac{1}{2}\\left(a^2 + 2 a b - b p - b q - p q\\right) \\sin \\theta = \\frac{1}{2}\\left(a^2 + a b\\right) \\sin \\theta\n$$\nwhich is constant.",
  "Solution:\nAlternate Solution: Let $O$ be the center of the circle and $r$ its radius. Then $[C P Q] = [C D Q P B] - [C D Q] - [C B P]$, where $[\\ldots]$ denotes area of the polygon with given vertices. Note that $[C D Q P B]$ is half $r$ times the perimeter of $C D Q P B$. Note that the heights of $C D Q$ and $C B P$ are $2 r$ so $[C D Q] = r \\cdot D Q$ and $[C B P] = r \\cdot P B$. Using the fact that $Q T = Q V$ and $P U = P T$, it now follows that $[C P Q] = [O V D C B U] - [C D V] - [C B U]$, which is independent of $P$ and $Q$."
]

[
  {
    "bytes": "b'\\xff\\xd8\\xff\\xdb\\x00\\x84\\x00\\x08\\x06\\x06\\x07\\x06\\x05\\x08\\x07\\x07\\x07\\t\\t\\x08\\n\\x0c\\x14\\r\\x0c\\x0b\\x0b\\x0c\\x19\\x12\\x13\\x0f\\x14\\x1d\\x1a\\x1f\\x1e\\x1d\\x1a\\x1c\\x1c $.\\' \",#\\x1c\\x1c(7),01444\\x1f\\'9=82<.342\\x01\\t\\t\\t\\x0c\\x0b\\x0c\\x18\\r\\r\\x182!\\x1c!22222222222222222222222222222222222222222222222222\\xff\\xc0\\x00\\x11\\x08\\x026\\x02\\xff\\x03\\x01\"\\x00\\x02\\x11\\x01\\x03\\x11\\x01\\xff\\xc4\\x01\\xa2\\x00\\x00\\x01\\x05\\x01\\x01\\x01\\x01\\x01\\x01\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x01\\x02\\x03\\x04\\x05\\x06\\x07\\x08\\t\\n\\x0b\\x10\\x00\\x02\\x01\\x03\\x03\\x02\\x04\\x03\\x05\\x05\\x04\\x04\\x00\\x00\\x01}\\x01\\x02\\x03\\x00\\x04\\x11\\x05\\x12!1A\\x06\\x13Qa\\x07\"q\\x142\\x81\\x91\\xa1\\x08#B\\xb1\\xc1\\x15R\\xd1\\xf0$3br\\x82\\t\\n\\x16\\x17\\x18\\x19\\x1a%&\\'()*456789:CDEFGHIJSTUVWXYZcdefghijstuvwxyz\\x83\\x84\\x85\\x86\\x87\\x88\\x89\\x8a\\x92\\x93\\x94\\x95\\x96\\x97\\x98\\x99\\x9a\\xa2\\xa3\\xa4\\xa5\\xa6\\xa7\\xa8\\xa9\\xaa\\xb2\\xb3\\xb4\\xb5\\xb6\\xb7\\xb8\\xb9\\xba\\xc2\\xc3\\xc4\\xc5\\xc6\\xc7\\xc8\\xc9\\xca\\xd2\\xd3\\xd4\\xd5\\xd6\\xd7\\xd8\\xd9\\xda\\xe1\\xe2\\xe3\\xe4\\xe5\\xe6\\xe7\\xe8\\xe9\\xea\\xf1\\xf2\\xf3\\xf4\\xf5\\xf6\\xf7\\xf8\\xf9\\xfa\\x01\\x00\\x03\\x01\\x01\\x01\\x01\\x01\\x01\\x01\\x01\\x01\\x00\\x00\\x00\\x00\\x00\\x00\\x01\\x02\\x03\\x04\\x05\\x06\\x07\\x08\\t\\n\\x0b\\x11\\x00\\x02\\x01\\x02\\x04\\x04\\x03\\x04\\x07\\x05\\x04\\x04\\x00\\x01\\x02w\\x00\\x01\\x02\\x03\\x11\\x04\\x05!1\\x06\\x12AQ\\x07aq\\x13\"2\\x81\\x08\\x14B\\x91\\xa1\\xb1\\xc1\\t#3R\\xf0\\x15br\\xd1\\n\\x16$4\\xe1%\\xf1\\x17\\x18\\x19\\x1a&\\'()*56789:CDEFGHIJSTUVWXYZcdefghijstuvwxyz\\x82\\x83\\x84\\x85\\x86\\x87\\x88\\x89\\x8a\\x92\\x93\\x94\\x95\\x96\\x97\\x98\\x99\\x9a\\xa2\\xa3\\xa4\\xa5\\xa6\\xa7\\xa8\\xa9\\xaa\\xb2\\xb3\\xb4\\xb5\\xb6\\xb7\\xb8\\xb9\\xba\\xc2\\xc3\\xc4\\xc5\\xc6\\xc7\\xc8\\xc9\\xca\\xd2\\xd3\\xd4\\xd5\\xd6\\xd7\\xd8\\xd9\\xda\\xe2\\xe3\\xe4\\xe5\\xe6\\xe7\\xe8\\xe9\\xea\\xf2\\xf3\\xf4\\xf5\\xf6\\xf7\\xf8\\xf9\\xfa\\xff\\xda\\x00\\x0c\\x03\\x01\\x00\\x02\\x11\\x03\\x11\\x00?\\x00\\xf7\\xfa(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\nL\\xd2\\xd7\\x92x\\xa7\\xc4\\xfe4\\xd1|{\\xa2xj\\xc7W\\xd3\\xae$\\xd5[v[O*m\\xd3v3\\xfe\\xb0\\xee\\xe01\\xed\\xf7h\\x03\\xd6\\xb3A8\\xeb\\xc5r\\xef\\xa4\\xf8\\xcbi\\xd9\\xe2\\xab\\r\\xdd\\xb7i\\x1c\\x7f\\xe8\\xea\\xc9\\xb3\\xf1\\x9e\\xab\\xa3x\\xae\\xd7\\xc3\\x9e/\\xb6\\xb4\\x8aK\\xfc\\x8b\\rF\\xc8\\xb0\\x82v\\xce6\\x15c\\x94n@\\xeay#\\xd4\\x12\\x01\\xdf\\xd1Fh\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x934\\x8d\"\\xa2\\xee$\\x01\\x8c\\xe4\\x9c{\\xd7\\x04<k\\xa8\\xf8\\xa3S\\x9fN\\xf0U\\xb5\\xbc\\xd6\\xf6\\xd2yw:\\xc5\\xd8&\\xd9\\x1b\\xba\\xc6\\xa3\\x06V\\xf7\\x04\\x0f\\xc0\\x82@;\\xed\\xd4\\x9b\\xf1\\xd4b\\xb9\\x98\\xbc7\\xe2\\x00\\xa2I\\xbck~\\xf7\\x00q\\xb2\\xca\\xd9a\\xff\\x00\\xbe<\\xb2\\xd8\\xff\\x00\\x81\\xe7\\xde\\xb9\\xa9\\xfcq\\xac\\x9f\\x1bh\\xfe\\n6\\xcb\\x0e\\xa8g\\xf3/\\xaf#O\\xdc\\xc9l\\x8b\\xbf1\\x83\\x927\\x80T\\x83\\x9d\\xa7p\\x04\\x9f\\x98\\x00zm\\x14Q@\\x05\\x14Q@\\x05\\x14Q@\\x05\\x14Q@\\x05\\x14Q@\\x05\\x14Q@\\x05\\x14Q@\\x05\\x14Q@\\x05\\x14Q@\\x05\\x14Q@\\x05\\x14Q@\\x05\\x14Q@\\x05x\\xde\\x87\\xff\\x00\\x157\\xed\\x1b\\xac\\xea?z\\xdfB\\xb4\\xfb4L?\\x85\\xf0\\x14\\x8f\\xcd\\xa6\\xfc\\xab\\xd6\\xef\\xefb\\xd3\\xb4\\xeb\\x9b\\xd9\\xce!\\xb7\\x89\\xe6s\\xe8\\xaa2\\x7fA^Y\\xf0\\x12\\xceY|=\\xacx\\x8a\\xe8\\

Canada

Canadian Mathematical Olympiad

[
  "Geometry > Plane Geometry > Circles > Tangents",
  "Geometry > Plane Geometry > Quadrilaterals > Inscribed/circumscribed quadrilaterals",
  "Geometry > Plane Geometry > Triangles > Triangle trigonometry",
  "Geometry > Plane Geometry > Analytic / Coordinate Methods > Trigonometry",
  "Geometry > Plane Geometry > Miscellaneous > Angle chasing"
]

proof only

5

03qq

Define a hook to be a figure made up of six unit squares as shown in the diagram or any of the figures obtained by applying rotations and reflections to this figure.
![](attached_image_1.png)
Determine all $m \times n$ rectangles that can be covered with hooks so that
* the rectangle is covered without gaps and without overlaps;
* no part of a hook covers area outside the rectangle.

[
  "$m$ and $n$ should be the positive integers and should satisfy one of the following conditions:\n\n(1) $3 \\mid m$ and $4 \\mid n$ (or vice versa);\n(2) one of $m$ and $n$ is divisible by $12$ and one is not less than $7$.\n\nA figure is obtained by applying rotations and reflections to another figure. We regard the two figures as equivalent.\nLabel the six unit squares of the hook as shown below. The shaded square must belong to another hook, and it is adjacent to only one square of this other hook. Then the only possibility of the shaded square is $1$ or $6$.\n\n(i) If it is $6$, two hooks form a $3 \\times 4$ rectangle. We call it $\\mathbf{(1)}$.\n![](attached_image_2.png)\n(ii) If it is $1$, there are two cases.\nIt is easy to see that the shaded square cannot be covered in the first diagram as shown below. Hence the latter is true. We call it $\\mathbf{(2)}$.\n![](attached_image_3.png)\n\nThus, in a tessellation, all hooks are matched into pairs. Each pair forms $\\mathbf{(1)}$ or $\\mathbf{(2)}$.\n$\\mathbf{(1)}$\nThere are $12$ squares in $\\mathbf{(1)}$ and $\\mathbf{(2)}$. Hence $12 \\mid m n$.\n![](attached_image_4.png)\n$\\mathbf{(2)}$\n\nNow we consider three cases, separately.\n\n(1) $3 \\mid m$ and $4 \\mid n$ (or vice versa)\nWithout loss of generality, we may assume $m = 3m_0$ and $n = 4n_0$.\nThen $m_0 n_0$ rectangles of the type $\\mathbf{(1)}$ form an $m_0 \\times n_0$ rectangle. Since two hooks cover a $3 \\times 4$ rectangle, an $m \\times n$ rectangle can be covered with hooks.\n\n(2) $12 \\mid m$ or $12 \\mid n$. Without loss of generality, we may assume $12 \\mid m$.\nIf $3 \\mid n$ or $4 \\mid n$, the question reduces to (1).\nAssume that $n$ is not divisible by $3$ nor by $4$. If a tessellation exists, then there is at least one of $\\mathbf{(1)}$ and $\\mathbf{(2)}$ in it, so $n \\ge 3$. Hence $n \\ge 5$ because $3 \\times n$ and $4 \\times n$. Since the square at the corners can belong to either $\\mathbf{(1)}$ or $\\mathbf{(2)}$, it follows from $n \\ge 5$ that the squares at the adjacent corners cannot belong to the same type $\\mathbf{(1)}$ or $\\mathbf{(2)}$. Hence $n \\ge 6$. Since $n$ is not divisible by $3$ and $4$, $n \\ge 7$.\n\n(3) $12 \\mid m n$, but neither $m$ nor $n$ is divisible by $4$. Now $2 \\mid m$, $2 \\mid n$. We may assume without loss of generality that $m = 6m_0$, $n = 2n_0$, neither $m_0$ nor $n_0$ is divisible by $2$. We will prove that if these conditions are satisfied, an $m \\times n$ rectangle cannot be covered with hooks.\nConsider coloring the columns of an $m \\times n$ matrix with black and white colors alternately. Then the number of the black squares equals that of the white ones. One $\\mathbf{(2)}$ always covers $6$ black squares. A horizontal $\\mathbf{(1)}$ always covers $6$ black squares. A vertical $\\mathbf{(1)}$ covers either $8$ black squares and $4$ white ones, or $4$ black squares and $8$ white ones. Since the number of the black squares equals that of the white ones, the number of $\\mathbf{(1)}$ is the same in the preceding two cases. Hence the total number of a vertical $\\mathbf{(1)}$ is even. Using the same argument as above (coloring the rows alternately), we obtain that the total number of a horizontal $\\mathbf{(1)}$ is even.\nConsider classifying the squares of the $m \\times n$ rectangle into $4$ types marked $1$, $2$, $3$, and $4$ as shown below. The number of squares of each type is equal to $\\frac{m n}{4}$.\n![](attached_image_5.png)\nFrom the two diagrams,\n![](attached_image_6.png)\n![](attached_image_7.png)\nwe obtain that the number of $a$ and $c$ covered by $\\mathbf{(1)}$ is the same, so is for $b$ and $d$. Hence the number of squares of type $1$ covered by $\\mathbf{(1)}$ equals that of type $3$.\n![](attached_image_8.png)\n(i)\n![](attached_image_9.png)\n(ii)\n![](attached_image_10.png)\n(iii)\n![](attached_image_11.png)\n(iv)\nThe number of squares of type $1$ covered by (i) or (ii) equals that of type $3$. The difference be

[
  {
    "bytes": "b'\\x89PNG\\r\\n\\x1a\\n\\x00\\x00\\x00\\rIHDR\\x00\\x00\\x00\\x88\\x00\\x00\\x00\\x86\\x08\\x02\\x00\\x00\\x00\\x89\\xd2Uu\\x00\\x00\\x02\\xdaIDATx\\x9c\\xed\\xdc1K#m\\x18F\\xe1\\xc7E\\x051]0\\xb5\\x88\\x8d\\x82?@\\xec\\xac\\xb4\\xd3^\\xd2\\xa7\\x15{\\x7fA\\xc0R[I\\xa9\\xb5\\x88\\xb5E\\x8a\\x08\\x82\\xa000`\\xa71v\\x03V:[\\xcc\\xc7\\x97\\xb0,\\xdb>\\xa78W\\x11H579\\xbc\\x99jf\\xae\\xae\\xeb\\x88h>\\xc51\\x1f\\x11\\x93\\xc9\\xa4\\xd7\\xeb=<<d\\x8f\\xd1\\x7f\\xda\\xed\\xf6|D\\xdc\\xdc\\xdc\\\\]]E\\xc4\\xdc\\xdc\\\\\\xe2\\x9a\\xe6\\xd4\\xba\\xa1\\xae\\xeb\\xaa\\xaa\\xe6\\xff\\xff~pp\\xd0\\xef\\xf7\\xb3\\xd6\\xdc\\xdf\\xdfw\\xbb\\xdd\\xed\\xed\\xed\\xc1`\\x90\\xb5\\xa1(\\x8a\\xbd\\xbd\\xbd\\xf5\\xf5\\xf5\\xdb\\xdb\\xdb\\xac\\r\\x93\\xc9dgg\\'\\x9a\\xbf\\xb2F\\xab\\xd5Z[[\\xcb\\x1aT\\x96eD,--%n\\xf8\\xfa\\xfa\\x8a\\x88\\xc5\\xc5\\xc5\\xc4\\r\\xcb\\xcb\\xcb\\xcdy\\xfd\\x95\\xb5@\\xfff\\x18(\\xc3@\\x19\\x06\\xca0P\\x86\\x812\\x0c\\x94a\\xa0\\x0c\\x03e\\x18(\\xc3@\\x19\\x06\\xca0P\\x86\\x812\\x0c\\x94a\\xa0\\x0c\\x03e\\x18(\\xc3@\\x19\\x06\\xca0P\\x86\\x812\\x0c\\x94a\\xa0\\x0c\\x03e\\x18(\\xc3@\\x19\\x06\\xca0P\\x86\\x812\\x0c\\x94a\\xa0\\x0c\\x03e\\x18(\\xc3@\\x19\\x06\\xca0P\\x86\\x812\\x0c\\xd4\\xf49\\xff\\xc7\\xc7\\xc7\\xd3\\xd3\\xd3\\xac\\x1d\\xcds\\xfeeY&n\\x18\\x8f\\xc7\\x11\\xf1\\xf1\\xf1\\x91\\xb8\\xa1\\xaa\\xaa\\xef\\xef\\xef\\x88\\x88\\xba\\xae///\\xb3v\\xe8\\xaf:\\x9d\\xce\\xf4\\xc4lmm\\x1d\\x1e\\x1efM)\\xcbr0\\x18\\xac\\xae\\xaev\\xbb\\xdd\\xac\\r\\xe3\\xf1\\xf8\\xfc\\xfc|ee\\xa5\\xd7\\xebem\\xa8\\xaa\\xea\\xec\\xec,b\\xe6\\xc4\\x1c\\x1d\\x1d\\xd5y\\xee\\xee\\xee\"bww7q\\xc3\\xd3\\xd3SDlnn&nx{{[XX\\xe8t:\\xde\\xfc\\xa1\\x0c\\x03e\\x18(\\xc3@\\x19\\x06\\xca0P\\x86\\x812\\x0c\\x94a\\xa0\\x0c\\x03e\\x18(\\xc3@\\x19\\x06\\xca0P\\x86\\x812\\x0c\\x94a\\xa0\\x0c\\x03e\\x18(\\xc3@\\x19\\x06\\xca0P\\x86\\x812\\x0c\\x94a\\xa0\\x0c\\x03e\\x18(\\xc3@\\x19\\x06\\xca0P\\x86\\x812\\x0c\\x94a\\xa0\\x0c\\x03e\\x18(\\xc3@\\x19\\x06\\xca0P\\x86\\x812\\x0c\\xd4\\xf4\\xcd\\x18\\xcf\\xcf\\xcf\\xfd~?kGQ\\x14Y\\x97\\xfe\\xc3\\xe7\\xe7g\\xe2\\xefPU\\xd5\\xcf\\xcfO\\xcc\\x86\\x19\\x8dF\\xa3\\xd1(k\\x10\\xc7\\xfb\\xfb\\xfb\\xc9\\xc9I\\xf6\\x8a\\x990\\x1b\\x1b\\x1b\\xfb\\xfb\\xfbY;^__\\xaf\\xaf\\xaf\\xb3\\xae\\xdeh\\xb7\\xdb\\xc7\\xc7\\xc7\\xb9\\x1b\\x1a\\xadV\\xcbw\\xc9@y\\xf3\\x872\\x0c\\x94a\\xa0\\x0c\\x03e\\x18(\\xc3@\\x19\\x06\\xca0P\\x86\\x812\\x0c\\x94a\\xa0\\x0c\\x03e\\x18(\\xc3@\\x19\\x06\\xca0P\\x86\\x812\\x0c\\x94a\\xa0\\x0c\\x03e\\x18(\\xc3@\\x19\\x06\\xca0P\\x86\\x812\\x0c\\x94a\\xa0\\x0c\\x03e\\x18(\\xc3@\\x19\\x06\\xca0P\\x86\\x812\\x0c\\x94a\\xa0\\x0c\\x03e\\x18(\\xc3@\\x19\\x06\\xca0P\\xd37c\\x14Eqqq\\x91\\xb5\\xe3\\xe5\\xe5%\\xeb\\xd2L\\xd30\\xc3\\xe1p8\\x1c&N\\xd1\\xac\\xdf\\xe2\"\\x9b\\xd5T\\xd9RV\\x00\\x00\\x00\\x00IEND\\xaeB`\\x82'",
    "path": "Bin_Yee_Mathematical_Olympiad_in_China_Problems_and_Solutions_p238_data_ddb5d122aa.png"
  },
  {
    "bytes": "b'\\x89PNG\\r\\n\\x1a\\n\\x00\\x00\\x00\\rIHDR\\x00\\x00\\x00\\x88\\x00\\x00\\x00\\x87\\x08\\x02\\x00\\x00\\x00B\\x8e\\x86\\xd0\\x00\\x00\\x17\\xf2IDATx\\x9c\\xed]y\\\\SW\\xf6\\xbf!\\xecZ\\xea\\xa8\\xe8T\\n\\x08\\xd5\\n\\x0cQ\\xf8\\xa8\\xb4\\x08.(\\ne\\xdf\\x14,j\\x81*XEDE\\x05QAq+\\xb2\\xc8\\xf8Qf>\\x85\\x82,B\\x95\\xc5\\r\\x14t\\x1c\\x11D);\\x082-\\x16\\xac(\\x01\\xc2\\x12\\x92\\xb0$/y\\xbf?\\xee\\xf4\\xfd\\xaeO\\xdb\\x81\\x04\\xc9\\x9b\\xcf\\xbc\\xef_prr\\xeey\\xf9\\xe6\\xdcs\\xef\\xb9\\xe7\\xbd0p\\x1c\\x074\\xa8\\x07E\\xe2/6\\x9b=44$GWh\\xa0\\xf871\\xcd\\xcd\\xcd\\x1b6lhnn\\x96\\xaf74\\x08\\xfc\\x9b\\x98\\xea\\xea\\xea\\xa6\\xa6\\xa6\\xa9S\\xa7\\xce\\x9a5K^\\xae\\x0c\\x0f\\x0fwvv\\xaa\\xa9\\xa9}\\xf4\\xd1G\\xf2\\xf2A(\\x14vtt(++\\x7f\\xfc\\xf1\\xc7\\xf2\\xf2A,\\x16\\xff\\xfa\\xeb\\xaf\\x8a\\xa8\\xc8\\xc5\\xc5%--M^\\x0e\\xdd\\xbbwo\\xdd\\xbau\\xe6\\xe6\\xe6\\xf7\\xee\\xdd\\x93\\x97\\x0fMMM,\\x16k\\xde\\xbcyO\\x9f>\\x95\\x97\\x0f]]]:::\\x8a$)\\x83\\xc1\\x90\\x8b7\\xe8\\xd0\\xb4\\x0f\\x00\\x00\\x05y\\rO\\xe3\\x8fA\\x13CQ\\xd0\\xc4P\\x1441\\x14\\x05M\\x0c

China

International Mathematical Olympiad

[
  "Discrete Mathematics > Combinatorics > Invariants / monovariants",
  "Discrete Mathematics > Combinatorics > Coloring schemes, extremal arguments"
]

English

proof and answer

All rectangles with positive integer side lengths such that either (i) one side is divisible by 3 and the other by 4, or (ii) one side is divisible by 12 and the other is at least 7 (the roles of the sides may be interchanged).

6

06j5

A $11 \times 11$ grid is to be covered completely without overlapping by some $2 \times 2$ squares and $L$-shapes each composed of three unit cells. Determine the smallest number of $L$-shapes used. (Each shape must cover some grids entirely and cannot be placed outside the $11 \times 11$ grid. The $L$-shapes may be reflected or rotated when placed on the grid.)

![](attached_image_1.png)

[
  "At least 23 $L$-shapes are needed.\nSuppose $x$ squares and $y$ $L$-shapes are used. Then the total number of cells is $4x + 3y$, which should be equal to $11^2 = 121$.\n\n![](attached_image_2.png)\n\n![](attached_image_3.png)\n\nWe colour the cells as shown. Then every square and every $L$-shape covers at most one blackened cell. As there are 36 blackened cells, we have $x + y \\ge 36$.\n\nTherefore, $y = 4(x + y) - (4x + 3y) \\geq 4(36) - 121 = 23$. The figure on the right gives one example using 23 L-shapes."
]

[
  {
    "bytes": "b'\\x89PNG\\r\\n\\x1a\\n\\x00\\x00\\x00\\rIHDR\\x00\\x00\\x02/\\x00\\x00\\x00\\xa7\\x08\\x02\\x00\\x00\\x00V\\xca+\\x8f\\x00\\x00\\x04\\x9dIDATx\\x9c\\xed\\xda\\xbfJ\\x9b{\\x00\\xc6\\xf1\\xb4\\nv2!\\xa24Q\\xa4[/\\xa0\\xab\\x93C\\x17\\x11o\\xa1t\\x10\\x04o@\\xbc\\x02o \\xb9\\x00A\\xe8\\x9f\\xa1\\xd0\\xb1[g\\xc5\\x0e\\x85\\x82\\xd9D\\xd2\\x16\\x87\\x98Vb\\xd2\\xa6\\xa6\\xeb!\\x1d\\xce\\xc1\\x83\\xef\\xe39\\xf9|\\xb67\\xd3\\xb3\\xfc\\xde\\xef\\xfb\\xf2\\xe6\\xdeh4*\\x01@\\xd4\\xfd\\xf4\\x00\\x00P#\\x00\\xee\\x005\\x02 oz\\xec\\xfa\\xc7\\x8f\\x1f\\xc7\\xc7\\xc7\\xd3\\xd3\\xe3\\xbf\\xff_=y\\xf2$=\\x01\\xf8G\\xda\\xed\\xf6\\xe7\\xcf\\x9f\\xd3+\\n2\\x18\\x0cfff\\xd2+\\nR\\xaf\\xd7k\\xb5\\xda\\xbd\\xb1\\x7f1lnn\\xee\\xef\\xef?x\\xf0 5\\xabH\\xbd^\\xef\\xe5\\xcb\\x97\\x1b\\x1b\\x1b\\xe9!\\xc0\\xdf[^^\\xbe\\xb8\\xb8\\x98\\x9a\\x9aJ\\x0f\\xb9u\\xa3\\xd1\\xe8\\xdb\\xb7o\\xe5r9=\\xa4\\x08\\xc3\\xe1\\xf0\\xe1\\xc3\\x87\\xadVk\\xfc\\x1d\\xa8Z\\xad>{\\xf6\\xac\\xd9lFf\\x15leeer\\xde\\x02\\xe1\\xbf\\xae\\\\.7\\x9b\\xcd\\xb5\\xb5\\xb5\\xf4\\x90[\\xd7\\xedv+\\x95J\\xa7\\xd3I\\x0f)\\xc2\\xc1\\xc1A\\xa3\\xd1(\\xf9n\\x04\\xc0]\\xa0F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\x9e\\x1a\\x01\\x90\\xa7F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\x9e\\x1a\\x01\\x90\\xa7F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\x9e\\x1a\\x01\\x90\\xa7F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\x9e\\x1a\\x01\\x90\\xa7F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\x9e\\x1a\\x01\\x90\\xa7F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\x9e\\x1a\\x01\\x90\\xa7F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\x9e\\x1a\\x01\\x90\\xa7F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\x9e\\x1a\\x01\\x90\\xa7F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\x9e\\x1a\\x01\\x90\\xa7F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\x9e\\x1a\\x01\\x90\\xa7F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\x9e\\x1a\\x01\\x90\\xa7F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\x9e\\x1a\\x01\\x90\\xa7F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\x9e\\x1a\\x01\\x90\\xa7F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\x9e\\x1a\\x01\\x90\\xa7F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\x9e\\x1a\\x01\\x90\\xa7F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\x9e\\x1a\\x01\\x90\\xa7F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\x9e\\x1a\\x01\\x90\\xa7F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\x9e\\x1a\\x01\\x90\\xa7F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\xde\\xf4\\xd8u\\xaf\\xd7;>>\\xde\\xdb\\xdb\\x8b\\xac)\\xd8\\xd9\\xd9\\xd9\\xeb\\xd7\\xaf?~\\xfc\\x98\\x1eR\\x84\\xe1p\\xb8\\xbb\\xbb\\x9b^\\x017\\xd7\\xeb\\xf5&\\xe4\\xc0\\xf6\\xfb\\xfdR\\xa94!\\xf7\\xe1\\x0f\\x1f>|\\xff\\xfe\\xbd\\xf4g\\x8d\\xba\\xdd\\xee\\xf9\\xf9\\xf9\\xe1\\xe1abU\\xd1.//[\\xad\\xd6\\xe5\\xe5ez\\xc8\\xad\\x1b\\x0e\\x87o\\xde\\xbc\\xd9\\xde\\xde.\\x97\\xcb\\xe9-pC\\xfd~\\x7fB\\x0e\\xec\\xcf\\x9f?K\\xa5\\xd2\\x84\\xdc\\x87OOO\\xaf\\xae\\xaeJ\\x7f\\xd6\\xa8V\\xab=}\\xfa\\xb4\\xd9l&V\\x15meeegggmm-=\\xe4\\xd6u\\xbb\\xddJ\\xa5\\x92^\\x01\\xffJ\\xb5Z\\x9d\\xa8\\x03\\xfb\\xea\\xd5\\xab\\xf4\\x90\"\\x1c\\x1c\\x1c4\\x1a\\x8d\\x92\\xefF\\x00\\xdc\\x05j\\x04@\\x9e\\x1a\\x01\\x90\\xa7F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\x9e\\x1a\\x01\\x90\\xa7F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\x9e\\x1a\\x01\\x90\\xa7F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\x9e\\x1a\\x01\\x90\\xa7F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\x9e\\x1a\\x01\\x90\\xa7F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\x9e\\x1a\\x01\\x90\\xa7F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\x9e\\x1a\\x01\\x90\\xa7F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\x9e\\x1a\\x01\\x90\\xa7F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\x9e\\x1a\\x01\\x90\\xa7F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\x9e\\x1a\\x01\\x90\\xa7F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\x9e\\x1a\\x01\\x90\\xa7F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\x9e\\x1a\\x01\\x90\\xa7F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\x9e\\x1a\\x01\\x90\\xa7F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\x9e\\x1a\\x01\\x90\\xa7F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\x9e\\x1a\\x01\\x90\\xa7F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\x9e\\x1a\\x01\\x90\\xa7F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\x9e\\x1a\\x01\\x90\\xa7F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\x9e\\x1a\\x01\\x90\\xa7F\\x00\\xe4\\xa9\\x11\\x00yj\\x04@\\x9e\\x1a\\x01\\

Hong Kong

1997-2023 IMO HK TST

[
  "Discrete Mathematics > Combinatorics > Coloring schemes, extremal arguments",
  "Discrete Mathematics > Combinatorics > Counting two ways",
  "Discrete Mathematics > Combinatorics > Invariants / monovariants"
]

proof and answer

23

7

07d3

There are 27 cards, each has some amount of (1 or 2 or 3) shapes (a circle, a square or a triangle) with some color (white, grey or black) on them. We call a triple of cards a **match** such that all of them have the same amount of shapes or mutually distinct amount of shapes, have the same shape or mutually distinct shapes and have the same color or mutually distinct colors. For instance, three cards shown in the figure are a **match** because they have distinct amount of shapes, distinct shapes but the same color of shapes.

What is the maximum number of cards that we can choose such that
none of the triples make a **match**?
![](attached_image_1.png)

[
  "We will prove that the answer of the problem is $9$.\n\nEach card can be corresponded with a point in $\\mathbb{Z}_3^3$. A line in $\\mathbb{Z}_3^3$ is defined to be a subset of the form $\\{P, P+V, P+2V\\}$ where $P$ and $V$ are two elements in $\\mathbb{Z}_3^3$, such that $V \\neq 0$ (in $\\mathbb{Z}_3^3$). It is easy to see that three elements of $\\mathbb{Z}_3^3$ form a line, if and only if their sum (in $\\mathbb{Z}_3^3$) is equal to $0$. For instance, in the following figure we can see three different lines. In this new language, the problem is to find the maximum number of points in $\\mathbb{Z}_3^3$ such that no three of them are collinear.\n![](attached_image_2.png)\n\nThe following lemma is the statement of the problem in $\\mathbb{Z}_3^2$, and proof that the answer is not greater than $4$.\n\n**Lemma.** There are no $5$ points in $\\mathbb{Z}_3^2$ such that no three of them are collinear (definition of line in $\\mathbb{Z}_3^2$ is similar).\n\n*Proof.* Assume to the contrary that $S$ is a set in $\\mathbb{Z}_3^2$ with more than $4$ elements such that no three points of $S$ are collinear. Let $P$ be one point in $\\mathbb{Z}_3^2$. There are exactly $4$ lines (in $\\mathbb{Z}_3^2$) passing through $P$. For example, if $P$ is a point in the corner, these are the lines containing $P$.\n![](attached_image_3.png)\nSince no three points of $S$ are collinear, each line passing through $P \\in S$ contains at most one other point in this set. So there are at most five points in $S$ (Note that for any point in $\\mathbb{Z}_3^2$ like $Q \\neq P$, there is a unique line containing both $P$ and $Q$).\nNow assume that $S$ has exactly $5$ elements. Consider $P \\in S$. Again, since there are only four lines passing through $P$, and there are exactly four other points in $S$, every line passing through $P$ will contain another point of $S$.\nIt means that every line in $\\mathbb{Z}_3^2$, intersects $S$ in exactly zero or two points. So there are $\\binom{5}{2} = 10$ lines in $\\mathbb{Z}_3^2$ containing two points of $S$. On the other hand, the total number of lines in $\\mathbb{Z}_3^2$ is $12$ (for each of $9$ points in $\\mathbb{Z}_3^2$, there are $4$ lines containing that point, and every line consists of $3$ different points). Therefore there are two lines $l_1$ and $l_2$ in $\\mathbb{Z}_3^2$ having empty intersection with $S$. But the union of $l_1$ and $l_2$ contains at least $5$ points. This contradicts $|S| = 5$.\n\nWe call a subset $\\mathcal{P}$ of $\\mathbb{Z}_3^3$ a plane, if there exist $a, b, c, d \\in \\mathbb{Z}_3$ with at least one of $a, b$ and $c$ is non-zero (in $\\mathbb{Z}_3$) and such that\n$$\n\\mathcal{P} = \\mathcal{P}_d(a, b, c) = \\{ (x, y, z) : ax + by + cz = d \\pmod{3} \\}.\n$$\nIt is easy to see that every plane consists of exactly $9$ points and for every three points $A, B$ and $C$ in $\\mathbb{Z}_3^3$, either there exists a unique plane passing through them, or they are collinear. In the latter case there are exactly four different planes containing them.\nWe call two planes parallel, if they have no common points. Again, it is easy to check that if two planes $\\mathcal{P}_1$ and $\\mathcal{P}_2$ are parallel, there exist two different numbers $i, j \\in \\mathbb{Z}_3$ and $(a, b, c) \\neq \\vec{0}$ in $\\mathbb{Z}_3^3$ such that\n$$\n\\mathcal{P}_1 = \\mathcal{P}_i(a, b, c), \\quad \\mathcal{P}_2 = \\mathcal{P}_j(a, b, c).\n$$\nFor any $(a, b, c) \\neq \\vec{0}$ (in $\\mathbb{Z}_3^3$), all $27$ points in $\\mathbb{Z}_3^3$ can be partitioned into three parallel planes $\\mathcal{P}_0(a, b, c)$, $\\mathcal{P}_1(a, b, c)$ and $\\mathcal{P}_2(a, b, c)$. But since $\\mathcal{P}_i(a, b, c) = \\mathcal{P}_{-i}(-a, -b, -c)$, two points $(a, b, c)$ and $(-a, -b, -c)$ give the same partition. Therefore, there are exactly $\\frac{26}{2} = 13$ ways to partition $\\mathbb{Z}_3^3$ into three parallel planes. Note that if we consider all these $13$ partitions, every plane in $\\mathbb{Z}_3^3$ will appear e

[
  {
    "bytes": "b'\\x89PNG\\r\\n\\x1a\\n\\x00\\x00\\x00\\rIHDR\\x00\\x00\\x01\\xc0\\x00\\x00\\x00\\xd8\\x08\\x02\\x00\\x00\\x00\\xf3\\xb5\\xa4f\\x00\\x00\\x1a\\xafIDATx\\x9c\\xed\\xdd{PT\\xd7\\xe1\\x07\\xf0\\xbd\\xcb\\x02\"T\\xd1\\xe2\\xa3&\\xd1\\x06G+\\x1aG\\x0b\\xe3$\\x9a\\xc6\\xb4\\xc5\\xc4dBu\\x12\\xd3\\x99f&i\\xec\\xd4N\\xa7\\xd3\\xe9\\xd8\\xc745\\x125>\\xda\\x8a\\x1a\\x10\\x89R\\x04\\x85\"\"\\x8b\\x02>\\x10A\\x96\\x87\\xe0\\x0b\\x01\\x15y\\x8b\\x80\\xbc\\x11vy/\\xec\\xee}\\x9c\\xdf\\x1f\\xfe\\xc6X\\xf1\\x01w\\xef\\xee\\xb9w\\xf7\\xfb\\xf9K\\xd7\\xdds\\xbe#\\xf0e\\xf7\\xdes\\xcfe\\x08!*\\x00\\x00\\x18?5\\xed\\x00\\x00\\x00J\\x85\\x02\\x05\\x00\\x10I\\xf3\\xe8O\\x99\\x99\\x99\\xdb\\xb7o\\x1f\\x19\\x19a\\x18\\x86b \\'\\xc7\\xb2\\xec\\xdc\\xb9s\\xb5Z\\xed\\x84\\t\\x13\\xac\\x1c\\xcad2\\x1d>|8**\\xca\\xcd\\xcdM\\x92l \\x02!\\x84a\\x98O?\\xfd\\xf4\\xaf\\x7f\\xfd\\xab\\xf5?Y\\x8d\\x8d\\x8d\\xbf\\xf9\\xcdoz{{\\xd5j\\xbc\\xf5\\xa1F\\x10\\x04A\\x10\\x92\\x92\\x92\\x16-Z\\xf4]\\x81VUUUUU\\r\\x0f\\x0f\\xe3kC\\x11\\xcb\\xb2\\r\\r\\r\\x1c\\xc7Y?\\x94\\xc9d*))\\xa9\\xae\\xaevqq\\xc1\\xd7\\x94\\x16B\\x08\\xcb\\xb2\\xfe\\xfe\\xfe\\x16\\x8b\\xc5\\xdd\\xdd\\xdd\\xca\\xd1\\x1a\\x1b\\x1b+++{zz4\\x1a\\xcd\\x8b\\x9f\\r\\xb6\\xc1\\xf3<\\xcf\\xf3\\xf7\\xee\\xdd\\xfb\\x9f\\x02uqqQ\\xa9T\\xe9\\xe9\\xe9\\xabW\\xaf\\xa6\\x97\\xcd\\xd9\\xadY\\xb3&//O\\xaa\\xd1\\x08!?\\xf9\\xc9O\\xc2\\xc3\\xc3\\x7f\\xfc\\xe3\\x1fK5&\\x8cK[[[@@\\x80J\\xa5\\x92\\xe4\\x83\\xdd\\x84\\t\\x13\\x18\\x86Y\\xbf~\\xfd\\x91#G\\xac\\x1f\\r\\xc4\\xd9\\xb1cGHH\\x88\\xa7\\xa7\\xa7\\n\\xc7@\\x01\\x00DC\\x81\\x02\\x00\\x88\\x84\\x02\\x05\\x00\\x10\\t\\x05\\n\\x00 \\x12\\n\\x14\\x00@$\\x14(\\x00\\x80H(P\\x00\\x00\\x91P\\xa0\\x00\\x00\"\\xa1@\\x01\\x00Dr\\x90\\x02mii)))1\\x1a\\x8d\\xb4\\x83\\x00\\x80\\x13q\\x84\\x02\\xb5X,\\xe7\\xce\\x9d\\xfb\\xf2\\xcb/kkkig\\x01\\x00\\'\\xe2\\x08\\x05\\xda\\xd0\\xd0\\x90\\x90\\x90p\\xe9\\xd2\\xa5\\x93\\'O\\x0e\\x0e\\x0e\\xd2\\x8e\\x03\\x00\\xceB\\xf1\\x05:<<\\x9c\\x92\\x92RRR\\xc2\\xb2lLLLMM\\r\\xedD\\x00\\xe0,\\x14_\\xa0\\x9d\\x9d\\x9d\\xe1\\xe1\\xe1,\\xcb\\xaaT*\\xbd^\\x1f\\x12\\x12b2\\x99h\\x87\\x02\\x00\\xa7\\xa0\\xec\\x02\\xb5X,\\xff\\xfc\\xe7?\\xbb\\xbb\\xbb\\x1f=\\x92\\x9a\\x9a\\x9a\\x9b\\x9bK1\\x12\\x008\\x0fe\\x17hQQQ\\\\\\\\\\xdc\\xe3\\x8f\\x10B\\x82\\x83\\x83\\xfb\\xfb\\xfb)%\\x02\\x00\\'\\xa2\\xe0\\x02\\xed\\xe9\\xe9\\t\\x0e\\x0e\\x16\\x04\\xe1\\x89\\xc7\\xcb\\xcb\\xcb\\x0f\\x1e<\\x88\\xbb\\x8d\\x02\\x80\\xad)\\xb8@cbb\\xae]\\xbb6\\xfaq\\x9e\\xe7\\xa3\\xa2\\xa2JKK\\xed\\x1f\\t\\x00\\x9c\\x8aR\\x0b\\xb4\\xa2\\xa2\"66\\xf6Y\\xf7\\x0e\\xea\\xe8\\xe88p\\xe0\\xc0\\xd0\\xd0\\x90\\x9dS\\x01\\x80SQd\\x81\\xf2<\\xff\\xed\\xb7\\xdf644<\\xeb\\t,\\xcb\\xe6\\xe6\\xe6^\\xb8p\\xc1\\x9e\\xa9\\x00\\xc0\\xd9(\\xb2@u:]NN\\x8e\\xc5by\\xces\\xda\\xdb\\xdb\\xb5Zm[[\\x9b\\xddR\\x01\\x80\\xb3Q^\\x81\\x1a\\x0c\\x86\\xc4\\xc4\\xc4\\xfa\\xfa\\xfa\\xe7?\\x8d\\x10\\x92\\x9f\\x9f\\x9f\\x91\\x91a\\x9fT\\x00\\xe0\\x84\\x14V\\xa0\\x84\\x90\\xcc\\xcc\\xcc\\xec\\xec\\xec\\xb1\\x9cd7\\x18\\x0c\\xc9\\xc9\\xc9\\xb86\\t\\x00lDa\\x05\\xda\\xd4\\xd4t\\xea\\xd4\\xa9\\x8e\\x8e\\x8e1>\\xbf\\xa0\\xa0 ;;\\xdbl6\\xdb4\\x15\\x008\\'%\\x15\\xa8\\xc5b\\xc9\\xcd\\xcd\\xd5\\xe9t\\xe3zILL\\xcc\\xdd\\xbbwm\\x97\\n\\x00\\x9c\\x96\\x92\\n\\xb4\\xb9\\xb9922r\\xbc\\x8b\\x93\\xee\\xdc\\xb9\\x13\\x17\\x17\\x877\\xa1\\x00 9\\xc5\\x14(\\xcb\\xb2\\xf1\\xf1\\xf1\\xb7n\\xdd\\x12\\xf1\\xda\\x84\\x84\\x84\\x92\\x92\\x12\\xc9#\\x01\\x80\\x93SL\\x81\\xd6\\xd5\\xd5EFF\\xf2</\\xe2\\xb5]]][\\xb7n\\x1d}\\xd1\\'\\x00\\x805\\x14S\\xa0_}\\xf5\\x95^\\xaf\\x17\\xfd\\xf2\\xcb\\x97/\\x1f?~\\\\\\xc2<\\x00\\x00\\xca(\\xd0\\x8c\\x8c\\x8c\\xf4\\xf4tkF\\xb0X,\\xdb\\xb6m\\xc3.M\\x00 !\\x05\\x14\\xe8\\xc0\\xc0@pp\\xf0\\xc3-\\x93\\xad\\xd1\\xde\\xde\\x1e\\x12\\x12\"\\xee \\x00\\x00\\xc0hr/P\\x8e\\xe3\"##%Y\\x87d6\\x9b\\x93\\x93\\x93o\\xde\\xbci\\xfdP\\x00\\x00*\\xf9\\x17hYY\\xd9\\xb1c\\xc7\\x86\\x87\\x87%\\x19\\xad\\xb5\\xb5\\xf5\\xc8\\x91#\\xf8 \\x0f\\x00\\x92\\xd0\\xd0\\x0e\\xf0<\\x03\\x03\\x03\\xc7\\x8f\\x1f\\x7f\\xce\\

Iran

Iranian Mathematical Olympiad

[
  "Discrete Mathematics > Combinatorics > Counting two ways",
  "Discrete Mathematics > Combinatorics > Coloring schemes, extremal arguments",
  "Algebra > Linear Algebra > Vectors"
]

proof and answer

9

8

08yo

In a $7 \times 7$ chessboard, a coin is placed in the square in the first row from the top, the fourth column from the left. We call square $Y$ a lower left square of square $X$ if $Y$ is $k$ squares to the left and $k$ squares below $X$ for some positive integer $k$. Similarly, we call square $Y$ a lower right square of square $X$ if $Y$ is $k$ squares to the right and $k$ squares below $X$ for some positive integer $k$. For a square $X$ not on the bottom line, one can perform one of the following four operations when a coin is placed on $X$:

a. Remove a coin from $X$ and place a coin in the square one below $X$.

b. Remove a coin from $X$ and place coins in each of the lower left squares of $X$.

c. Remove a coin from $X$ and place coins in each of the lower right squares of $X$.

d. Remove a coin from $X$ and place coins in the square one square to the left and one square below $X$, and the square one square to the right and one square below $X$. If there is only one such square, place a coin in that square only.

If there is already a coin in the place where one intends to place a coin, one will not place the coin there.
Find the maximum possible number of coins that can be placed on the square when the operation is performed an arbitrary number of times.

![](attached_image_1.png)
(a)
![](attached_image_2.png)
(b)
![](attached_image_3.png)
(c)
![](attached_image_4.png)
(d)

[
  "$19$\n\nIf one writes the number in each square as shown in the figure below, the sum of the numbers written in the squares where the coins are placed cannot be increased by the operations.\n![](attached_image_5.png)\nThe number written in the square where the coin was initially placed is $64$ and there are three squares with $1$ written in them, eight squares with $2$ and six squares with $4$. Since the number written in each of the other squares is at least $8$, $64 < 1 \\cdot 3 + 2 \\cdot 8 + 4 \\cdot 6 + 8 \\cdot 3$ shows that the number of coins placed in the squares is always less than or equal to $3 + 8 + 6 + 3 - 1 = 19$.\n\nOn the other hand, one can place $19$ coins in the squares by performing the operations as follows. In the following operation $(x)$ on the square in $i$th row from the top and $j$th column from the left is denoted by \"$x$ on $(i, j)$\".\n\nDo $d$ on $(1, 4)$, $b$ on $(2, 5)$, $a$ on $(5, 2)$, $d$ on $(6, 2)$, $d$ on $(4, 3)$, $a$ on $(5, 2)$, $d$ on $(5, 4)$, $d$ on $(6, 3)$, $d$ on $(6, 5)$, $d$ on $(3, 4)$, $d$ on $(4, 3)$, $a$ on $(4, 5)$, $d$ on $(5, 5)$, $d$ on $(6, 6)$, $d$ on $(5, 4)$, $c$ on $(2, 3)$, $a$ on $(5, 6)$, $d$ on $(4, 5)$, $d$ on $(3, 4)$ in that order.\n\nFrom the above, the answer is $19$.",
  "The proof that the number of coins placed in the squares is at most $19$ is the same as above. One can also place $19$ coins in the squares by performing the operations as follows.\n\nDo $d$ on $(1, 4)$, $d$ on $(2, 3)$, $d$ on $(3, 2)$, $d$ on $(4, 3)$, $a$ on $(5, 2)$, $d$ on $(6, 2)$, $d$ on $(5, 4)$, $d$ on $(6, 3)$, $d$ on $(6, 5)$, $d$ on $(3, 4)$, $a$ on $(4, 3)$, $d$ on $(5, 3)$, $d$ on $(4, 5)$, $d$ on $(5, 4)$, $a$ on $(5, 6)$, $d$ on $(6, 6)$, $d$ on $(2, 5)$, $d$ on $(3, 6)$, $d$ on $(4, 5)$, $a$ on $(5, 6)$, $d$ on $(3, 4)$, $b$ on $(4, 3)$, $c$ on $(4, 5)$ in that order.\n\nFrom the above, the answer is $19$."
]

[
  {
    "bytes": "b'\\x89PNG\\r\\n\\x1a\\n\\x00\\x00\\x00\\rIHDR\\x00\\x00\\x017\\x00\\x00\\x01;\\x08\\x02\\x00\\x00\\x007\\x82Q\\x1e\\x00\\x00\\x0c\"IDATx\\x9c\\xed\\xdd\\xdbZ\\xe2H\\x14\\x80Q\\x98\\xaf\\xdf\\xff\\x95\\x99\\x8b\\xe2\\x8b!\\xc8A\\xb4\\xbb\\xfe\\xc8Z\\x17=:\\xa2\\xee\\xae\\xaa} \\xd2\\xf1x:\\x9d\\x0e\\x87\\xc3\\xe1p8\\x1e\\x8f\\x87\\xc3\\xe1t:\\x1d\\x8f\\xc7\\xfb\\x7f.\\x0f{\\xf2\\xf1\\x9f~\\x85\\xe1\\xce\\xd7y\\xf8\\xc5o=`\\xfc]\\x1e\\xbe\\xbb\\xc4\\xf0\\xe9\\xff\\xdf<\\x86\\xc3\\x8d5\\xb9\\xb3P\\xb7>t\\x7fm7\\x9b\\xf5\\xa5\\xcf\\xfd\\xa6\\xee\\xa6\\x9fN\\xa7hd\\xc0\\xe1p8\\x1c\\xfe\\x1b\\xffY\\x12uI\\xda\\xcd\\x9f\\xcf\\xbcq\\xe7\\xd3\\xaf?\\xe5\\xfa\\xdd%\\xa6\\xcdG\\x9f\\xfc\\xf3\\xfa\\x8d\\xd7\\xde\\xdd|\\xa9\\xeb\\x0f\\xed\\xd7\\xad\\xbf\\xe33\\x7f\\xc1[\\x8f\\xb9\\xf5E\\xae\\x1f\\x7fk\\x9b\\x0eW\\xab\\xfd\\xf2^<\\x0c\\xf2\\xf9\\xcf}\\xf8\\xd7y\\xf2\\xcb~\\xf5\\x91\\x9f>\\xfec\\xd8{\\xe1k\\xfd\\xace\\x12\\x9e\\x18Fg\\x1d\\xc4\\xd0\\x89az\\x18\\xffM\\xfc\\xde\\x9f\\xfa5\\x8d\\x8b_ r\\x1a/\\xb2t}]\\x07\\x88d\\xc4E\\x96\\x16*Gd]`1=/L\\xbc\\xf0\\xc0\\xf4\\xcea\\xe2m\\xb1\\x05\\\\\\xcbM\\xbco\\xce\\x16\\x04M\\xdf\\x94\\xdc\\xc4\\xcb7\\x1d\\x8f\\xc7uC\\xd6\\x9c\\xbfo\\xfa\\x1a\\x9ax\\x7f\\x95\\xcd\\x0e\\x8ewm\\xeb\\xcb\\xa6w\\xd1\\xe1\\xcf\\xfa\\x9dHL|\\xc9\\x93?y/\\xbcH`w\"\\x05\\xee\\xcf\\xe3\\x87\\xfc[\\xddW<\\'mR\\xf4\\xe1\\xeb\\xda,\\xef\\x0b\\xa6\\xafXn\\xe2\\x9d\\xbe\"{\\xf4\\xa5\\xd7\\xa9\\x16vy_\\xa6\\xaf\\x98\\x89w\\x97^{}\\xe9\\xe9\\xf6\\xbf\\x08\\xa3\\xcc5\\xde\\x1d{!\\xdfF\\xa2n\\xae\\x03sK\\xa4\\xa2\\xe5&^\\xfe\\xb6\\xc8\\xc9\\xdb\\x85HFxU\\xc3^\\xd9\\xac\\x7ff\\xfaR\\x9bxw\\xe6G\\x86\\xd5\\xe9\\xc7\\x8e/1\\xf1\\xbe/\\xdb\\xfd\\xa4\\xe9\\x0be\\xe2my\\xf2@\\xd8\\xa9\\x7fi\\xfaj\\x9bx[\\xa6\\x1f\\x08\\x82L\\xbc;s}\\xf3.\\xfe\\xb6\\xe9ya\\xe2\\xdd\\x99\\x9f\\xfdQ\\xe7\\xf4\\xf3\\xb7\\x0b\\xd3\\xf3\\xc2\\xc4\\xfb\\xd6\\xa6\\x9f?\\x9e\\x91\\xcbR\\xd5\\x9d\\x9a\\xe9g2\\xf7\\xbcTu\\x87\\r\\xaf\\xb6oyX(\\x7fp\\x8fl\\xf7\\x93\\xa6/Tn\\xe2}s\\xcf\\x1c\\x88\\xef_@*\\x0cM<O\\x96\\xee\\xd5\\xcb\\x99&E\\xbfj\\xfa\\x8a\\xc9\\xd2\\xfd\\xf9\\x91\\x01l\\xfa\\x14\\xb7#\\xd3\\xd7*w\\xf5\\x88g,\\xafmxm\\xcb\\xa6\\x1f\\xbb}\\x99\\x9e\\x17\\xae\\x1e\\xb5|\\xe9@,\\xb7\\x08|\\xf2\\xd9\\xecx\\xc3.\\x7f\\xd5\\xf4\\x153\\xf1\\xb6|\\xf5\\x0e)\\xe3\\x8d\\x87\\xb9-E\\xbf\\xa3\\xd5K\\x99\\xee\\xab\\x07b}+\\xa3M*^g\\xa6\\x14}\\xcd\\xf4u\\xd3K[^\\xbb\\x95\\xd13\\x8f\\x99~\\xd4\\xf6K/\\xe5\\xc7<\\xf3K\\xe6\\xd9#\\xbd\\xb4\\xe5G\\xca\\xb6[\\x04\\xfe\\xac\\xe9\\xf5N/m\\x19\\xcf3_\\xfb\\xdcO\\x7fI\\xcc!p\\xc8\\xf6n\\xfaM\\x8c\\xf5\\xd2\\x96\\xbf\\xf1\\x8a\"}\\xf5\\x9b\\xa6\\x979Y\\xda2\\xfd@pmz\\x99\\x93\\xa5\\xf0\\xc0\\xf4\\xd2)K[^.\\xdbwN\\xd2\\xf4C\\xc67\\xc9\\xd2\\x16\\x19\\xc5\\'\\xfc\\xbc{\\xefl\\xdf\\xaf\\xa7\\x97\\xee\\xde\\xf4k\\x1b\\xfcm\\xdb\\x9f\\x97N,\\xcc\\x85_)?=\\x86o\\xfe\\x90\\xf3:c\\xbf\\xf3u\\xde|/\\x0e\\x99\\x9f9\\xbb\\x1fo\\x8b-\\x08\\x9a\\xbe)&\\xde\\x16\\xe3k\\xd0\\xf4M\\x91\\xa5-\\xdf,\\xdb\\xd3\\xab\\xfe\\xaf4}Uei\\xcb\\xcf\\x96\\xed\\xe9\\xc7\\x8b\\x1f!K\\xe1\\x01\\x13/\\x17t\\xbf\\xa0\\xe9\\x9b\"K[\\xbe_\\xb6\\xdd?\\xe5\\xf7\\x91\\xa5\\xbf\\x90\\xd7\\x93\\xfd,\\x13/\\x17Fv\\xc9\\xb1\\x94\\xe9\\xdb!Ks^8\\x13\\xb7\\x8a\\xfd\\xf4&\\xc0\\x8fpG\\x95\\xdd\\xbb\\xbew\\xf6:9\\xd7oO\\xef\\t;5\\xfd\\x8e*\\xb24\\xe7K\\xaf_\\xbd\\x95\\x90\\xb7\\x1e,Q_0}\\xd1L\\xbc-/\\xfc\\x06\\x8a\\xbf\\xf7\\xf5\\x89\\x90\\xa5{\\xe57#\\xbe\\x0fY\\xda\\xf2\\xc2\\xa0\\xfb\\x02\\x89\\xba/\\xb2\\xb4E\\xfe\\x04M\\xdf\\x14Y\\xba?\\xd3\\x0f\\xcd\\xbbq\\xf5\\x88\\x0b\\xff\\xec@H\\xf5\\x1d\\x91\\xa5-\\x92\\x87k\\xb2\\x14\\xeadi\\xcb\\xf4\\xa7@\\x04\\xc9\\xd2\\x16\\x13/\\xd7di\\x91\\x8e\\xca\\x9a,-\\xd2QY\\x93\\xa5-\\xff\\xac\\x8bj\\xd7;\"K[\\x9e\\xe9\\xa2\\x12\\xec\\xdd\\xc8\\xd2\"y\\xc8\\x9a,-z\\xd8Q\\xdd\\\\\\xfb\\xad\\xc8\\xd2\\xb7#EwG\\x96\\xb6<\\x7fw\\xb2\\xd7\\x92M\\x8a\\xee\\x91,mYnb\\xf4\\xcc\\x83\\xa5\\xdc\\x9bp\\xdf\\xa3}\\x1b\\x89\\xea\\xca\\xf0\\xef\\xa6\\x97\\xfe\\x06\\xf73\\xd0M\\xb4\\xf7N/m9\\x9dN\\xaf\\xdd\\xe9o\\xfd)\\xee\\x1

Japan

Japan Mathematical Olympiad

[
  "Discrete Mathematics > Combinatorics > Invariants / monovariants",
  "Discrete Mathematics > Combinatorics > Games / greedy algorithms"
]

English

proof and answer

19

9

09tk

Problem:

Gegeven is een driehoek $\triangle A B C$ met $\angle C=90^{\circ}$. Het midden van $A C$ noemen we $D$ en de loodrechte projectie van $C$ op $B D$ noemen we $E$. Bewijs dat de raaklijn in $C$ aan de omgeschreven cirkel van $\triangle A E C$ loodrecht op $A B$ staat.

![](attached_image_1.png)

[
  "Solution:\n\nNoem $S$ het snijpunt van de raaklijn en $A B$. We moeten dus bewijzen dat $\\angle B S C=90^{\\circ}$.\n\nVanwege $\\angle B C D=90^{\\circ}=\\angle C E D$ geldt $\\triangle B C D \\sim \\triangle C E D$, dus $\\frac{|D C|}{|D B|}=\\frac{|D E|}{|D C|}$. Omdat $|D A|=|D C|$ volgt hieruit $\\frac{|D A|}{|D B|}=\\frac{|D E|}{|D A|}$. Samen met $\\angle B D A=\\angle E D A$ geeft dit $\\triangle A D E \\sim \\triangle B D A$ (zhz). Dus $\\angle A B D=\\angle E A D$.\n\nOmdat $S C$ een raaklijn is aan de omgeschreven cirkel van $\\triangle A E C$ geldt vanwege de raaklijnomtrekshoekstelling ook dat $\\angle E A D=\\angle E A C=\\angle S C E$. Dus $\\angle S C E=\\angle A B D=\\angle S B E$. Hieruit volgt dat $S B C E$ een koordenvierhoek is. Dus $\\angle B S C=\\angle B E C=90^{\\circ}$.\n\n![](attached_image_2.png)",
  "Solution:\n\nZij $P$ de spiegeling van $B$ in $D$. Dan snijden $A C$ en $P B$ elkaar middendoor, dus is $C B A P$ een parallellogram. Dus $\\angle C A P=\\angle A C B=90^{\\circ}=\\angle C E P$. Dit betekent dat $C E A P$ een koordenvierhoek is en dat $C P$ een middellijn van zijn omgeschreven cirkel is. De raaklijn in $C$ aan deze omgeschreven cirkel staat loodrecht op de middellijn $C P$. Aangezien in het parallellogram $A B \\parallel C P$, staat de raaklijn dus ook loodrecht op $A B$.\n\n![](attached_image_3.png)",
  "Solution:\n\nZij $S'$ de loodrechte projectie van $C$ op $A B$. Er geldt dan $\\angle B S' C=90^{\\circ}=\\angle B E C$, dus $B C S' E$ is een koordenvierhoek. Er volgt dat $\\angle E D C=90^{\\circ}-\\angle E C D=\\angle E C B=180^{\\circ}-\\angle E S' C=\\angle E S' A$, dus $\\angle E D A=180^{\\circ}-\\angle E D C=180^{\\circ}-\\angle E S' A$, waaruit volgt dat $A D E S'$ een koordenvierhoek is. Nu is $\\angle S' A E=\\angle S' D E$. Verder is vanwege Thales $D$ het middelpunt van de cirkel door $A, C$ en $S'$, dus is $\\angle D S' A=\\angle S' A D$. Deze twee resultaten samen geven $\\angle E A C=\\angle S' A C-\\angle S' A E=\\angle S' A D-\\angle S' A E=\\angle D S' A-\\angle S' D E$. Met de buitenhoekstelling in driehoek $D S' B$ is dit gelijk aan $\\angle S' B D=\\angle S' B E$ en vanwege koordenvierhoek $B C S' E$ is dat weer gelijk aan $\\angle S' C E$. Dus $\\angle E A C=\\angle S' C E$. Met de raaklijnomtrekshoekstelling volgt hieruit dat $S' C$ raakt aan de omgeschreven cirkel van $\\triangle E A C$. Deze raaklijn $S' C$ staat dus inderdaad loodrecht op $A B$."
]

[
  {
    "bytes": "b'\\xff\\xd8\\xff\\xdb\\x00\\x84\\x00\\x08\\x06\\x06\\x07\\x06\\x05\\x08\\x07\\x07\\x07\\t\\t\\x08\\n\\x0c\\x14\\r\\x0c\\x0b\\x0b\\x0c\\x19\\x12\\x13\\x0f\\x14\\x1d\\x1a\\x1f\\x1e\\x1d\\x1a\\x1c\\x1c $.\\' \",#\\x1c\\x1c(7),01444\\x1f\\'9=82<.342\\x01\\t\\t\\t\\x0c\\x0b\\x0c\\x18\\r\\r\\x182!\\x1c!22222222222222222222222222222222222222222222222222\\xff\\xc0\\x00\\x11\\x08\\x01\\xb6\\x036\\x03\\x01\"\\x00\\x02\\x11\\x01\\x03\\x11\\x01\\xff\\xc4\\x01\\xa2\\x00\\x00\\x01\\x05\\x01\\x01\\x01\\x01\\x01\\x01\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x01\\x02\\x03\\x04\\x05\\x06\\x07\\x08\\t\\n\\x0b\\x10\\x00\\x02\\x01\\x03\\x03\\x02\\x04\\x03\\x05\\x05\\x04\\x04\\x00\\x00\\x01}\\x01\\x02\\x03\\x00\\x04\\x11\\x05\\x12!1A\\x06\\x13Qa\\x07\"q\\x142\\x81\\x91\\xa1\\x08#B\\xb1\\xc1\\x15R\\xd1\\xf0$3br\\x82\\t\\n\\x16\\x17\\x18\\x19\\x1a%&\\'()*456789:CDEFGHIJSTUVWXYZcdefghijstuvwxyz\\x83\\x84\\x85\\x86\\x87\\x88\\x89\\x8a\\x92\\x93\\x94\\x95\\x96\\x97\\x98\\x99\\x9a\\xa2\\xa3\\xa4\\xa5\\xa6\\xa7\\xa8\\xa9\\xaa\\xb2\\xb3\\xb4\\xb5\\xb6\\xb7\\xb8\\xb9\\xba\\xc2\\xc3\\xc4\\xc5\\xc6\\xc7\\xc8\\xc9\\xca\\xd2\\xd3\\xd4\\xd5\\xd6\\xd7\\xd8\\xd9\\xda\\xe1\\xe2\\xe3\\xe4\\xe5\\xe6\\xe7\\xe8\\xe9\\xea\\xf1\\xf2\\xf3\\xf4\\xf5\\xf6\\xf7\\xf8\\xf9\\xfa\\x01\\x00\\x03\\x01\\x01\\x01\\x01\\x01\\x01\\x01\\x01\\x01\\x00\\x00\\x00\\x00\\x00\\x00\\x01\\x02\\x03\\x04\\x05\\x06\\x07\\x08\\t\\n\\x0b\\x11\\x00\\x02\\x01\\x02\\x04\\x04\\x03\\x04\\x07\\x05\\x04\\x04\\x00\\x01\\x02w\\x00\\x01\\x02\\x03\\x11\\x04\\x05!1\\x06\\x12AQ\\x07aq\\x13\"2\\x81\\x08\\x14B\\x91\\xa1\\xb1\\xc1\\t#3R\\xf0\\x15br\\xd1\\n\\x16$4\\xe1%\\xf1\\x17\\x18\\x19\\x1a&\\'()*56789:CDEFGHIJSTUVWXYZcdefghijstuvwxyz\\x82\\x83\\x84\\x85\\x86\\x87\\x88\\x89\\x8a\\x92\\x93\\x94\\x95\\x96\\x97\\x98\\x99\\x9a\\xa2\\xa3\\xa4\\xa5\\xa6\\xa7\\xa8\\xa9\\xaa\\xb2\\xb3\\xb4\\xb5\\xb6\\xb7\\xb8\\xb9\\xba\\xc2\\xc3\\xc4\\xc5\\xc6\\xc7\\xc8\\xc9\\xca\\xd2\\xd3\\xd4\\xd5\\xd6\\xd7\\xd8\\xd9\\xda\\xe2\\xe3\\xe4\\xe5\\xe6\\xe7\\xe8\\xe9\\xea\\xf2\\xf3\\xf4\\xf5\\xf6\\xf7\\xf8\\xf9\\xfa\\xff\\xda\\x00\\x0c\\x03\\x01\\x00\\x02\\x11\\x03\\x11\\x00?\\x00\\xf7\\xfa(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xa2\\x80\\n(\\xaa\\x1a\\xbe\\xb5a\\xa0\\xd9}\\xb3R\\x9f\\xc8\\xb7\\xf3\\x12=\\xfb\\x19\\x86\\xe6;Tp\\x0fr(\\x02\\xfd\\x14\\x0eh\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\x8a(\\xa0\\x02\\xb9_\\x89\\x1ay\\xd4\\xbe\\x1dk\\xf0\\x0c\\xef[7\\x991\\xc1\\xdd\\x1f\\xef\\x17\\x1f\\x8a\\xd7UP\\xdc\\xc0\\x97V\\xd3[\\xc83\\x1c\\xa8Q\\xbe\\x84s@\\x15t\\x1d@j\\xfe\\x1e\\xd3u!\\x8f\\xf4\\xbbX\\xe6\\xe3\\xb6\\xe5\\x07\\xfa\\xd6\\x85q\\x7f\\nn\\x1eO\\x86\\xfa\\\\3\\x7f\\xae\\xb3\\xf3m$\\x1e\\x869\\x191\\xf9\\x01]\\xa5\\x00\\x14QE\\x00\\x14QE\\x00\\x14QE\\x00\\x14QE\\x00\\x14QE\\x00\\x14QE\\x00\\x14QE\\x00\\x14QE\\x0

Netherlands

IMO-selectietoets

[
  "Geometry > Plane Geometry > Circles > Tangents",
  "Geometry > Plane Geometry > Quadrilaterals > Cyclic quadrilaterals",
  "Geometry > Plane Geometry > Miscellaneous > Angle chasing"
]

proof only

10

0a6c

Problem:
A dot-trapezium consists of several rows of dots such that each row contains one more dot than the row immediately above (apart from the top row). For example here is a dot-trapezium consisting of 15 dots, having 3 rows and 4 dots in the top row.

![](attached_image_1.png)

A positive integer $n$ is called a trapezium-number if there exists a dot-trapezium consisting of exactly $n$ dots, with at least two rows and at least two dots in the top row. How many trapezium-numbers are there less than 100?

[
  "Solution:\nLet $n$ be a trapezium number and suppose there are $a$ dots in the first row and $b$ dots in the last row. So the required conditions are $a \\geq 2$ and $b \\geq a + 1$. Then the equation becomes:\n\n$$2n = b(b + 1) - a(a - 1) = b^{2} - a^{2} + b + a = (a + b)(b - a + 1)$$\n\nbecause it is the difference between two triangle numbers. Let the two factors on the RHS be $x = (a + b)$ and $y = (b - a + 1)$. Rearranging gives us\n\n$$a = \\frac{x - y + 1}{2} \\qquad \\mathrm{and} \\qquad b = \\frac{x + y - 1}{2}.$$ \n\nIn order for $a$ and $b$ to be integers we must have $x$ and $y$ being opposite parity. So we are looking for factorizations of the form $2n = xy$ such that one of $x$ and $y$ is even while the other is odd. We also need $a < b$ (so that the trapezium has at least two rows) which is equivalent to $y \\geq 2$. Finally we also need $a \\geq 2$ (so there are at least two dots in the top row) which is equivalent to $x \\geq y + 3$. We need\n\nNow write $n = 2^{k}m$ with $m$ odd.\n\n- If $n = 2^{k}$ is a power of 2, then the only factorization of $2n = 2^{k + 1} = xy$ such that both $x$ and $y$ have opposite parity is $x = 2^{k + 1}$ and $y = 1$. This doesn't work because we require $y > 1$. (when $y = 1$ the \"trapezium\" would consist of only one row)\n- If $m > 2^{k + 1} + 1$ or $1 < m < 2^{k + 1} - 1$ then we can choose\n\n$$x = \\max \\{2^{k + 1},m\\} \\quad \\mathrm{and}\\quad y = \\min \\{2^{k + 1},m\\}.$$ \n\nTo check that this works we simply check that $y > 1$ and $x \\geq y + 3$. Note that this still works even when $k = 0$.\n- If $m = 2^{k + 1} \\pm 1$ and $m$ is prime then the only factorization of $2n = 2^{k + 1}m = xy$ such that both $x$ and $y$ have opposite parity and $x > y > 1$ is\n\n$$x = \\max \\{2^{k + 1},m\\} \\quad \\mathrm{and}\\quad y = \\min \\{2^{k + 1},m\\}.$$ \n\nHowever this doesn't work because we require $x > x + 1$. (when $y = 1$ the \"trapezium\" would consist have one dot in the top row)\n\nThe only remaining possibility is when $m = 2^{k + 1} \\pm 1$ and $m$ is composite. If $k > 2$ then $m = 2^{k + 1} \\pm 1 \\geq 15$, so $n = 2^{k} m \\geq 8 \\times 15 > 100$ and we don\u2019t need to consider it. For $k \\leq 2$ we get $m = 1, 3, 5, 7, 9$. We can\u2019t have $m = 1$ because then $n$ would be a power of 2. We also can\u2019t have $m = 3, 5, 7$ because they are prime. Finally we consider $m = 9$ and so $k = 2$. In this case we get $n = 2^{k} m = 36$, which is a trapezium number as seen here:\n\n![](attached_image_2.png)\n\nTherefore all non-trapezium-numbers less than 100, are the powers of two and numbers of the form $n = 2^{k}(2^{k + 1} \\pm 1)$ where $(2^{k + 1} \\pm 1)$ is prime (and $k \\leq 2$). The powers of two are: $\\{1, 2, 4, 8, 16, 32, 64\\}$. The numbers of the form $2^{k}(2^{k + 1} \\pm 1)$ with $k \\leq 2$ and $(2^{k + 1} \\pm 1)$ being prime are\n\n$$\\{2^{0}(2^{1} + 1) = 3, 2^{1}(2^{2} - 1) = 6, 2^{1}(2^{2} + 1) = 10, 2^{2}(2^{3} - 1) = 28\\}.$$ \n\nAll together the non-trapezium numbers are $\\{1, 2, 3, 4, 6, 8, 10, 16, 28, 32, 64\\}$. There are 99 positive integers less than 100 and exactly 11 of them are non-trapezium numbers. So the final answer is $99 - 11 = 88$.",
  "Solution:\nFirst, notice that any odd integer can be written as a sum of consecutive integers: $2n + 1 = (n) + (n + 1)$, e.g. $23 = 11 + 12$.\n\nThen observe that any multiple of 3 can be written as a sum of consecutive integers: $3n = (n - 1) + (n) + (n + 1)$, for example, $18 = 5 + 6 + 7$.\n\nSimilarly, any multiple of 5 can be written as a sum of consecutive integers:\n\n$$5n = (n - 2) + (n - 1) + (n) + (n + 1) + (n + 2).$$\n\nIn general, any number with an odd factor can be written as a sum of consecutive integers. The only numbers that have no odd factors (other than 1) are the powers of two. There are 7 such numbers less than 100: $\\{1,2,4,8,16,32,64\\}$.\n\nIn general, any number with an odd factor (greater than one) can be written as a sum of consecutive integers. Note tha

[
  {
    "bytes": "b'\\xff\\xd8\\xff\\xe0\\x00\\x10JFIF\\x00\\x01\\x01\\x00\\x00\\x01\\x00\\x01\\x00\\x00\\xff\\xdb\\x00C\\x00\\x08\\x06\\x06\\x07\\x06\\x05\\x08\\x07\\x07\\x07\\t\\t\\x08\\n\\x0c\\x14\\r\\x0c\\x0b\\x0b\\x0c\\x19\\x12\\x13\\x0f\\x14\\x1d\\x1a\\x1f\\x1e\\x1d\\x1a\\x1c\\x1c $.\\' \",#\\x1c\\x1c(7),01444\\x1f\\'9=82<.342\\xff\\xdb\\x00C\\x01\\t\\t\\t\\x0c\\x0b\\x0c\\x18\\r\\r\\x182!\\x1c!22222222222222222222222222222222222222222222222222\\xff\\xc0\\x00\\x11\\x08\\x00J\\x00\\xa0\\x03\\x01\"\\x00\\x02\\x11\\x01\\x03\\x11\\x01\\xff\\xc4\\x00\\x1f\\x00\\x00\\x01\\x05\\x01\\x01\\x01\\x01\\x01\\x01\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x01\\x02\\x03\\x04\\x05\\x06\\x07\\x08\\t\\n\\x0b\\xff\\xc4\\x00\\xb5\\x10\\x00\\x02\\x01\\x03\\x03\\x02\\x04\\x03\\x05\\x05\\x04\\x04\\x00\\x00\\x01}\\x01\\x02\\x03\\x00\\x04\\x11\\x05\\x12!1A\\x06\\x13Qa\\x07\"q\\x142\\x81\\x91\\xa1\\x08#B\\xb1\\xc1\\x15R\\xd1\\xf0$3br\\x82\\t\\n\\x16\\x17\\x18\\x19\\x1a%&\\'()*456789:CDEFGHIJSTUVWXYZcdefghijstuvwxyz\\x83\\x84\\x85\\x86\\x87\\x88\\x89\\x8a\\x92\\x93\\x94\\x95\\x96\\x97\\x98\\x99\\x9a\\xa2\\xa3\\xa4\\xa5\\xa6\\xa7\\xa8\\xa9\\xaa\\xb2\\xb3\\xb4\\xb5\\xb6\\xb7\\xb8\\xb9\\xba\\xc2\\xc3\\xc4\\xc5\\xc6\\xc7\\xc8\\xc9\\xca\\xd2\\xd3\\xd4\\xd5\\xd6\\xd7\\xd8\\xd9\\xda\\xe1\\xe2\\xe3\\xe4\\xe5\\xe6\\xe7\\xe8\\xe9\\xea\\xf1\\xf2\\xf3\\xf4\\xf5\\xf6\\xf7\\xf8\\xf9\\xfa\\xff\\xc4\\x00\\x1f\\x01\\x00\\x03\\x01\\x01\\x01\\x01\\x01\\x01\\x01\\x01\\x01\\x00\\x00\\x00\\x00\\x00\\x00\\x01\\x02\\x03\\x04\\x05\\x06\\x07\\x08\\t\\n\\x0b\\xff\\xc4\\x00\\xb5\\x11\\x00\\x02\\x01\\x02\\x04\\x04\\x03\\x04\\x07\\x05\\x04\\x04\\x00\\x01\\x02w\\x00\\x01\\x02\\x03\\x11\\x04\\x05!1\\x06\\x12AQ\\x07aq\\x13\"2\\x81\\x08\\x14B\\x91\\xa1\\xb1\\xc1\\t#3R\\xf0\\x15br\\xd1\\n\\x16$4\\xe1%\\xf1\\x17\\x18\\x19\\x1a&\\'()*56789:CDEFGHIJSTUVWXYZcdefghijstuvwxyz\\x82\\x83\\x84\\x85\\x86\\x87\\x88\\x89\\x8a\\x92\\x93\\x94\\x95\\x96\\x97\\x98\\x99\\x9a\\xa2\\xa3\\xa4\\xa5\\xa6\\xa7\\xa8\\xa9\\xaa\\xb2\\xb3\\xb4\\xb5\\xb6\\xb7\\xb8\\xb9\\xba\\xc2\\xc3\\xc4\\xc5\\xc6\\xc7\\xc8\\xc9\\xca\\xd2\\xd3\\xd4\\xd5\\xd6\\xd7\\xd8\\xd9\\xda\\xe2\\xe3\\xe4\\xe5\\xe6\\xe7\\xe8\\xe9\\xea\\xf2\\xf3\\xf4\\xf5\\xf6\\xf7\\xf8\\xf9\\xfa\\xff\\xda\\x00\\x0c\\x03\\x01\\x00\\x02\\x11\\x03\\x11\\x00?\\x00\\xf7\\xfa(\\xa2\\x80\\n(\\xa2\\x80\\n+\\xcc\\xbe$|a\\xb4\\xf0&\\xa7\\x16\\x95\\x06\\x9eo\\xef\\x9a1$\\x80\\xcb\\xb1bS\\xd0\\x1e\\t$\\xe3\\xa7\\x1cb\\xba\\x1f\\x87\\xfe<\\xb2\\xf1\\xfe\\x84\\xf7\\xf6\\xd05\\xb4\\xf0\\xc9\\xe5\\xcfn\\xcc\\x18\\xa3c \\x83\\xdc\\x11\\xdf\\x03\\xa1\\xa0\\x0e\\xb2\\x8a*\\xb6\\xa3\\x7fo\\xa5i\\xb7Z\\x85\\xdb\\xec\\xb6\\xb6\\x89\\xa6\\x95\\xb1\\x9c*\\x8c\\x9e;\\xf4\\xa0\\x0b4W\\x87\\xe9\\x9f\\xb4v\\x9fw\\xaf\\xc7kw\\xa2Ik\\xa7K&\\xc1s\\xe7\\xeed\\x04\\xe03.:z\\x80x\\xf7\\xafp\\xa0\\x02\\x8a+\\xcf~%|U\\xb3\\xf8|\\xd6\\xb6\\xa2\\xc9\\xaf\\xb5\\x0b\\x952\\x08\\xbc\\xcd\\x8a\\x89\\x9cnc\\x83\\xd4\\x82\\x00\\x1e\\x87\\x91\\xdc\\x03\\xd0\\xa8\\xae#\\xe1\\xbf\\xc4\\x8b?\\x88Z}\\xcb\\xc7j\\xd6w\\x96\\x85D\\xd03\\xef\\x18l\\xe1\\x95\\xb028=\\xb8\\xae\\xde\\x80\\n)\\x93K\\x1c\\x10\\xc94\\xae\\x128\\xd4\\xb3\\xb1\\xe8\\x00\\xe4\\x9a\\xf0\\xf3\\xfbH\\xe9\\xe3\\\\\\xf2F\\x851\\xd2\\xfc\\xcd\\xbfh\\xf3\\xc7\\x99\\xb7?{f1\\xf8g\\xf1\\xa0\\x0fs\\xa2\\xa3\\x82x\\xae\\xad\\xe2\\xb8\\x81\\xc4\\x90\\xca\\x81\\xd1\\xd7\\xa3)\\x19\\x04~\\x15%\\x00\\x14QE\\x00\\x14QE\\x00\\x14QE\\x00y\\x0f\\xc5?\\x83w\\x1e5\\xd6\\xa3\\xd6t\\x8b\\xeb{{\\xc6\\x8db\\x9e;\\x9d\\xc1\\x1c/F\\x05A \\xe3\\x8cc\\xb5t\\xff\\x00\\x0c~\\x1f\\xa7\\xc3\\xfd\\x02[Y.V\\xe6\\xfa\\xeaA%\\xc4\\xa8\\x08\\\\\\x81\\x80\\xab\\x9e\\xc3\\x9e{\\xe6\\xbbz(\\x00\\xaaZ\\xbe\\x99\\x06\\xb5\\xa3^\\xe9w%\\x84\\x17p\\xbc.W\\xa8\\x0c1\\x91\\xef\\xcd]\\xa2\\x80>x\\xd2\\xff\\x00g\\x0b\\xf8\\xbcA\\x1bj:\\xcd\\xa4\\x9aLrn>J\\xb8\\x9aE\\x07\\xa6\\x08\\xc2\\xe7\\xd7\\'\\x1e\\xf5\\xf4=\\x14P\\x01^_\\xf1_\\xe1D\\xbe>\\x9e\\xcfQ\\xd3\\xafa\\xb6\\xd4m\\xe3\\xf2H\\xb8\\xdd\\xe5\\xc9\\x1eI\\x1c\\x80H \\x96\\xecs\\x9fj\\xf5\\n(\\x03\\xce\\xfe\\x14\\xfc3o\\x87

New Zealand

NZMO Round One

[
  "Number Theory > Divisibility / Factorization > Factorization techniques",
  "Algebra > Algebraic Expressions > Sequences and Series > Sums and products"
]

proof and answer

88