Re: [obm-l] Combinatória

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

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.

Um polinômio p de grau n é dito simétrico se o coeficiente de x^i for igual
ao de x^(n-i) para todo i. Um polinômio real de grau n é dito unimodal simétrico
se, além de ser simétrico, os seus coeficientes forem positivos e
não-decrescentes de x^0 até x^[n/2] e não-crescentes de x^[(n+1)/2] até x^n.
O que precisamos provar é que o produto de polinômios unimodais simétricos
é unimodal simétrico; fica para vocês pensarem.

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