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?

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$

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

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

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!

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 !

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 .

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

$\mathrm{ }$

@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

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?