Difference between revisions of "2022 IMO Problems/Problem 6"
Griphomaniac (talk | contribs) (→Problem) |
m (→Solution) |
||
| (5 intermediate revisions by 3 users not shown) | |||
| Line 9: | Line 9: | ||
Find, as a function of <math>n</math>, the smallest possible total number of uphill paths in a Nordic square. | Find, as a function of <math>n</math>, the smallest possible total number of uphill paths in a Nordic square. | ||
| + | |||
| + | ==Video solution== | ||
| + | https://www.youtube.com/watch?v=-AII0ldyDww [Video contains solutions to all day 2 problems] | ||
==Solution== | ==Solution== | ||
| − | + | ''The minimum total number of uphill paths in a Nordic square is <math>2n(n-1)+1</math>'' | |
| − | For every pair of adjacent cells in the grid, there is at least one pathway that begins at the higher valued cell, steps to the lower valued cell, and then continues stepping to lower adjacent cells until (by finite descent) a valley is reached. When reversed, this forms an uphill pathway that terminates at that exactly that pair of adjacent cells | + | '''Proof:''' |
| + | For every pair of adjacent cells in the grid, there is at least one pathway that begins at the higher valued cell, steps to the lower valued cell, and then continues stepping to lower adjacent cells until (by finite descent) a valley is reached. When reversed, this forms an uphill pathway that terminates at that exactly that pair of adjacent cells. | ||
| − | There are <math>2n(n-1)</math> such adjacent pairs ( | + | There are <math>2n(n-1)</math> such adjacent pairs (each with at least one unique uphill path). In addition, the cell containing the value 1 will always be a valley which, by itself, forms an additional (singleton) uphill path. Therefore the minimum total number of uphill paths is at least <math>2n(n-1)+1</math>. |
| − | The diagram below shows | + | The diagram below shows a general family of constructions of Nordic squares that achieve this lower bound, thus proving the claim: |
[[File:2022 IMO 6.png|900px|center]] | [[File:2022 IMO 6.png|900px|center]] | ||
| − | In these constructions, numbers are progressively inserted into the white spaces in ascending order emanating outwards from the "1" in the corner in the directions of the red arrows, and the remaining j largest numbers are then inserted into the cells labelled as "mountains". In this manner, the | + | In these constructions, numbers are progressively inserted into the white spaces in ascending order emanating outwards from the "1" in the corner in the directions of the red arrows, and the remaining j largest numbers are then inserted into the cells labelled as "mountains". In this manner, the pathway of finite descent from each pair of adjacent cells is unique, and all terminate at the "1" valley, therefore the above-derived minimum is achieved. <math>\blacksquare</math> |
| + | |||
- [[User:Griphomaniac|Griphomaniac]] ([[User talk:Griphomaniac|talk]]) 13:16, 21 July 2022 (EDT) | - [[User:Griphomaniac|Griphomaniac]] ([[User talk:Griphomaniac|talk]]) 13:16, 21 July 2022 (EDT) | ||
| + | |||
| + | ==See Also== | ||
| + | |||
| + | {{IMO box|year=2022|num-b=5|after=Last Problem}} | ||
Latest revision as of 18:17, 30 January 2024
Contents
Problem
Let 
be a positive integer. A Nordic square is an 
board containing all the integers from 
to 
so that each cell contains exactly one number. Two different cells are considered adjacent if they share an edge. Every cell that is adjacent only to cells containing larger numbers is called a valley. An uphill path is a sequence of one or more cells such that:
(i) the first cell in the sequence is a valley,
(ii) each subsequent cell in the sequence is adjacent to the previous cell, and
(iii) the numbers written in the cells in the sequence are in increasing order.
Find, as a function of , the smallest possible total number of uphill paths in a Nordic square.
Video solution
https://www.youtube.com/watch?v=-AII0ldyDww [Video contains solutions to all day 2 problems]
Solution
The minimum total number of uphill paths in a Nordic square is 
Proof: For every pair of adjacent cells in the grid, there is at least one pathway that begins at the higher valued cell, steps to the lower valued cell, and then continues stepping to lower adjacent cells until (by finite descent) a valley is reached. When reversed, this forms an uphill pathway that terminates at that exactly that pair of adjacent cells.
There are 
such adjacent pairs (each with at least one unique uphill path). In addition, the cell containing the value 1 will always be a valley which, by itself, forms an additional (singleton) uphill path. Therefore the minimum total number of uphill paths is at least .
The diagram below shows a general family of constructions of Nordic squares that achieve this lower bound, thus proving the claim:
In these constructions, numbers are progressively inserted into the white spaces in ascending order emanating outwards from the "1" in the corner in the directions of the red arrows, and the remaining j largest numbers are then inserted into the cells labelled as "mountains". In this manner, the pathway of finite descent from each pair of adjacent cells is unique, and all terminate at the "1" valley, therefore the above-derived minimum is achieved. 
- Griphomaniac (talk) 13:16, 21 July 2022 (EDT)
See Also
| 2022 IMO (Problems) • Resources | ||
| Preceded by Problem 5 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Last Problem |
| All IMO Problems and Solutions | ||
