Maths Olympiad Prep

Library / /245 of 520

Combinatorics Difficulty 6.9 National olympiad Find the answer

Given a matrix {aij}i,j=09\{a_{ij}\}_{i,j=0}^{9}, aij=10i+j+1a_{ij}=10i+j+1. Andrei is going to cover its entries by 5050 rectangles 1×21\times 2 (each such rectangle contains two adjacent entries) so that the sum of 5050 products in these rectangles is minimal possible. Help him.
A. Badzyan

Solution

To solve this problem, we need to minimize the sum of the products of the entries in the 1×21 \times 2 rectangles. Let's break down the steps to achieve this:

1. Define the Matrix:
The matrix {aij}i,j=09\{a_{ij}\}_{i,j=0}^{9} is given by aij=10i+j+1a_{ij} = 10i + j + 1. This means each element in the matrix can be calculated using this formula.

2. Calculate the Products:
For each 1×21 \times 2 rectangle, we need to calculate the product of the two adjacent entries. There are two possible orientations for each rectangle:
- Horizontal: covering entries aija_{ij} and ai(j+1)a_{i(j+1)}
- Vertical: covering entries aija_{ij} and a(i+1)ja_{(i+1)j}

3. Compare the Products:
We need to compare the sum of the products for different configurations to find the minimal possible sum. Let's consider the products for both horizontal and vertical rectangles:
- Horizontal product: aijai(j+1)a_{ij} \cdot a_{i(j+1)}
- Vertical product: aija(i+1)ja_{ij} \cdot a_{(i+1)j}

4. Observation and Comparison:
We need to compare the sum of products for different configurations. Let's consider the following observation:
aijai(j+1)+a(i+1)ja(i+1)(j+1)>aija(i+1)j+ai(j+1)a(i+1)(j+1) a_{ij} \cdot a_{i(j+1)} + a_{(i+1)j} \cdot a_{(i+1)(j+1)} > a_{ij} \cdot a_{(i+1)j} + a_{i(j+1)} \cdot a_{(i+1)(j+1)}
This inequality suggests that the sum of products is minimized when we use vertical rectangles rather than horizontal rectangles.

5. Summing the Products:
To minimize the sum of the products, we should use vertical rectangles. Let's calculate the sum of the products for vertical rectangles:
i=08j=09aija(i+1)j \sum_{i=0}^{8} \sum_{j=0}^{9} a_{ij} \cdot a_{(i+1)j}
Each vertical rectangle covers two adjacent entries in the same column.

6. Calculate the Sum:
We need to calculate the sum of the products for all vertical rectangles:
i=08j=09(10i+j+1)(10(i+1)+j+1) \sum_{i=0}^{8} \sum_{j=0}^{9} (10i + j + 1) \cdot (10(i+1) + j + 1)
Simplifying the expression inside the sum:
(10i+j+1)(10(i+1)+j+1)=(10i+j+1)(10i+10+j+1)=(10i+j+1)(10i+j+11) (10i + j + 1) \cdot (10(i+1) + j + 1) = (10i + j + 1) \cdot (10i + 10 + j + 1) = (10i + j + 1) \cdot (10i + j + 11)
Expanding the product:
(10i+j+1)(10i+j+11)=100i2+20ij+10i+10ij+j2+11j+10i+j+11=100i2+30ij+j2+21j+20i+11 (10i + j + 1)(10i + j + 11) = 100i^2 + 20ij + 10i + 10ij + j^2 + 11j + 10i + j + 11 = 100i^2 + 30ij + j^2 + 21j + 20i + 11

7. Summing Over All Rectangles:
We need to sum this expression over all valid ii and jj:
i=08j=09(100i2+30ij+j2+21j+20i+11) \sum_{i=0}^{8} \sum_{j=0}^{9} (100i^2 + 30ij + j^2 + 21j + 20i + 11)

8. Final Calculation:
This double sum can be computed by summing each term separately:
i=08j=09100i2+i=08j=0930ij+i=08j=09j2+i=08j=0921j+i=08j=0920i+i=08j=0911 \sum_{i=0}^{8} \sum_{j=0}^{9} 100i^2 + \sum_{i=0}^{8} \sum_{j=0}^{9} 30ij + \sum_{i=0}^{8} \sum_{j=0}^{9} j^2 + \sum_{i=0}^{8} \sum_{j=0}^{9} 21j + \sum_{i=0}^{8} \sum_{j=0}^{9} 20i + \sum_{i=0}^{8} \sum_{j=0}^{9} 11

Each of these sums can be computed separately, but the key observation is that using vertical rectangles minimizes the sum of the products.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.