uniolympiads English

IMC 2024, Ημέρα 1, Θέμα 3

For which positive integers nn does there exist an n×nn \times n matrix AA whose entries are all in {0,1}\{0, 1\}, such that A2A^2 is the matrix of all ones?

Πρωτότυπο από το επίσημο PDFFor which positive integers n does there exist an n × n matrix A whose entries are all in {0, 1}, such that A 2 is the matrix of all ones?

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

(proposed by Alex Avdiushenko, Neapolis University Paphos, Cyprus)

Hint: Let JJ be the n×nn \times n matrix with all ones. Consider A3=AJ=JAA^3 = AJ = JA.

Solution. Answer: Such a matrix AA exists if and only if nn is a complete square.

Let JnJ_n be the n×nn \times n matrix with all ones, so A2=JnA^2 = J_n. Consider the equality

A3=AJn=JnA.A^3 = AJ_n = J_nA.

In the matrix AJnAJ_n, all columns are equal to the sum of colums in AA, that is, the (i,j)(i,j)th entry in AJnAJ_n is the number of ones in the iith row of AA. Similarly, the (i,j)(i,j)th entry in JnAJ_nA is the number of ones in the jjth column of AA. These numbers must be equal, so AA contains the same number of ones in every row and every column. Let this common number be kk; then AJn=JnA=kJnAJ_n = J_nA = kJ_n.

Now from

nJn=Jn2=(A2)2=A(AJn)=A(kJn)=k(AJn)=k2JnnJ_n = J_n^2 = (A^2)^2 = A(AJ_n) = A(kJ_n) = k(AJ_n) = k^2J_n
we can read n=k2n = k^2, so nn must be a complete square.

It remains to show an example for a matrix AA of order n=k2n = k^2. For l=0,1,…,k−1l = 0, 1, \dots, k-1, let BlB_l be the k×kk \times k matrix whose (i,j)(i,j)th entry is 11 if j−i≡l(modk)j - i \equiv l \pmod{k} and 00 otherwise, i.e., BlB_l can be obtained from the identity matrix by cyclically shifting the colums ll times, and let

A=(B0B1B2…Bk−1B0B1B2…Bk−1⋮⋮⋮⋱⋮B0B1B2…Bk−1);A = \begin{pmatrix} B_0 & B_1 & B_2 & \dots & B_{k-1} \\ B_0 & B_1 & B_2 & \dots & B_{k-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ B_0 & B_1 & B_2 & \dots & B_{k-1} \end{pmatrix};

The (i,j)(i,j)th block in A2A^2 is

(B0B1…Bk−1)(Bj−1⋮Bj−1)=(B0+B1+⋯+Bk−1)Bj−1=JkBj−1=Jk,\begin{pmatrix} B_0 & B_1 & \dots & B_{k-1} \end{pmatrix}\begin{pmatrix} B_{j-1} \\ \vdots \\ B_{j-1} \end{pmatrix} = (B_0 + B_1 + \dots + B_{k-1})B_{j-1} = J_kB_{j-1} = J_k,
so this matrix indeed satisfies A2=Jk2A^2 = J_{k^2}.

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 3–4. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;