[obm-l] Re: [obm-l] Questão de Combinatória

["Cláudio \(Prática\)" <claudio@xxxxxxxxxxxxxxxxxxxxxxx>]

Aqui vai a solução de mais um problema em aberto esquecido....

----- Original Message -----
From: "haroldo" <divaneto@uol.com.br>
To: <obm-l@mat.puc-rio.br>
Sent: Friday, January 31, 2003 8:58 AM
Subject: [obm-l] Questão de Combinatória



abaixo questão original da olimpiada Austrália -
 Let n be even .Four different numbers a,b,c,d are chosen from the integers
1,2,..,n
in such way that a+c=b+d.
Show that the number of such selections is n*(n-2)*(2n-5)/24.

    .sugestão: podemos considerar sem perda de generalidade que a<b<d<c
             e que para par (a,c) o número de quadruplas depende apenas de
c-a.


Vou tentar uma solução meio "no braço".

Seja n = 2m.
Vamos enumerar todas as somas possíveis de dois elementos distintos de
{1,2,...,2m}

3 = 1+2
4 = 1+3
5 = 1+4 = 2+3
6 = 1+5 = 2+4
7 = 1+6 = 2+5 = 3+4
....
2m-1 = 1+(2m-2) = 2+(2m-3) = ... = (m-1)+m
2m = 1+(2m-1) = 2+(2m-2) = ... = (m-1)+(m+1)
2m+1 = 1+2m = 2+(2m-1) = ... = m+(m+1)
2m+2 = 2+2m = 3+(2m-1) = ... = m+(m+2)
2m+3 = 3+2m = 4+(2m-1) = ... = (m+1)+(m+2)
2m+4 = 4+2m = 5+(2m-1) = ... = (m+1)+(m+3)
...
4m-5 = (2m-5)+2m = (2m-4)+(2m-1) = (2m-3)+(2m-2)
4m-4 = (2m-4)+2m = (2m-3)+(2m-1)
4m-3 = (2m-3)+2m = (2m-2)+(2m-1)
4m-2 = (2m-2)+2m
4m-1 = (2m-1)+2m

Seja N(k) = número de pares (não ordenados) distintos de {1,2,...,2m} cuja
soma é k.
Então, da enumeração acima, deduzimos que:

N(3) = N(4) = 1
N(5) = N(6) = 2
N(7) = N(8) = 3
...
N(2m-1) = N(2m) = m-1
N(2m+1) = m
N(2m+2) = N(2m+3) = m-1
N(2m+4) = N(2m+5) = m-2
...
N(4m-6) = N(4m-5) = 3
N(4m-4) = N(4m-3) = 2
N(4m-2) = N(4m-1) = 1

Além disso, repare que para cada k, os pares cuja soma é k são disjuntos
dois a dois.

Seja P(k) = número de quadruplas distintas (a,b,c,d) de {1,2,...,2m} com a <
b < c < d tais que:
a+d = b+c.

P(k) = C(N(k),2) = N(k)*[N(k)-1]/2

O que desejamos de fato, é a soma de todos os P(k) ( 3 <= k <= 4m-1 ).
Isso é igual a:
4*[C(1,2) + C(2,2) + C(3,2) + ... + C(m-1,2)] + C(m,2) =
4*C(m,3) + C(m,2) =
4*m*(m-1)*(m-2)/6 + m*(m-1)/2 =
[m*(m-1)/2]*[4*(m-2)/3 + 1] =
[m*(m-1)/2]*[(4m-5)/3] =
m*(m-1)*(4m-5)/6

Lembrando que m = n/2, teremos:

(n/2)*(n/2 - 1)*(2n - 5)/6 = n*(n-2)*(2n-5)/24


Um abraço,
Claudio.

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================