Math Is Fun Forum

After thinking more about my suggestion, if you were allowed to check for positivity of numbers then it'd be fairly trivial. a < b iff a-b < 0, etc.

This would work though:

I think it's easier to list all the length-n strings that don't contain three zeroes in a row.

There are three types of these:
- Type 1: those that end with 1
- Type 2: those that end with 10 (and the string 0)
- Type 3: those that end with 100 (and the string 00)

You can get relations out of these quite nicely.

Starting with length-1 strings, we have 0 and 1.
That is one Type 1 string, one Type 2 string and no Type 3 strings.
We can write this as (1,1,0).

The length-2 strings are 00, 01, 10, 11.
The number of types can be summarised as (2,1,1).

The length-3 strings are 001, 010, 011, 100, 101, 110, 111.
This summarises as (4,2,1).

You can get the triple for a length-n string by using the triple for the length-(n-1) string.

For every length(n-1) string, you can get a Type 1 length-n string by adding a 1 to the end.
For every Type 1 length(n-1) string, you can get a Type 2 length-n string by adding a 0.
And similarly, you get a Type 3 length-n by adding to a Type 2 length(n-1).

Therefore, if the triple for one length of string is (a,b,c), then the triple for the next length of string will be (a+b+c, a, b).

Going back to your question, you can find the number of strings that do contain 000 by finding the number that don't, and taking this away from 2^n.

Hopefully I've explained that well enough, but here's a table to show what I mean.

Length | Type 1s | Type 2s | Type 3s | Total | Strings containing 000
--------------------------------------------------------------------------
   1   |    1    |    1    |    0    |   2   |   0
   2   |    2    |    1    |    1    |   4   |   0
   3   |    4    |    2    |    1    |   7   |   1
   4   |    7    |    4    |    2    |   13  |   3
   5   |    13   |    7    |    4    |   24  |   8
   6   |    24   |    13   |    7    |   44  |   20
   7   |    44   |    24   |    13   |   81  |   47
   8   |    81   |    44   |    24   |   149 |   107
   9   |    149  |    81   |    44   |   274 |   238
  ...

I'd do this by listing the first few terms and spotting the pattern.

Thinking of integration as an area is certainly a useful technique when it works, but the problem is that there are some integrable functions where that doesn't make sense.

One example would be

f(x) = {1, if x is rational.
          {0, otherwise.

It depends on exactly what you're allowed to do.

One way would be to subtract one from every element in the list, and keep doing so until only one of the elements is positive. (Or if they all start non-positive, add one to each element until one of them becomes positive)

Ah, now I see how this works. Nice puzzle.

I agree with bobby. I think having the alphabet on top of the ad looks better than the other way around.
1) loses points with me because I have to scroll down to see XYZ.

Mine is more efficient, but 220ms is still virtually nothing and it probably took me a good while longer to write mine.
I tend to try making my code as optimal as I can even when it's not really necessary. Yours is probably a lot easier to debug too. (In fact, for a bit mine was giving a different answer to yours, and it took me a little while to figure out the reason)

Still, at least it's good practice for problems where efficiency can mean the difference between minutes and days.

By the way, thanks for mentioning FreeMat. I only had access to MATLAB while at University, and I've been looking for a good replacement for a while now.

I've always written it the opposite of that way. But I also use a |.

ie., for me, P(A|B) means P(A), given B.

Since the questions are symmetric though, it doesn't matter too much. No matter how you interpret it, you'll give a set of correct answers.

The way to answer these questions is to work out the ways of both events happening, then divide by the ways of the given event happening.

For the first question, there is only one way of rolling a 5 with the first dice and totalling 10 - rolling two fives.

But there are 6 ways of rolling a 5 with the first:
(5,1); (5,2); (5,3); (5,4); (5,5); (5,6)

Therefore, P(B|A) is 1/6.

The second question has the same first half.
But this time we work out that there are 3 ways of rolling a 10 with both:
(4,6); (5,5); (6,4)

Therefore, P(A|B) is 1/3.

The other four are answered in much the same way.

Much as I hate to say it, I think the American spellings are the more commonly used ones.
So it makes sense to have that as the default.