To review:
>There are approximately 1030 schemata present in a single string of L = 100.  Even if we restrict ourselves to schemata defined on 4 positions, the number of such schemata is still large.  For a string of L = 100 there are 4,000,000 distinct sets of 4 positions, so each schema will exhibit one of the 81 possible variants for each of these sets.
A schema must have one of three letters{1,0,#} at each of its defining positions.  Thus if we select a particular set of k defining positions, 3k variants are possible.  For k = 4, there are 34 = 81 distinct schemata to be tested.
>Because there are only 81 alternatives for each set, we can still be assured that a rather small population will test all of the alternatives at all positions.  A population of a few hundred strings can produce useful estimates for all of the 81 x 4,000,000 schemata defined on 4 positions.  Nine times out of ten such schemata will be passed on to the next generation without disruption by crossover. 
>From this we see that, with genetic algorhythms, the agent tests a very large number of schemata, even if we restrict our attention to the shorter schemata that are largely undisturbed by crossover.  This is so even if the agent uses only a small number of rules (strings). Because one rule, in itself, is an instance of a large number of short schemata, it would be surprising if none of the short strings were consistently associated with above average performance.