Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Two friends are playing a game. In every turn, after one of them says a number $k$, the other one has to say a number in form $a\cdot b$ where $a,b\in \mathbb{N}$ such that $a+b=k$ holds. The game continues in that way, from a just said number.

From which numbers could the game have started if at one point one of the friends said number $2011$?

share|improve this question
add comment

2 Answers 2

up vote 10 down vote accepted

Short answer: We can start at any number larger then $4$.

Solution: Instead of $2011$, suppose we are given any integer $\alpha$, and we want to know when we can reach $\alpha$. Suppose we start at $k$, and $k>4$. Then choose $a=\lfloor \frac{k}{2}\rfloor$ and $b=\lceil\frac{k}{2}\rceil$. (If $k$ is even, this is just $a=b=\frac{k}{2}$). Then because $k>4$, we will have that $ab>k$, so the sequence grows and by repeating this it will eventually be larger then $\alpha$. Now, we can decrease the sequence by $1$ at any point by choosing $a=1$, $b=k-1$, so once we have passed $\alpha$, we can just decrease by one at a time until we reach exactly $\alpha$.

For integers $k\leq 4$, notice that there is no choice of nonnegative $a$, $b$ such that $a+b=k$ and $a\cdot b>k$, so we are confined to this short interval.

share|improve this answer
    
Thank you. Are there any general directions how I should think when solving problems like these? I couldn't even classify this in "number theory", as someone added a tag, I though it was more combinatorics. Some links? –  Lazar Ljubenović Feb 12 '12 at 15:44
3  
@LazarLjubenović: One thing I suggest, is just go and try easy cases. Try things and see what happens! Can you construct 2011? What happens if $a=1$? What happens if $k$ is $1$, $2$, $3$, $4$, $5$, or $6$. My solution comes purely from thinking about these simple cases. Often, even for difficult problems, you'd be surprised how often, thinking about the small cases, or just carrying through a calculation can lead you to the proof, and help understand what is going on. –  Eric Naslund Feb 12 '12 at 15:47
add comment

You can start at $5$ with the sequence $5,6,9,20,96,1008,2012,2011$ and with any larger number since each step can reduce $k$ by $1$.

You cannot start with $1,2,3$ or $4$, since you cannot increase from these.

For such problems you can explore which possibilities lead to the final result.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.