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 to the immediate right of the card numbered 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 is already to the immediate right of the card numbered i .
As an explicit example, if the first four cards were { 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 } and the monkey gets a banana.
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.
Perfect!
Oh no, I forgot to box my answer! :( In case it is not clear, the answer is 435.
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??
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.
I don't see anything misleading. The question means that the only legal moves are moving card i to the right of card i − 1 .
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?
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?
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.
We can asign a value for each copule of consecutive numbers, such that the value of couple ( i , i + 1 ) is 3 0 − 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 , . . . , 3 0 contains all possible couples, so S = 2 3 0 ⋅ 2 9 . 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 3 0 − k .
When the cards are in order we have that S is equal to 2 3 0 ⋅ 2 9 so the monkey stops. So, we need to sort the cards so that S increases of 1 at each step. So we start with 3 0 , 2 9 , 2 8 , 2 7 , . . . , 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 2 3 0 ⋅ 2 9 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 ( 3 0 ∗ ( 3 0 − 1 ) ) / 2 = ( 1 5 ∗ ( 2 9 ) ) = 4 3 5
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: 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:
i = 1 ∑ 2 9 x = 1 + 2 + 3 + … + 2 9 = 2 ( 1 + 2 9 ) × 2 9 = 4 3 5 .
The monkey will earn the most bananas in the event that the array is initially sorted in descending order: 3 0 , 2 9 , 2 8 , . . . , 2 , 1 . Namely, this is the only configuration where for every pair of indices, i and j , i < j ⟹ 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, ( 2 3 0 ) = 2 3 0 ∗ 2 9 = 4 3 5 .
How do you know each move can make only one pair ordered correctly? Also, how do you know that 435 is the maximum?
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: 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:
3 0 2 9 2 8 2 7 ... (initial ordering)
2 9 3 0 2 8 2 7 ... (numbers ( 2 9 , 3 0 ) in order)
3 0 2 8 2 9 2 7 ... (numbers ( 2 8 , 2 9 ) in order now, but at the expense of losing the order of ( 2 9 , 3 0 ) )
2 8 2 9 3 0 2 7 ... (...but now we have ordered ( 2 8 , 2 9 ) , ( 2 9 , 3 0 ) , ( 2 8 , 3 0 ) ! 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.
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 3 0 , 2 9 , 2 8 , 2 7 . . . 1 or, really, any arbitrary sequence such that the card i + 1 does not appear to the right of card i , we can arrange this completely in only 2 9 moves. e.g. for 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
Problem Loading...
Note Loading...
Set Loading...
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 i = 1 ∑ 3 0 i − 1 = 0 + 1 + 2 + ⋯ + 2 9 = 2 2 9 ⋅ 3 0 = 4 3 5
Now, we give a construction proving this bound is achievable. Consider the initial configuration of the cards in reverse order ( 3 0 , 2 9 , ⋯ , 1 ). By moving the first card every time, the final order of 1 , 2 , ⋯ , 3 0 will be achieved in 435 moves. This is true since after 2 m ( m − 1 ) moves, the last m cards will be in order. Then, the answer is 4 3 5 .
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 2 n ( n − 1 ) .