Solved 2000+ problems

Probability Level 4

Let π \pi be a permutation of { 1 , 2 , . . . , 2000 } \{1, 2, . . . , 2000\} .

Find the maximum possible number of ordered pairs ( i , j ) ∈ { 1 , 2 , . . . , 2000 } 2 (i, j)\in\{1, 2, . . . , 2000\}^2 with i < j i < j such that π ( i ) . π ( j ) > i . j \pi(i).\pi(j)> i. j .

This problem is adapted from HMMT.


The answer is 1997001.

Khang Nguyen Thanh by Khang Nguyen Thanh , 27, Vietnam

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Jesse Nieminen
Sep 7, 2015

One of the best possible permutations is {2, 3, ..., 2000, 1} (There is no better permutation. Only better would be {1,2,...,2000} for which inequality if false} Here the number of possible ordered pairs is 1 + ... + 1998 = 1998*1999/2 = 1997001. (I'll edit this solution to better solution when I get home)

0 Helpful 0 Interesting 0 Brilliant 0 Confused

Why it is the best permutation?

Khang Nguyen Thanh - 5 years, 9 months ago

Log in to reply

It is one of the best permuatitations, because there is no better permutation. Better permutation would have 2000 numbers in ascending order and only possible is therefore {1, 2, ..., 2000}. However in this permutation pi(i)*pi(j) = i * j so the inequality is false.

Jesse Nieminen - 5 years, 9 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...