IMC 2022, Ημέρα 1, Θέμα 3
Let be a prime number. A flea is staying at point of the real line. At each minute, the flea has three possibilities: to stay at its position, or to move by to the left or to the right. After minutes, it wants to be at again. Denote by the number of its strategies to do this (for example, : it may either stay at for the entire time, or go to the left and then to the right, or go to the right and then to the left). Find modulo .
Πρωτότυπο από το επίσημο PDF

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.
Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.
Επίσημη λύση
(proposed by Fedor Petrov, St. Petersburg)
Hint: Find a recurrence for or use generating functions.
Solution 1. The answer is for , for , and for .
The case is already considered, let further . For a residue modulo denote by the number of Flea strategies for which she is at position modulo after minutes. Then . The natural recurrence is , where the indices are taken modulo . The idea is that modulo we have and . Indeed, for all strategies for minutes for which not all actions are the same, we may cyclically shift the actions, and so we partition such strategies onto groups by strategies which result with the same . Remaining three strategies correspond to . Thus, if we denote , we get a system of equations , for all . It is not hard to solve this system (using the 3-periodicity, for example). For we get , and for .
Solution 2. Note that is the constant term of the Laurent polynomial (the moves to right, to left and staying are in natural correspondence with , and .) Thus, working with power series over we get (using the notation for the coefficient of in )
Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 3–4. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.
Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.
Πώς πήγε;
Οι κινήσεις που σημειώνεις επιστρέφουν νωρίτερα στη διαλογή.