Problem Solving - an Illustration

 Problem Solving - an Illustration

M. Velrajan

How to solve problems is illustrated with a simple, fascinating number game.

Let S be a string of digits 0, 1, 2, . . . , 9 of length n and 1 ≤ m < n. 

Replace the mth and nth digits of S by mth digit + 1 and nth digit + 1, 

respectively, subject to 9 + 1 = 0  i.e. the addition is addition modulo 10 and interchange the first m and the remaining n - m digits to get the new string of length n.

For example, suppose S = 03421678 and m = 6.

Then 

S      034216 78

S1    790342 17

Repeat the above for the new string of digits.

The problem is whether we get the same string S after a finite stage and if so, after which stage.

Think how to solve this problem.

. . . . . . . .

Understand

. . . . . . . .

Yes, the operation given first increases only the mth and nth place digits of S by 1, of course 9 + 1 = 0 then interchanges the first m and the remaining n - m digits. 

Analyse

This interchange shifts the digits places in S.

The 1st digit in S becomes (n - m + 1)th digit in S1.

The 2nd digit in S becomes (n - m + 2)th digit in S1.

. . . . . . .

The mth digit in S becomes (n - m + m)th = nth digit in S1.

And the (m + 1)th digit in S becomes 1st digit in S1, 

the (m + 2)th digit in S becomes 2nd digit in S1, 

. . . . .

the nth = (m + n - m)th digit in S becomes (n - m)th digit in S1.

Think and Apply Knowledge

Is there a way to express all these shifts by a single mathematical expression ?

Yes, the operation shifts all the digits by n - m places in a cyclic manner (after 

nth place 1st place) after incrementing the mth and nth digits of S by 1.

Digit in 1 ≤ i ≤ m  place in S takes the n - m + i place in the new string S1.

Following the same

Digit in m + 1 ≤ j ≤ n  place in S takes the n - m + j =  n - m + m + k = n + k place in S1, where j = m + k, 1 ≤ k ≤ n - m.

But the digit in (m + k)th place in S  takes the kth  place in S1, 1 ≤ k ≤ n - m.

So, n + k has to become k i.e.  + should be the addition modulo n.

But if + is addition modulo n, the mth place in S  takes the (n - m + m)th = nth = 0th place in S1 and there is no 0th place in S1, 0th place has to be the nth place.

If ⨁ is a special addition modulo n, with 

i ⨁ j = i + j, if  i + j ≤ n and i ⨁ j =  k, if  i + j = n + k , 1 ≤ k < n then 

digit in 1 ≤ i ≤ n place in S takes the (n - m) ⨁ i place in S1.

i.e. the shift of digits by the given operation is given by the function 

σ(i) = (n-m) ⨁ i,  1 ≤ i ≤ n.

i.e. σ is the permutation

σ =       1            2           3        .  .  .  m   m+1  m+2  .  .  .   n     

         n-m+1  n-m+2  n-m+3  .   .  .  n      1       2     .  .  .  n-m  

So, the operation given first increases only the mth and nth digits of S by 1, of course 9 + 1 = 0 then shifts digits places by the permutation σ.   

Our aim is to find whether we get the same string S after a finite stage and if so, after which stage.  

we get the same string S after a finite stage, if there is no change in digits places and values.

First we find after which stage there is no change in digits places.

We observe that at the kth stage the digits shift are given by the permutation σk. So, there is no change in digits places after the kth stage if σk is the identity permutation. 

The least value of k so that σk is the identity permutation is the order of the permutation σ.

For k ≥ 1, σk(i) = (n-m) ⨁  (n-m)  ⨁. . . ⨁  (n-m)(k times) ⨁ i,  1 ≤ i ≤ n.  

σk is the identity permutation iff  σk(i) = i,  1 ≤ i ≤ n 

                                                   iff  kn - km is a multiple of n

                                                   iff km is a multiple of n.

The order of σ is the least value of k so that  km is a multiple of n.

If k = n then km is a multiple of n. If k = n/d, d is a divisor of both n and m then km = (n/d)m = n(m/d) is a multiple of n.

But we want the least value of k so that  km is a multiple of n. So d to be the greatest common divisor of m and n.

The least value of k so that km is a multiple of n is k = n/d, where d = (n, m).

The order of σ = n/d, where d = (n, m).

Note that k = n/d is the least value of k so that km is a multiple of n, 

hence for any 1 ≤ i ≤ n, σ(n/d)(i) = i and σl(i) ≠ i, for all l < n/d.

And in σ the cycle containing i is (i σ(i) σ2(i)  σ3(i)  .  .  .  σ(n/d)-1(i)), a cycle of length n/d, for all 1 ≤ i ≤ n.

Hence σ is a product of disjoint cycles each of length n/d.

Since the operation given increases only the mth and nth place digits of S by 1, we have to find digits at which places take the mth and nth place in the successive application of the operation. In σ as the product of disjoint cycles only the 1 ≤ i ≤ n which are in the cycles containing m and n - m occupies the mth and nth places in the successive application of the operation.

The cycle containing m is 

(m σ(m) σ2(m)  σ3(m)  .  .  .  σ(n/d)-1(m)) 

         = (m   n  n-m  2(n-m) 3(n-m) .  .  .  [(n/d)-1](n-m))

Since (m   n  n-m  2(n-m) 3(n-m) .  .  .  [(n/d)-1](n-m))

                = (n  n-m  2(n-m) 3(n-m) .  .  .  [(n/d)-1](n-m)  m)

                = (n-m  2(n-m) 3(n-m) .  .  .  [(n/d)-1](n-m)  m  n)

                =  .  .  .  .  .

                = ([(n/d)-1](n-m)  m  n n-m  2(n-m) 3(n-m) .  .  .  [(n/d)-2](n-m))

only the numbers m,  n,  n-m,  2(n-m), 3(n-m),  .  .  . , [(n/d)-1](n-m) occupies the mth and nth places exactly one times from σ0, σ, σ2, σ3,  .  .  .  , σ(n/d)-1.

Hence the digits that are only in the mth, nth, (n-m)th,  2(n-m)th, 3(n-m)th, .  .  .  [(n/d)-1](n-m)th places of the string S occupies the mth and nth places exactly one times from S, σ(S), σ2(S), σ3(S),  .  .  . , σ(n/d)-1(S).

Since the digits that are only in the mth and nth places are incremented by 1,

the digits that are only in the mth, nth, (n-m)th,  2(n-m)th, 3(n-m)th, .  .  .  [(n/d)-1](n-m)th places of the string S are incremented by 2 modulo 10 after the (n/d)th stage, all the digits in the other places of the string S are not changed   and all the digits occupy the places they occupied in S.

Hence after the 5(n/d)th stage we get the same string S.

Illustration : 

Suppose S = 031678 and m = 4.

Then n = 6, d = (6, 4) = 2, 5(n/d) = 15.

S      0316 78

S1    7903 17

S2    1879 04

S3    0518 70

S4    7105 19

S5    1071 06

S6    0710 72

S7    7307 11

S8    1273 08

S9    0912 74

S10  7509 13

S11  1475 00

S12  0114 76

S13  7701 15

S14  1677 02

S15  0316 78

Oh at 15th stage we get the original string.

Of course the given problem involves permuting the digits in the string; there is no surprise in the emergence of σ in the solution. But See the Role of properties of permutations in solving the problem and Enjoy the Beauties.

We note that this problem may be useful in coding - decoding and Graph Labelling.

Develop Mathematical Thinking in such a manner to understand, analyse, apply the knowledge for solving not only mathematical problems but also any life, live problems. 

Empower yourself.  

To Download PDF

Click Here