P2- second combinatorics exam of 2017 Iran MO 3rd round

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

P2- second combinatorics exam of 2017 Iran MO 3rd round

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2017 Iran MO 3rd round, second combinatorics exam P2

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

178 posts

bgn

#1 h Sep 12, 2017, 3:16 PM • 2 Y

Y by Adventure10, Mango247

Two persons are playing the following game on a $n\times m$ table, with drawn lines:
Person $\#1$ starts the game. Each person in their move, folds the table on one of its lines. The one that could not fold the table on their turn loses the game.
Who has a winning strategy?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

370 posts

#3 h Jan 7, 2018, 8:51 AM • 2 Y

Y by Adventure10, Mango247

I don't quite understand the question. Does it mean that the table is never unfolded? In other word, is it equivalent to that everyone cut a rectangle off the table?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

191 posts

#4 h Jan 8, 2018, 10:56 AM • 2 Y

Y by Adventure10, Mango247

Let $f(1)=1,f(2n)=n,f(2n+1)=f(n)$ . Then the second player has the winning strategy iff $f(n) \oplus f(m)=0$

This post has been edited 1 time. Last edited by ltf0501, Jan 8, 2018, 10:56 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

328 posts

#6 h Jul 27, 2018, 3:47 AM • 2 Y

Y by Adventure10, Mango247

we would define a number to be deadly

if it can be written in form of $2^k-1$ in which $k\in N$ otherwise we call peaceful

claim: the first player has strategy of winning if and only if $m$ and $n$ are not both deadly!

steps to prove the claim:

$1-$ first prove is both $m$ and $n$ are deadly then second player is going to win!

$2-$ thereupon prove both $m$ and $n$ are both peaceful then the first player will win (just for hint take numbers in form of $2^k+3$ into your consideration!)

$3-$ the next step is to say fist player can always fold the table in a way such as that which can transform a table with one peaceful and one deadly side to one in which both sides are deadly!

$4-$ then with number three it's actually obvious that fist player will win if one side is peaceful and one is deadly

This post has been edited 3 times. Last edited by H.HAFEZI2000, Jul 27, 2018, 9:08 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1472 posts

math90

#7 h Jul 27, 2018, 5:48 AM • 2 Y

Y by Adventure10, Mango247

I don’t understand the statement of the problem. Could someone explain it?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

328 posts

#8 h Jul 27, 2018, 9:13 AM • 1 Y

Y by Adventure10

math90 wrote:

I don’t understand the statement of the problem. Could someone explain it?

simply a $n \times m$ table with n columns and m rows then each time you choose a rectangle in which three sides of that are on borders of the table and also its area less or equal to the half area of the rectangle at the beginning of the step! the one who ends up with a $1 \times 1$ square is lost!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

65 posts

Arefe

#10 h Aug 21, 2020, 3:09 PM • 1 Y

Y by Mango247

H.HAFEZI2000 wrote:

math90 wrote:

I don’t understand the statement of the problem. Could someone explain it?

simply a $n \times m$ table with n columns and m rows then each time you choose a rectangle in which three sides of that are on borders of the table and also its area less or equal to the half area of the rectangle at the beginning of the step! the one who ends up with a $1 \times 1$ square is lost!

I think we should choose the area with more than or equal to half of the rectangle !

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

65 posts

Arefe

#11 h Aug 21, 2020, 3:27 PM

Y by

It's easy to see by induction first on $n \in \mathbb {N}$ and then on $k \in \mathbb {W}$ that for each $n$ , $m=2^k(n+1)-1$ is the winning for the second player .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

162 posts

#12 h Sep 12, 2020, 5:32 AM • 2 Y

Y by Juanscholtze, Nathanisme

same as above
From now on suppose the $\# \text{rows} \leq \# \text{columns}$
The method is by induction.
A situation which first person wins is $W$ and if looses $L$

If $n=1$
$\spadesuit$ Notice if $m=i$ is $L$ then $m\in \{i+1,\dots,2i \}$ is $W$ by folding to the $L$ position.

$\textbf{Claim 1 :-}$ $m=2i+1$ is $L$ .
Proof: Notice by any folding of first person we get to a $1 \times j$ s.t $j \geq \lceil \frac{2i+1}{2} \rceil =i+1$
So since $j \leq 2i$ by $\spadesuit$ We are stuck in a $W$ for second person. ( position changed) $\square$
now by above claims it's obvious that for $n=1$ $W$ 's are $2^k -1$ s.t $k\in \mathbb{N}$ inductively.

$\textbf{Main Claim :-}$ $[n \times m]$ s.t $m\geq n$ is $L$ if and only if $m \in (a_i)_{i\in \mathbb{Z}_{\geq 0}} \begin{cases} a_{i+1}=2a_{i}+1 \\ a_0 = n \end{cases}$
I proved it for $[1 \times m]$ now suppose it's true for $[i \times m] \quad \forall i \in \{1,\dots ,n-1\}$ . I prove it for $i=n$

$\textbf{Claim 2:}$ $[ n \times n]$ is $L$ .
Proof: wlog first player fold by the columns so we get to a $[j \times n]$ s.t $n > j \geq \lceil \frac{n}{2} \rceil$
FSoC it's $W$ then by induction hypothesis $n \in (a_i)_{i\in \mathbb{Z}_{\geq 0}} \begin{cases} a_{i+1}=2a_{i}+1 \\ a_0 = j \end{cases}$
But Obviously this sequence is increasing and $2j+1 \geq 2 \lceil \frac{n}{2} \rceil +1 >n$ Contradiction. $square$

$\textbf{Claim 3 :-}$ If $[n \times i]$ is $L$ then $[n \times j] \quad \forall j\in \{i+1 ,\dots, 2i \}$ is $W$ .
Proof: It's obvious because first player can fold to $[n \times i]$ and now she is the second player there and by previous claim we know she wins.

So now make the sequence $(a_i)_{i\in \mathbb{Z}_{\geq 0}} \begin{cases} a_{i+1}=2a_{i}+1 \\ a_0 = n \end{cases}$ I claim if $m \in (a_i)$ it's $L$ otherwise it's $W$ .

So suppose it's true for $m \in \{ n, \dots ,i\}$ and let $a_r$ be the largest term of the sequence $<i$ . So $a_r < i \leq a_{r+1}$
If $i < a_{r+1}=2a_r +1$ Then by $\textbf{Claim 3}$ It's $W$ .

So suppose $i=a_{r+1} = 2a_r +1$
FSoC suppose it's $W$ .

Case 1 : first player folds by column, So we have a $[n \times i]$ s.t $2a_r +1 > i \geq \lceil \frac{2a_r+1}{2} \rceil = a_r +1$ .
So by $\textbf{Claim 3}$ It's now winning for the second person. ( position changed ). Contradicting winning of the first player.

Case 2 : She folds by the rows. So it become $[j \times 2a_r+1]$ s.t $n > j \geq \lceil \frac{n}{2} \rceil$
Now by induction hypothesis we should have $2a_r +1 \in (a_i)_{i\in \mathbb{Z}_{\geq 0}} \begin{cases} a_{i+1}=2a_{i}+1 \\ a_0 = j \end{cases}$
Notice the sequence is reversible by $a_i = \frac{ a_{i+1} -1}{2}$ So by reversing $n$ should appear in the sequence ( notice $n>j$ ).

But as we know the sequence is increasing and $a_1 = 2j+1 \geq 2 \lceil \frac{n}{2} \rceil +1 >n$ impossible.
So We are finally Done $\mathfrak{Q.E.D}$
Notice the final answer becomes $\boxed {(n+1) 2^k -1}$
notes on exam

This post has been edited 6 times. Last edited by Gaussian_cyber, Sep 13, 2020, 1:17 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

109 posts

Eliot

#14 h Sep 14, 2020, 5:47 PM

Y by

$\mathrm{ }$

This post has been edited 1 time. Last edited by Eliot, Oct 5, 2020, 1:10 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

162 posts

#15 h Sep 14, 2020, 6:02 PM

Y by

@2above
Yes it was pretty easy. (not suitable for 3rd round imo)
It's long because getting them into words were a bit hard for me.
Also I have some ideas for the 3D I'm gonna share soon in this post [will edit it]
Also @above what’s your induction hypothesis, The same method (at least mine) fails in 3D.
If you have a generalizable proof post it plz

This post has been edited 2 times. Last edited by Gaussian_cyber, Sep 14, 2020, 6:33 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

539 posts

Mr.C

#16 h Sep 14, 2020, 6:30 PM

Y by

Eliot wrote:

hmm.. How is your folding in 3D?
In the way that is in my mind

The same kind of induction works except you should suppose like the length of row less than column less than width?

try it ... it won't work ...
.
@above
the $3D$ version is really hard , i had some real good improvement but i couldnt "solve" it , i could only solved some subsets of the problem
.
@2above , i would like to see your aproach and solution if its possible would you post it?

This post has been edited 2 times. Last edited by Mr.C, Sep 14, 2020, 7:25 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a