Slime slayer

Steve is being attacked by an army of slimes. There are different sizes of slimes and Steve needs to hit them with his sword as follows:

  • A level 0 slime needs to be hit once to be killed.
  • A level 1 slime needs to be hit once, then it divides into 3 level 0 slimes.
  • A level 2 slime needs to be hit 4 times, then it divides into 3 level 1 slimes.
  • For n > 2 n>2 , a level n n slime needs to be hit 4 n 1 4^{n-1} times, then it divides into 3 level n 1 n-1 slimes.

What is the smallest possible number of slimes, given that the army of slimes takes 10 000 hits total to be destroyed?


The answer is 7.

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.

1 solution

Tarmo Taipale
Oct 24, 2017

Let's first prove that an n n -level slime will take 4 n 4^n hits total to be killed. By induction:

When n = 0 n=0 , the n n -level slime takes 1 = 4 0 1=4^0 hits and the statement holds true.

Then, let's suppose the statement holds true for n = m n=m and prove it holds true for n = m + 1 n=m+1 : The m m -level slime takes 4 m 4^m hits to be destroyed. The m + 1 m+1 -level slime takes 4 m 4^m hits to divide into three level m m slimes. The total number of hits for slime level m + 1 m+1 is 4 m + 3 × 4 m = 4 × 4 m = 4 m + 1 4^m+3 \times 4^m = 4 \times 4^{m} = 4^{m+1} , and the statement is proven.

This means we can represent the number of slimes of each level by defining a 0 , a 1 , . . . a_0, a_1, ... for each n n where a n a_n is the number of n n -level slimes in the army. By the fact proven above and the fact tha the whole army takes 10 000 to destroy, we get

a 0 + 4 a 1 + 4 2 a 2 + . . . + 4 n a n = 10000 a_0+4a_1+4^2a_2+...+4^na_n=10000

where n n is the level of the highest-level slime.

If we present the number 10000 10 000 as a number in 4-base number system, i.e. 10000 = ( a n a n 1 . . . a 1 a 0 ) 4 10 000=(a_na_{n-1}...a_1a_0)_4 the equation above holds true which means this combination of slimes is one of the possible ones. Let's show it is the one with the least slimes.

It is a known fact that each integer n n has an unambiguous presentation in k k -base number system (and thus, the number 10 000 in 4-base system), i.e. n = a 0 + k a 1 + k 2 a 2 + . . . n=a_0+ka_1+k^2a_2+... where a 0 , a 1 , . . . a_0,a_1,... are integers between 0 0 and k 1 k-1 . That means, all other combinations of slimes has at least one of numbers a 0 , a 1 . . . a_0,a_1... with a value greater than 3 3 . If we have one combination, and a i a_i is such number in it, we can form another combination of slimes by replacing four i i -level slimes with one i + 1 i+1 -level slime. This combination has less slimes, and we have proven that the combination of slimes formed by the 4-base presentation of 10 000 has the least slimes.

Let's transform 10 000 into base 4:

10000 = 2 × 4096 + 1024 + 3 × 256 + 16 = 2 × 2 6 + 1 × 2 5 + 3 × 2 4 + 1 × 2 2 10 000=2\times4096+1024+3\times256+16=2\times2^6+1\times2^5+3\times2^4+1\times2^2

The combination has 2 level 6 slimes, 1 level 5 slime, 3 level 4 slimes and 1 level 2 slime which makes 2 + 1 + 3 + 1 = 7 2+1+3+1=\boxed{7} total.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...