 Jan 9th, 2013
620
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. >>>> Proof by Mathematical induction <<<<<
2.
4. According the standard convention for reading
5. numbers in every positional number system: Decomposing
6. the numbers as linear combinations of powers for a given
7. radix, the concatenation in ascending order for the first
8. digits in the given radix always assigns the smallest
9. possible value.
10.
11. Convention: When reading numbers from left to right,
12. each digit have associated a power of a given radix.
13. The exponents for those powers are distributed in
14. descending order from left to right. So a number
15. written in base r whose representation is written
16. for example as "123bca" in the base r=16 (hexadecimal)
17. will have assigned the following value in decimal (base-10):
18.
19. "23bca"
20. ---> ( 2 )*r^4 + ( 3 )*r^3 + ( b )*r^2 + ( c )*r^1 + ( a )*r^0
21. ---> 146378 (decimal)
22.
23. Now it will be observed in the further that for each
24. case that the smallest possible k-digits permutation
25. ( k < r ) for the first k digits in base r is the
26. concatenation in ascending order of those digits.
27.
28. k=1.
29. Trivial since there is 1 and only 1 one-digit permutation: {"1"}
30.
31. k=2.
32. The two permutations are: {"12","21"}
33.
34. The possible assignations are also two:
35.
36. "12" <---> ( 1 )*r^1 + ( 2 )*r^0
37.
38. "21" <---> ( 2 )*r^1 + ( 1 )*r^0
39.
40. Subtracting these assignations:
41.
42. "21 -12"  <--> (2-1)*r^1 + (1-2)*r^0 = 1*r^1 - 1*r^0 = (r-1)
43.
44. "21" is greater than "12" by a difference of (r-1),
45. then for two-digits permutations, "12" or the concatenation
46. of the first two digits have assigned always the smallest
47. possible value regardless the radix.
48.
49. k=3. There are six (3!) possible assignations, but we only
50. are interested in compare the concatenation of the first 3
51. digits with the other five remaining permutations so there
52. will be 5 differences to be checked:
53.
54. Assignations:
55.
56. "123" <---> ( 1 )*r^2 + ( 2 )*r^1 + ( 3 )*r^0
57. "132" <---> ( 1 )*r^2 + ( 3 )*r^1 + ( 2 )*r^0
58. "213" <---> ( 2 )*r^2 + ( 1 )*r^1 + ( 3 )*r^0
59. "231" <---> ( 2 )*r^2 + ( 3 )*r^1 + ( 1 )*r^0
60. "312" <---> ( 3 )*r^2 + ( 1 )*r^1 + ( 2 )*r^0
61. "321" <---> ( 3 )*r^2 + ( 2 )*r^1 + ( 1 )*r^0
62.
63. Differences:
64.
65. "132" <---> ( 1 )*r^2 + ( 3 )*r^1 + ( 2 )*r^0
66. "123" <---> ( 1 )*r^2 + ( 2 )*r^1 + ( 3 )*r^0
67. ----------------------------------------------
68. ( 0 )*r^2 + ( 1 )*r^1 + ( -1 )*r^0
69.
70. Or: (r-1)
71.
72. "213" <---> ( 2 )*r^2 + ( 1 )*r^1 + ( 3 )*r^0
73. "123" <---> ( 1 )*r^2 + ( 2 )*r^1 + ( 3 )*r^0
74. ----------------------------------------------
75. ( 1 )*r^2 + ( -1 )*r^1 + ( 0 )*r^0
76.
77. Or: r^2-r = r*(r-1)
78.
79. Also: 10*(r-1) if we remember that 10 represents
80. the base.
81.
82. "231" <---> ( 2 )*r^2 + ( 3 )*r^1 + ( 1 )*r^0
83. "123" <---> ( 1 )*r^2 + ( 2 )*r^1 + ( 3 )*r^0
84. ----------------------------------------------
85. ( 1 )*r^2 + ( 1 )*r^1 + ( -2 )*r^0
86.
87. Or: (r+1)*(r-1)+(r-1) = (r+2)*(r-1)
88.
89. "312" <---> ( 3 )*r^2 + ( 1 )*r^1 + ( 2 )*r^0
90. "123" <---> ( 1 )*r^2 + ( 2 )*r^1 + ( 3 )*r^0
91. ----------------------------------------------
92. ( 2 )*r^2 + ( -1 )*r^1 + ( -1 )*r^0
93.
94. Or: (2*r+1)*(r-1)
95.
96. "321" <---> ( 3 )*r^2 + ( 2 )*r^1 + ( 1 )*r^0
97. "123" <---> ( 1 )*r^2 + ( 2 )*r^1 + ( 3 )*r^0
98. ----------------------------------------------
99. ( 2 )*r^2 + ( 0 )*r^1 + ( -2 )*r^0
100.
101. Or: 2*(r+1)*(r-1)
102.
103. In general for k>3:
104.
105. Let be c_i and c_(i+1) two digits inside the
106. concatenation in ascending order for the first N
107. digits of base-r (N <= r, 0<=i<=(N-1) ),
108. then both c_i and c_(i+1) ranges in 0..(N-1),
109. and if "i" is the corresponding count index
110. from left to right, then clearly: c_i < c_(i+1).
111.
112. According to the previous description the
113. first digit at the left c_0 have associated
114. the power r^(N-1) and the last digit most at
115. right c_(N-1) have associated the power r^0.
116. This additional comment is unnecessary in the
117. present proof but it illustrates that while
118. the coefficients increases by 1 from left to
119. right, the exponents does exactly the opposite,
120. decreases by 1 from left to right. So in the
121. ascending order concatenation, two adjacent
122. digits are represented in general by:
123.
124. s0= c_i*r^j + c_(i+1)*r^(j-1)
125.
126. Relative to the (base-10) value assigned to a permutation.
127.
128. Now if the coefficients are commuted, we will have:
129.
130. s1= c_(i+1)*r^j + c_i*r^(j-1)
131.
132. And subtracting (s1-s0):
133.
134. (s1-s0)= c_(i+1)*r^j + c_i*r^(j-1) +(-1)*( c_i*r^j + c_(i+1)*r^(j-1) )
135.    = ( c_(i+1) - c_i )*r^j + ( c_i - c_(i+1) )*r^(j-1)
136.    = ( c_(i+1) - c_i )*r^j -- ( c_(i+1) - c_i )*r^(j-1)
137.    = ( c_(i+1) - c_i )*r^(j-1+1) -- ( c_(i+1) - c_i )*r^(j-1)
138.    = ( c_(i+1) - c_i )*r^(j-1)*r -- ( c_(i+1) - c_i )*r^(j-1)
139.    = ( ( c_(i+1) - c_i )*r^(j-1) )*(r-1)
140.
141. (**Note: Some minus signs were duplicated for readability)
142.
143. There is obtained a positive multiple of (r-1)
144. like in the particular cases studied before.
145.
146. So, continuing this process for k=4, k=5, ...
147. and so on "ad infinitum", if it were provided
148. that (k<r), then the mentioned concatenation
149. in ascending order for the first digits in
150. base-r will be found to be always the smallest
151. possible permutation without repetition built
152. using k digits.
153.
154. Also notice the following interesting property
155. about each one of the studied differences:
156. All of them are multiples of (r-1).
157.
158. (END)
RAW Paste Data