The rows and columns of a 2n×2n table are numbered from 0 to 2n−1. The cells of the table have been coloured with the following property being satisfied: for each 0≤i,j≤2n−1, the j-th cell in the i-th row and the (i+j)-th cell in the j-th row have the same colour. (The indices of the cells in a row are considered modulo 2n.) Prove that the maximal possible number of colours is 2n. Proposed by Hossein Dabirian, Sepehr Ghazi-nezami, Iran
Problem
Source:
Tags: IMO Shortlist, combinatorics, number theory, matrix
18.07.2011 06:42
Paint the cells such that as many colors as possible are used. (i.e. for any two cells if they do not need to have the same color, then we paint them differently.) In such situation, I claim that we have used exactly 2n colors. I will use induction. Consider the cells with both even coordinates. The configuration of their colors are in fact the same as the 2n−1 case. Thus 2n−1 colors are used for these cells by induction. And for a cell (i,j) where at least one i,j is odd, using the recurrence stated in the problem, we will return to (i,j) after exactly 3⋅2n−1 cells. Thus there are 3⋅2n−1 cells having the same color with (i,j), including itself. This is in fact the last theorem in the paper http://www.ams.org/journals/mcom/1967-21-100/S0025-5718-1967-0223064-6/S0025-5718-1967-0223064-6.pdf Hence exactly (2n)2⋅343⋅2n−1=2n−1 colors are used for the remaining cells. The result follows.
03.04.2017 02:46
Let N=2n. Consider the directed graph G on (Z/N)2 with edges (j,i)→(i+j,j). The problem reduces to showing that there are exactly 2n connected components in this graph. First looking mod 2, observe the vertices with both even coordinates are completely disjoint from those with both odd coordinates. This means that we'll proceed by induction on n, with base cases n≤2 being done by hand. So we'll show that exactly 2n−1 new coordinates are generated on the 34⋅N2 vertices with at least one odd coordinate (and applying induction hypothesis). The main structural claim is that: Claim: Let a and b be integers, at least one of which is odd. Then (a,b) is contained in a cycle of length exactly 3⋅2n−1. In the motivating example (1,0) this implies the cycle is (1,0)→(2,1)→(3,2)→(5,3)→(8,5)→….More generally, starting from (a,b) the (k+1)st vertex is (aFk+1+bFk,aFk+bFk−1), where F0=0, F1=1, F2=1, F3=2, is the Fibanocci sequence. We will now prove three lemmas, from which the claim follows immediately by setting (a,b)≡(aFk+1+bFk,aFk+bFk−1) and doing calculation. (Again (1,0) is the main motivating example.) Lemma: We have F_k \equiv 0 \pmod 4 if and only if k \equiv 0 \pmod 6. In that case, F_{k-1} \equiv 1 \pmod 4. Proof. Obvious, just write out the sequence modulo 4. \blacksquare Lemma: For all m \ge 1, \nu_2(F_{6m}) = \nu_2(m) + 3. Proof. The easiest proof is notice that F_{3m} = \frac{1}{\sqrt5} \left( \left( 2+\sqrt5 \right)^{2m} - (2-\sqrt5)^{2m} \right) and then copy verbatim the proof of the exponent lifting lemma. \blacksquare Lemma: For all m \ge 1, \nu_2(F_{6m-1} - 1) = \nu_2(F_{6m+1} - 1) = \nu_2(m) + 2. Proof. Let a = F_{6m-1}, b = F_{6m}, so \nu_2(b) = \nu_2(m) + 3 \ge 3. We use the identity F_{6m}^2 + 1 = F_{6m-1}F_{6m+1} \implies b^2 + 1 = a(a+b) \implies a = -\frac{1}{2} b + \underbrace{\sqrt{5(b/2)^2 + 1}}_{c}. Now c \equiv 1 \pmod 4 since a \equiv 1 \pmod 4, and (c-1)(c+1) = \frac{5b^2}{4}. Hence \nu_2(c-1) = 2\nu_2(b)-2-1 \ge \nu_2(b). So \nu_2(a) = \nu_2(b)-1 as desired. \blacksquare Finally this implies the problem since each cycle has length 3 \cdot 2^{n-1} and the number of squares is \frac 34 N^2, which gives 2^{n-1} cycles.
03.08.2017 09:52
Define a color-sequence to be a sequence a_0,a_1,... taken \pmod{2^n} with a_{n+2}=a_{n+1}+a_n. The key is that the squares at (a_n, a_{n+1}) are the same for all n given a color sequence \{a_n\}. Note that \{a_n\} is periodic \pmod{2^n}, so we just need to prove that the number of equivalence classes of color-sequences \pmod{2^n} is at most 2^n. As an example, we have the color-sequences 1,0,1,1,2,3,\ldots; 3,0,3,3,2,1,\ldots; 0,0,\ldots; and 2,2,0,\ldots \pmod{4}. First we prove a lemma: Lemma: Let an odd color-sequence be a color sequence with at most one of a_0, a_1 even. Then the period of an odd color-sequence is 3\cdot 2^{n-1}. Proof: We inductively show that \phi^{3\cdot 2^{n-1}}=(1+a\cdot 2^{n+1})+(b\cdot 2^n)\sqrt{5} for integers a,b with b odd. It is easy to check that for n=2 we have \phi^6=9+4\sqrt{5}. Now, if the result is true for n, note that \phi^{3\cdot 2^n}=[(1+a\cdot 2^{n+1})^2+5(b\cdot 2^n)^2] + [2(1+a\cdot 2^{n+1})\cdot (b\cdot 2^n)]\sqrt{5}which is of the form (1+a'\cdot 2^{n+2})+(b'\cdot 2^{n+1})\sqrt{5}, as desired. Now use the extended 2-adic valuation. We show that the least integer d_n such that v_2(\phi^{d_n}-1)=n is d_n=3\cdot 2^{n-1}. It is easy to check that d_2=6. Now, clearly d_n\mid d_{n+1}. But by the information above, v_2\left(\phi^{3\cdot 2^{n-1}}-1\right)=n, so it follows that d_n\neq d_{n+1}. Thus d_{n+1}\ge 2d_n, and it is easy to see that v_2(\phi^{2d_n}-1)=n+1, as desired. Now suppose \{a_n\} was an odd color-sequence but has period less than 3\cdot 2^n. Write a_n=x\phi^n+y(-\phi)^{-n} and let p be the period. We can easily check that the period is even by showing that the period is even for any such sequence \pmod{4}. Now, if a_p\equiv a_0 and a_{p+1}\equiv a_1, then 2^n\mid (\phi^p-1)(x-y\phi^{-p}) and 2^n\mid (\phi^p-1)(x\phi+y\phi^{-p-1}). But v_2(\phi^p-1)<n, so 2\mid x-y\phi^{-p}, x\phi+y\phi^{-p-1}. But then it follows that 2\mid \phi(x-y\phi^{-p})-(x\phi+y\phi^{-p-1})=-y(\phi^{1-p}+\phi^{-1-p}). Since v_2(\phi)=0, we get 2\mid y(\phi^2+1)=\sqrt{5}y\phi. Thus 2\mid y. Similarly, we get 2\mid x. But then it follows 2\mid a_0,a_1, and \{a_n\} is not an odd color-sequence, contradiction! Thus the order of all odd color-sequences is 3\cdot 2^{n-1}. \blacksquare Now we prove the statement that there are 2^n equivalence classes of color-sequences \pmod{2^n} through induction. Note that the statement is true for n=2 (as shown above). A non odd color-sequence \pmod{2^n} is equivalent to a color-sequence \pmod{2^{n-1}}, since any sequence of form 2b_0,2b_1,...\pmod{2^{n}} has a corresponding sequence b_0,b_1,...\pmod{2^{n-1}}. There are 2^{n-1} such sequences in this case. Else, consider the odd color-sequences. There are 3\cdot 2^{2n-2} ways to choose the first two terms: 3 ways to choose parity and 2^{n-1} for each parity. Now since any two consecutive terms are unique to each equivalence class, it follows that there are \frac{3\cdot 2^{2n-2}}{3\cdot 2^{n-1}}=2^{n-1} equivalence classes, since there are 3\cdot 2^{n-1} unique pairs of consecutive terms per equivalence class by our lemma above. It follows that there are 2^{n-1}+2^{n-1}=2^n equivalence classes \pmod{2^n}, completing the inductive step. \square
02.02.2018 18:52
Please check my dolution
07.11.2018 23:58
Let F_1=F_2=1,F_{n+2}=F_n+F_{n+1} be the Fibonacci sequence. It's easy to verify that 6\mid n \iff 4\mid F_n and that F_{2n}= F_n(F_{n-1}+F_{n+1}), F_{2n+1}=F_n^2 + F_{n+1}^2. (Both of these follow from the well-known F_{m+n} = F_mF_{n+1} + F_{m-1}F_n.) Lemma 1: 2^{k+1} \mid F_{3\cdot 2^{k-1}} for k\ge 2 and F_{3\cdot 2^{k-1} +1} \equiv 2^k+1 \pmod {2^{k+1}} for all k\ge 1. Proof: We induct on k with the appropriate base cases. The first statement's inductive step is trivial since F_{3\cdot 2^k} = F_{3\cdot 2^{k-1}} (F_{3\cdot 2^{k-1}-1} + F_{3\cdot 2^{k-1}+1}); the second term is the sum of two odd terms, so it contributes a factor of 2. Similarly, the second statement follows because F_{3\cdot 2^{k-1}+1} = F_{3\cdot 2^{k-2}}^2 + F_{3\cdot 2^{k-2}+1}^2; the first term vanishes modulo 2^{k+1} for k\ge 3 while, by the inductive hypothesis, the second term is of the form (a\cdot 2^k + 2^{k-1} + 1)^2 \equiv 2^k+1\pmod {2^{k+1}}. Now I claim the period of F_n modulo 2^k is 3\cdot 2^{k-1} for any k\ge 1. We can verify k=1,2 manually. For k\ge 3, let p be the period. By the lemma, we know F_{3\cdot 2^{k-1}},F_{3\cdot 2^{k-1}+1}\equiv 0,1\pmod {2^k}, hence we can easily show F_{n+3\cdot 2^{k-1}}\equiv F_n\pmod {2^k} so p\mid 3\cdot 2^{k-1}; meanwhile, since F_{3\cdot 2^{k-2}+1} \equiv 2^{k-1} + 1\not\equiv 1\pmod {2^k} by the lemma, we see that p\nmid 3\cdot 2^{k-1}. Since 4\mid F_p, our first observation yields 6\mid p; in particular, since 3\mid p, the above divisibilities tell us we must have p=3\cdot 2^{k-1} as desired. Now we can easily prove the original problem by induction on n with base cases n=0,1 easy to verify. For the inductive step, consider any value of n>1. Note that the operation f(i,j) =(j,i+j) (taken modulo 2^n) is clearly a bijection on the cells of the table. Now for any square (a,b) with 2\mid a,b, we see that f^k (a,b) always has two even coordinates, so by dividing the coordinates by 2, we get a correspondence to the squares of a 2^{n-1}\times 2^{n-1} table following the same constraints. Therefore, the 2^{2n-2} cells (a,b) with two even coordinates can be colored by a maximum of 2^{n-1} colors; now we ignore such squares and focus on squares with at least one odd coordinate. In this case, note that f^k (a,b) = (F_{k-1}a + F_kb, F_ka+F_{k+1}b). Because f is a bijection, in any maximal coloring the squares with the same color correspond to a cycle of f; I claim this cycle always has length 3\cdot 2^{k-1}. Indeed, a cycle requires f^k(a,b)=(a,b), or F_{k-1}a + F_kb \equiv a, F_ka + F_{k+1}b \equiv b; since every third square in this cycle has two odd coordinates, WLOG suppose a,b are both odd. Then it's not hard to show that we need F_k\equiv 0, F_{k-1}\equiv F_{k+1}\equiv 1\pmod {2^n}, meaning the size of the cycle is just the period of F modulo 2^n, or 3\cdot 2^{n-1}. Now since there are 3\cdot 2^{2n-2} total squares with (a,b) not both even, we get 2^{n-1} total cycles; combining with the previous observation gives 2^n total colors as desired.
17.03.2020 23:59
From arguements similar to the above solutions, we just need that the Fibonacci sequence has period 3*2^{n-1} modulo 2^n. Let A= \begin{bmatrix} 0&1\\ 1&1 \end{bmatrix} Claim: v_2(\det(A^{3*2^{n-1}}-I))=2n. Proof: Note that \det(A^{3*2^{n-1}}-I)=\det(A^{3*2^{n-2}}-I)\det(A^{3*2^{n-2}}+I) by induction, \det(A^{3*2^{n-2}}-I) has 2n-2 powers of 2 Now, we just need \det(A^{3*2^{n-2}}+I) has only 2 powers of 4. This follows from the fact that F_{3*2^{n-1}}+F_{3*2^{n-1}+2}=2mod4.(Examine the fibonacci sequence mod 4, has period 6) Thus, our claim has been proven. Thus, A^{3*2^{n-1}}-I cannot be the 0 map modulo 2^{n+1}. By another arguement that has been repeated in above solutions, we can show by induction A^{3*2^{n}}-I is the 0 map modulo 2^{n+1}. Hence we are done.
23.04.2020 18:50
Solution with william122 The cases n = 0,1 are direct to verify. Suppose now n \ge 2. Draw directed edge (i,j) \to (j,i+j) for each square (i,j). Define an odd square to be a square with at least one odd coordinate. Note that each cycle in the n-1 case through vertices v_1,...,v_t directly bijects to a cycle in the n case through vertices 2v_1,...,2v_t. Observe that if a cycle contains an odd square then all squares in the cycle must be odd. We will show that for a 2^n\times 2^n board, 1) there are 2^{n-1} cycles through the odd vertices 2) for each cycle C going through some odd square, the set of squares in the 2^{n+1} \times 2^{n+1} board that are in C \pmod{2^n} is covered by 2 cycles C_1, C_2 \pmod 2^{n+1}, with |C_1| = |C_2| = 2|C| = 3\cdot 2^n. For each cycle through squares (s_1,s_2), (s_2,s_3),...,(s_t,s_1) define the corresponding sequence by (s_0,s_1,s_2,...) with s_i := s_{i-1} + s_{i-2} \forall i. Note that a cycle passes through some odd square if and only if there are no consecutive even terms in the sequence (s_i). There are a,b \in \mathbb Z[\sqrt{5}] such that s_i = a\alpha^i + b(\frac{-1}{\alpha})^i since \alpha := \frac{1+\sqrt{5}}{2}, \frac{-1}{\alpha} are roots of the characteristic polynomial x^2 - x- 1. Lemma: The smallest m for which there exists \kappa \in \mathbb Z_2[\sqrt{5}] such that \alpha^m = 1 + 2^n\kappa is m = 3\cdot 2^{n-1} for all n \ge 1. Proof: Note that when n = 1, m = 3. By LTE we have \nu_2(\alpha^{3m} -1) = 1 + \nu_2(m), which concludes the proof. \blacksquare Now suppose s_t, s_{t+1}\equiv s_0, s_1\pmod {2^n} respectively, then a\alpha^t + b(\frac{-1}{\alpha})^t \equiv a + b.a\alpha^{t+1} + b(\frac{-1}{\alpha})^{t+1} \equiv a\alpha + b(\frac{-1}{\alpha})We then obtain a(\frac{-1}{\alpha} - \alpha)(\alpha^t - 1) = 0, but \frac{-1}{\alpha} - \alpha = -\sqrt{5}, thus a(\alpha^t - 1) = 0. Likewise b(\alpha^t - 1) = 0. Thus if \nu_2(\alpha^t -1) < n then 2|a,b, contradiction to the sequence passing through an odd square. Thus any cycle passing through an odd square of an 2^n \times 2^n has length equal to the order of \alpha \pmod {2^n} which is 3\cdot 2^{n-1}. It suffices to show that each cycle splits into 2, and we do this by noting that for each sequence s, (s_{3\cdot 2^{n-2}},s_{3\cdot 2^{n-2}}) is congruent to (s_0,s_1) \pmod {2^{n-1}} yet not congruent \pmod {2^n}, hence their difference is a multiple of 2^{n-1}. Note that for each odd square (a,b) \pmod {2^{n-1}} there are 4 squares \pmod {2^n} (namely \{a,a+2^{n-1}\}\otimes \{b, b+2^{n-1}\}) congruent to it \pmod {2^{n-1}}, and for each sequence s\pmod {2^n} congruent to some sequence s' \pmod {2^{n-1}} that correspond to cycles on the odd squares, s covers only 2 of the 4 residues produced by each square of the cycle corresponding to s'\pmod {2^{n-1}}. Since the cycles covering s' \pmod {2^n} must be disjoint it follows that there are exactly 2 of them. \mathcal{YUH}.
10.08.2020 10:28
Let (i,j) deontes the j^{th} cell of the i^{th} row. For any a,b, let the sequence with a_0=a,a_1=b,a_{n+2}=a_{n+1}+a_nbe the (a,b)-Fibonaaci sequence, where the terms are considered modulo 2^n-1. From the condition, the cell formed by every two consecutive terms in the (a,b)- Fibonacci sequence has the same color of (a,b). Define the equivalence relation (a_1,b_1)\sim(a_2,b_2) if (a_1,b_1) belongs to the (a_2,b_2)- Fibonacci sequence. It suffices to show that there are exactly 2^n equivalence classes. We proceed by induction on n. The base cases are trivial. Now suppose all smaller case holds, we consider the case n. Now suppose (a,b) is a cell in the case n-1. Then (2a,2b) is a cell in the case n. Meanwhile, the equivalence classes of (a,b) in the case n-1. has the same number of elements as the equivalence classes of (a,b) in the case n. Hence there're 2^{n-1} equivalence classes which contains (a,b) with both a and b even. Now we show the following: CLAIM. If a and b are not both even, then the equivalence classes containing (a,b) has 3\cdot 2^{n-1} elements. Or in other words, the (a,b)-Fibonacci sequence has period 3\cdot 2^{n-1}. Proof. Let \{a_n\} be the (a,b)-Fibonacci sequence Notice that let F_n be the n^{th} Fibonacci number then a_{n+2}=F_{n+1}a_1+F_na_0Hence it suffices to show that the Pisano period of Fibonacci sequence mod 2^n is 3\cdot 2^{n-1}. This is well-known but I will still prove it. We claim that for n\geq 2, v_2(F_{3\cdot 2^{n-1}})=n+1and F_{3\cdot 2^{n-1}-1}\equiv 2^{n}+1 \pmod{2^{n+1}}We proceed by induction on n. The base cases are trivial. Suppose these are true for some n-1, we consider the case n. Indeed, we have F_{3\cdot 2^{n}}=F_{3\cdot 2^{n-1}}(F_{3\cdot 2^{n-1}-1}+F_{3\cdot 2^{n-1}+1})By the inductive hypothesis we have F_{3\cdot 2^{n-1}-1}+F_{3\cdot 2^{n-1}+1}\equiv 2\pmod{2^n} Hence v_2(F_{3\cdot 2^{n}})=v_2(F_{3\cdot 2^{n-1}})+1=n+1. Now by inductive hypothesis we have F_{3\cdot 2^{n-1}-2}\equiv 2^n-1\pmod{2^{n+1}}Hence F_{3\cdot 2^{n-1}-2}=2^{n+1}k+2^n-1 for some odd k. Therefore F_{3\cdot 2^n-2}=(2^{n+1}k+2^n-1)^2=2^{n+1}-1\pmod{2^{n+2}}From which we easily obtain F_{3\cdot 2^{n}-1}=F_{3\cdot 2^{n}}-F_{3\cdot 2^{n}-2}=2^{n+1}+1\pmod{2^{n+2}}\blacksquare Since there are 2^2n-2^{2n-2}=3\cdot 2^{2n-2} cells whose coordinates are not all even, hence they form 2^{n-1} equivalence classes, this completes the proof.
28.12.2021 13:33
An equivalent formulation is to consider the ring R_n=\mathbb{Z}[\varphi]/2^n\mathbb{Z}[\varphi] (which is isomorphic to \mathbb{Z}/2^n\mathbb{Z}[\varphi]), where \phi=\frac{1+\sqrt{5}}{2}, and to consider the number of orbits obtained by repeatedly multiplying by \varphi. This is because (a+b\varphi)\varphi=a\varphi+b\varphi^2=a\varphi+b+b\varphi=b+(a+b)\varphi, which corresponds to passing from the cell (a,b) to (b,a+b). Since \varphi is invertible in this ring, it suffices to count the number of such orbits in R_n^\times, and add this number from 1 to n, and also add the orbit due to 0\cdot \varphi^n. Therefore, if we find the order of \varphi ord_n(\varphi), the number of orbits will be \frac{|R_n^\times|}{ord_n(\varphi)}. Lemma: ord_n(\varphi)=3\cdot 2^{n-1} Proof: for n=1, it is trivial, and in fact we have v_2(\varphi^3-1)=v_2(1+2\varphi-1)=v_2(2\varphi)=1 (we define v_2(x) for 0\neq x\in \mathbb{Z}[\varphi] as the highest power of 2 dividing both coefficients). So we can now use LTE (the proof is as normal and basically comes down to prove that v_2(x^{2^k}+y^{2^k})=1 if x\equiv y\pmod{2}; clearly x^{2^k}+y^{2^k}\equiv 2x^{2^k}\equiv 0\pmod{2}, and if it was also true mod 4 we would have \left(\frac{x^{2^{k-1}}}{y^{2^{k-1}}}\right)^2 \equiv -1, but this is not possible, because (a+b\varphi)^2=(a^2+b^2)+(2ab+b^2)\varphi \equiv -1\pmod{4}\implies a^2+b^2\equiv -1\pmod{4} which is a contradiction), for n\geq 1 because 2|\varphi^3-1 and 2^n is even. We therefore obtain: v_2(\varphi^{3\cdot 2^{n}}-1)=v_2(\varphi^6-1)-1+v_2(3\cdot 2^n)=v_2(5+8\varphi-1)+n-1=2-1+n=n+1, which implies ord_n(\varphi)=3\cdot 2^{n-1} for n\geq 1[by induction we have 3\cdot 2^{n-1}=ord_n(\varphi)|ord_{n+1}(\varphi)|3\cdot 2^n, but ord_{n+1}(\varphi) can't be 3\cdot 2^{n-1} since v_2(\varphi^{3\cdot 2^{n-1}}-1) is only n and not n+1]. Finally the number of orbits in R_n^\times must be \frac{|R_n^\times|}{ord_n(\varphi)}=\frac{(2^n)^2-(2^{n-1})^2}{3\cdot 2^{n-1}}=\frac{3\cdot 2^{2(n-1)}}{3\cdot 2^{n-1}}=2^{n-1}. Therefore, summing this number for all k=1,...,n and including the contribution of the orbit of 0, we get that the total number of orbits, and thus the maximal number of colours is 1+\sum_{k=1}^n 2^{k-1}=1+2^n-1=2^nas wanted.
30.01.2022 03:48
+\!\!\!\!\!\!\:\times Sketch: We can reduce the problem to finding the period of the Fibonacci sequence \!\!\!\mod{2^n} by considering the cycles (i,j) \to (j,i+j) \to (i+j,i+2j) \to \cdots.Let F_n be the nth Fibonacci number. We prove two claims: Claim: If 6 \mid n, then \nu_2(F_{2n})=\nu_2(F_n)+1. Proof: Let L_n be the nth Lucas number. Use F_{2n}=F_nL_n and take L_n \!\!\mod{8}. Claim: \nu_2(F_{3 \cdot 2^{n+1}})=n+1 for all nonnegative integers n. Proof: Use the fact that F_{2n+1}=F_n^2+F_{n+1}^2. Combining these claims gives the desired result.
25.04.2022 23:04
Wrong.
15.02.2024 03:31
Correspond the cells to 2-dimensional vectors in ({\mathbb Z}/2^n{\mathbb Z})^2. Let A= \begin{bmatrix} 0&1\\ 1&1 \end{bmatrix}. We want to show that the digraph \textbf{v} \to A\textbf{v} has exactly 2^n connected components. (Thus, one may color the unfriendly cells in the equality case suggested by inductive hypothesis, and color each cycle with a single unique color, for a total of 2^n colors.) We proceed by induction on n \ge 2 (since n=1 is workable by hand), with the base case trivial. For the inductive step, call cells with both coordinates even unfriendly and all other cells friendly, and note that they are all part of connected components independent of that of all other cells. Furthermore, scaling down by a factor of 2 implies that there are exactly 2^{n-1} unfriendly connected components, by inductive hypothesis on the n-1 case. The key claim is the following. Claim: The graph of friendly vertices is compromised of cycles of length exactly 3 \cdot 2^{n-1}. Proof. We show that A^{3 \cdot 2^{n-1}} \equiv I modulo 2^n. More specifically, we have \nu_2(\det(A^{3 \cdot 2^{n-1}} - I)) = n which we will prove; this will show that 3 \cdot 2^{n-1} is indeed the smallest period that works. We induct on n \ge 2 with base case easy. Note that \det(A^{3 \cdot 2^{n-1}} - I) = \det(A^{3 \cdot 2^{n-2}} - I)\det(A^{3 \cdot 2^{n-2}} + I). By inductive hypothesis, 2^{n-1} \parallel \det(A^{3 \cdot 2^{n-2}} - I), so it suffices to show that 2 \parallel \det(A^{3 \cdot 2^{n-2}} + I), or rather that this determinant is 2 \pmod{4}. Note that (inductively), A^k has a main diagonal of elements that are both F_k, the kth Fibonacci number. It is easy to see that the 3 \cdot 2^{n-2}nd Fibonacci number is even (by say, mod 3 bash), so \det(A^{3 \cdot 2^{n-2}} + I) is just \det(A^{3 \cdot 2^{n-2}}) + 2 \cdot F_{3 \cdot 2^{n-2}} + 1 \equiv 1 + 0 + 1 \equiv 2 \pmod{4}, and we are done. Thus, there are at exactly \frac{(2^n)^2-(2^{n-1})^2}{3 \cdot 2^{n-1}} = 2^{n-1} friendly connected components. Adding the unfriendly connected components, there are exactly 2^n connected components in total.
18.03.2024 20:00
I have obtained a miraculous proof of this fact which doesn't use the pisot period of F_n. So it's probably a fakesolve but idk how plz check. DM me if you find the fake part of it. Note that this gives chains. (i, j) \to (i+j, i) \to (2i+j, i+j) \to \dots It remains to show that there are at most 2^n such chains. Note that these chains end up being pairs of elements from the Fibonacci sequence. Claim: There are exactly 2^n such chains. Proof. Consider the residues \pmod{2} of the first element. If the element is (0, 0), then it follows that by mapping (i, j) \to \left(\frac{i}{2}, \frac{j}{2}\right) that there are 2^n of these pairs. If the element is (0, 1), (1, 0), (1, 1), shift till its (1, 1). Then subtract the chain generated by (1, 1) from the original chain, and divide each element of tha chain by 2. This gives us our other 2^n pairs. \blacksquare