# Combinatorics contest math question [closed]

James has a red jar,a blue jar and a pile of 100 pebbles.Initially both jars are empty. A move consists of moving a pebble from the pile into one of the jars or returning a pebble from one of the jars to the pile. The numbers of pebbles In the red and blue jars determine the state of the game. The following conditions must be satisﬁed:

a)The red jar may never contain fewer pebbles than the blue jar;

b)The game may never be returned to a previous state.

What is the maximum number of moves that James can make?

## closed as off-topic by Morgan Rodgers, user91500, Jendrik Stelzner, José Carlos Santos, Mostafa AyazSep 13 '18 at 20:53

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Morgan Rodgers, user91500, Jendrik Stelzner, José Carlos Santos, Mostafa Ayaz
If this question can be reworded to fit the rules in the help center, please edit the question.

• Try this game with a smaller number of pebbles, and see what you can conclude. For example, try $1,2,3$ pebbles, and see if you notice any pattern. – астон вілла олоф мэллбэрг Sep 13 '18 at 7:06
• I really don't like when people get downvoted automatically just because they did not explain their efforts so far. The easisest way to avoid it is to supply a few (often naive or even silly) sentences describing something that may look like an honest try to solve the problem. But that's just cheating. In many cases you don't have the slightest idea how to approach the problem and in such cases it's fair to admit that you are helpless. This problem is interesting and deserves to be solved and I will upvote the question just to cancel the downvote. – Oldboy Sep 13 '18 at 9:38
• Hint: consider the problem for $N$ pebbles and make a $N \times N$ grid, where the point $(r,b)$ corresponds to $r$ and $b$ pebbles in the red and blue jar respectively. Which points are according to (a) allowed? Next color the grid points in a black/white checkerboard and play a few games and observe how you can move through the grid and how many black/white points you find in full games. If you get stuck let me know where and I give some more hints. – Ronald Blaak Sep 13 '18 at 12:37
• Guys, I solved it! Thanks for your inputs – Shashwat Tomar Sep 13 '18 at 13:51
• @oldboy I don't think that this is a particular nice way of contributing to this site. You essentially follow the hint I provided in the comment above (after the OP already mentioned to have it solved), post the intermediate result as a question as link and then use the solution I presented there to answer this question as if it were your own. – Ronald Blaak Sep 15 '18 at 7:47

For the sake of simplicy I'll solve the problem for $N=10$, leaving it up to you to extrapolate it for any given $N$.

Denote the number of pebbles in the red jar with $x$ and the number of pebbles in the blue jar with $y$. Represent allowed values for $x$ and $y$ in a plane and you get a shaded triangle. This shaded area represent the limits imposed in your problem: $x+y\le10$ and $x\ge y$. Each point with integer coordinates (including those on triangle edges) represent a valid state of your problem.

If you connect all game states you get a path. That path cannot use each valid point more than once (states cannot repeat). The length of the path represent the number of state transitions. A path of maximum lenght is obviously a solution to your problem.

One possible path of length 16 (with 17 points and 16 state transitions) is shown below:

Blue points have even value of $x+y$. Points with odd value of $x+y$ have red color. Notice that colors always change between consecutive points.

Let's count the total number of valid ($x,y$) points counting them from the bottom of the triangle: $11 + 9 + 7 + 5 + 3 + 1=36$

The number of red points can be determined in the same way: $5+4+3+2+1=15$. So if you use all red points, the maximum number of points in the path is $2\times15+1=31$, which means 30 state transitions.

Now we know the upper limit but is it reachable? Is it possible to construct such a path? Yes, in a fairly simple and straightforward way which is applicable to any number of pebbles. The following path has 31 points and 30 state transitions.

Please see detailed explanation of Ronald Blaak here who actually solve the most important part of this problem HERE

It can be shown that for any given (even) N, the maximum number of state transitions is:

$$2 + 4 + 6 + ... + N=\frac{N}{4}(N+2)$$

• Beautifully presented! – TonyK Sep 13 '18 at 14:12
• Two further questions- – Shashwat Tomar Sep 15 '18 at 5:47
• I solved the question without using graphs-is this ok? – Shashwat Tomar Sep 15 '18 at 5:47
• Secondly-Your solution is very elegant but I would have never had the creativity to convert the problem to a graphical format? How do you when it is optimal to do this? – Shashwat Tomar Sep 15 '18 at 5:49
• @user16701 All valid solutions are acceptable. If you were able to solve it without graphs, that's perfectly ok. To answer your second question: there is no simple recipe how to solve any kind of problem. You solve many and after that you start to see patterns in solutions. The next time you are presented with a problem looking like this one, you will have one more weapon in your arsenal. – Oldboy Sep 15 '18 at 6:30