Ook ook

At Brilli's zoo, she is trying to train a monkey to learn how to count. The monkey is given a stack of cards, numbered 1 to 30, in some random order. The cards are laid out from left to right. Each time the monkey moves the card numbered i + 1 i+1 to the immediate right of the card numbered i i , he gets a banana. Otherwise, the monkey gets an ant bite and has to undo his move.

What is the most number of bananas that the monkey can get?

Details and assumptions

No monkeys (or ants) were harmed in the making of this question.

The monkey does not get a banana if the card numbered i + 1 i+1 is already to the immediate right of the card numbered i i .

As an explicit example, if the first four cards were { 1 , 3 , 2 , 5 } \{1, 3, 2, 5 \} and the monkey moves card number 3 to the right of card number 2, the stack becomes { 1 , 2 , 3 , 5 } \{ 1, 2, 3, 5 \} and the monkey gets a banana.


The answer is 435.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

8 solutions

Daniel Chiu
Dec 8, 2013

First, we establish a bound.

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

Proof: We prove this result by induction.

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

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

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

Thus, since each card i i can be moved a maximum of i 1 i-1 times, the maximum number of moves is i = 1 30 i 1 = 0 + 1 + 2 + + 29 = 29 30 2 = 435 \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 , , 1 30,29,\cdots,1 ). By moving the first card every time, the final order of 1 , 2 , , 30 1,2,\cdots,30 will be achieved in 435 moves. This is true since after m ( m 1 ) 2 \dfrac{m(m-1)}{2} moves, the last m m cards will be in order. Then, the answer is 435 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 i exactly i 1 i-1 times.

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

Perfect!

Cody Johnson - 7 years, 6 months ago

Oh no, I forgot to box my answer! :( In case it is not clear, the answer is 435.

Daniel Chiu - 7 years, 6 months ago

This means that any card having a greater value can be moved to the right of a card with smaller value....isn't the question a bit misleading about saying that any other move other than moving (i+1) to the immediate right of i will cause an ant bite and undo the move??

Eddie The Head - 7 years, 6 months ago

Log in to reply

If the monkey can move cards in any way with no consequences, then the maximum will be infinite. Putting the restriction ensures that there is an upper bound on the possible number of moves that can be made.

Lino Demasi - 7 years, 6 months ago

I don't see anything misleading. The question means that the only legal moves are moving card i i to the right of card i 1 i-1 .

Daniel Chiu - 7 years, 6 months ago
Timothy Zhou
Dec 9, 2013

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

Can you explain why having the cards in reverse order maximizes the bananas?

Lino Demasi - 7 years, 6 months ago
Katie Gardner
Dec 9, 2013

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 :)

Can you explain why this has to be the maximum?

Lino Demasi - 7 years, 6 months ago

Log in to reply

I'm not really sure how how to explain it properly. I just had the reasoning that you could do no moves if they were in ascending order and so if the cards were in totally the opposite order then you would have the most potential moves to reverse them.

Katie Gardner - 7 years, 6 months ago
Stefano Scx
Dec 9, 2013

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

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

Anubhav Balodhi
Jul 1, 2015

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 (n*(n-1))/2 . Thus for n=30, we have ( 30 ( 30 1 ) ) / 2 (30*(30-1))/2 = ( 15 ( 29 ) ) (15*(29)) = 435 435

Lokesh Gupta
Jan 18, 2014

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.

Matheus Naves
Dec 21, 2013

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: i = 1 n x \displaystyle \sum_{i=1}^n x where n is the position of the term a n a_{n} in the sequence. As we want the number of reassignments maximums of 30 cards, only to find the term number 29. So:

i = 1 29 x \displaystyle \sum_{i=1}^{29} x = 1 + 2 + 3 + + 29 1 + 2 + 3 + \ldots + 29 = ( 1 + 29 ) × 29 2 \frac {(1+29) \times 29}{2} = 435 \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 30, 29, 28, ..., 2, 1 . Namely, this is the only configuration where for every pair of indices, i i and j j , i < j a i > a 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 2 ) = 30 29 2 = 435 {{30} \choose {2}} = \frac{30*29}{2} = \boxed{435} .

How do you know each move can make only one pair ordered correctly? Also, how do you know that 435 is the maximum?

Daniel Chiu - 7 years, 6 months ago

I believe you misinterpreted the question. You can move the cards however many spaces you want; you are not restricted to just switching one adjacent card with another. A bell should have rung when the problem said "otherwise, the monkey is bitten and has to retract his move."

Michael Tong - 7 years, 6 months ago

Michael: I don't think so. In my suggested sequence of moves (below) I have moved cards in arbitrary amounts of spaces.

Daniel: You are correct, I have wrongly written that each move in the optimal solution makes one ordered pair correctly arranged. It is actually sometimes possible to lose ordering between some pairs. But, what we get in total is something equivalent to improving only one at a time:

30 29 28 27 30\, 29\, 28\, 27 ... (initial ordering)

29 30 28 27 29\, 30\, 28\, 27 ... (numbers ( 29 , 30 ) (29, 30) in order)

30 28 29 27 30\, 28\, 29\, 27 ... (numbers ( 28 , 29 ) (28, 29) in order now, but at the expense of losing the order of ( 29 , 30 ) (29, 30) )

28 29 30 27 28\, 29\, 30\, 27 ... (...but now we have ordered ( 28 , 29 ) , ( 29 , 30 ) , ( 28 , 30 ) (28, 29), (29, 30), (28, 30) ! Equivalent to improving only one at a time)

However, I still wasn't able to write a formal proof for why we necessarily must get these orderings back "for free" in a latter correct move. I will keep trying.

Thank you for pointing this out! I have obviously jumped to conclusions a bit too quickly, and my approach could've been wrong in the end.

Petar Veličković - 7 years, 6 months ago

Log in to reply

The reason I thought that was because you said that "the monkey has to make the amount of moves equal to the amount of indices" but that's not necessarily true. Given 30 , 29 , 28 , 27...1 30, 29, 28, 27 ... 1 or, really, any arbitrary sequence such that the card i + 1 i+1 does not appear to the right of card i i , we can arrange this completely in only 29 29 moves. e.g. for n = 5 n = 5

5 4 3 2 1

5 4 3 1 2

5 4 1 2 3

5 1 2 3 4

1 2 3 4 5

Michael Tong - 7 years, 6 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...