MathDB

2001 BAMO

Part of BAMO Contests

Subcontests

(5)
5
1

2001 BAMO p5 3^{334} divides a_2001, number of permutations

For each positive integer nn, let ana_n be the number of permutations τ\tau of {1,2,...,n}\{1, 2, ... , n\} such that τ(τ(τ(x)))=x\tau (\tau (\tau (x))) = x for x=1,2,...,nx = 1, 2, ..., n. The first few values are a1=1,a2=1,a3=3,a4=9a_1 = 1, a_2 = 1, a_3 = 3, a_4 = 9. Prove that 33343^{334} divides a2001a_{2001}. (A permutation of {1,2,...,n}\{1, 2, ... , n\} is a rearrangement of the numbers {1,2,...,n}\{1, 2, ... , n\} or equivalently, a one-to-one and onto function from {1,2,...,n}\{1, 2, ... , n\} to {1,2,...,n}\{1, 2, ... , n\}. For example, one permutation of {1,2,3}\{1, 2, 3\} is the rearrangement {2,1,3}\{2, 1, 3\}, which is equivalent to the function σ:{1,2,3}→{1,2,3}\sigma : \{1, 2, 3\} \to \{1, 2, 3\} defined by σ(1)=2,σ(2)=1,σ(3)=3\sigma (1) = 2, \sigma (2) = 1, \sigma (3) = 3.)
1
1
4
1

2001 BAMO p4 kingdom of 12 cities in circle, magician 13th every month

A kingdom consists of 1212 cities located on a one-way circular road. A magician comes on the 1313th of every month to cast spells. He starts at the city which was the 5th down the road from the one that he started at during the last month (for example, if the cities are numbered 1–121–12 clockwise, and the direction of travel is clockwise, and he started at city #99 last month, he will start at city #22 this month). At each city that he visits, the magician casts a spell if the city is not already under the spell, and then moves on to the next city. If he arrives at a city which is already under the spell, then he removes the spell from this city, and leaves the kingdom until the next month. Last Thanksgiving the capital city was free of the spell. Prove that it will be free of the spell this Thanksgiving as well.
3
1
2
1