Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Jan 20, 2010

Brave Warrior

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!!

6 comments:

  1. the order in which the warrior should cut the heads.

    100-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

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

    ReplyDelete
  3. well, i found another one

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

    ReplyDelete
  4. @Bhanu.. Thanx for the proof.

    I 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.

    ReplyDelete
  5. 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
  6. @Ramdas..
    sure..
    essentially I am doing the same thing..
    using the explanation by BFS would have been better.. Thanx

    ReplyDelete