Maximum length sequence with negative and positive subsequences

107 Views Asked by At

From ' mathematical puzzles' By Peter Winkler:

" At the stockholders' meeting the CEO presents month-by-month profits and losses and declares : ' Since the last meeting we have made a profit in every consecutive 8-month period!'

But a shareholder says 'we have also made a loss in every consecutive 5-month period'.

What is the maximum number of months that could have passed since the last meeting?"

In other words : find the maximum length sequence such that the sum of all 5-long consecutive subsequences are negative and the sum of all 8-long consecutive subsequences are positive

It will be less than 8*5=40 since otherwise there would be a simultaneous positive 8-long partition and negative 5-long partition of the 40 months.

The solution in the book is rather elaborate (proof by induction that the solution is x+y-2 where x=8 and y=5) (and whilst the puzzles are great the writing style is obscure imho)

I am sure there must be a simpler solution .... but I cannot find one !