CHARADAS, TESTES, ETC. E TAL

[sonolento soneca]

Prezados companheiros,

Encontrei um método para tirar do apuro a nobre rainha Dani.

Aliás diga-se de passagem, a Putônia tem muita semelhança com um certo outro país que conheço. Como eu sou péssimo jogador e não canto pagode (outra coisa muito apreciada lá), não tive tanto sucesso por aquelas terras, só me restava dar alguns beliscões furtivamente em algumas nádegas...

Com o desespero da nobre rainha, fui chamado para ajudar a resolver o problema.

Após algum tempo de raciocínio, imaginei o seguinte: com uma combinação dos 10 valentes apaixonados dispostos a perder a vida em nome da rainha poderia descobrir a maldita garrafa envenenada. Seria feito da seguinte forma:

1) Numera-se as garrafas de 1 a 1000 ( g1,g2.g3,...g1000) e os bebedores de 1 a 10 (b1,b2,...,b10).

2) Faz-se uma combinação de 2 bebedores entre os 10 e obtem-se 45 combinações diferentes. Para cada combinação de bebedores dá-se um gole de uma garrafa (g1->b1+b2, g12->b1+b3, ...., g45->b9+b10 – da garrafa g1 bebem b1 e b2, da garrafa g2 bebem b1 e b3 e assim sucesssivamente);

3) Faz-se o mesmo procedimento para combinações de 3 bebedores obtendo 120 combinações
(g46->b1+b2+b3, .....g165->b8+b9+b10)

- Parênteses: Fórmula da combinação (esta é do tempo do colégio): Cn,p = n! / (p! x (n-p)!).
Ex: C 10,2 = 10! / (2! x 8!) = 45.

4) Repete-se o procedimento para 4 bebedores obtendo 210 combinações. Repete-se com 5 bebedores obtendo 252 combinações e assim sucessivamente...

5) Somando-se as combinações: 45 (2 bebedores) + 120 (3 bebedores) + 210 (4 bebedores) + 252 (5 bebedores) + 210 (6 bebedores) + 120 (7 bebedores) + 43 (8 bebedores – nem precisou usar todas as combinações), tem-se 1000 combinações para as 1000 garrafas, restando apenas aguardar quais bebedores cairão duros no trigésimo dia e identificar qual garrafa é a envenenada.


É isso.

A propósito da Putônia, parece que o rei Ronaldo está solteiro novamente se preparando para as disPUTAS futebolísticas do próximo ano e a ex-rainha é apresentadora de TV, com um programa que por incrível que pareça se chama PRESEPADA.

[Tricampeão]

Falei que os caras são feras, a resposta do Sonolento é impecável. No entanto, conheço outras duas possíveis. Querem tentar descobrir? Qual foi a solução que o Dom Lulú achou?

[Dom Lulú]

Falei que os caras são feras, a resposta do Sonolento é impecável. No entanto, conheço outras duas possíveis. Querem tentar descobrir? Qual foi a solução que o Dom Lulú achou?

Caro Tri:
Realmente, tenho que concordar que a solução do Sonolento chega às raias do brilhantismo. Minha solução, muito mais modesta, é a seguinte:
1) Elenquemos os dez "sacrificáveis" de "A" a "J";
2) Enumeremos as garrafas de 1 até 1000;
3) Separemos inicialmente (p/ o chamado "primeiro dia") dez lotes com cem garrafas para cada um dos sacrificáveis, que deverão dar uma "bicadinha" em cada uma das cem garrafas de su lote;
4) Para o chamado 2º dia, cada lote de cem garrafas deve ser subdividido em lotes de 10 garrafas, com a seguinte distribuição para cada sacrificável:

- "A", fica com as garrafas de 1 a 10 (de seu próprio lote de cem) + garrafas de 101 a 110 (do lote de cem garrafas de B) + garrafas de 201 a 210 (do lote de cem garrafas de C) e assim por diante. Cada um dá um tragozinho nesse 2º dia em cada uma do novo lote de 100 garrafas em seu poder.
- "B", fica com 11 a 20, 111 a 120 (de su próprio lote inicial de 100), 211 a 220 e assim por diante, inclusive para cada indivíduo (até J);

5) No 3º dia, cada lote de 10 garrafas deverá ser subdividido em lotes unitários, ou seja, de uma única garrafa. Assim, cada sacrificável terá um novo lote de 100 garrafas com a seguinte distribuição:


- "A", fica com as garrafas nºs 01, 11, 21, 31..............até 991, perfazendo um novo lote de 100 garrafas, para cada um dos sacrificáveis.

Ora, só para efeito de raciocínio, se a garrafa envenenada fosse a nº 1, o sujeito "A" morreria no 31º dia. Ninguém morreria no 32º dia e também ninguém morreria no 33º dia (pois só o A tomou a garrafa de nº 1). Entretanto, se a garrafa envenenada fosse a de nº 12, por exemplo, "A" morreria no 1º dia, "B" morreria no 2º dia e ninguém morreria no 3º dia. Sem saber óbviamente qual a garrafa, surge aí uma grande dúvida: Qualquer uma das duas garrafas dos lotes unitários tanto de "A" como de "B" poderiam estar envenenadas.

Então, é preciso de uma chamada "Prova Real", utilizando um chamado 4º dia (ainda dá, 30+4=34, pois o casamento se dará no 35º dia).
Ordenados em fila indiana nesse 4º dia, cada sacrificável faz um "escravo de Jó" para frente passando o seu lote do 3º dia. Assim, B fica com o lote de A, C fica com o lote de B e assim por diante.

Conclusões:
- Invariávelmente teremos uma morte no 31º dia.
- Só não teremos uma morte no 32º dia se o mesmo que morreu no 31º também tomou o veneno de um dos lotes de 10 contido no seu próprio lote inicial de 100 garrafas;
- Se tivermos uma morte qualquer no 33º dia, a garrafa envenenada estará automáticamente identificada;
- Se não tivermos uma morte no 33º dia, caímos no caso da Prova Real realizada no 4º dia e também idenficaremos a garrafa envenenada.
- Curiosidade para se pensar: Nesse procedimento, teremos um mínimo de 2 mortes e um máximo de 4 mortes em qualquer hipótese considerada.

Abraço

Dom Lulú

Tricampeão: Seu novo enigma me deixou uma dúvida...........pode-se repetir exatamente a mesma sequencia de boquetes de um dia para o outro, ou obrigatóriamente deverá existir variação ???

[Tricampeão]

Dom Lulú, a solução que você apresentou é uma das duas outras que eu disse que conhecia. No entanto, ainda resta um pequeno problema a resolver. Suponha que a garrafa envenenada seja a 11; nesse caso, A morre no trigésimo-primeiro dia, B no trigésimo-segundo, ninguém no trigésimo-terceiro dia e ninguém também no trigésimo-quarto dia, já que apenas A e B terão bicado dela. No entanto, a garrafa envenenana poderia também ser a 20 e provocar as mesmas mortes. Então, acredito que esta solução precisa de uma segunda "Prova-Real", nos moldes da primeira, que poderia ser realizada no quinto dia, permitindo que a maldita garrafa seja identificada quando os sinos da Basílica de Putônia estiverem prestes a badalar, anunciando a entrada da noiva.

Quanto ao novo enigma, você está certo, manter a mesma distribuição do dia anterior evita que a engolidora de porra fique sem grana. Eu devia ter colocado uma condição extra para impedir essa solução trivial. De qualquer forma, ela não é a melhor possível. Considere que SempreAlerta encontrou uma maneira de a ratazana ganhar sempre, fazendo com que os sacanas tenham um dia que parar com a brincadeira e liberar a bruaca.

[sonolento soneca]

TRICAMPEÃO e companheiros,

Fim de ano, ao contrário de muitos, eu não ganho 13o., conclusão - não tenho tido oportunidades ($$$) de fazer TDs e postar. Mas sempre resta os enigmas dos bons companheiros pra decifrar.

Acho que descobri qual distribuição o Sempre Alerta - aliás, onde andas tu, rapá ? - sugeriu para a boqueteira de modo que ela ganhasse dinheiro, fazendo com que os três putanheiros a colocassem em liberdade.

Assim como fez o Dom Lulu no outro enigma, vou esperar pra ver se alguém também encontra a solução.

Falando em TRICAMPEÃO, espero que neste domingo o meu SPFC, o TRIcolor do Morumbi se torne TRI também ... TRICAMPEÃO MUNDIAL!!!

Abraços,

Sonolento.

[Tricampeão]

Pois é, caro Sonolento, fim de ano é foda, alguns não têm décimo-terceiro, e os que têm entregam tudo pras piranhas antes do dia 15. Mas o pior são aquelas festinhas meia-boca de empresa, onde a carne é dura, a cerveja é quente, só toca pagode e a mesa de truco tá sempre ocupada. Nessas horas, um enigmazinho maneiro é a salvação da lavoura, o único problema é que você fica andando pra lá e pra cá com o olho vidrado, trombando na pentelhada que seus colegas de trabalho levaram e ficou presa debaixo do toldo por causa da chuva que caiu de surpresa, a galera pensa que você andou cheirando erva doce mofada. Por isso, aí vai mais um problema altamente elaborado pra ajudar a enfrentar essas horas difíceis.

Quatro foristas sem grana pra putear estavam sentados jogando conversa fora na cobertura do Edifício Itália (do lado de fora, é claro, não naquele restaurante carésimo que tem lá). Um deles propôs a questão de descobrirem de que andar seus óculos de nerd poderiam ser deixados cair em queda livre sem quebrar-se. Não chegando a um acordo a partir de meras elocubrações teóricas, uma vez que não dispunham de tabelas com o módulo de Young dos materiais envolvidos, a aceleração gravitacional exata no local e a viscosidade do ar de Sampa naquele úmido dia de dezembro, partiram para um ensaio experimental. A princípio, iam jogar uma garrafa de cerveja do primeiro andar, depois do segundo, se ela não se quebrasse na primeira queda, e assim por diante, até encontrar a altura fatal. ElPatrio, entretanto, sugeriu que, uma vez que dispunham de duas garrafas, talvez fosse possível encontrar um algoritmo que trouxesse a resposta mais rápido. Não que os caras tivessem que ganhar tempo, estavam na bosta, ociosidade total, apenas cacoete de quem tem mania de fazer as coisas do jeito mais difícil.
Que algoritmo permite minimizar o número de testes, considerando que o prédio em questão possui 44 andares?

Apenas para completar a cultura matemática dos colegas, minha solução para o problema do grand cru envenenado. Peço aos companheiros que verifiquem se ela está realmente correta, porque esta eu nunca vi em lugar nenhum:
1) Numerar as garrafas, de 0 a 999, número que será chamado NumGarrafa.
2) Numerar cada otário que vai provar o vinho, de 0 a 9, número que será chamado NumProvador.
3) Atribuir a cada provador um valor equivalente à potência de 2 correspondente ao seu número, de 1 a 512, valor que será chamado ValProvador.
4) Decompor cada NumGarrafa na soma adequada de valores de ValProvador. Cada imbecil cujo valor entrar na soma precisará bicar da garrafa. Por exemplo, da garrafa 456 ( = 256 + 128 + 64 + 8 ) beberão os panacas número 8, 7, 6 e 3; ninguém precisará provar a garrafa 0.
ou, o que dá no mesmo,
4) Escrever os números das garrafas e dos provadores na base 2, valores que serão chamados, respectivamente, de BinGarrafa e BinProvador e calcular, para cada combinação garrafa x provador, o resultado de BinGarrafa & BinProvador, & indicando aqui "bitwise and". Se o valor calculado for diferente de 0, o cara terá que bicar da garrafa.
5) Calcular, após 30 dias, a soma de ValProvador de todos os que morrerem envenenados. Esse será o NumGarrafa procurado.
Vejam que, com esta resposta, a garrafa é identificada em 31 dias, como na proposta pelo Sonolento, e morrem entre 0 e 10 idiotas. A solução apresentada pelo Lulú demora mais uns dias mas mata menos babacas.
Infelizmente, ninguém ainda descobriu uma maneira de resolver o problema sem cometer o pecado de abrir 1000 garrafas de Château-Lafitte um mês antes de beber, comprometendo sua suavidade ímpar através da inevitável oxidação que disso sobrevirá.

[sonolento soneca]

Saudações tricolores a todos. É TRICAMPEÃO MUNDIAL !!!

Sem grana pros TDs ... vamos aos enigmas. Mais uma resposta - a do enigma da boqueteira:

Recapitulando... A boqueteira (B) tem que distribuir 10 boquetes por dia entre 3 putanheiros (G, L e F) de modo que G tem que receber mais boquetes que L e L mais que F. Ela ganha $, em relação a cada putanheiro, se fizer mais boquetes que o dia anterior e paga $ se fizer menos que o dia anterior. Além disto, ela morre se não conseguir pagar $ a qualquer um dos 3 e começa a brincadeira sem nenhum $.

Se ela fizer a distribuição abaixo, com o tempo ela sempre ganhará.

1o. dia: G ( 9 boq.) ; L ( 1 boq.) ; F ( 0 boq.)
2o. dia: G ( 7 boq. / +$); L ( 2 boq. / -$); F ( 1 boq./ -$) ->B (+$)
3o. dia: G ( 5 boq. / +$$); L ( 3 boq. / -$$); F ( 2 boq. / -$$) -> B (+$$)
4o. dia: G ( 9 boq. / +$); L ( 1 boq./ -$); F ( 0 boq./ -$) -> B (+$)

5o. dia: igual ao 2o. dia = B recebe $ ficando com saldo de +$$
6o. dia: igual ao 3o. dia = B recebe $ ficando com saldo de +$$$

e assim sucessivamente...

Conclusão, B é quem mais enriquece e embora G também ganhe, L e F sempre perdem, inviabilizando a brincadeira.





Tricampeão, esta sua solução do enigma da garrafa, usando números binários, é muito boa. É típica de quem trabalha com informática, certo?

[Dom Lulú]

Caro Tricampeão:
- Considerando o prédio de 44 andares e, imaginando o pior caso, que seria de quebrar no 44º andar, se tivéssemos apenas uma garrafa, precisaríamos de 44 tentativas.
- Entretanto, com duas garrafas, poderíamos dividir os 44 andares em um intervalo tal, que explorando os seus múltiplos determinaríamos o ponto de quebra de uma primeira garrafa. Em seguida, utilizaríamos a segunda garrafa para explorarmos o intervalo entre o ponto de quebra e o múltiplo imediatamente anterior, para determinarmos exatamente o andar em que se dará a quebra. Obviamente, a questão será determinar o intervalo de andares que determinará o menor número de tentativas, sempre considerando o pior caso (quebra no 44º andar).
- Seja N o número de tentativas e I o intervalo de andares, podemos estabelecer a seguinte equação algébrica:
N=44/I + (I-1), teremos que achar o menor número "N" em relação aos possíveis intervalos "I":
1 44
2 23
3 16,66666667
4 14
5 12,8
6 12,33333333
7 12,28571429
8 12,5
9 12,88888889
10 13,4
11 14
12 14,66666667
13 15,38461538
14 16,14285714
15 16,93333333
16 17,75
17 18,58823529
18 19,44444444
19 20,31578947
20 21,2
21 22,0952381
22 23

Notem que o intervalo de 7 andares proporciona o menor número possível de tentativas para se encontrar o ponto de quebra no pior caso.
Generalizando o raciocínio: Jogamos a primeira garrafa do 7º andar. Se ela quebrar, jogamos a segunda garrafa do 1º andar, depois do 2º e assim por diante até determinarmos o ponto exato de quebra. Se não quebrar no 6º andar é porque era mesmo no 7º andar.
Caso a primeira garrafa não quebre no 7º andar, vamos jogá-la do 14º andar. Se quebrar, utilizaremos a segunda garrafa a partir do 8º andar, de acordo com procedimento anterior e assim por diante.

Caso esse raciocínio esteja correto, a ética me obriga a dividir os méritos com um amigo (apelidado carinhosamente de "Bebeloira")......

Abraços

Dom Lulú

[Tricampeão]

Muito bem, já vi que esse promete render bastante.

Considerando o prédio de 44 andares e, imaginando o pior caso, que seria de quebrar no 44º andar, se tivéssemos apenas uma garrafa, precisaríamos de 44 tentativas.

Certo.

Entretanto, com duas garrafas, poderíamos dividir os 44 andares em um intervalo tal, que explorando os seus múltiplos determinaríamos o ponto de quebra de uma primeira garrafa.

Errado. A proposição do problema não exige, nem é conveniente manter um intervalo constante de andares nessa exploração.

Em seguida, utilizaríamos a segunda garrafa para explorarmos o intervalo entre o ponto de quebra e o múltiplo imediatamente anterior, para determinarmos exatamente o andar em que se dará a quebra.

Certo.

Obviamente, a questão será determinar o intervalo de andares que determinará o menor número de tentativas, sempre considerando o pior caso (quebra no 44º andar).

Errado. Esse não é necessariamente o pior caso. O pior caso depende da estratégia adotada. Se entendi bem, na que você propôs, ele acontece quando a resistência das garrafas atinge apenas 41 andares. Então, a primeira garrafa seria atirada do 7º, depois do 14º, depois do 21º, 28º, 35º, não se quebrando, depois do 42º, quebrando-se, levando a segunda garrafa a ser jogada do 36º em diante, um por um, até o 41º, para fechar as possibilidades. Isso dá um total de 12 arremessos, como você calculou. Mas há um algoritmo que resulta num total menor de arremessos para o pior caso.

[sonolento soneca]

Tricampeão e companheiros,

Este último foi phoda... Semana passada demorei um bom tempo para decifrá-lo, depois do almoço aqui na empresa, ficava pensando, pensando, tentando descobrir o algoritmo que minizava o número de tentativas pra descobrir a partir de qual andar a garrafa ou os óculos de nerd do El Pátrio se quebraria.

Era engraçado quando o pessoal passava por mim e me vendo tão concentrado e sério, perguntava se eu tava com algum problema muito sério pra resolver.




Se o meu raciocínio estiver correto, 9 é o menor número de tentativas que se tem que jogar as garrafas para descobrir o andar da quebra.

Nome aos bois: G1 (primeira garrafa) e G2 (segunda garrafa); 44 andares (A1,A2,...A44).

Primeira tentativa (P1):jogar G1 de A9 (intervalo de 9 andares).
Se G1 quebrar e o ponto de quebra for A9 – pior hipótese – joga-se G2 de A2, de A3 ...até A9 perfazendo um total de 9 tentativas.
Se G1 não quebrar, faz-se a Segunda tentativa.

Segunda tentativa (P2): jogar G1 de A17 (intervalo de 8 andares de P1-P2).
Se G1 quebrar e o ponto de quebra for A17 – pior hipótese – joga-se G2 de A10, de A11... até A17 perfazendo um total de nove tentativas (P1 + P2).
Se G1 não quebrar, faz-se Terceira tentativa.

Terceira tentativa (P3): jogar G1 de A24 (intervalo de 7 andares de P2-P3).
Se G1 quebrar e o ponto de quebra for A24 – pior hipótese – joga-se G2 de A18, de A19... até A24 perfazendo um total de nove tentativas (P1 + P2 + P3).
Se G1 não quebrar, faz-se Quarta tentativa... e assim sucessivamente (se não houver quebra diminui-se 1 andar no intervalo em relação a tentativa anterior e faz-se outra tentativa).

Como, num intervalo de 9 andares, precisa-se de 9 tentativas pra se descobrir o ponto de quebra na pior hipótese (nono andar); num intervalo de 8 andares, precisa-se de 8 tentativas pra se descobrir o ponto de quebra na pior hipótese (oitavo andar); num intervalo de 7 andares, precisa-se de 7 tentativas e assim sucessivamente...Se dividirmos os 44 andares em intervalos de 9, 17 (9+8), 24 (9+8+7), 30 (9+8+7+6), 35 (9+8+7+6+5), 39 (9+8+7+6+5+4), 42 (9+8+7+6+5+4+3) e 44 (9+8+7+6+5+4+3+2) com nove tentativas (no máximo) em qualquer hipótese se descobre o ponto de quebra.

É isso.


Bom 2006 a todos !!!

[Tricampeão]

Parabéns pela solução do problema, caro Sonolento. Porra, vocês matam mais rápido do que eu consigo escrever desafios novos. Vão ter que esperar um pouquinho para eu postar o próximo.

[ElPatrio]

... ficava pensando, pensando, tentando descobrir o algoritmo que minizava o número de tentativas pra descobrir a partir de qual andar a garrafa ou os óculos de nerd do El Pátrio se quebraria.

Caro sonolento, sou um nerd sem óculos.

Parabéns por resolver mais essa!!

Logo vou postar um probleminha para vcs se deliciarem aí.

Abraço.

[ElPatrio]

...Se dividirmos os 44 andares em intervalos de 9, 17 (9+8), 24 (9+8+7), 30 (9+8+7+6), 35 (9+8+7+6+5), 39 (9+8+7+6+5+4), 42 (9+8+7+6+5+4+3) e 44 (9+8+7+6+5+4+3+2) com nove tentativas (no máximo) em qualquer hipótese se descobre o ponto de quebra.

O desafio foi resolvido de forma brilhante pelo soneca porém permitam-me um breve comentário. É interessante perceber que a chave da solução deste problema é notar que o número de andares do e-nésimo intervalo mais n - 1 deve ser sempre constante e isso leva a uma progressão aritmética cuja soma total de andares por intervalo é igual a 44.

Daí percebe-se que o número de andares por intervalo deve ser diminuído em uma unidade (razão da p.a.) a cada intervalo sucessivo de baixo para cima, forçando assim a soma constante a qual me referi (ex. n=1 9 andare, n=2 8 andares e 8 + 1 = 9...). Sendo que a quantidade de andares do intervalo que contém o andar 44 é o primeiro termo da p a e a quantidade de andares do intervalo extremo oposto é igual ao último termo da p. a.

Se considerarmos o último intervalo (aquele que contém o andar 44) com um andar apenas teremos a seguinte progressão:

1 + n - 1 = X, ou seja, n = X, sendo que X é a constante que coincide com o número do andar inicial.

Mas a soma dos termos de uma p. a. é dada por:

X(X + 1)/2 = 44 fazendo os cálculos encontramos uma valor de aproximadamente 8,9. Mas minha hipótese inicial de que o último intervalo contém apenas um andar (termo inicial da p. a.) é um "chute". Porém é um chute razoável já que o número de andares é de "apenas" 44 andares. Como o sonolento soneca nos mostrou esse valor é na verdade 2 e não 1 e o número de intervalos n é igual a 7 e não a 9.

[ElPatrio]

TRAGÉDIA: FÓRUM DE GPS VAIDOSAS E SUICÍDAS É INVADIDO POR INIMIGOS:


Em um determinado fórum de putaria as gps são muito vaidosaxxx e não admitem tomar TD NEGATIVO. Se isso acontece imediatamente se suicidam. Essas gps são também lógicas competentes, muito inteligentes, entre um td e outro, elas quebram a cabeça ao resolver os desafios do Tri-Campeão, algumas, mais determinadas, vão atender o cliente com o problema na cabeça atrapalhando assim o atendimento, mas nada que comprometa. Reza a lenda que certa vez uma garota praticava sexo oral se muito entusiasmo quando de repente ela largou o cliente ali e saiu gritando nua pelo saguão do Hotel: EUREKA, EUREKA. Porém nada disso atrapalhava o bom andamento do fórum até que em um dia o fórum sofre um ataque de foristas de outro fórum botando fim a calmaria. Os inimigos, sabedores da vaidade doentia que acomete as gps, tratam logo de postar TDS NEGATIVOS FALSOS, num ato de pura maldade com as pobres garotas. Como as gps não tem acesso aos seus respectivos tópico então a gp não consegue perceber que tomou td negativo, mas pode perfeitamente bisbilhotar tópicos de outras garotas e quando algum td negativo é postado há uma sinalização geral na página principal do fórum indicando que algum td negativo foi postado mas sem apontar quem levou. Fazendo com que as garotas, ao verem tal sinalização, corram logo para vasculhar tópicos de outras garotas torcendo para encontrar algum td negativo. Quando uma garota se suicida seu tópico é apagado. Sabendo-se que no sétimo dia uma garota se suicida, pergunta-se: quantas garotas tomaram TD negativo?

[Tricampeão]

Companheiro ElPatrio, folgo em vê-lo de volta.

Caro sonolento, sou um nerd sem óculos.

Então, o quê que é isso aí brilhando na sua cara? Um sutiã fosforescente?