Consider all possible 1000 digit positive base 10 integers all of whose digits are odd. For how many of these integers, do each pair of adjacent digits differ precisely by 2 ?
Note: Try to solve this problem analytically, although computer program/ spreadsheet solutions are welcome.
According to given condition,
1) If a number is 3 or 7, then its alternate number is
also 3 or 7.
No. of 3 digit numbers formed with starting digit
either 3 or 7 = 3 ( {353,313,357} or {753,757,797}
Let 1st 3 or 7 can occur in 1st place or 2nd place,
so next 2 digits can be selected in 3 ways, from there
using the 2nd appended digit (which is 3 or 7 again)
next 2 digits can be selected in 3 ways
So, 4 ways of choosing either 3 or 7 and 1st place or 2nd
place.
if its the second place 1st digit can be selected in 2 ways
if its the 1st place, last digit can be selected in 2 ways
So, total 4*2=8 ways here.
from there every 2 digits can be selected in 3 ways using
last digit again.
So, there are 3^(10002)/2 ways of choosing the numbers
Finally 8*3^499 numbers satisfy the given criteria.

Posted by Praneeth
on 20081007 07:17:48 