Comments - Codeforces

→ Pay attention

Before contest
Codeforces Round 1134 (Div. 4)
3 days
Register now »

→ Top rated

#	User	Rating
1	Benq	3676
2	Kevin114514	3659
3	jiangly	3640
4	turmax	3450
5	tourist	3408
6	strapple	3360
7	Um_nik	3354
8	squareOf105	3348
9	maroonrk	3312
10	idontwannadothis…e	3191

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	Qingyu	154
2	nik_exists	151
3	maspy	149
4	AmShZ	146
5	Um_nik	143
6	Errichto	139
7	BledDest	136
8	adamant	135
9	maroonrk	133
10	cry	130

View all →

→ Find user

→ Recent actions

Detailed →

Comments

divyam

On ayush24 → Mathmania — Codefest'17, 9 years ago

+18

For each n let F_n be the number of permutations of {1, 2, . . . , n} with the required property; call them good. For n = 1, 2, 3 every permutation is good, so F₁ = 1, F₂ = 2, F₃ = 6.

Take an n > 3 and consider any good permutation (a₁, a₂, . . . , a_n) of {1, 2, . . . , n}. Then n − 1 must be a divisor of the number

2(a₁ + a₂ + · · · + a_n−1)
= 2(1 + 2 + · · · + n − a_n )
= n(n + 1) − 2a_n = (n + 2)(n − 1) + (2 − 2a_n ).

So 2a_n − 2 must be divisible by n − 1, hence equal to 0 or n − 1 or 2n − 2. This means that a_n = 1 or a_n = (n + 1)/2 or a_n = n. Suppose that a_n = (n + 1)/2. Since the permutation is good, taking k = n−2 we get that n-2 has to be a divisor of

2(a₁ + a₂ + · · · + a_n−2) = 2(1 + 2 + · · · + n) − a_n − a_n−1
= n(n + 1) − (n + 1) − 2a_n−1 = (n + 2)(n − 2) + (3 − 2a_n−1).

So 2a_n−1 − 3 should be divisible by n − 2, hence equal to 0 or n − 2 or 2n − 4. Obviously 0 and 2n − 4 are excluded because 2a_n−1 − 3 is odd. The remaining possibility (2a_n−1 − 3 = n − 2) leads to a_n−1 = (n + 1)/2 = a_n, which also cannot hold. This eliminates (n + 1)/2 as a possible value of a_n. Consequently a_n = 1 or a_n = n.

If a_n = n then (a₁, a₂, . . . , a_n−1) is a good permutation of {1, 2, . . . , n−1}. There are F_n−1 such permutations. Attaching n to any one of them at the end creates a good permutation of {1, 2, . . . , n}.

If a_n = 1 then (a₁−1, a₂−1, . . . , a_n−1−1) is a permutation of {1, 2, . . . , n−1}. It is also good because the number 2(a₁−1) + · · · + (a_k−1) = 2(a₁ + · · · + a_k) − 2k is divisible by k, for any k ≤ n − 1. And again, any one of the F_n−1 good permutations (b₁, b₂, . . . , b_n−1) of {1, 2, . . . , n−1} gives rise to a good permutation of {1, 2, . . . , n} whose last term is 1, namely (b₁+1, b₂+1, . . . , b_n−1+1, 1).

The bijective correspondences established in both cases show that there are F_n−1 good permutations of {1, 2, . . . , n} with the last term 1 and also F_n−1 good permutations of {1, 2, . . . , n} with the last term n. Hence follows the recurrence F_n = 2F_n−1. With the base value F₃ = 6 this gives the outcome formula F_n = 3 * 2ⁿ⁻² for n ≥ 3.

divyam

On bharat.khanna.cse14 → Manthan, Codefest 17 Announcement, 9 years ago

Codefest'17 is excited to present a mathematical programming contest — Mathmania. It will bring a delectable collection of problems which will be an absolute delight for all the mathematics geeks. Cash prizes worth INR 50,000.

divyam