[obm-l] RE: [obm-l] Re: [obm-l] funções e poliminós

[Ralph Teixeira <RALPH@xxxxxx>]

 >2.Determine todas as funções estritamente crescentes f:N->N tais que 
>f(n+f(n))=2f(n) 

Interessante.... A resposta é múltipla:

i) Qualquer função do tipo f(n)=n+a para a>=0 fixo;
ii) Ou qualquer função do tipo f(0)=0 e f(n)=n+a para n>0, com a>=0 fixo.

Em primeiro lugar note que, se f é estritamente crescente, então
f(n+1)>=f(n)+1, e a igualdade só ocorre se f(n) e f(n+1) forem consecutivos,
certo? Ora, assim, f(a+b)>=f(a+b-1)+1>=f(a+b-2)+2>=...>=f(a)+b para
quaisquer a,b naturais. A igualdade (f(a+b)=f(a)+b) só ocorre se
f(a),f(a+1), f(a+2),...,f(a+b) forem números consecutivos!

Em particular, f(n+f(n))>=f(n)+f(n)=2f(n); a igualdade só ocorre se f(n),
f(n+1), f(n+2), ..., f(n+f(n)) forem todos consecutivos!

(Fazendo um pequeno aparte, note que se f é estritamente crescente, então
f(n)=0 só pode ter, no máximo, n=0 como solução.)

Como a igualdade OCORRE, olhe os dois primeiros termos da lista:
f(n+1)=f(n)+1 para qualquer n (exceto possivelmente se f(n)=0, quando a
nossa lista acima só tem "f(n)" e nem chega até "f(n+1)", de qualquer forma,
isto só pode ocorrer se n=0, né?).

Agora é fácil: como f(n+1)=f(n)+1 para qualquer n (exceto 0), tem-se
f(n)=n+a para qualquer n (onde a é fixo; a=f(1)-1, digamos).

Verifiquemos se precisa de mais algo: tomando f(n)=n+a, tem-se

f(n+f(n))=f(n+(n+a))=f(2n+a)=(2n+a)+a=2n+2a=2f(n) (OK!)

Enfim, para n=0 temos:

i) Se f(0)=0, então f(0+f(0))=f(0+0)=f(0)=0, e 2f(0)=0; funciona ok.
ii) Se f(0)=x>0, então f(0+f(0))=f(0+x)=x+a, e 2f(0)=2x; conclui-se que
x+a=2x, isto é, f(0)=a. Pode ser também!

Resposta final:

f(n)=n+a para a fixo e qualquer n>0
f(0)=0 OU f(0)=a (escolha o que você quiser).

>3. É possível empacotar 250 tijolos 1x1x4 em uma caixa de dimensões 
>10x10x10?

     Hmmmm.... Nao.

     Sejam (i,j,k) os índices de cada um dos "cubinhos" 1x1x1 da caixa
10x10x10 (0<=i,j,k<=9).
     Sejam A0={cubinhos onde i+j+k=0 mod 4}, A1={cubinhos onde i+j+k=1 mod
4}, A2={....=2 mod4} e A3={....=3 mod 4}. Em outras palavras, An é o
conjunto dos cubinhos cujos índices i+j+k deixam resto n na divisão por 4.

     Bom, primeiro convença-se de que cada tijolo 1x1x4 necessariamente
ocupará um cubinho de cada tipo (A0, A1, A2, A3). Assim, se fosse possível
cobrir a caia 10x10x10, teríamos 250 cubinhos de cada tipo.

     Mas quantos cubinhos do tipo A0 existem? Bom, a resposta é: "há tantos
cubinhos quantas forem as soluções de i+j+k=4m com 0<=i,j,k<=9". Olhando só
os restos na divisão por 4, temos as seguintes opções para i, j e k:
{0,1,2,3,0,1,2,3,0,1}. Veja os casos (tudo é feito modulo 4):

i) i=0 (3 opções) então j+k=0; temos j=0,k=0 (3x3 opções) ou j=1,k=3 (3x2
opções) ou j=k=2 (2x2 opções) ou j=3,k=1 (2x3 opções).
TOTAL DE SOLUÇÕES AQUI: 3.(9+6+4+6) = 75

ii) i=1 (3 opções) então j+k=3; as opções para (j,k) são (0,3), (1,2), (2,1)
ou (3,0) com 3x2+3x2+2x3+2x3=24 opções para j e k.
TOTAL: 3x24=72 opções aqui.

iii) i=2 (2 opções) então j+k=2; (j,k)=(0,2),(1,1),(2,0) ou (3,3). Total:
2x(3x2+3x3+2x3+2x2)=50 opções

iv) i=3 (2 opções) e j+k=1; (j,k)=(0,1),(1,0),(2,3)ou(3,2) com
2x(3x3+3x3+2x2+2x2)=52 opções.

Ou seja, há um total de 75+72+50+52=249 cubinhos do tipo A0. Mas, para
cobrir o cubo 10x10x10 com aqueles tijolinhos, teríamos de cobrir 250
cubinhos do tipo A0! Absurdo, portanto não é possível cobri-los.

--//--

Você podia contar cubinhos no braço também... Fica mais fácil de ver numa
figura, mas a idéia é que os cubinhos A0 são dos tipos:
     i+j+k=0 (o cubinho do canto)
     i+j+k=4 (um "plano" de cubinhos; use combinatória ou conte mesmo os
cubinhos aqui caso a caso: i=0 implica j+k=4, com 5 soluções; i=1 implica
j+k=3, com 4 soluções;... etc etc.... TOTAL: 5+4+3+2+1=15 cubinhos)
     i+j+k=8 (outro "plano" de cubinhos, com 9+8+7+6+...+1=45 cubinhos)
     i+j+k=12 (7+8+9+10+9+8+7+6+5+4=73 cubinhos)
     i+j+k=16 (3+4+5+6+7+8+9+10+9+8=69 cubinhos)
     i+j+k=20 (1+2+3+4+5+6+7+8=45 cubinhos)
     i+j+k=24 (1+2+3+4=10 cubinhos)
     i+j+k=28 (não dá mais)

Em suma, há

1+
1+2+3+4+5+
1+2+3+4+5+6+7+8+9+
      4+5+6+7+8+9+10+9+8+7+
              8+9+10+9+8+7+6+5+4+3+
                       8+7+6+5+4+3+2+1+
                               4+3+2+1 =
=1+15+45+73+69+36+10=249 cubinhos do tipo A0. O absurdo é o mesmo.
=========================================================================
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>
=========================================================================