Monday, April 11, 2011

9 Digit Number Problem Every nth number formed by n digit is Divided By Every nth digit

Arrange the digits 0 to 9 such, that the number formed by the
first digit is divisible by 1, the number formed by the first two
digits is divisible by 2, that formed by the first three digits
divisible by 3, and so forth, thus the number formed by the first
9 digits will be divisible by 9 and that formed by all 10 digits
divisible by 10.

Here is what we would do.

_ _ _ _ _ _ _ _ _ _

those are my ten blanks.

Now let's start asking questions.

Since the whole thing has to be divisible by 10, the last number
must be a zero.

And since the first five digits must be divisible by 5, the fifth
digit must be a 5 or 0, but we have already used 0 so it must be a
five.

One last quickie is that the 2nd, 4th, 6th, and 8th and last
digits must be even, so all the rest are odd

So let's look at we have. I'll write the digits that could go in a
certain place under where they could go:


_ _ _ _ 5 _ _ _ _ 0
1 2 1 2 2 1 2 1
3 4 3 4 4 3 4 3
7 6 7 6 6 7 6 7
9 8 9 8 8 9 8 9

Now things get trickier.

Let's start with the 4th spot.

Any number is divisible by 4 if the last two digits are divisible
by 4

So what are the two-digit numbers divisible by 4 that begin with
an odd number that is not 5?

12 16 32 36 72 76 92 96

Hey, so the 4th digit is either a 2 or a 6.

Now, let's look at the 8th digit. If the first 8 digits are
divisible by 8, then they are divisible by 4 also. So if we apply
the same logic as above, we find that the 8th digit is either a 2 or
a 6.

So spaces 2 and 6 must be 4 or 8.

That narrows it down. So we have this:

_ _ _ _ 5 _ _ _ _ 0
1 4 1 2 4 1 2 1
3 8 3 6 8 3 6 3
7 7 7 7
9 9 9 9



Now for my next trick let's recall that every third space must be
divisible by 3. So every three numbers must sum to be divisible
by 3.

In particular spaces 4, 5, and 6 must sum to 3, and we already
have a five. So either we have

2 5 8 or 6 5 4

in positions 4, 5, and 6.

That is good stuff. That means we have either this:

_ 4 _ 2 5 8 _ 6 _ 0
1 1 1 1
3 3 3 3
7 7 7 7
9 9 9 9

or this:

_ 8 _ 6 5 4 _ 2 _ 0
1 1 1 1
3 3 3 3
7 7 7 7
9 9 9 9

Let's check each of the four digits we could put in the 8th place.
Since a number is divisible by 8 if its last 3 digits are, we need
number in the 6th, 7th, and 8th places to be divisible by 8. We see
that 816 and 896 work in the first case, and 432 and 472 work in the
second case. So we have:

_ 4 _ 2 5 8 _ 6 _ 0
1 1 1 1
3 3 9 3
7 7 7
9 9 9

or this:

_ 8 _ 6 5 4 _ 2 _ 0
1 1 3 1
3 3 7 3
7 7 7
9 9 9


Let's look at the 9th place now. Recall that 1+2+3+4+5+6+7+8+9 = 45,
so we don't need to worry about the 9th place - it will always work
out.

Let's look at the 1st and 3rd places. In case 1, only 147 and 741 are
options. In case 2, we could have 183, 189, 381, 387, 783, 789, 981, or
987. Note that 387 and 783 don't work, because then we don't have any
digits left for the 7th digit.

So our first case becomes:

_ 4 _ 2 5 8 9 6 3 0
1 1
7 7

We can just check the two numbers this can give rise to, namely 1472589630
and 7412589630. Since neither of them are divisible by 7, case one must be
a dead end. So we have to work with case two if we want a solution:

_ 8 _ 6 5 4 _ 2 _ 0
1 1 3 1
3 3 7 3
7 7 7
9 9 9

(and the first 3 digits are 183, 189, 381, 789, 981, or 987)

If we look at the 7th, 8th, and 9th digits to see if we can get them to sum
to three, we see that only 321, 327, 723, and 729 are options.

So which of our options for digits 1,2,3 and 7,8,9 can we use together? In
order to not repeat digits, we could use these:

183 and 729
189 and 327
189 and 723
381 and 729
789 and 321
981 and 327
981 and 723
987 and 321

This means that the only possible solutions to the puzzle are these:

1836547290
1896543270
1896547230
3816547290
7896543210
9816543270
9816547230
9876543210

This is now a small enough number of cases that we can check them by hand.
The first thing we should do is check the first 7 digits for divisibility by
seven. Here are the results:

1836547/7 = 262363.857142857...
1896543/7 = 270934.714285714...
1896547/7 = 270935.285714286...
3816547/7 = 545221
7896543/7 = 1128077.57142857...
9816543/7 = 1402363.28571429...
9816547/7 = 1402363.85714286...
9876543/7 = 1410934.71428571...

Sunday, April 10, 2011

There are n buses in a city. Each of them carries at most m passengers. Find the probability that at least two of them carry the same number of passen

There are n buses in a city. Each of them carries at most m passengers. Find the probability that at least two of them carry the same number of passengers.



This is equal to 1-(probability that they all carry different number of passengers). That probability in paranthesis is equal to (m+1)!/((m+1-n)! * (m+1)^n). This is given that (m+1) >= n. If (m+1) < n, then the probability is 1.

- m+1 because maximum m passengers mean m+1 different possiblities (a bus could carry 0 passengers).
- The first bus has (m+1) possibilities in terms of number of passengers. The second has m+1, the third has m+1 and so on. Total number of orderings possible is (m+1) ^ n.
- For the number of passengers to be different in each bus, first bus has m+1 possibilities, second has m, third has m-1 nd so on. For n buses, this is equal to (m+1)!/(m+1-n)!. Dividing this by (m+1)/n gives the possibility. Subtract this number from one to find at least two buses with the same amount of passengers.


Solved by James