Peculiar Order Relation on a Finite Set in the Year 2021
Let us introduce the set M = { 1 , − 1 } , and for any positive integer number n , we can define the Cartesian Product M n = M × M × . . . × M , where M is repeated n times, and, of course, M 1 = M . Assume that M is provided with the regular order, and we can now define an order denoted by " < " on the set M n where n ≥ 2 using a recursive definition. Let us assume that the order is already defined on M k , where k ≥ 1 , and then given two elements of M k + 1 represented by l = ( a 1 , a 2 , a 3 , . . . , a k + 1 ) and m = ( b 1 , b 2 , b 3 , . . . , b k + 1 ) , we say that l < m when one of the following three conditions is true:
1) a 1 = − 1 and b 1 = 1 .
2) a 1 = b 1 = 1 and ( a 2 , a 3 , . . . , a k + 1 ) < ( b 2 , b 3 , . . . , b k + 1 ) in M k .
3) a 1 = b 1 = − 1 and ( b 2 , b 3 , . . . , b k + 1 ) < ( a 2 , a 3 , . . . , a k + 1 ) in M k .
If you can express the elements of M 1 1 in an increasing order l 0 < l 1 < l 2 < . . . < l 2 1 1 − 1 , then enter the number of 1's in l 2 0 2 1 , as your answer. Otherwise, enter 555.
The answer is 7.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
The list in the problem is l 0 < l 1 < l 3 < ⋯ < l 2 1 1 . Did you mean to skip l 2 ?
Log in to reply
No, Mr. Haussman. It was a mistake. I corrected it. Sorry about that and thank you for letting me know.
Log in to reply
There is still a problem. The set M 1 1 contains 2 1 1 elements, but the list l 0 < l 1 < l 2 < ⋯ < l 2 1 1 contains 2 1 1 + 1 elements.
Log in to reply
@Jon Haussmann – Yes, you are right. I corrected that also.
Given an arbitrary positive integer number n , we can define the following function f n : M n → { 0 , 1 , 2 , . . . , 2 n − 1 } by the following rule f n ( a 1 , a 2 , . . . , a n ) = ( α 1 α 2 . . . α n ) 2 , where the expression in the right side of the following equation is a binary number defined on the following way α 1 = { 1 , 0 , if a 1 = 1 if a 1 = − 1 . For any integer k greater than 1, α k = { 1 , 0 , if a 1 a 2 . . . a k = 1 if a 1 a 2 . . . a k = − 1 . We can see that f n has an inverse function that can be defined in the following way f n − 1 ( α 1 α 2 . . . α n ) 2 = ( a 1 , a 1 a 2 , a 2 a 3 , . . . , a n − 1 a n ) , where
a k = { 1 , − 1 , if α k = 1 if α k = 0 . Now, we are going to use Mathematical Induction to prove the following equivalence.
( a 1 , a 2 , . . . , a n ) < ( b 1 , b 2 , . . . , b n ) ⟺ f n ( a 1 , a 2 , . . . , a n ) < f n ( b 1 , b 2 , . . . , b n ) ( ∗ ) Notice that the two symbols "<" represent different orders. The first represents the order on M n and the second represents the regular order on the integers. Of course, this property is obviously true when n = 1 .
Assume that the equivalence is true if n = k , and we must prove that it is true when n = k + 1 . To prove (*) for n = k + 1 let us consider two ( k + 1 ) t h -tuples ( a 1 , a 2 , . . . , a k + 1 ) and ( b 1 , b 2 , . . . , b k + 1 ) in M k + 1 . Let us consider also that f k + 1 ( a 1 , a 2 , . . . , a k + 1 ) = ( α 1 α 2 . . . α n ) 2 and f k + 1 ( b 1 , b 2 , . . . , b k + 1 ) = ( β 1 β 2 . . . β n ) 2 , where the α k ′ s and the β k ′ s are defined as we did it above. We are going to divide the proof in the following cases.
Case 1. a 1 = − 1 and b 1 = 1 .
The equivalence (*) is true due to the fact that ( a 1 = − 1 and b 1 = 1 ) ⟺ ( α 1 = 0 and β 1 = 1 )
Case 2. a 1 = b 1 = 1 . In this case, it is easy to see that if f k + 1 ( 1 , a 2 , . . . , a k + 1 ) = ( 1 α 2 . . . α n ) 2 and f k + 1 ( 1 , b 2 , . . . , b k + 1 ) = ( 1 β 2 . . . β n ) 2 , then f k ( a 2 , . . . , a k ) = ( α 2 . . . α n ) 2 and f k ( b 2 , . . . , b k + 1 ) = ( β 2 . . . β n ) 2 , and vice-versa.
Then we can prove the equivalence (*) for n = k + 1 in the following way. The condition ( 1 , a 2 , . . . , a k + 1 ) < ( 1 , b 2 , . . . , b k + 1 ) is equivalent to ( a 2 , . . . , a k + 1 ) < ( b 2 , . . . , b k + 1 ) by the definition of the order on M k + 1 . Using the hypothesis of induction the last inequality is equivalent to ( α 2 . . . α k + 1 ) 2 < ( β 2 . . . β k + 1 ) 2 , and this one is equivalent to f k + 1 ( 1 , a 2 , . . . , a k + 1 ) < f k + 1 ( 1 , b 2 , . . . , b k + 1 )
Case 3. a 1 = b 1 = − 1 . In this case, it also easy to see that f k + 1 ( − 1 , a 2 , . . . , a k + 1 ) = ( α 2 . . . α k + 1 ) 2 and f k + 1 ( − 1 , b 2 , . . . , b k + 1 ) = ( β 2 . . . β k + 1 ) 2 In turn, these two equations are equivalent to f k ( a 2 , . . . , a k + 1 ) = ( t 2 . . . t k + 1 ) 2 and f k ( b 2 , . . . , b k + 1 ) = ( t 2 . . . t k + 1 ) 2 , where t k = { 0 , 1 , if α k = 1 if α k = 0 . and s k = { 0 , 1 , if β k = 1 if β k = 0 . Now the equivalence (*) can be proved in a simple way for n = k + 1 . The condition ( − 1 , a 2 , . . . , a k + 1 ) < ( − 1 , b 2 , . . . , b k + 1 ) is equivalent to ( b 2 , . . . , b k + 1 ) < ( a 2 , . . . , a k + 1 ) by the definition of the order on M k + 1 . The last inequality is equivalent to f k ( b 2 , . . . , b k + 1 ) < f k ( a 2 , . . . , a k + 1 ) , by the hypothesis of induction, and using our comment at the beginning of this case, this last inequality is equivalent to f k + 1 ( − 1 , a 2 , a 3 , . . . , a k + 1 ) < f k + 1 ( − 1 , b 2 , b 3 , . . . , b k + 1 ) .
Then the proof of (*) is complete.
From the property (*), we can obtain that f n is not only bijective, but it also keeps the order. Therefore, in the case that n = 1 1 we have that l k = g 1 1 − 1 ( k ) , where k is an integer satisfying 0 ≤ k ≤ 2 1 1 − 1 = 2 0 4 7 . Now using that g 1 1 − 1 ( ( α 1 . . . α 1 1 ) 2 ) = ( a 1 , a 1 a 2 , . . . , a 1 0 a 1 1 ) as it was defined above, and that the binary representation of 2021 is ( 1 1 1 1 1 1 0 0 1 0 1 ) 2 , we obtain that g 1 1 − 1 ( 2 0 2 1 ) = ( 1 , 1 , 1 , 1 , 1 , 1 , − 1 , 1 , − 1 , − 1 , − 1 ) . So the answer is 7 .