Serving the Quantitative Finance Community

 
User avatar
kr
Posts: 5
Joined: September 27th, 2002, 1:19 pm

Question from a software interview

August 17th, 2004, 3:11 pm

for 6 digits, there is no solution. PutA = 111111B = 011112C = 001122D = 000222E = 001113F = 000123G = 000033H = 000024I = 000015J = 000006K = 000114(maybe this isn't the standard way, I just wrote them down as they came to my head)Then we see that we haveAJIKFEFEFEFEFE.... i.e. ends in a 2-cycleBKFEFEFEFE.... CDGHKFEFEFE....In the 'lifted' space we have 311100 -> 231000 -> 311100 ... and that's as close as one can get
 
User avatar
kr
Posts: 5
Joined: September 27th, 2002, 1:19 pm

Question from a software interview

August 17th, 2004, 3:26 pm

for 7 digits, putA 1111111B 0111112C 0011113D 0011122E 0001114F 0001123G 0001222H 0000115I 0000124J 0000133K 0000223L 0000016M 0000025N 0000034O 0000007Then we have AOLHIEJI... / BH... / CI... / DKI... / FF... / GJ... / MH... / NH...so the only solutions are F (1cycle) and IEJ (3cycle)Upon lifting, F = 0001123 -> 3211000 which is the fixed point I mentioned below - the unique one now provedand the 3cycle is 0000124 -> 4110100 -> 3300100 -> 4102000 -> 4110100 etc.
 
User avatar
kr
Posts: 5
Joined: September 27th, 2002, 1:19 pm

Question from a software interview

August 17th, 2004, 4:06 pm

without listing the partitions for 8, we haveAVRMHOH...BM...CN...DPN...EO...FJP...GQN...II...KI...LUSM...RM...TM...I = 00001124 -> 4210100 as below,2cycle isO = 00000134 -> H = 51011000 -> 43000100 -> 51011000...
 
User avatar
kr
Posts: 5
Joined: September 27th, 2002, 1:19 pm

Question from a software interview

August 17th, 2004, 5:14 pm

notice in the general case that1- there is at least one '0', otherwise a_i >= 1 for all i, sum_i a_i =n => a_i = 1 for all i, but 1....1 is not a fixed point of the transformation2- As before, let R = # of nonzero digits represented; then R = (n-1) - a_0, where a_0 = # of zeroes3- Then sum_i a_i >= 1 + 2 + ... + R = R(R+1) / 2 = n when R = (sqrt(1 + 8.n) - 1) / 2. Corollary: Let n>8. Then the number of zeroes > n/2.Corollary: Let n>8. There are more zeroes than any other digit represented.Corollary: Let n>8. There is at least one '1' in the representation. Corollary: Let n>8. Put z = # of zeroes. Then we have 000.....000 & (n-z-1) digits & z. The digits sum to n, thus the "middle" digits sum to n-z. Thus they must be all '1's and one '2'. Corollary: Let n>8. The digits represented are 0,1,2 and z. Thus R = 3 = (n-1) - a_0, so a_0 = n-4 and the number must be of the form00000...000112(n-4).So my sequence represents the only possible solution for n>8. QED
Last edited by kr on August 16th, 2004, 10:00 pm, edited 1 time in total.
 
User avatar
alexandreC
Posts: 0
Joined: June 9th, 2004, 11:35 pm

Question from a software interview

August 24th, 2004, 9:19 pm

Last edited by alexandreC on August 23rd, 2004, 10:00 pm, edited 1 time in total.
 
User avatar
alexandreC
Posts: 0
Joined: June 9th, 2004, 11:35 pm

Question from a software interview

August 24th, 2004, 9:30 pm

very nice work.your scheme can converge for the fixed point,but can also converge for something that is not a solution, as you've mentioned.I was wondering if there is any initial condition that induce your scheme not to converge at all - and we would end up with an oscilating pattern for example.Alex
Last edited by alexandreC on August 23rd, 2004, 10:00 pm, edited 1 time in total.