Differing views

Source: Australian Mathematical Society Gazette Puzzle Corner

Problem: An optimist and a pessimist are examining a sequence of numbers. The optimist remarks, ‘Oh jolly! The sum of any eight consecutive terms is positive!’ But the pessimist interjects, ‘Not so fast, the sum of any five consecutive terms is negative.’ Can they both be right? How long can this sequence of numbers be?

Incentive: Treat at H8 Canteen/Sodexho Cafeteria for the first person to solve it :P

Update (27/07/10): Solution: Posted in comments by Varun Jog (Berkeley Grad Student, EE IITB Alumnus) and Siddhant Agarwal (EE Senior Undergraduate, IITB)

Comments

  1. Varun Jog3:47 PM, July 25, 2010

    The max possible length of the sequence is 11.
    Proof that > 11 is not possible:
    Consider the first 12 numbers-- a1,a2,a3,...a12
    Since sum of 10 consecutive numbers is negative (2 blocks of 5), we can get
    a1+a2 < 0 (1)
    a3+a4 < 0 (2)
    Note also that
    a2+a3+a4 > 0 (consider the 8 block starting from a2 and cut out the last 5)
    Hence a5+a6 < 0 (3)(The 5 block from a2 has to be negative)
    Similarly a4+a5+a6 > 0 => a7+a8 < 0 (4)
    1,2,3,4 imply sum of first 8 numbers is negative, which is not true.

    A seq of length 11 could be
    10, -12, 11, 2.55, -11.8, 10, -11.8, 2.55, 11, -12, 10
    (That we can assume the seq to be symmetric simplifies the search)

    ReplyDelete
  2. sid7:15 PM, July 25, 2010

    there is a more elegant proof which I read in problem solving strategies:

    a1+a2+...+a5<0
    a2+a3+...+a6<0
    ..
    a8+a9+...+a12<0

    so u see the rows sums are negative. And all column sums are positive. Contradiction! So max number possible is 11 and I am a mortal to doubt the eg of Varun Jog :)

    ReplyDelete
  3. NG10:35 PM, July 25, 2010

    Its a famous(bad-famous) IMO problem I think.

    ReplyDelete
  4. Pratik Poddar9:26 AM, July 27, 2010

    Awesome solution :) Thanks :)

    BTW, A friend at Morgan Stanley (Lets call him A - Since he does not want to be named :P) gave a better sequence
    -1.6 at positions 2, 5, 7, 10
    1 at positions 1, 3, 4, 6, 8, 9, 11

    ReplyDelete
  5. Pratik Poddar3:03 PM, July 27, 2010

    @sid.. nice proof :) Thanx

    ReplyDelete

Post a Comment

Popular posts from this blog

Buying Dimsums

Source: Alok Goyal (Stellaris VP, Ex-Helion VC) puzzle blog Problem: A fast food restaurant sells dimsums in boxes of 7 and 3. What’s the greatest number of dimsums a person cannot buy. Generalize it for p and q where p and q are relatively prime. I loved the puzzle. Hope you enjoy it too.
Read more

Fraction Brainteaser

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20 out of 28 Geometry questions.  In total, Siddhant scores 25 out of 34.  Vaibhav writes another Maths test and correctly answers 20 out of 25 Arithmetic questions and 6 out of 9 Geometry questions. in total, Vaibhav scores 26 out of 34. Note that a) Vaibhav scores more than Siddhant b) Siddhant score better than Vaibhav in both individual topics -  5/6 > 20/25 and 20/28 > 6/9 How is it possible? 
Read more

Consecutive Heads

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process. 1) Calculate P{X>Y} 2) What's the expected value of X 3) What's the expected value of Y This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment. Solution: 1) (Solved by me finally after 13 months :)) Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently. So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0" f(State) = P(X>Y | "State" configuration initially) ...
Read more