Re: [obm-l] Combinatória

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 30.09.04 09:40, Nicolau C. Saldanha at nicolau@mat.puc-rio.br wrote:

> On Thu, Sep 30, 2004 at 01:19:55AM -0400, Faelccmm@aol.com wrote:
>> Ok !
>> 
>> Falando novamente sobre o assunto, vejam as equações:
>> 
>> (I): x1 + x2 + x3 + x4 = 27 (o maior valor para incógnitas é 9 e todos os
>> valores são naturais)
>> (II): x1 + x2 + x3 + x4 = 18 (o maior valor para incógnitas é 9 e todos os
>> valores são naturais)
>> 
>> Há como provar que a equação (II) possui mais soluções que (I) sem
>> resolvê-las pelo método exposto por você ?
>> 
>> Da para generalizar este problema, ou seja, comparar 2 equações destes tipos
>> (com cotas superior) e dizer qual a que possui mais soluções ?
> 
> Sim. Seja f_{n,a}(k) o número de soluções de x1 + ... + xn = k, 0 <= xi <= a.
> Então f é não-decrescente de 0 até na/2 e não-crescente de na/2 até na;
> se n > 1 podemos trocar "não-decrescente" e "não-crescente" por
> "estritamente crescente" e "estritamente decrescente", respectivamente.
>
Acho que basta provar que para todo inteiro k tal que 0 <= k < na/2, existe
uma sobrejecao do conjunto das solucoes de x1 + .. + xn = k + 1 sobre o
conjunto das solucoes de x1 + ... + xn = k.

A sobrejecao eh obtida facilmente:
Seja (a_1,a_2,...,a_n) uma solucao de x_1 + ... + x_n = k.
Se a_1 < a, entao (a_1 + 1,a_2,...,a_n) eh uma solucao de:
x1 + ... + xn = k + 1.
Caso contrario, seja j o menor indice tal que a_j < a. Entao:
(a_1,...,a_j + 1,...,a_n) eh solucao de x1 + ... + xn = k + 1.

O caso em que k > na/2 eh tratado mediante uma mudanca de variaveis similar
a que o Shine usou: yi = a - xi. Esta mudanca de variaveis estabelece uma
bijecao entre o conjunto das solucoes de:
x1 + ... + xn = k 
e o das solucoes de:
x1 + ... + xn = na - k,
para 0 <= k <= na/2.

[]s,
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
=========================================================================