|
Bn = B(n-1) x (n-1) + B(n-2) x (n-2)
Seja An todas as arrumacoes de n poss�veis (pela regra), ou seja,
n {An} = Bn
* A primeira parcela [B(n-1) x (n-1)] se refere �s (n-1) posicoes em q
podemos colocar o en�simo termo em cada uma das arruma�oes de A(n-1), fazendo
valer a regra.
* A segunda parcela � um pouco mais complexa.
Ela se refere aos casos particulares em que com os primeiros (n-1) termos
temos APENAS UM par de algarismos desobedecendo a regra, ou seja, temos 2
algarismos consecutivos em ordem.
Assim, podemos colocar o �ltimo algarismo entre esses dois, fazendo a regra
voltar a valer.
Um dos pares de n�meros consecutivos de 1 a (n-1) pode ser considerado como
um algarismo apenas, fazendo valer a regra para A(n-2), o q nos dar� arrumacoes
onde haver� apenas UM par desobedecendo a regra (o par q escolhemos). Nesse
caso, h� B(n-2) maneiras poss�veis.
Ora, podemos fazer valer a regra, desta maneira, com qualquer par de
n�meros consecutivos (em ordem) de 1 a (n-1). Como existem (n-2) pares neste
conjunto, e h� B(n-2) maneiras para cada par, prova-se a segunda parcela.
Assim, Bn = B(n-1) x (n-1) + B(n-2) x (n-2)
Onde vc ficou surpreso, Nicolau? ----- Original Message -----
From: "Nicolau C. Saldanha" <nicolau@mat.puc-rio.br>
Sent: Quinta-feira, 7 de Dezembro de 2000 00:35
Subject: 260 N�o, n�o � o n�mero de pontos de ningu�m. � o n�mero de membros da nossa lista: 260. Eu verifico este n�mero periodicamente e esta � a 1a vez que observo um n�mero >250. Mas mudando de assunto... Arrumamos em fila n bolinhas numeradas de 1 a n. De quantas formas podemos faz�-lo sem que: 1 fique imediatamente antes de 2, 2 fique imediatamente antes de 3, ... (n-1) fique imediatamente antes de n? Chamemos a resposta de Bn Estas s�o as �nicas restri��es. N�o � proibido que 2 venha logo antes de 1. Temos B2 = 1 (21) B3 = 3 (132, 213, 321) B4 = 11 (1324, 1432, 2143, 2413, 2431, 3142, 3214, 3241, 4132, 4213, 4321) O problema n�o � t�o dif�cil, mas h� algo que me surpreendeu na resposta. []s, N. |