Advertisement

**Not a member of Pastebin yet?**

**, it unlocks many cool features!**

__Sign Up__- >>>> Proof by Mathematical induction <<<<<
- About this evident fact:
- According the standard convention for reading
- numbers in every positional number system: Decomposing
- the numbers as linear combinations of powers for a given
- radix, the concatenation in ascending order for the first
- digits in the given radix always assigns the smallest
- possible value.
- Convention: When reading numbers from left to right,
- each digit have associated a power of a given radix.
- The exponents for those powers are distributed in
- descending order from left to right. So a number
- written in base r whose representation is written
- for example as "123bca" in the base r=16 (hexadecimal)
- will have assigned the following value in decimal (base-10):
- "23bca"
- ---> ( 2 )*r^4 + ( 3 )*r^3 + ( b )*r^2 + ( c )*r^1 + ( a )*r^0
- ---> 146378 (decimal)
- Now it will be observed in the further that for each
- case that the smallest possible k-digits permutation
- ( k < r ) for the first k digits in base r is the
- concatenation in ascending order of those digits.
- k=1.
- Trivial since there is 1 and only 1 one-digit permutation: {"1"}
- k=2.
- The two permutations are: {"12","21"}
- The possible assignations are also two:
- "12" <---> ( 1 )*r^1 + ( 2 )*r^0
- "21" <---> ( 2 )*r^1 + ( 1 )*r^0
- Subtracting these assignations:
- "21 -12" <--> (2-1)*r^1 + (1-2)*r^0 = 1*r^1 - 1*r^0 = (r-1)
- "21" is greater than "12" by a difference of (r-1),
- then for two-digits permutations, "12" or the concatenation
- of the first two digits have assigned always the smallest
- possible value regardless the radix.
- k=3. There are six (3!) possible assignations, but we only
- are interested in compare the concatenation of the first 3
- digits with the other five remaining permutations so there
- will be 5 differences to be checked:
- Assignations:
- "123" <---> ( 1 )*r^2 + ( 2 )*r^1 + ( 3 )*r^0
- "132" <---> ( 1 )*r^2 + ( 3 )*r^1 + ( 2 )*r^0
- "213" <---> ( 2 )*r^2 + ( 1 )*r^1 + ( 3 )*r^0
- "231" <---> ( 2 )*r^2 + ( 3 )*r^1 + ( 1 )*r^0
- "312" <---> ( 3 )*r^2 + ( 1 )*r^1 + ( 2 )*r^0
- "321" <---> ( 3 )*r^2 + ( 2 )*r^1 + ( 1 )*r^0
- Differences:
- "132" <---> ( 1 )*r^2 + ( 3 )*r^1 + ( 2 )*r^0
- "123" <---> ( 1 )*r^2 + ( 2 )*r^1 + ( 3 )*r^0
- ----------------------------------------------
- ( 0 )*r^2 + ( 1 )*r^1 + ( -1 )*r^0
- Or: (r-1)
- "213" <---> ( 2 )*r^2 + ( 1 )*r^1 + ( 3 )*r^0
- "123" <---> ( 1 )*r^2 + ( 2 )*r^1 + ( 3 )*r^0
- ----------------------------------------------
- ( 1 )*r^2 + ( -1 )*r^1 + ( 0 )*r^0
- Or: r^2-r = r*(r-1)
- Also: 10*(r-1) if we remember that 10 represents
- the base.
- "231" <---> ( 2 )*r^2 + ( 3 )*r^1 + ( 1 )*r^0
- "123" <---> ( 1 )*r^2 + ( 2 )*r^1 + ( 3 )*r^0
- ----------------------------------------------
- ( 1 )*r^2 + ( 1 )*r^1 + ( -2 )*r^0
- Or: (r+1)*(r-1)+(r-1) = (r+2)*(r-1)
- "312" <---> ( 3 )*r^2 + ( 1 )*r^1 + ( 2 )*r^0
- "123" <---> ( 1 )*r^2 + ( 2 )*r^1 + ( 3 )*r^0
- ----------------------------------------------
- ( 2 )*r^2 + ( -1 )*r^1 + ( -1 )*r^0
- Or: (2*r+1)*(r-1)
- "321" <---> ( 3 )*r^2 + ( 2 )*r^1 + ( 1 )*r^0
- "123" <---> ( 1 )*r^2 + ( 2 )*r^1 + ( 3 )*r^0
- ----------------------------------------------
- ( 2 )*r^2 + ( 0 )*r^1 + ( -2 )*r^0
- Or: 2*(r+1)*(r-1)
- In general for k>3:
- Let be c_i and c_(i+1) two digits inside the
- concatenation in ascending order for the first N
- digits of base-r (N <= r, 0<=i<=(N-1) ),
- then both c_i and c_(i+1) ranges in 0..(N-1),
- and if "i" is the corresponding count index
- from left to right, then clearly: c_i < c_(i+1).
- According to the previous description the
- first digit at the left c_0 have associated
- the power r^(N-1) and the last digit most at
- right c_(N-1) have associated the power r^0.
- This additional comment is unnecessary in the
- present proof but it illustrates that while
- the coefficients increases by 1 from left to
- right, the exponents does exactly the opposite,
- decreases by 1 from left to right. So in the
- ascending order concatenation, two adjacent
- digits are represented in general by:
- s0= c_i*r^j + c_(i+1)*r^(j-1)
- Relative to the (base-10) value assigned to a permutation.
- Now if the coefficients are commuted, we will have:
- s1= c_(i+1)*r^j + c_i*r^(j-1)
- And subtracting (s1-s0):
- (s1-s0)= c_(i+1)*r^j + c_i*r^(j-1) +(-1)*( c_i*r^j + c_(i+1)*r^(j-1) )
- = ( c_(i+1) - c_i )*r^j + ( c_i - c_(i+1) )*r^(j-1)
- = ( c_(i+1) - c_i )*r^j -- ( c_(i+1) - c_i )*r^(j-1)
- = ( c_(i+1) - c_i )*r^(j-1+1) -- ( c_(i+1) - c_i )*r^(j-1)
- = ( c_(i+1) - c_i )*r^(j-1)*r -- ( c_(i+1) - c_i )*r^(j-1)
- = ( ( c_(i+1) - c_i )*r^(j-1) )*(r-1)
- (**Note: Some minus signs were duplicated for readability)
- There is obtained a positive multiple of (r-1)
- like in the particular cases studied before.
- So, continuing this process for k=4, k=5, ...
- and so on "ad infinitum", if it were provided
- that (k<r), then the mentioned concatenation
- in ascending order for the first digits in
- base-r will be found to be always the smallest
- possible permutation without repetition built
- using k digits.
- Also notice the following interesting property
- about each one of the studied differences:
- All of them are multiples of (r-1).
- (END)

Advertisement

Add Comment

Please,

**to add comment**__Sign In__Advertisement