Two players $A$ and $B$ play a game on a $1\times m$ board, using $2012$ pieces numbered from $1$ to $2012.$ At each turn, $A$ chooses a piece and $B$ places it to an empty place. After $k$ turns, if all pieces are placed on the board increasingly, then $B$ wins, otherwise $A$ wins. For which values of $(m,k)$ pairs can $B$ guarantee to win?
Problem
Source: Turkish TST 2012 Problem 6
Tags: LaTeX, combinatorics proposed, combinatorics
29.03.2012 14:28
Do you mean that in order B to win all the 2012 pieces must be placed increasingly or no matter how many are placed if they are placed increasingly B wins?
29.03.2012 23:39
I think after $k$ turns, only that $k$ pieces must be placed increasingly.
30.03.2012 14:33
If m>=2012 then certainly player B is garantee to win just by placing every piece with n number(1=<n<=2012) to the n numbered box(k can be any natural number). If m=1 I think they will have to decide whether it is placed increasingly or not. If 1<m<2012 then we have of course 1<=k<=m(If k>m it is like we have k=m). For k=1 it's up to the players to decide.For k>1 if k=m player A can start by choosing 1,2,3,.. so player B would have to put them at the same numbered box. Then when the only empty boxes will be the two last and there are at least 3 numbers left player A chooses any number that it is not the min or 2012(max) so if B places it in the m-box A can choose a bigger number so B can't win or if he places it in the m-1 box he can choose a smaller(B also loses).If k<m then we have to determine in what occassion A can do the trick he did before.For example when k=m number 2011 had to be put at least at the 2011 box or m(if m<=2011) but if k=4 and m=100 B can put 2011 at the fourth box and be secured because A can not choose more than 3 numbers smaller than 2011.So B wins only if at the start of the game for every n with 1=<n<=2012 n can be placed in at least one box where the total boxes before this one are equal or more than min{k-1,n-1} and the total boxes after this one are equal or more than min{k-1,2012-n}.it is not expressed in a form of pairs but it contains every possible occassion.
18.04.2012 20:35
cartmanez wrote: but if k=4 and m=100 B can put 2011 at the fourth box and be secured because A can not choose more than 3 numbers smaller than 2011.So B wins So we don't have the whole solution here, but for this sentence I think you made a litle mistake; $A$ takes $100$ $B$ has to place it on $1,2$ or $3$ and then $A$ takes $101,102$ (when it wasn't on the first place or $99,98$ else to let $B$ lose. Also dear friend, can you use more space between the texts and use Latex to make your solution is easier to read? ** $m \ge 2012$ $B$ wins as shown by cartmanez For $m <2012$ just let $k \ge log_2(m+2)$ to let $A$ wins and otherwise $B$ wins, just by putting the $i^{th}$ given number on a $2^{k-i}$ muliple that goes. $A$ also use this system : gives number $2^{k-1}+1$ at start and then a number $2^{k-i}$ bigger in the next steps, when $B$ places the number $N$ on a place smaller than $N$ at some step, $A$ just fill in between $N$ and $N^{-1}.$ (previous given number of zero if it was at start). Else $A$ goes on until the biggest possible $N$ is constructed, $A$ use some each time the biggest power of $2$ adding at the previous number.
20.04.2012 23:12
k is the number of turns and m is the number of boxes so if m=100 k=4 and A chooses 100 why B has to place it on 1,2 or 3? He can place it anywhere from 4 to 97 and be secured.