Given an integer \( n \geq 1 \), Jo-Ané alternately writes crosses (\( \mathcal{X} \)) and circles (\( \mathcal{O}\)) in the cells of a square grid with \( 2n + 1 \) rows and \( 2n + 1 \) columns: she first writes a cross in a cell, then a circle in a second cell, then a cross in a third cell, and so on. When the table is completely filled, her score is calculated as the sum \( \mathcal{X}+ \mathcal{O} \), where \( \mathcal{X} \) is the number of rows containing more crosses than circles and \( \mathcal{O} \) is the number of columns containing more circles than crosses. Determine, in terms of \( n \), the highest possible score that Jo-Ané can obtain..
Problem
Source: Pan African Mathematics Olympiad P3
Tags: PAMO 2024, combinatorics
16.08.2024 03:09
The answer is $\boxed{4n}$. You can simply prove this by proving that a score of $4n+1$ or more is impossible since we would then need to count all rows or all columns, so we must have at least $(n+1)(2n+1)=2n^2+3n+1$ X's or O's, but we only have $2n^2+2n+1$ X's and $2n^2+2n$ O's (contradiction). Then, you can construct a grid with a particular algorithm to achieve a score of $4n \forall n\geq 1$ as follows: 1. Fill the entire column $C_{n+1}$ with X's. 2. Fill the entire row $R_{n+1}$ with O's except the square $(R_{n+1},C_{n+1})$. 3. Starting from $R_1$ on top up to row $R_n$, for odd indices $R_i$ fill all columns $C_j$ with X's for $n+2\leq j\leq 2n+1$, and fill the rest with O's. Also, for even indices $R_i$, reverse the argument. 4. Starting from $R_{n+2}$ up to $R_{2n+1}$, for odd indices $R_i$ fill all columns $C_j$ with X's where $1\leq j\leq n$ and fill the rest with O's. Do the reverse for even indices. This gives a score of $X+O=|\{R_1,R_2,...,R_n,R_{n+2},...,R_{2n+1}\}|+|\{C_1,C_2,...,C_n,C_{n+2},...,C_{2n+1}\}|=2n+2n=4n$.
16.08.2024 03:12
fasttrust_12-mn wrote: Given an integer \( n \geq 1 \), Jo-Ané alternately writes crosses (\( \mathcal{X} \)) and circles (\( \mathcal{O}\)) in the cells of a square grid with \( 2n + 1 \) rows and \( 2n + 1 \) columns: she first writes a cross in a cell, then a circle in a second cell, then a cross in a third cell, and so on. When the table is completely filled, her score is calculated as the sum \( \mathcal{X}+ \mathcal{O} \), where \( \mathcal{X} \) is the number of rows containing more crosses than circles and \( \mathcal{O} \) is the number of columns containing more circles than crosses. Determine, in terms of \( n \), the highest possible score that Jo-Ané can obtain.. It's 2019 Argentina IberoAmerican TST P1 (it isn't uploaded though)
16.08.2024 03:32
Some solutions in Spanish here
27.08.2024 23:47
BR1F1SZ wrote: It's 2019 Argentina IberoAmerican TST P1 (it isn't uploaded though) As far as I know, the origin is 2017 Czech and Slovak MO, 1st round P1. Not uploaded to AoPS, but see here (in Slovak).
20.09.2024 13:15
pepat wrote: BR1F1SZ wrote: It's 2019 Argentina IberoAmerican TST P1 (it isn't uploaded though) As far as I know, the origin is 2017 Czech and Slovak MO, 1st round P1. Not uploaded to AoPS, but see here (in Slovak). Is it normal for a P3 and P6 from PAMO to be stolen?? this is not fair