**Source:**Insight (IITB Newsletter) Questech

**Problem**:

In a land far away, there is a village threatened by an hundred-headed beast. This beast can only be killed by cutting of all the hundred heads. Legend says that any brave warrior can cut off exactly 10, 20, 30 or 40 heads at one time. However with each of these, 40, 2, 60 and 4 new heads appear respectively.

The village has lost several brave warriors against this beast. Can you save the village from this beast ?

Update(21/01/10):

**Solution:**Solution provided by Bhanu Prakash (M.Tech Student, CSE, IITB) in comments!!

the order in which the warrior should cut the heads.

ReplyDelete100-20=82

82-40=46

46-40=10

10-10=0 and so he is dead..

I am sure this problem is not that trivial.so please say me what i am missing

Prove that this is the best you can do. :)

ReplyDeletewell, i found another one

ReplyDelete100-40=64

64-20=46

46-40=10

10-10=0

The possible number of heads after first try is

130, 82, 64

similarly after second try

160, 112, 94, 46, 28

Similarly after third try

10,..etc

and hence the solutions provided are the best possible...:)

@Bhanu.. Thanx for the proof.

ReplyDeleteI wrote the solution in dynamic programming form to get the proof.

best(100)= min{best(130), best(82), best (130), best(64)} + 1 = min{best(82), best (130), best(64)} + 1;

best(130) >= 4 {as 40*3<130}

best(82) >= 3 {as 40*2<82}

best(64)= min{best(94), best(46), best (28)} + 1

best(94) >= 3 {as 40*2<94}

best(46) >= 2 {as 40*1<46}

best(28) >= 2 {as we are anyways not able to do it in 1 chance}

So, best(64)>= 3;

So, best(100)>=4;

Since the solution given by you

100-20+2 = 82

82-40+6 = 46

46-40+4 = 10

10-10 = 0

takes 4 steps, it is an optimal solution. You can find different optimal solutions.

Thanx for the solution and proof.

wont a happy BFS solve it. why DP? makes sense only if u want to solve for any N I guess, but if u want to prove that for 100, 4 is the best then simple BFS tree shud show it i guess?

ReplyDelete@Ramdas..

ReplyDeletesure..

essentially I am doing the same thing..

using the explanation by BFS would have been better.. Thanx