{"id":839,"date":"2011-02-25T00:51:18","date_gmt":"2011-02-25T05:51:18","guid":{"rendered":"http:\/\/jsomers.net\/blog\/?p=839"},"modified":"2014-02-06T21:11:48","modified_gmt":"2014-02-07T02:11:48","slug":"project-euler-problem-191-or-how-i-learned-to-stop-counting-and-love-induction","status":"publish","type":"post","link":"https:\/\/jsomers.net\/blog\/project-euler-problem-191-or-how-i-learned-to-stop-counting-and-love-induction","title":{"rendered":"Project Euler problem 191, or, how I learned to stop counting and love induction"},"content":{"rendered":"

Of the 142 Project Euler problems<\/a> I've battled so far, it may just be that #191<\/a> has put up the most interesting fight, not because the problem itself was all that difficult or unusual or enlightening, but because the road to solving it---seven to ten hours of work, seven sheets of paper<\/a>, several trips to the online encyclopedia of integer sequences<\/a>, three or four minor insights, and one major breakthrough---was for me almost a paradigm of puzzle-solving, or, closer to the point, a paradigm of how a mathematically crippled mistake-prone dabbler like myself solves puzzles.<\/p>\n\n

Here's the problem statement that kicked it all off:<\/p>\n\n

\n

A particular school offers cash rewards to children with good attendance and punctuality. If they are absent for three consecutive days or late on more than one occasion then they forfeit their prize.<\/p>\n \n

During an n-day period a trinary string is formed for each child consisting of L's (late), O's (on time), and A's (absent).<\/p>\n \n

Although there are eighty-one trinary strings for a 4-day period that can be formed, exactly forty-three strings would lead to a prize:<\/p>\n\n

  OOOO OOOA OOOL OOAO OOAA OOAL OOLO OOLA OAOO OAOA\n  OAOL OAAO OAAL OALO OALA OLOO OLOA OLAO OLAA AOOO\n  AOOA AOOL AOAO AOAA AOAL AOLO AOLA AAOO AAOA AAOL\n  AALO AALA ALOO ALOA ALAO ALAA LOOO LOOA LOAO LOAA\n  LAOO LAOA LAAO\n<\/code><\/pre>\n  \n  
How many \"prize\" strings exist over a 30-day period?<\/p>\n<\/blockquote>\n\n
I encourage you to give it a shot. If you've solved lots of puzzles like this in the past, you'll probably be able to cook up a solution in under an hour. If not, expect to spend an afternoon or two scratching out all sorts of cases and conditions and combinatoric formulations. Either way it should be a great deal of fun.<\/p>\n\n
When I first saw the problem I had only two approaches in mind:<\/p>\n\n
    \n
  1. If we let n<\/code> be the number of days, we know that there are 3n<\/sup> possible strings of O<\/code>s and A<\/code>s and L<\/code>s. To find the number of \"prize\" strings, then, all we have to do is subtract<\/em> from 3n<\/sup> the number of strings that couldn't<\/em> be winners.<\/p><\/li>\n
  2. Or, we could go the constructive route and try to only count prize strings.<\/p><\/li>\n<\/ol>\n\n
    Intuition told me that the first way would be a lot easier, so that's the way I went.<\/p>\n\n
    A first crack<\/h3>\n\n
    The problem statement helps us out by giving the solution to a small case, n<\/code> = 4, which we can use to validate our approach before ramping up to the much trickier case where n<\/code> = 30.<\/p>\n\n
    What we're trying to do is enumerate all of the strings with either the substring AAA<\/code> or two or more not-necessarily-adjacent L<\/code>s, because these are the strings that are ineligible<\/em> for a prize. We know that we have 34<\/sup> = 81<\/strong> possible strings to begin with, and from the problem statement we've been told that 43<\/strong> of these are prize strings, so whatever rules or program we come up with to prune them should wipe out exactly 38<\/strong> (=81 - 43).<\/p>\n\n
    At a first pass I mustered the following rough (and wildly incorrect) count:<\/p>\n\n