18
Claim: There may be only one sorted alignment in decreasing/increasing order such as
X1, X2, X3,...... when X1, X2, X3 are distinct numbers
PROOF IS DONE FOR DECREASING ORDER ONLY. SIMILARLY IT MAY BE PROVEN FOR INCREASING ORDER
Proof:
X1, X2, X3,...... is decreasing. We call this as order 1
Say there is any other order as order 2 which is a different permutation than order 1.
Say the difference in order 2 starts only after t-th element of order 1. That means till t-th element both the sequence are same.
let's write the orders again.
X1, X2, X3,......,X(t),X(t+1).... order 1 (decreasing)
X1, X2, X3,.......,X(t),Y(t+1),....,X(t+1).... order 2
Here X(t+1) is not uqual to Y(t+1) as we assumed.
Notice that X(t+1) must be somewhere after Y(t+1) in order 2, because both the orders are chosen from same set of elements.
But Y(t+1) was somewhere after X(t+1) in order 1. So X(t+1)>Y(t+1)
That means oder 2 violates decreasing order. So the proof is complete.
