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^(1000-2)/2 ways of choosing the numbers

Finally 8*3^499 numbers satisfy the given criteria.

Posted by Praneeth on 2008-10-07 07:17:48