wu :: forums
« wu :: forums - Take 1000 Odd Digits, Get Number »
Welcome, Guest. Please Login or Register.
Nov 25th, 2024, 10:44am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   medium (Moderators: Eigenray, Icarus, ThudnBlunder, Grimbal, william wu, SMQ, towr)
   Take 1000 Odd Digits, Get Number		 « Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Take 1000 Odd Digits, Get Number  (Read 466 times)
K Sengupta
Senior Riddler
****





   


Gender: male
 Posts: 371
Take 1000 Odd Digits, Get Number  
« on: Jul 24th, 2007, 7:24am »		 Quote Quote Modify Modify
Analytically determine the total number of 1000 digit positive decimal integers constituted entirely by odd digits with the proviso that any two adjacent digits must differ by 2.
IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
 Posts: 2276
Re: Take 1000 Odd Digits, Get Number  
« Reply #1 on: Jul 24th, 2007, 11:50pm »		 Quote Quote Modify Modify
3501 - 3499?
 
Analysis:
 
hidden:
Let Tn be the number of n-digit numbers having the required property, and let Tn(d) be the number of such numbers starting with digit d. Then we have the following relations:
 
1) Tn = 2Tn(1) + 2Tn(3) + Tn(5)
2) Tn(1) = Tn-1(3)
3) Tn(3) = Tn-1(1) + Tn-1(5)
4) Tn(5) = 2Tn-1(3)
5) T1(1) = T1(3) = T1(5) = 1
 
By induction, it can be shown that
 
T2n(1) = 3n-1, T2n(3) = T2n(5) = 2T2n(1).
« Last Edit: Jul 24th, 2007, 11:51pm by Barukh » IP Logged
jollytall
Senior Riddler
****





   


Gender: male
 Posts: 585
Re: Take 1000 Odd Digits, Get Number  
« Reply #2 on: Jul 24th, 2007, 11:55pm »		 Quote Quote Modify Modify
Two different odd numbers always differ by 2 at least. So probably you wanted to say something else. This way it is really easy (doesn't worth even hiding).
The last digit can be anything (i.e. 5 choices). The next can be 4 different numbers, and so on. So I would go for 5*4^999.
 
What do I miss? Did you want to say "differ by 4"?
IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
 Posts: 2276
Re: Take 1000 Odd Digits, Get Number  
« Reply #3 on: Jul 25th, 2007, 12:35am »		 Quote Quote Modify Modify
on Jul 24th, 2007, 11:55pm, jollytall wrote:
Two different odd numbers always differ by 2 at least.

I think it says that the adjacent digits differ by exactly 2.
 
So, for instance, if the first digit of the number is 1, you've got just one choice for the second (3), while if it starts from 3, you have two choices (1, 5).
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
 Posts: 13730
Re: Take 1000 Odd Digits, Get Number  
« Reply #4 on: Jul 25th, 2007, 12:36am »		 Quote Quote Modify Modify
on Jul 24th, 2007, 11:55pm, jollytall wrote:
Two different odd numbers always differ by 2 at least. So probably you wanted to say something else. This way it is really easy (doesn't worth even hiding).
The last digit can be anything (i.e. 5 choices). The next can be 4 different numbers, and so on. So I would go for 5*4^999.
 
What do I miss? Did you want to say "differ by 4"?
He might mean differ by 2 exactly, rather than at least 2.
in which case for 1 or 9, the next digit can be only 3 or 7 respectively, while in other cases you have two choices.
IP Logged
Wikipedia, Google, Mathworld, Integer sequence DB
K Sengupta
Senior Riddler
****





   


Gender: male
 Posts: 371
Re: Take 1000 Odd Digits, Get Number  
« Reply #5 on: Jul 25th, 2007, 2:06am »		 Quote Quote Modify Modify
on Jul 24th, 2007, 11:55pm, jollytall wrote:
Two different odd numbers always differ by 2 at least. ...........  Did you want to say "differ by 4"?

 
I would like to clarify that any two adjacent digits of  each of the numbers  must have  a difference of precisely 2.  
« Last Edit: Jul 25th, 2007, 2:08am by K Sengupta » IP Logged
K Sengupta
Senior Riddler
****





   


Gender: male
 Posts: 371
Re: Take 1000 Odd Digits, Get Number  
« Reply #6 on: Jul 25th, 2007, 2:30am »		 Quote Quote Modify Modify
on Jul 24th, 2007, 11:50pm, Barukh wrote:
3501 - 3499?
 
Analysis:
 
hidden:
Let Tn be the number of n-digit numbers having the required property, and let Tn(d) be the number of such numbers starting with digit d. Then we have the following relations:
 
1) Tn = 2Tn(1) + 2Tn(3) + Tn(5)
2) Tn(1) = Tn-1(3)
3) Tn(3) = Tn-1(1) + Tn-1(5)
4) Tn(5) = 2Tn-1(3)
5) T1(1) = T1(3) = T1(5) = 1
 
By induction, it can be shown that
 
T2n(1) = 3n-1, T2n(3) = T2n(5) = 2T2n(1).

 
True.
 
My independent computations also show that 8*3499 indeed  is the required answer.
 
 
« Last Edit: Jul 25th, 2007, 2:33am by K Sengupta » IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
 Posts: 1948
Re: Take 1000 Odd Digits, Get Number  
« Reply #7 on: Jul 25th, 2007, 4:34am »		 Quote Quote Modify Modify
And for an odd number n of digits, 14*3(n-3)/2.
IP Logged
K Sengupta
Senior Riddler
****





   


Gender: male
 Posts: 371
Re: Take 1000 Odd Digits, Get Number  
« Reply #8 on: Jul 26th, 2007, 7:46am »		 Quote Quote Modify Modify
I furnish my methodology leading to the end result of 8*3^499, which is fundamentally similar to the solution posted by Barukh.
 
Solution:
 
Let us denote:
 
 E_n = the number of such n-digit numbers with last digit 1 or 9, and:
 
F_n =  the number of such n- digit numbers with last digit 3 or 7
 
G_n = the number of such n-digit numbers with last digit 5
 
Then, we must have:
 
E_(n+1) = F_n;  
F_(n+1) =  2* G_n + E_n, and:
G_(n+1) = F_n
 
Accordingly F_(n+2) = 2*G_(n+1) + E_(n+1) = 2*F_n + F_n = 3*F_n
 
Evidently, F_1 = 2(3, 7), and F_2 = 4(13, 53, 57, 97)
 
Accordingly, we must have:
F_(2n) = 4*3^(n-1); F_(2n-1) = 2*3^(n-1).
 
Therefore, E_(2n) = G_(2n) = 2*3^(n-1), and consequently:
 
E_(2n) + F_(2n) + G_(2n) = 8*3^(n-1)
 
Substituting n= 500, we obtain 8*3^499 as the desired  result.
 
IP Logged
K Sengupta
Senior Riddler
****





   


Gender: male
 Posts: 371
Re: Take 1000 Odd Digits, Get Number  
« Reply #9 on: Jul 26th, 2007, 7:48am »		 Quote Quote Modify Modify
on Jul 25th, 2007, 4:34am, Eigenray wrote:
And for an odd number n of digits, 14*3(n-3)/2.

 
I have been unable to work out a satisfactory methodology for the general case corresponding to an odd number n of digits, and consequently I am still looking for the foregoing procedure leading to the final solution.
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
 Posts: 13730
Re: Take 1000 Odd Digits, Get Number  
« Reply #10 on: Jul 26th, 2007, 8:22am »		 Quote Quote Modify Modify
on Jul 26th, 2007, 7:48am, K Sengupta wrote:
I have been unable to work out a satisfactory methodology for the general case corresponding to an odd number n of digits, and consequently I am still looking for the foregoing procedure leading to the final solution.
You can easily derive it from Barukh's solution.
 
T2n+1(1) = T2n(3) =   2 T2n(1)
T2n+1(3) = T2n(1) + T2n(5) = 3 T2n(1)  
T2n+1(5) = 2Tn-1(3) = 4 T2n(1)
 
2*2T2n(1)+2*3T2n(1)+4T2n(1)  = 14*3n-1, or substituting in k=2n+1,  14*3(k-3)/2
« Last Edit: Jul 26th, 2007, 8:24am by towr » IP Logged
Wikipedia, Google, Mathworld, Integer sequence DB
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board