A game with rice

88 Views Asked by At

You have $N$ rices, and K places. You can put or take a rice in place numbered $1$ at any time. You can put a rice or take a rice from a place numbered $i$ iff there is a rice at a place $i-1$.

For example for $N=2,K=3$, you put a rice at a place $1$, then you put a rice at a place $2$, then you take a rice from a place $1$, and you finally put that rice at a place $3$.

I've noticed that as far as you can go is $2^N-1$ (i.e. how big $K$ can be). It can be proven by induction that you can reach $2^N-1$, by reaching $2^{N-1}-1$ with $N-1$ rices, and then putting a rice at a place $2^{N-1}$, then inversely picking back those $N-1$ rices(which you can do because put and take are symmetric), and putting those $N-1$ rices ahead of $2^{N-1}$ up to $2^N-1$, as if position $2^{N-1}+1$ were position $1$. That is, strategy with first playing with $N-1$ rices, and then involving the $N$-th one can't do better than this.

Is there a way with playing with all $N$ rices "from the start", and reaching further than $2^N-1$? Also if anyone has heard of a game like this it would be nice if you would put me to a paper or a link.

1

There are 1 best solutions below

7
On

You want the first rice grain in the final configuration to be placed as far along the game board as possible. The process you describe to put that grain at position $2^{N-1}$ doesn't have any obvious improvement, in terms of how far up the board it is. Placing that grain is not even the halfway point in the game, so you haven't really played with any fewer than $N$ rice grains; you've just been discriminating about when you use them.

I'm reasonably sure that the maximum $K$ is $2^N-1$ as you have already noticed.


In terms of move count, each placement has a recursive pattern of (build) - (place support grain) - (remove) - (build on support). Both "build" and "remove" are based on placing (or removing) support grains in the same pattern with one fewer grain to play with.

So an upper bound on number of moves to place top grains is 1, 4, 13, 40, etc., each count one more than three times the previous, as determined by the recursive nature of the process.

Initially however you can place a rice grain in one of these positions more quickly in the intermediate steps, and still remove all the supporting grains, reducing this number. So for example with four grains, you can obviously place and clear beneath a grain at position 4 in 7 steps rather than 9 (=4+1+4) from the upper bound above. However when it comes time to remove that grain, you'll need the full 9 steps because you won't have the spare grain any more. So the upper bound move count can be improved.

For non-maximum targets, some method of choosing intermediate support grains will be needed.