Ook ook

First, we establish a bound.

Lemma: The maximum number of times card $i$ can be moved is $i-1$ .

Proof: We prove this result by induction.

The base case $i=1$ is true, since card 1 cannot be moved.

For the inductive step, assume the lemma holds for $i=k$ . Then, card $i=k+1$ can be moved once initially, and it can only be moved again if card $k$ is moved, since otherwise card $k+1$ is already to the right of card $k$ . By the inductive hypothesis, card $k$ can only be moved at most $k-1$ times. Since card $k+1$ can be moved once for each time card $k$ is moved, and including the original move, card $k+1$ can be moved a maximum of $k-1+1=k$ times.

Thus, by induction, card $i$ can be moved at most $i-1$ times, completing the induction and the proof of the lemma.

Thus, since each card $i$ can be moved a maximum of $i-1$ times, the maximum number of moves is $\sum_{i=1}^{30} i-1=0+1+2+\cdots+29=\dfrac{29\cdot 30}{2}=435$

Now, we give a construction proving this bound is achievable. Consider the initial configuration of the cards in reverse order ( $30,29,\cdots,1$ ). By moving the first card every time, the final order of $1,2,\cdots,30$ will be achieved in 435 moves. This is true since after $\dfrac{m(m-1)}{2}$ moves, the last $m$ cards will be in order. Then, the answer is $435$ .

Motivation: I tried 4 cards, and found a maximum of 6 moves, starting in reverse order. I also noticed that I moved card $i$ exactly $i-1$ times.

Generalization: For $n$ cards, the maximum number of moves is $\dfrac{n(n-1)}{2}$ .

This made me think of recursion. Let's arrange all the cards in reverse numerical order, so no card i has i+1 to the right, to maximize our bananas.

For 1 card there are 0 ways to earn food.

For 2 cards there is only 1 flip.

For 3 cards, (3, 2, 1) we flip the first two cards before switching them to after the 1. 3 moves required.

For 4 cards, we take 3 moves to order the cards 2341 before switching them to after the 1. 3+3=6 moves required.

For 5 cards, similarly, we arrange the first four to 23451 before switching the 4 in front: 6+4=10 ways. Hmm there seems to be a pattern. 1+2+3+4...

Generalizing to 30 cards, the number of bananas gained is 1+2+...+29 = (30)(29)/2 = 435

The way that the monkey can get the most bananas is if the cards are laid out in reverse order

So to start with lets say there were only 3 cards. The monkey would start with 3-2-1 and then do

2-3-1

3-1-2

1-2-3

It would first move the 3 next to the 2, and then the 2 followed by the 3 next to the one (1 + 2 moves)

Now say the monkey had 4 cards, it would start with 4-3-2-1 and do

3-4-2-1

4-2-3-1

2-3-4-1

3-4-1-2

4-1-2-3

1-2-3-4

First it moves the 4 next to the 3, then it moves the 3 followed by the 4 next to the 2, and the 2 followed by 3 followed by 4 next to the one (1 + 2 + 3) moves

So this is related to the triangle numbers. (as we have 1, 1+2, 1+2+3 1+2+3+4...etc) So the formula for the number of cards and the number of moves is n(n-1)/2 where n is the number of cards

substituting in 30 gives 15 * 29 = 435.

So the maximum number of bananas the monkey can get is 435 :)

We can asign a value for each copule of consecutive numbers, such that the value of couple $(i,i+1)$ is $30-i$ . The value of the string is $S$ that is given by the sum of values of the couples that contains. For example the string $1,2,3,4,...,30$ contains all possible couples, so $S=\frac{30\cdot 29}{2}$ . Given any string, we can prove that $S$ always increases when the monkey moves a card in the right way. In fact when the monkey moves the card $k$ , placing it on the right of $k-1$ , if the right hand of $k$ was $k+1$ , $S$ increases of $1$ , else $S$ increases of $30-k$ .

When the cards are in order we have that $S$ is equal to $\frac{30\cdot 29}{2}$ so the monkey stops. So, we need to sort the cards so that $S$ increases of $1$ at each step. So we start with $30,29,28,27,...,1$ . The initial value of $S$ is $0$ . Easily occurs that the monkey can increase $S$ of $1$ at each step with appropriate moves. So the monkey stops after $\frac{30\cdot 29}{2}$ moves.

For 1 card. ans=0

For 2 card. ans=1.

For 3 card. ans=3

This is the series of Triangular numbers, $(n*(n-1))/2$ . Thus for n=30, we have $(30*(30-1))/2$ = $(15*(29))$ = $435$

If stacks are numbered 1 to N, the general answer to this question is Summation (N-1). i.e. (N-1)xN/2. In this case, N=30, so summation 30 = 29x30/2 = 435.

To understand the pattern of movement, let us take an example of 5 cards.The initial arrangement and movement is such that the bananas are maximized.

Initial arrangement= 54321.

Movement=

54321->

45321->

53421->

34521->

45231->

52341->

23451->

34512->

45123->

51234->

12345.

If the descending order of the cards we provide the largest number of rearrangements according as they had request to the monkey, we note by varying the number of cards that the number of maxima reshuffling follows this sequence: 1,3,6,10,15...

Where each term can be written as: $\displaystyle \sum_{i=1}^n x$ where n is the position of the term $a_{n}$ in the sequence. As we want the number of reassignments maximums of 30 cards, only to find the term number 29. So:

$\displaystyle \sum_{i=1}^{29} x$ = $1 + 2 + 3 + \ldots + 29$ = $\frac {(1+29) \times 29}{2}$ = $\boxed{435}$ .

The monkey will earn the most bananas in the event that the array is initially sorted in descending order: $30, 29, 28, ..., 2, 1$ . Namely, this is the only configuration where for every pair of indices, $i$ and $j$ , $i < j \implies a_i > a_j$ . With each correct move, the monkey makes one of those orderings correct; meaning, to sort the entire array in ascending order, the monkey has to make the amount of moves equal to the amount of pairs of indices. This is equal to the amount of 2-combinations of 30, ${{30} \choose {2}} = \frac{30*29}{2} = \boxed{435}$ .