I suck at combo

by math154, Aug 25, 2010, 10:41 PM

(2004 ISL C5.) Let $N$ be a positive integer. Two players $A$ and $B$ , taking
turns, write numbers from the set $\{1,\ldots,N\}$ on a blackboard. $A$ begins
the game by writing $1$ on his first move. Then, if a player has written $n$ on
a certain move, his adversary is allowed to write $n+1$ or $2n$ (provided the
number he writes does not exceed $N$ ). The player who writes $N$ wins. We
say that $N$ is of type $A$ or of type $B$ according as $A$ or $B$ has a winning
strategy.
(a) Determine whether $N=2004$ is of type $A$ or of type $B$ .
(b) Find the least $N>2004$ whose type is different from that of $2004$ .

Solution

Note: This is written pretty badly since I have homework to do.

Feel free to point out typos and stuff.

Define $f:\mathbb{Z}\to\{A,B\}$ so that $f(N)=A$ if $A$ can force a win for $N$ , and $f(N)=B$ otherwise. Obviously $f(1)=A$ and $f(2)=B$ (for convenience take $f(0)=B$ ). Let $a_1,a_2,a_3,\ldots$ (with $a_1=1$ ) be the sequence of numbers that $A$ writes down and $b_1,b_2,b_3,\ldots$ (with $b_1=2$ ) be the sequence of numbers that $B$ writes down.

Lemma 1: If $f(2t+1)=A$ , then for any $N\ge 2t+1$ , so that $B$ writes numbers so that $b_j\le N$ , there exists an index $i$ such that $A$ can write down $a_1,\ldots,a_i\le 2t+1$ with
$a_i\in\left(\frac{2t+1}{2},2t+1\right],\quad a_i\equiv2t+1\equiv1\pmod2.$ (The analogous result for $f(2t+1)=B$ also holds.)
Proof: Assume otherwise. Let
$I_1=\left(\frac{2t+1}{2},2t+1\right],I_2=\left(\frac{2t+1}{4},\frac{2t+1}{2}\right],\ldots.$ Say that a player writes a number that lies in $I_j$ . Then the other player writes a number either in $I_j$ or $I_{j-1}$ . We let $a_i=b_{i-1}+1$ for all $i$ so that $a_i$ is always odd and $b_i$ is always even. For some index $k$ , either $a_k\in I_1$ or $b_k\in I_1$ . In the former case, we have an obvious contradiction. In the latter case, $b_k$ is even whence it's at most $2t$ and we can take $a_{k+1}=b_k+1\in I_1$ , we get another contradiction. $\blacksquare$

Lemma 2: If $f(2t)=A$ , then for any $N\ge2t$ , so that $B$ writes numbers so that $b_j\le N$ , there exists an index $i$ such that $A$ can write down $a_1,\ldots,a_i\le 2t$ with
$a_i\in\left(t,2t\right],\quad a_i\equiv2t\equiv0\pmod2.$ (The analogous result for $f(2t)=B$ also holds.)
Proof: Assume otherwise. Let
$I_1=\left(t,2t\right],I_2=\left(\frac{t}{2},t\right],\ldots.$ Say that a player writes a number that lies in $I_j$ . Then the other player writes a number either in $I_j$ or $I_{j-1}$ . So for some index $k$ , either $b_k\in I_2$ or $a_k\in I_2$ . In the former case, we can take even $a_{k+1}=2b_k\in I_1$ , a contradiction. In the latter case, $B$ can write down even $b_k=2a_k\in I_1$ , which allows $B$ to eventually write down $2t$ (for $N=2t$ , $A$ is forced to repeatedly write one more than $B$ ), contradicting $f(2t)=A$ . $\blacksquare$

Lemma 3: If $N=2k+1$ is odd ( $k\ge0$ ), then
$f(N)=f(2k+1)=A.$
Proof: Note that $a_i\equiv1\pmod2\implies2a_i\equiv a_i+1\equiv0\pmod2$ , so $b_i\in\{2a_i,a_i+1\}$ must be even and thus strictly less than $N=2k+1$ . Thus we can take $a_{i+1}=b_i+1\equiv1\pmod2$ with $a_{i+1}\le N$ . (We start with $a_1=1$ , which is odd and at most $N$ .) $\blacksquare$

Lemma 4: If $N=2k$ is even ( $k\ge1$ ), then

\[f(N)=f(2k)=f\left(\left\lfloor{\frac{k}{2}\right\rfloor\right).\]

Proof: This is obviously true for $k=1$ , so now assume $k\ge2$ . Consider the intervals
$I_1=(k,2k=N],I_2=\left(\frac{k}{2},k\right],I_3=\left(\frac{k}{4},\frac{k}{2}\right].$ WLOG assume that

\[f\left(\left\lfloor{\frac{k}{2}\right\rfloor\right)=A,\]

so $A$ can find a sequence of moves with $a_i\in I_3$ and $a_i\equiv\lfloor{k/2}\rfloor\pmod2$ by the first and second lemmas. Parity tells us that $B$ will be forced to write down some $b_r\in I_2$ , whence $a_{r+1}=2b_r\in I_1$ , which is of course even, allows $A$ to win. $\blacksquare$

Thus $f(0)=B$ , $f(2k+1)=A$ , $f(4k+2)=f(4k)=f(k)$ , so the rest is trivial.

Motivation: Since combinatorial insights take forever for me to see, the $n\mapsto2n$ part motivates the consideration of the intervals
$\left(\frac{N}{2},N\right],\left(\frac{N}{4},\frac{N}{2}\right],\left(\frac{N}{8},\frac{N}{4}\right],\ldots.$

This post has been edited 2 times. Last edited by math154, Aug 26, 2010, 1:17 AM

combinatorics

games

Comment

2 Comments

The post below has been deleted. Click to close.

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

HMMMM JUst take the integer n base 2 and it's probably a lot easier to write up and understand

by JacobGuo, Aug 26, 2010, 12:07 AM

Report

The post below has been deleted. Click to close.

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

Well the official solution with binary numbers is certainly nice and probably equivalent in some way to my solution, but I don't feel like it would be too convenient to write out my solution as it is with binary numbers... and I dunno, for me the approach I used seems more direct, probably since I can't do any hard combo...

This post has been edited 1 time. Last edited by math154, Aug 26, 2010, 1:22 AM

by math154, Aug 26, 2010, 1:19 AM

Report

Submit

!!!!!!!!
by stroller, Mar 10, 2020, 8:15 PM
cooooooool
nice blog
by Navansh, Jun 4, 2019, 7:47 AM
Victor is one of the GOATs.
by awesomemathlete, Oct 2, 2018, 11:48 PM
This blog is truly amazing.
by sunfishho, Feb 20, 2018, 6:32 AM
what a gem.
by vjdjmathaddict, May 10, 2017, 3:26 PM
Advertisement
by ahaanomegas, Dec 15, 2013, 7:21 PM
yo dawg i heard you imo
by Mewto55555, Aug 1, 2013, 10:25 PM
Good job on 5 problems on USAMO. I know that is a pretty bad score for someone as awesome as you on a normal USAMO, but no one got all 6 this year so it's GREAT!

VICTOR WANG 42 ON IMO 2013 LET'S GO.

See you at MOP this year (probably ).
by yugrey, May 3, 2013, 10:32 PM
you can just write "Solution
" instead of "Click to reveal hidden text
"

by math154, Feb 6, 2013, 6:33 PM
Hello. May I ask a stupid question: how to turn "Hidden Text" into hidden "Solution" tag?
by ysymyth, Feb 1, 2013, 12:59 PM
This is a good blog.I like it.
by Lingqiao, Jul 17, 2012, 4:21 PM
hi.i like the blog.
by Dranzer, Feb 9, 2012, 12:25 PM
sorry, i've decided this blog is just for the random stuff i do. don't take it personally... you can always post things on your own blog
by math154, Nov 23, 2011, 10:26 PM
what i got uncontribbed for posting a nice geo problem?
by yugrey, Nov 23, 2011, 1:32 AM
Can I be a contributor?
by Binomial-theorem, Oct 5, 2011, 12:39 AM
by gauss1181, Mar 8, 2009, 5:09 PM
i hate you
by alsyy, Mar 8, 2009, 4:37 PM
Fine. I don't care.
by math154, Mar 8, 2009, 1:34 AM
Math154: It was West Somethign Middle School from Columbia that got 2nd.
by Mewto55555, Mar 8, 2009, 1:20 AM
Oh dang, I already feel like deleting this blog. Maybe I should not do that for a while, though.
by math154, Mar 6, 2009, 2:50 AM
math154 mew and tinytim tied for first at chapter...
by AIME15, Mar 6, 2009, 1:06 AM
Thanks! Good luck to you too.
by math154, Mar 5, 2009, 1:00 AM
good luck on saturday
by gauss1181, Mar 5, 2009, 12:51 AM
Yeah gauss, our chapter sends the top 50 individuals and the top 10 teams.
by math154, Mar 4, 2009, 10:49 PM
Me wants be contrib.
by AIME15, Mar 4, 2009, 5:07 PM
I'll contrib in the future when I feel like it. I'm not gonna forget you, though, so don't worry.
by math154, Mar 2, 2009, 11:55 PM
third! contrib?
by nikeballa96, Mar 2, 2009, 10:40 PM
2nd Shout!
by gauss1181, Feb 28, 2009, 5:25 PM
1st Shout!
by mathemagician1729, Feb 28, 2009, 4:02 AM

101 shouts

I guess this is a blog

I suck at combo

by math154, Aug 25, 2010, 10:41 PM

2 Comments