Cheenta
How 9 Cheenta students ranked in top 100 in ISI and CMI Entrances?
Learn More

Test of Mathematics Solution Subjective 36 - Invariance Principle

Test of Mathematics at the 10+2 Level

Test of Mathematics Solution Subjective 36 (from ISI Entrance). The book, Test of Mathematics at 10+2 Level is Published by East West Press. This problem book is indispensable for the preparation of I.S.I. B.Stat and B.Math Entrance.

Also see: Cheenta I.S.I. & C.M.I. Entrance Course


Problem

Let $ a_1 , a_2 , ... , a_n $ be n numbers such that each $ a_i $ is either 1 or -1. If $ a_1 a_2 a_3 a_4 + a_2 a_3 a_4 a_5 + ... + a_n a_1 a_2 a_3 = 0 $ then prove that 4 divides n.

Solution

Let us denote each product of four numbers as $ b_i $ . For example $ b_1 = a_1 a_2 a_3 a_4 $. Note that the last one begins with $ a_n $ indicating there are n $ b_i $'s.

We check the equation modulo 4 (that is in each step we change 'something' in the equation and check what happens to the remainder of the sum when divided by 4).In the first step we note that equation is 0 mod 4 (since 0 when divided by 4 gives 0 as the remainder).

Next we convert one of the a's which is -1 into +1. Note that each $ a_i $ appears in exactly 4 $ b_j $. Hence converting the one $ a_i $ from -1 to +1 will alter the values of 4 $ b_j $ Thus we may have five cases:

  • All the four b's were -1. Hence after conversion all of their values will change into +1. Therefore the value of the total sum will increase by +8 (as previously the four b's added up to -4 and now they add up to +4). Thus no change of the sum modulo 4.
  • Exactly three b's were -1 and the remaining was +1. Hence after conversion three of their values will change into +1 and the remaining one changes from +1 to -1. Therefore the value of the total sum will increase by +4 (as previously the four b's added up to -2 ((-1) + (-1) + (-1) + (+1)) and now they add up to +2). Thus no change of the whole sum modulo four.
  • Exactly two b's were -1 and the remaining two were +1. Hence after conversion two of their values will change into +1 and the remaining two will change from +1 to -1. Therefore the value of the total sum will increase by 0 (as previously the four b's added up to 0 ((-1) + (-1) + (+1) + (+1)) and now they add up to 0). Thus no change of the whole sum modulo four.
  • Exactly one b was -1 and the remaining were +1. Hence after conversion three of their values will change into -1 and the remaining one changes from -1 to +1. Therefore the value of the total sum will decrease by 4 (as previously the four b's added up to 2 ((+1) + (+1) + (+1) + (-1)) and now they add up to -2). Thus no change of the whole sum modulo four.
  • All the four b's were +1. Hence after conversion all of their values will change into -1. Therefore the value of the total sum will decrease by 8 (as previously the four b's added up to +4 and now they add up to -4). Thus no change of the sum modulo 4.

Thus we see that changing one $ a_i $ -1 to +1 does not change the value of the total sum modulo 4. Similarly we change all negative one's into positive one's (and in each step the sum remains invariant in modulo 4) to get n. Thus $ n \equiv 0 \mod 4 $ . This implies 4 divides n.

Key Idea

Modular arithmetic, invariance principle.

Knowledge Partner

Cheenta is a knowledge partner of Aditya Birla Education Academy
Cheenta

Cheenta Academy

Aditya Birla Education Academy

Aditya Birla Education Academy

Cheenta. Passion for Mathematics

Advanced Mathematical Science. Taught by olympians, researchers and true masters of the subject.
JOIN TRIAL
support@cheenta.com