In the year 4096, while making an intergalactic excursion to planet 2048 in galaxy 1024, your space vehicle ran out of fuel and you crash landed on planet 512. Unfortunately, the inhabitants of the planet do not welcome visitors and so planned to execute you by chopping you into 256 pieces before scattering your remains to 128 different national parks to be fed on by 64 different strange creatures residing in each park.
You have one chance to stay alive: Before the day of execution, you will participate in the "Powers of Two Stacking Festival". If you manage to emerge victorious in the festival, your life will be spared as the inhabitants think it would be a waste to execute such an intelligent living being.
At the start of the festival, all participants are placed in separate rooms where there are a countless number of cards with the number 2 written on them. Whenever two cards of 2 are stacked together, they magically fuse together to become a card of 4 and you are 'awarded' 4 points. In turn, when you stack together two cards of 4, they fuse to become a card of 8 and you are 'awarded' 8 points. As a general rule of thumb, two identical cards of 2 n fuse to become a single card of 2 n + 1 when they are stacked together and you are 'awarded' 2 n + 1 points whenever you perform this operation.
The game ends when a card of 2048 is produced. Your final score is calculated by adding all the points 'awarded' to you in the process plus the number of operations you carry out (An operation is defined by the process of stacking together two cards, so you can only stack 2 cards in a single operation). All the participants are competing to get the lowest final score. The participant with the lowest final score is declared the winner. It is possible for multiple winners to exist if more than one participant share the same lowest final score.
To emerge victoriously, you need to achieve the least possible score allowed since some of the participants are extremely smart and will always achieve the least attainable score.
What is the minimum score attainable in the game?
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.
For completeness, note that your approach only calculates a lower bound. It doesn't show that this lower bound is the greatest possible as yet. You still need to give a construction to justify that it can be achieved.
When you make the first 4 , you receive the minimum of 2 2 + 1 , where 2 2 are the points awarded and 1 is the number of operation.
When you make the first 8 , you receive the minimum of 2 ( 2 2 + 1 ) + 2 3 + 1 = 2 3 + 2 3 + 2 + 1 = ( 3 − 1 ) × 2 3 + 2 + 1 , where 2 ( 2 2 + 1 ) is because you've made 2 number 4 's.
When you make the first 1 6 , you receive the minimum of 2 ( 2 3 + 2 3 + 2 + 1 ) + 2 4 + 1 = 2 4 + 2 4 + 2 4 + 2 2 + 2 + 1 = ( 4 − 1 ) × 2 4 + 2 2 + 2 + 1 , where 2 ( 2 3 + 2 3 + 2 + 1 ) is because you've made 2 number 8 's.
So, when you make the first 2 n , you receive the minimum of ( n − 1 ) × 2 n + 2 n − 2 + 2 n − 3 + . . . + 2 + 1 .
With n = 1 1 , when you make the first 2 0 4 8 = 2 1 1 , you receive the minimum of 1 0 × 2 1 1 + 2 9 + 2 8 + . . . + 2 + 1 = 2 0 4 8 0 + 2 1 0 − 1 = 2 1 5 0 3 .
Problem Loading...
Note Loading...
Set Loading...
It is easy to see that the minimum score is attained if we only have a card of 2 0 4 8 when the game ends and the rest of the cards are 2 since we do not perform unnecessary operations or gain excess points by fusing extra cards together, ie. if we play optimally, the number of operations and points "awarded" are both minimized.
Define the function f ( n ) and g ( n ) where f ( n ) denotes the least possible points "awarded" when a card of 2 n is produced while g ( n ) denotes the least possible number of operations performed when a card of 2 n is produced. In other words, since 2 1 1 = 2 0 4 8 , we want to find f ( 1 1 ) + g ( 1 1 ) .
It is trivial to note that f ( 1 ) = 0 . To compute f ( 2 ) , note that to obtain a card of 4 , we fuse together two cards of 2 , so f ( 2 ) = 2 . 2 1 = 4 . To compute f ( 3 ) , since we are fusing together two cards of 4 , we end up with 2 . 2 2 + 2 f ( 2 ) points. Note that 2 . 2 2 are the points obtained upon fusing while 2 f ( 2 ) points are cumulative from our previous operations leading to the production of two cards of 4 .
This can be easily generalized. Therefore, we obtain the following recurrence formula:
f ( n ) = 2 f ( n − 1 ) + 2 n .
This recurrence formula is nice and all, but let’s try and find a closed form for f ( n ) . Let’s use n = 3 and n = 4 as motivating examples.
For 2 3 = 8 , note that the points awarded come from 2 3 when the card is produced and 2 2 . 2 as the cumulative points. So we can write f ( 3 ) = 2 3 . 1 + 2 2 . 2 .
Similarly, for 2 4 = 1 6 , the points awarded come from 2 4 and 2 f ( 3 ) = 2 ( 2 3 . 1 + 2 2 . 2 ) . Therefore, we can write f ( 4 ) = 2 4 . 1 + 2 3 . 2 + 2 2 . 2 2 .
These observations lead naturally to the conjecture:
f ( n ) = 2 n . 1 + 2 n − 1 . 2 + ⋯ + 2 2 . 2 n − 2
= ( n − 1 ) 2 n .
Substituting this into our recurrence formula above, we find that this formula is indeed true.
Now, to calculate g ( n ) , first notice that g ( n + 1 ) = 2 g ( n ) + 1 . To get the card 2 n + 1 form fusing two cards of 2 n , we need 1 operation while 2 g ( n ) denotes the cumulative operations leading to the production of the two 2 n cards.
Let’s try to find a closed form for g ( n ) . After writing out a few values, we find that g ( 1 ) = 0 , g ( 2 ) = 1 , g ( 3 ) = 3 , g ( 4 ) = 7 , g ( 5 ) = 1 5 . It does not take too much ingenuity for us to conjecture that g ( n ) = 2 n − 1 − 1 . Substituting this into our recurrence formula, we find that this is indeed true.
Therefore,
g ( n ) + f ( n ) = 2 n − 1 − 1 + ( n − 1 ) 2 n
g ( 1 1 ) + f ( 1 1 ) = 2 1 0 − 1 + ( 1 0 ) 2 1 1 = 2 1 5 0 3
It is easy to see that this minimum score is indeed attainable. In fact, it is suggested by the recurrence formula. To get the card 2 n + 1 , we focus on assembling two cards of 2 n separately before fusing them together, starting from n = 1 . This way, we can ensure that no extra cards is produced.