Re: [obm-l] Combinatoria.

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 09.10.03 08:23, guilherme S. at guilherme_s_ctba@yahoo.com.br wrote:

> belez pessoal, estou com dificuldade nesta questao:
> 
> Escrevem-se numeros distintos (inclusve os começados
> por zero) em cartoes. Como 0,1 e8 nao se alteram de
> cabeça para baixo e como 6 de cabeça para baixo se
> transforma em 9, um so cartao pode representar dois
> numeros.Qual e o numero minimo de cartoes para
> representar todos os numeros de cinco digitos?
> 
Eu fiz algum progresso nesse mas nao cheguei a uma resposta definitiva.

Estou supondo que voce quer escrever todos os inteiros do intervalo:
[10000,99999].

Tomemos o algarismo 1.
Voce vai precisar de pelo menos 3 cartoes "1".
Exemplos: 1a1b1, onde a e b sao algarismos diferentes de 1.

Alem desses, voce vai precisar de um cartao "11".
Exemplos: 11111, 1111a, 111a1, 11a11, 1a111, a1111, onde a pode ser qualquer
algarismo diferente de 1 (exceto 0 no ultimo exemplo).

O mesmo raciocinio se aplica a 2, 3, 4, 5, 7 e 8.

Total ateh agora = 4*7 = 28 cartoes.

*****

Eh claro que cartoes "6" e "66" podem ser usados como "9" e "99".
No entanto, para formar os numeros 6969a, a6969, 9696a e a9696 (a: algarismo
qualquer), apenas 3 cartoes "6" e um "66" nao serao suficientes. Nesse caso,
voce vai realmente precisar de 5 cartoes "6".

Total ateh agora = 28 + 5 = 33 cartoes.

*****

Alem disso, voce vai precisar de 2 cartoes "0" e um "00".
Exemplos: a0000, a000b, a0b00, a00b0, a00bc, a0b0c, a0bc0, ab0c0, abc00,
a0bcd, ab0cd, abc0d, abcd0, onde a,b,c,d podem ser quaisquer algarismos nao
nulos.

Em suma, voce vai precisar de no maximo 33 + 3 = 36 cartoes.

*****

Eu diria que estes 36 cartoes sao de fato necessarios, mas admito que algum
deles possa ser redundante em virtude das simetrias mencionadas no
enunciado.

Eh claro que pode haver alguma outra colecao com menos cartoes que produza
todos os numeros de 5 algarismos, mas acho que a descrita acima (ou algum
subconjunto proprio dela) seja a otima.


Um abraco,
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
=========================================================================