[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re:Res: [obm-l] QUADRADO COLORIDO
Oi, Klaus:
Apesar do nome pomposo, o "principio da inclusao-exclusao" eh bastante simples e intuitivo. Apesar disso, eh extremamente
poderoso e vale a pena ser aprendido. Ele nada mais eh do que a generalizacao da formula:
#(A uniao B) = #(A) + #(B) - #(A inter B) para um numero arbitrario de conjuntos.
(#(X) = numero de elementos do conjunto X)
No mais, eu tambem achei a outra solucao do gabarito meio enrolada, de modo que aqui vai uma solucao alternativa pro
problema, no veneravel estilo "eu-sou-burro-mas-nao-sou-cego" (o meu favorito): ela usa apenas o principio multiplicativo e
divide o problema em varios casos mutuamente exclusivos, cada um dos quais pode ser tratado de forma razoavelmente simples.
Fixe a cor do quadrado central, digamos A.
Os outros 8 quadrados podem ser pintados de 2^8 = 256 maneiras distintas.
Alem disso, qualquer quadrado 2x2 monocromatico serah necessariamente A.
O caso em que o quadrado central eh V eh totalmente simetrico (basta trocar A com V na solucao abaixo).
Assim, pra calcular a probabilidade desejada, basta considerar apenas um caso
(ateh porque Prob = NCF/NCP = (2*NCF)/(2*NCP)).
Considere a cruz formada pelo quadrado central e pelos 4 quadrados que tem um lado em comum com ele.
Quanto a pintura destes 4 quadrados, temos 6 casos a considerar:
1: os 4 sao A;
2: 3 sao A e 1 eh V;
3.1: 2 sao A e 2 sao V - os dois V com um vertice comum;
3.2: 2 sao A e 2 sao V - os dois V totalmente disjuntos;
4: 1 eh A e 3 sao V;
5: os 4 sao V.
Em cada casao, o numero total de pinturas possiveis eh:
1: 2^4 = 16
2: 4*2^4 = 64
3.1: 4*2^4 = 64
3.2: 2*2^4 = 32
4: 4*2^4 = 64
5: 2^4 = 16
Total de Casos Possiveis: 256
Quantas dessas pinturas tem um quadrado 2x2 A?
1: 16 - 1 = 15 (soh nao vai ter se os quatro cantos forem V);
2: 4*(16 - 4) = 48 (uma vez escolhido o quadrado V da cruz, das 16 maneiras de se pintar os quadrados dos cantos, apenas 4 nao
vao produzir um quadrado 2x2 A - justamente aquelas em que os quadrados dos cantos nao adjacentes ao quadrado V sao
pintados de V);
3.1: 4*2^3 = 32 (uma vez escolhido os 2 quadrados V adjacentes, basta pintar o canto disjunto dos dois de A que teremos um
quadrado 2x2 A. Os outras 3 cantos podem ser pintados de qualquer jeito);
3.2: 0;
4: 0;
5: 0 (eh razoavelmente facil ver o porque nestes 3 ultimos casos).
Total de Casos favoraveis: 95
Probabilidade = 95/256.
[]s,
Claudio.
---------- Cabeçalho original -----------
De: owner-obm-l@mat.puc-rio.br
Para: obm-l@mat.puc-rio.br
Cópia:
Data: Mon, 20 Nov 2006 04:46:40 -0800 (PST)
Assunto: Res: [obm-l] QUADRADO COLORIDO
> Ola Douglas,
> a resposta nao eh essa nao. Essa questao caiu na segunda fase da obm-2003(?) nivel 3. Tem a solucao la no site da obm(dá
uma verificada), só que nao entendi algumas coisas na solucao. A primeira solucao dada é via principio da inclusao-exclusao(nao
entendi pq nao cheguei nisso ainda) a segunda é mais comum. No entanto, não entendo pq só se contou aqueles casos para um
quadrado de lado 2 monocromático. Existem outros casos eu posso ter por exemplo com 5 cores de azul, começando a pintar do
lado superior esquerdo do quadrado e pintar o inferior direito tambem de azul e logo em seguida os adjacentes a esse de
vermelho.Essa é uma configuracao(eu acho) possivel.Só que não está lá, aliás só se conta com 5 cores quando se pinta o 5º
quadradinho no meio de uma das colunas que faltam (pq??). O mesmo acontece com 6 cores.
>
>
> ----- Mensagem original ----
> De: Douglas Ribeiro Silva <dougzbr@gmail.com>
> Para: obm-l@mat.puc-rio.br
> Enviadas: Segunda-feira, 20 de Novembro de 2006 3:44:14
> Assunto: Re: [obm-l] QUADRADO COLORIDO
>
>
> Temos 2^9 diferentes modos diferentes de pintar os quadrados. Para
> termos um quadrado de lado 2 inteiramente da mesma cor, ele está no
> canto superior esquerdo, superior direito, inferior esquerdo ou
> inferior direito. Ele também pode ser todo pintado de vermelho ou todo
> pintado de azul. Então sobram 5 quadrados que podem ser pintados de
> outras cores quaisquer. 2^5 maneiras. Multiplicamos por 4(para cada
> canto do quadrado) e depois por 2(para cada cor). Logo temos 2^8
> maneiras. Então a probalididade é 2^8/2^9 = 1/2. Não sei se está
> correto, mas acho que é assim. Qualquer problema avisem!
>
> Abraços!
>
> Em 18/11/06, Klaus Ferraz<klausferraz@yahoo.com.br> escreveu:
> >
> > (OBM)Um quadrado de lado 3 é dividido em 9 quadrados de lado unitário,
> > formando um quadriculado.Cada quadrado unitário é pintado de azul ou
> > vermelho.Cada cor tem probabilidade 1/2 de ser escolhida e a cor de cada
> > quadrado é escolhida independentemente das demais. Qual a probabilidade de
> > obtermos, após colorirmos todos os quadrados unitários, um quadrado de lado
> > 2 pintado inteiramente de uma mesma cor?
> > ________________________________
> > O Yahoo! está de cara nova. Venha conferir!
>
> =========================================================================
> 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 Yahoo! está de cara nova. Venha conferir!
> http://br.yahoo.com
>
=========================================================================
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
=========================================================================