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 "2016 JBMO Problems/Problem 4"

(→‎Problem)
(\* Solution *\)
 
(3 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 +
__TOC__
 +
 
== Problem ==
 
== Problem ==
  
−
A <math>5 \times 5</math> table is called regular f each of its cells contains one of four pairwise distinct real numbers,such that each of them occurs exactly one in every <math>2 \times 2</math> subtable.The sum of all numbers of a regular table is called the total sum of the table.With any four numbers,one constructs all possible regular tables,computes their total sums and counts the distinct outcomes.Determine the maximum possible count.
+
A <math>5 \times 5</math> table is called regular if each of its cells contains one of four pairwise distinct real numbers, such that each of them occurs exactly once in every <math>2 \times 2</math> subtable.The sum of all numbers of a regular table is called the total sum of the table. With any four numbers, one constructs all possible regular tables, computes their total sums, and counts the distinct outcomes. Determine the maximum possible count.
  
 
== Solution ==
 
== Solution ==
 +
===Solution 1 (Official solution)===
 +
We will prove that the maximum number of total sums is <math>60</math>.
 +
The proof is based on the following claim:
 +
In a regular table either each row contains exactly two of the numbers or each column contains exactly two of the numbers.
 +
 +
Proof of the Claim:
 +
 +
Let R be a row containing at least three of the numbers. Then, in row <math>R</math> we can find three of the numbers in consecutive positions, let <math>x</math>, <math>y</math>, <math>z</math> be the numbers in consecutive positions(where <math>{x, y, s, z} = {a, b, c, d}</math>). Due to our hypothesis that in every
 +
<math>2 × 2</math> subarrays each number is used exactly once, in the row above <math>R</math>(if there is such a row), precisely above the numbers <math>x</math>, <math>y</math>, <math>z</math> will be the numbers <math>z</math>, <math>t</math>, <math>x</math> in this order. And above them will be the numbers <math>x</math>, <math>y</math>, and <math>z</math> in this order. The same happens in the rows below <math>R</math> (see the following figure).
 +
 +
 +
{| class="wikitable"
 +
| • || x || y || z || •
 +
|-
 +
| • || z || t || x || •
 +
|-
 +
| • || x || y || z || •
 +
|-
 +
| • || z || t || x || •
 +
|-
 +
| • || x || y || z || •
 +
|}
 +
 +
 +
Completing the array, it easily follows that each column contains exactly two of the numbers
 +
and our claim is proven. <b>(1)</b>
  
 +
Rotating the matrix (if it is necessary), we may assume that each row contains exactly two of the numbers. If we forget the first row and column from the array, we obtain a <math>4 × 4</math> array, that can be divided into four <math>2 × 2</math> subarrays, containing thus each number exactly four times, with a total sum of <math>4(a + b + c + d)</math>.
  
 +
It suffices to find how many different ways are there to put the numbers in the first row <math>R1</math> and
 +
the first column <math>C1</math>. <b>(2)</b>
 +
 +
Denoting by <math>a_1</math>, <math>b_1</math>, <math>c_1</math>, <math>d_1</math> the number of appearances of <math>a</math>, <math>b</math>, <math>c</math>, and <math>d</math> respectively in <math>R1</math> and <math>C1</math>, the total sum of the numbers in the entire <math>5 × 5</math> array will be <math>S = 4(a + b + c + d) + a1 \cdot a + b1 \cdot b + c1 \cdot c + d1 \cdot d</math>. <b>(3)</b>
 +
 +
If the first, third, and the fifth row contain the numbers <math>x</math> and <math>y</math>, with <math>x</math> denoting the number at the entry <math>(1, 1)</math>, then the second and the fourth row will contain only the numbers <math>z</math>, <math>t</math>, with <math>z</math> denoting the number at the entry <math>(2, 1)</math>. Then <math>x_1 + y_1 = 7</math> and <math>x_1 > 3</math>, <math>y_1 > 2</math>, <math>z_1 + t_1 = 2</math>, and <math>z_1 > t_1</math>. Then <math>{x_1, y_1} = {5, 2}</math> or <math>{x_1, y_1} = {4, 3}</math>, respectively <math>{z_1, t_1} = {2, 0}</math> or <math>{z_1, t_1} = {1, 1}</math>. <b>(4)</b>
 +
 +
Then <math>(a_1, b_1, c_1, d_1)</math> is obtained by permuting one of the following quadruples:
 +
<math>(5, 2, 2, 0)</math>, <math>(5, 2, 1, 1)</math>, <math>(4, 3, 2, 0)</math>, or <math>(4, 3, 1, 1)</math>. <b>(5)</b>
 +
 +
There are a total of <math>4!/2! = 12</math> permutations of <math>(5, 2, 2, 0)</math>, <math>12</math> permutations of <math>(5, 2, 1, 1)</math>, <math>24</math> permutations of <math>(4, 3, 2, 0)</math>, and <math>12</math> permutations of <math>(4, 3, 1, 1)</math>. Hence, there are at most <math>60</math> different possible total sums. <b>(6)</b>
 +
 +
We can obtain indeed each of these <math>60</math> combinations: take three rows <math>ababa</math> alternating with two rows <math>cdcdc</math> to get <math>(5, 2, 2, 0)</math>; take three rows <math>ababa</math> alternating with one row <math>cdcdc</math> and a row <math>dcdcd</math> to get <math>(5, 2, 1, 1)</math>; take three rows <math>ababc</math> alternating with two rows <math>cdcda</math> to get <math>(4, 3, 2, 0)</math>; take three rows <math>abcda</math> alternating with two rows <math>cdabc</math> to get <math>(4, 3, 1, 1)</math>. <b>(7)</b>
 +
 +
By choosing for example <math>a = 103</math>, <math>b = 102</math>, <math>c = 10</math>, and <math>d = 1</math>, we can make all these sums different.
 +
<b>(8)</b>
 +
 +
Hence, the maximum possible number of different sums is <math>\boxed{60}</math>.
 
== See also ==
 
== See also ==
  
 
{{JBMO box|year=2016|num-b=3|after=Last Problem|five=}}
 
{{JBMO box|year=2016|num-b=3|after=Last Problem|five=}}
 +
 +
[[Category:Intermediate Combinatorics Problems]]

Latest revision as of 00:20, 12 January 2023

Problem

A $5 \times 5$ table is called regular if each of its cells contains one of four pairwise distinct real numbers, such that each of them occurs exactly once in every $2 \times 2$ subtable.The sum of all numbers of a regular table is called the total sum of the table. With any four numbers, one constructs all possible regular tables, computes their total sums, and counts the distinct outcomes. Determine the maximum possible count.

Solution

Solution 1 (Official solution)

We will prove that the maximum number of total sums is $60$. The proof is based on the following claim: In a regular table either each row contains exactly two of the numbers or each column contains exactly two of the numbers.

Proof of the Claim:

Let R be a row containing at least three of the numbers. Then, in row $R$ we can find three of the numbers in consecutive positions, let $x$, $y$, $z$ be the numbers in consecutive positions(where ${x, y, s, z} = {a, b, c, d}$). Due to our hypothesis that in every $2 × 2$ subarrays each number is used exactly once, in the row above $R$(if there is such a row), precisely above the numbers $x$, $y$, $z$ will be the numbers $z$, $t$, $x$ in this order. And above them will be the numbers $x$, $y$, and $z$ in this order. The same happens in the rows below $R$ (see the following figure).


• x y z •
• z t x •
• x y z •
• z t x •
• x y z •


Completing the array, it easily follows that each column contains exactly two of the numbers and our claim is proven. (1)

Rotating the matrix (if it is necessary), we may assume that each row contains exactly two of the numbers. If we forget the first row and column from the array, we obtain a $4 × 4$ array, that can be divided into four $2 × 2$ subarrays, containing thus each number exactly four times, with a total sum of $4(a + b + c + d)$.

It suffices to find how many different ways are there to put the numbers in the first row $R1$ and the first column $C1$. (2)

Denoting by $a_1$, $b_1$, $c_1$, $d_1$ the number of appearances of $a$, $b$, $c$, and $d$ respectively in $R1$ and $C1$, the total sum of the numbers in the entire $5 × 5$ array will be $S = 4(a + b + c + d) + a1 \cdot a + b1 \cdot b + c1 \cdot c + d1 \cdot d$. (3)

If the first, third, and the fifth row contain the numbers $x$ and $y$, with $x$ denoting the number at the entry $(1, 1)$, then the second and the fourth row will contain only the numbers $z$, $t$, with $z$ denoting the number at the entry $(2, 1)$. Then $x_1 + y_1 = 7$ and $x_1 > 3$, $y_1 > 2$, $z_1 + t_1 = 2$, and $z_1 > t_1$. Then ${x_1, y_1} = {5, 2}$ or ${x_1, y_1} = {4, 3}$, respectively ${z_1, t_1} = {2, 0}$ or ${z_1, t_1} = {1, 1}$. (4)

Then $(a_1, b_1, c_1, d_1)$ is obtained by permuting one of the following quadruples: $(5, 2, 2, 0)$, $(5, 2, 1, 1)$, $(4, 3, 2, 0)$, or $(4, 3, 1, 1)$. (5)

There are a total of $4!/2! = 12$ permutations of $(5, 2, 2, 0)$, $12$ permutations of $(5, 2, 1, 1)$, $24$ permutations of $(4, 3, 2, 0)$, and $12$ permutations of $(4, 3, 1, 1)$. Hence, there are at most $60$ different possible total sums. (6)

We can obtain indeed each of these $60$ combinations: take three rows $ababa$ alternating with two rows $cdcdc$ to get $(5, 2, 2, 0)$; take three rows $ababa$ alternating with one row $cdcdc$ and a row $dcdcd$ to get $(5, 2, 1, 1)$; take three rows $ababc$ alternating with two rows $cdcda$ to get $(4, 3, 2, 0)$; take three rows $abcda$ alternating with two rows $cdabc$ to get $(4, 3, 1, 1)$. (7)

By choosing for example $a = 103$, $b = 102$, $c = 10$, and $d = 1$, we can make all these sums different. (8)

Hence, the maximum possible number of different sums is $\boxed{60}$.

See also

2016 JBMO (Problems • Resources)
Preceded by
Problem 3 		Followed by
Last Problem
1 • 2 • 3 • 4
All JBMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2016_JBMO_Problems/Problem_4&oldid=186393"