Problem:
Let n be a positive integer. There are 2n(n+1)​ marks, each with a black side and a white side, arranged into an equilateral triangle, with the biggest row containing n marks. Initially, each mark has the black side up. An operation is to choose a line parallel to one of the sides of the triangle, and flipping all the marks on that line. A configuration is called admissible if it can be obtained from the initial configuration by performing a finite number of operations. For each admissible configuration C, let f(C) denote the smallest number of operations required to obtain C from the initial configuration. Find the maximum value of f(C), where C varies over all admissible configurations.
Solution:
For n=1 the answer is clearly 1, since there is only one configuration other than the initial one, and that configuration takes 1 step to get to. From now on we will consider n≥2.
Note that there are 3n possible operations in total, since we can select 3n lines to perform an operation on ( n lines parallel to each side of the triangle.) Performing an operation twice on the same line is equivalent to doing nothing. Hence, we will describe any combination of operations as a triple of n-tuples ((a1​,a2​,…,an​),(b1​,b2​,…,bn​),(c1​,c2​,…,cn​)), where each element ai​,bi​,ci​ is either 0 or 1 ( 0 means no operation, 1 means the opposite), each tuple of the triple denotes operating on a line parallel to one of the sides, and the indices, i.e. 1,2,…,n, denote the number of marks in the row of operation. Let A denote the set of all such 3n-tuples. Hence ∣A∣=23n.
Let B denote the set of all admissible configurations. Let N=2n(n+1)​. We will describe each element of B by an N-tuple (z1​,z2​,…,zN​), where each element is either 0 or 1 ( 0 means black, 1 means white). (Which element refers to which position is not important.)
For each element a∈A, let b=f(a) be the element of B that is the result of applying the operations in a. Then f(a+a′)=f(a)+f(a′) for all a,a′∈A, where addition is considered in modulo 2 . Let K be the set of all a∈A such that f(a) is the all-black configuration. The following eight elements are easily seen to be in K.
- ((0,0, \ldots, 0),(0,0, \ldots, 0),(0,0, \ldots, 0))=\mathrm
- ((0,0,…,0),(1,1,…,1),(1,1,…,1))=x
- ((1,1,…,1),(1,1,…,1),(0,0,…,0))=y
- ((1,1,…,1),(0,0,…,0),(1,1,…,1))=x+y
- ((0,1,0,1,…),(0,1,0,1,…),(0,1,0,1,…))=z
- ((0,1,0,1,…),(1,0,1,0,…),(1,0,1,0,…))=x+z
- ((1,0,1,0,…),(1,0,1,0,…),(0,1,0,1,…))=y+z
- ((1,0,1,0,…),(0,1,0,1,…),(1,0,1,0,…))=x+y+z
We will show that they are the only elements of K.
Suppose L=((a1​,a2​,…,an​),(b1​,b2​,…,bn​),(c1​,c2​,…,cn​)) is in K. Then ai​+bj​+ck​=0 whenever i+j+k=2n+1 (why this is is left as an exercise for the reader.) By adding x and/or y if necessary, we will assume that bn​=cn​=0. Since a2​+bn−1​+cn​= a2​+bn​+cn−1​=0, we have that bn−1​=cn−1​. There are two cases:
-
bn−1​=cn−1​=0. Then from a3​+bn−2​+cn​=a3​+bn−1​+cn−1​=a3​+bn​+cn−2​, we have that bn−2​=cn−2​=0. Continuing in this manner (considering equalities with a4​,a5​,… ), we find that all the bi​ 's and ci​ 's are 0 , from which we deduce that L=id.
-
bn−1​=cn−1​=1. Then from a3​+bn−2​+cn​=a3​+bn−1​+cn−1​=a3​+bn​+cn−2​, we have that bn−2​=cn−2​=0. Continuing in this manner (considering equalities with a4​,a5​,…), we find that (b1​,b2​,…,bn​)=(c1​,c2​,…,cn​)=(…,1,0,1,0), from which we deduce that either L=z or L=x+z.
Hence L is one of the eight elements listed above. It follows that the 23n elements of A form 23n−3 sets, each set corresponding to an element of B. For each element a∈A, let x1​ be the number of a1​,a3​,… that are 1 , and let x2​ be the number of a2​,a4​,… that are 1. Define y1​,y2​,z1​, and z2​ similarly with the bi​ 's and ci​ 's. We want to find the element in the set containing a that has the smallest value of T=x1​+x2​+y1​+y2​+z1​+z2​. The maximum of this value over all the sets is the desired answer.
We observe that an element a∈A has the minimal value of T in its set if and only if it satisfies the following inequalities:
-
x1​+x2​+y1​+y2​≤n
-
x1​+x2​+z1​+z2​≤n
-
y1​+y2​+z1​+z2​≤n
-
x2​+y2​+z2​≤⌊23⌊n/2⌋​⌋=V
-
x1​+y1​+z2​≤⌊22⌈n/2⌉+⌊n/2⌋​⌋=W
-
x2​+y1​+z1​≤⌊22⌈n/2⌉+⌊n/2⌋​⌋=W
-
x1​+y2​+z1​≤⌊22⌈n/2⌉+⌊n/2⌋​⌋=W
We wish to find the maximal value of T that an element satisfying all these inequalities can have. Adding the last four inequalities and dividing by 4 , we obtain T≤⌊2V+3W​⌋. We consider four cases:
-
n=4k. V=W=3k, and so T≤6k. We can choose x1​=x2​=y1​=y2​=z1​=z2​= k to attain the bound.
-
n=4k+1. V=3k and W=3k+1, and so T≤6k+1. We can choose x1​=x2​=y1​=y2​=z2​=k and z1​=k+1 to attain the bound.
-
n=4k+2. V=3k+1 and W=3k+1, and so T≤6k+2. We can choose x1​=x2​=y1​=y2​=k and z1​=z2​=k+1 to attain the bound.
-
n=4k+3.V=3k+1 and W=3k+2, and so T≤6k+3. We can choose x1​=x2​=y2​=k and y1​=z1​=z2​=k+1 to attain the bound.
This concludes our proof.
This problem and solution were suggested by Warut Suksompong.
The problems on this page are the property of the MAA's American Mathematics Competitions