uniolympiads English

IMC 2023, Ημέρα 2, Θέμα 6

Ivan writes the matrix (2324)\begin{pmatrix} 2 & 3 \\ 2 & 4 \end{pmatrix} on the board. Then he performs the following operation on the matrix several times:

  • he chooses a row or a column of the matrix, and
  • he multiplies or divides the chosen row or column entry-wise by the other row or column, respectively.

Can Ivan end up with the matrix (2423)\begin{pmatrix} 2 & 4 \\ 2 & 3 \end{pmatrix} after finitely many steps?

Πρωτότυπο από το επίσημο PDF2 3 Problem 6. Ivan writes the matrix on the board. Then he performs the following 2 4 operation on the matrix several times: • he chooses a row or a column of the matrix, and • he multiplies or divides the chosen row or column entry-wise by the other row or column, respectively. 2 4 Can Ivan end up with the matrix after finitely many steps? 2 3

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

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

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

Επίσημη λύση

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

Hint: Construct an invariant quantity that does not change during Ivan's prcedure.

Solution. We show that starting from A=(2324)A = \begin{pmatrix} 2 & 3\\ 2 & 4\end{pmatrix}, Ivan cannot reach the matrix B=(2423)B = \begin{pmatrix} 2 & 4\\ 2 & 3\end{pmatrix}.

Notice first that the allowed operations preserve the positivity of entries; all matrices Ivan can reach have only positive entries.

For every matrix X=(x11x12x21x22)X = \begin{pmatrix} x_{11} & x_{12}\\ x_{21} & x_{22}\end{pmatrix} with positive entries, let L(X)=(log⁡2x11log⁡2x12log⁡2x21log⁡2x22)L(X) = \begin{pmatrix} \log_2 x_{11} & \log_2 x_{12}\\ \log_2 x_{21} & \log_2 x_{22}\end{pmatrix}. By taking logarithms of the entries, the steps in Ivan game will be replaced by adding or subtracting a row or column to the other row. Such standard row and column operations preserve the determinant.

Hence, if the matrices in the game are A=X0,X1,X2,…A = X_0, X_1, X_2, \ldots, then we have det⁡L(A)=det⁡L(X1)=det⁡L(X2)=…\det L(A) = \det L(X_1) = \det L(X_2) = \ldots, and it suffices to verify that det⁡L(A)≠det⁡L(B)\det L(A) \ne \det L(B).

Indeed,

det⁡L(A)=log⁡22⋅log⁡24−log⁡24⋅log⁡23=log⁡2(4/3)>0\det L(A) = \log_2 2 \cdot \log_2 4 - \log_2 4 \cdot \log_2 3 = \log_2(4/3) > 0
and similarly det⁡L(B)<0\det L(B) < 0, so det⁡L(A)≠det⁡L(B)\det L(A) \ne \det L(B).

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

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

Πώς πήγε;