MathDB
T=sum_{i=1}^n f(i)* (fi-1)/2 and n is odd, find min(T)

Source: USAMO 1987 Problem 5

July 24, 2011
algebra unsolvedalgebra

Problem Statement

Given a sequence (x1,x2,…,xn)(x_1,x_2,\ldots, x_n) of 0's and 1's, let AA be the number of triples (xi,xj,xk)(x_i,x_j,x_k) with i<j<ki<j<k such that (xi,xj,xk)(x_i,x_j,x_k) equals (0,1,0)(0,1,0) or (1,0,1)(1,0,1). For 1≤i≤n1\leq i \leq n, let did_i denote the number of jj for which either j<ij < i and xj=xix_j = x_i or else j>ij > i and xj≠xix_j\neq x_i.
(a) Prove that A=(n3)−∑i=1n(di2).A = \binom n3 - \sum_{i=1}^n\binom{d_i}2. (Of course, (ab)=a!b!(a−b)!\textstyle\binom ab = \tfrac{a!}{b!(a-b)!}.) [5 points]
(b) Given an odd number nn, what is the maximum possible value of AA? [15 points]
Back to ProblemsView on AoPS