Problema:Temos 12 moedas das quais uma é falsa.Em tres pesagens saber qual é, e se pesa menos ou se pesa mais.
none
Desafio-os a resolver este problema:(1)
Temos 12 moedas aparentemente iguais,
das quais uma, sendo falsa, tem um peso
diferente das outras (nao se sabe se maior se menor).
Recorrendo a uma balanca de pratos iguais e em
três pesagens apenas, determinar qual a moeda falsa,
e se pesa mais ou pesa menos.
(1) Nota:
Não garanto que isto seja possivel com apenas tres pesagens.
E' precisamente isso que queria confirmar convosco.
Caso de saiba 'a partida se a moeda falsa e' mais pesada
(ou mais leve) a coisa torna-se muito facil e ate' ha' varias
maneiras de chegar la' em apenas tres pesagens.
Carlos J. G. Duarte
epa, eu fiz isto 10 segundos, por isso podes ter as reserevasd
que quiseres, mas acho que com tres e' dificil:
a tecnica e; dividir as moedas em metades iguais:
xxxxxx xxxxxx
sabe-se o grupo de 6 que contem a falsa
xxx xxx
sabe-se o grupo de 3
x1 x2
se x1 == x2, entao x3 e' a falsa, a isso foi conseguido com as tres
pesagens.
se x1 != x2, entao uma delass e' a falsa, mas teria de
ser feita nova pesagem com a x3, para saber
qual a falsa.
...
de notar, que se calhar, podem-se fazer combinacoes de moedas,
de forma a determinar em menos pesagenss qual a falsa.
mas par aisso precisava de mais tempo, e estou com uma certa
pressa :)
carlos
Joe Fagundes
peso e cor diferentes dos outros ( não se sabe se maior se menor, nem qual a
cor)
Recorrendo apenas a um palito e um baralho de cartas em que o ás de espadas
foi substituído por um agrafador, adivinhem lá, sem recorrer a equações
diferenciais, e admitindo que a 2ª guerra mundial foi, sabe-se agora, no
século XVII,e que o 1º nome de Hitler era afinal Heil, qual a massa atómica
do Saramaguium ( novo elemento da tabela periódica)
none wrote in message <3623f360....@193.126.65.39>...
tal...@nao.sei.pt
>Cabecinhas pensadoras
>
>Desafio-os a resolver este problema:(1)
>
>Temos 12 moedas aparentemente iguais,
>das quais uma, sendo falsa, tem um peso
>diferente das outras (nao se sabe se maior se menor).
>
>Recorrendo a uma balanca de pratos iguais e em
>três pesagens apenas, determinar qual a moeda falsa,
>e se pesa mais ou pesa menos.
>
>(1) Nota:
>Não garanto que isto seja possivel com apenas tres pesagens.
>E' precisamente isso que queria confirmar convosco.
>Caso de saiba 'a partida se a moeda falsa e' mais pesada
>(ou mais leve) a coisa torna-se muito facil e ate' ha' varias
>maneiras de chegar la' em apenas tres pesagens.
na minha opinião são precisas 4 pesagens.
6 - 6
3 - 3
2 - 2
1 - 1
none
>na minha opinião são precisas 4 pesagens.
>
>6 - 6
>3 - 3
>2 - 2
>1 - 1
Wrong :-)
Consideremos a seguinte nomenclatura:
Ei()<=>Di() Pesagem i
E() Prato Esquerdo da balanca
D() Prato Direito da balanca
M+ = Moeda falsa mais pesada
M- = Moeda falsa menos pesada
M+/- = Moeda falsa mais ou menos pesada (indeterminacao)
Se a primeira pesagem for como propoes i.e 6-6 sera':
E1(1,2,3,4,5,6) <=> D1(7,8,9,10,11,12)
---------------------------------------------------
E1>D1 M+ em (1,2,3,4,5,6) ou M- em (7,8,9,10,11,12)
E1=D1 Impossivel
E1<D1 M- em (1,2,3,4,5,6) ou M+ em (7,8,9,10,11,12)
i.e., ficamos a saber exactamente o mesmo.
Mas se for:
E1(1,2,3,4) <=> D1(5,6,7,8)
-----------------------------------------
E1>D1 M+ em (1,2,3,4) ou M- em (5,6,7,8)
E1=D1 M+/- em (9,10,11,12)
E1<D1 M- em (1,2,3,4) ou M+ em (5,6,7,8)
Se E1>D1 i.e. M+ em (1,2,3,4) ou M- em (5,6,7,8) vem:
E2(1,2,5,6) <=> D2(9,10,11,12)
------------------------------
E2>D2 M+ em (1,2)
E2=D2 M+ em (3,4) ou M-(7,8)
E2<D2 M- em (5,6)
Se E2=D2 i.e M+ em (3,4) ou M- em (7,8) vem:
E3(3,7) <=> D3(9,10)
--------------------
E3>D3 M+=3
E3=D3 M+=4 ou M-=8
E3<D3 M-=7
A questao surge precisamente quando E3=D3 i.e. M+=4 ou M-=8
Dai' a necessidade da quarta pesagem:
E4(4) <=> D4(9)
---------------
E4>D4 M+=4
E4=D4 M-=8
E4<D4 Impossivel
Pergunta: Nao havera' nenhuma maneira de contornar isto ?
none
Duarte) wrote:
>epa, eu fiz isto 10 segundos, por isso podes ter as reserevas
>
>a tecnica e; dividir as moedas em metades iguais:
>
> xxxxxx xxxxxx
>
>sabe-se o grupo de 6 que contem a falsa
>
> xxx xxx
>
>sabe-se o grupo de 3
>
> x1 x2
>
>se x1 == x2, entao x3 e' a falsa, a isso foi conseguido com as tres
>pesagens.
>
>se x1 != x2, entao uma delass e' a falsa, mas teria de
>ser feita nova pesagem com a x3, para saber
>qual a falsa.
>
>...
>
>de notar, que se calhar, podem-se fazer combinacoes de moedas,
>de forma a determinar em menos pesagenss qual a falsa.
>mas par aisso precisava de mais tempo, e estou com uma certa
>pressa :)
>
>carlos
A coisa e' um "nadinho" mais complicada :-)
Ve o thread.
none
Ei()<=>Di() Pesagem i
E() Prato Esquerdo da balanca
D() Prato Direito da balanca
M+ = Moeda falsa mais pesada
M- = Moeda falsa menos pesada
M+/- = Moeda falsa mais ou menos pesada (indeterminacao)
Se for:
E1(1,2,3,4) <=> D1(5,6,7,8)
-----------------------------------------
E1>D1 M+ em (1,2,3,4) ou M- em (5,6,7,8)
E1=D1 M+/- em (9,10,11,12)
E1<D1 M- em (1,2,3,4) ou M+ em (5,6,7,8)
Se E1>D1 i.e. M+ em (1,2,3,4) ou M- em (5,6,7,8) vem:
E2(1,2,5,6) <=> D2(9,10,11,12)
------------------------------
E2>D2 M+ em (1,2)
E2=D2 M+ em (3,4) ou M-(7,8)
E2<D2 M- em (5,6)
Se E2=D2 i.e M+ em (3,4) ou M- em (7,8) vem:
E3(3,7) <=> D3(9,10)
--------------------
E3>D3 M+=3
E3=D3 M+=4 ou M-=8
E3<D3 M-=7
A problema surge precisamente para E3=D3 i.e. M+=4 ou M-=8
que obriga 'a quarta pesagem:
E4(4) <=> D4(9)
---------------
E4>D4 M+=4
E4=D4 M-=8
E4<D4 Impossivel
Pergunta: Nao havera' nenhuma maneira de evitar a quarta pesagem ?
mocho
>>E' precisamente isso que queria confirmar convosco.
>>Caso de saiba 'a partida se a moeda falsa e' mais pesada
>>(ou mais leve) a coisa torna-se muito facil e ate' ha' varias
>>maneiras de chegar la' em apenas tres pesagens.
>
>
>6 - 6
>3 - 3
>2 - 2
>1 - 1
>
voçes são muito complicados.
pensem simples
1- 6- 6 - e determina-se o grupo de seis com peso diferente. Ficam, 6 moedas
2- de seguida faz-se 2-2 e não 3-3 .
se as 2-2 derem pesos diferentes pode-se ignorar as duas moedas que ficaram
de fora e fazer 1-1 com as moedas com peso diferente.
Se as moedas 2-2 forem de igual peso é porque a solução está nas duas moedas
que ficam de fora
de qualquer forma chega-se a uma
3- 1-1
Certo
Luis Miguel Freire
2º pega-se no grupo mais pesado de 6 moedas e coloca-se 3 de cada lado
se a balança ficar equilibrada é porque a moeda falsa é mais leve que as
outras
- partindo do principio que a moeda é mais leve que as outras
3º pega-se no grupo mais leve de 6 moedas e coloca-se 3 de cada lado
4º pega-se no grupo mais leve de 3 moedas e coloca-se 1 de cada lado
-se a balança ficar equilibrada a falsa é a que ficou de fora, senão é a
mais leve
assim fica em quatro passos mas se souber se a moeda falsa é mais leve ou
não que as outras, ou se tiver sorte consegue-se em três passos
by: Luis Miguel Freire
E-Mail: Lu...@ip.pt
------------------------------------------------
Remember: To err is human, but to really screw
things up requires a computer.
------------------------------------------------
none wrote in message <3623f360....@193.126.65.39>...
>Cabecinhas pensadoras
>
>Desafio-os a resolver este problema:(1)
>
>Temos 12 moedas aparentemente iguais,
>das quais uma, sendo falsa, tem um peso
>diferente das outras (nao se sabe se maior se menor).
>
>Recorrendo a uma balanca de pratos iguais e em
>três pesagens apenas, determinar qual a moeda falsa,
>e se pesa mais ou pesa menos.
>
>(1) Nota:
pjnevess
none wrote:
> Cabecinhas pensadoras
>
> Desafio-os a resolver este problema:(1)
>
> Temos 12 moedas aparentemente iguais,
> das quais uma, sendo falsa, tem um peso
> diferente das outras (nao se sabe se maior se menor).
>
> Recorrendo a uma balanca de pratos iguais e em
> três pesagens apenas, determinar qual a moeda falsa,
> e se pesa mais ou pesa menos.
>
> (1) Nota:
> Não garanto que isto seja possivel com apenas tres pesagens.
> E' precisamente isso que queria confirmar convosco.
> Caso de saiba 'a partida se a moeda falsa e' mais pesada
> (ou mais leve) a coisa torna-se muito facil e ate' ha' varias
> maneiras de chegar la' em apenas tres pesagens.
Se disseres o material em que sao feitas, podemos logo dizer se a
falsa e mais pesada ou mais leve.
Senao nem precisas de pesar nada, derretes as moedas uma a uma e vez
aquela que tem o ponto de fusao diferente :-)
Com tres pesagens, sem se saber se a falsa e mais pesada ou leve e
dificil.
Podemos tentar a seguinte forma.
pomos
xxxxx xxxxx e ficam de fora xy
prato equilibrado descartamos as 10 moedas
x y
x x uma das moedas que pusemos de fora logo no inicio
a unica questao e se a falsa esta nas 10 moedas iniciais.
PauloMesquita
>>
>>6 - 6
>>3 - 3
>>2 - 2
>>1 - 1
>>
>
>voçes são muito complicados.
>pensem simples
>
>1- 6- 6 - e determina-se o grupo de seis com peso diferente. Ficam, 6
moedas
>2- de seguida faz-se 2-2 e não 3-3 .
>se as 2-2 derem pesos diferentes pode-se ignorar as duas moedas que ficaram
>de fora e fazer 1-1 com as moedas com peso diferente.
>Se as moedas 2-2 forem de igual peso é porque a solução está nas duas
moedas
>que ficam de fora
>de qualquer forma chega-se a uma
>3- 1-1
>
>Certo
>
>
>
Errado.
Uma das moedas da pesagem 3- 1-1 pesará menos e a outra mais, conclusão não
saberás qual é a moeda pretendida.
Marco António
10s percebi que nao era assim tao simples, pois ja' que
nao sabemos se a falsa pesa mais ou menos, entao ao
pesares 6 contra 6 nao sabes de que lado ela esta'.
Marco António
moedas
Quando pesas 6-6, estas teem OBRIGATORIAMENTE pesos diferentes. Mas
como nao sabes se a moeda falsa pesa mais ou menos nao sabes de que
lado ela esta'.
Marco António
O que tem uma probabilidade de 83,(3)% de acontecer :)
Marco António
Uma das hipoteses para 4 pesagens:
tres grupos de 4 (A4 B4 C4)
A4 vs B4
B4 vs C4
daqui se descobre em que grupo se encontra a falsa
e se e' mais pesada ou mais leve.
Depois divide-se X4 em
D2 vs E2
e entao X2
em
F1 vs G1
(as letras distinguem grupos e o numero a quantidade
de moedas do grupo - o vs (versus) aparece como a
pesagem comparativa)
$abidola
Games Bond
conclui-se que são precisas de 4 pesagens, no mínimo, para determinar a
solução.
Todavia, pretende-se encontrar a solução para este problema.
Um comboio Alfa Porto-Lisboa, circula a 200 Km/h (vel. estabelizada). A
velocidade do vento é 0 Km/h e não está a chover. O tempo está seco. A 1 km
de distância à fente do local onde está o comboio, encontra-se uma simpática
vaca parada no meio da linha.
O máquinista, distraíu-se e não se apercebe do animal em plena via férrea,
e, por isso, não activa o travões mantendo a mesma velocidade.
Quando o comboio atinge em cheio no pobre animal, pretende-se saber qual a
intensidade do susto que atingiu a vaca.
Cumps.
GB
Nuno Miguel Mendes
> Cabecinhas pensadoras
>
> Desafio-os a resolver este problema:(1)
>
> Temos 12 moedas aparentemente iguais,
> das quais uma, sendo falsa, tem um peso
> diferente das outras (nao se sabe se maior se menor).
>
> Recorrendo a uma balanca de pratos iguais e em
> três pesagens apenas, determinar qual a moeda falsa,
> e se pesa mais ou pesa menos.
>
Seja Qtotal a quantidade de informacao pretendida
Q' a quantidade de informacao necessaria para determinar qual eh a
moeda diferente
Q'' a quantidade de informacao necessaria para determinar se a moeda
eh mais leve ou mais pesada
Q'= log 12 = 3.58 bit
Q''= log 2 = 1 bit
Cada pesagem da-nos um 1 de 3 tipos de informacao:
a) Desiquilibrio para a esquerda
b) Desiquilibrio para a direita
c) Equilibrio
Logo, cada pesagem da-nos uma quantidade de informacao maxima de
log 3 = 1.58 bit
Assim o numero minimo de pesagens eh de (3.58 + 1) / 1.58 = 2.90
Temos assim uma aproximacao do numero de pesagens necessario, mas
nao temos a garantia que seja apenas necessarias 3 pesagens, pq nem sempre
aproveitamos toda a informacao fornecida em cada pesagem
Vamos tentar
Sem perda de generalidade suponhamos que a moeda eh mais leve
vamos representa/la por # e as restantes por $
1a pesagem:
$$$$ | $$$$
---- ---- de fora: $$$#
2a pesagem:
As 8 moedas que equilibraram passaram a ser padrao
Pegamos em 3 dessas e comparamos com 3 das que ficaram de
fora
$$$ | $$$
--- --- De fora: #
Ja determinamos a moeda
3a pesagem:
#
$ | -
-
E descobrimos que a moeda eh mais leve
Quem tiver paciencia suficiente poderia verificar que eh sempre
possivel chegar a uma conclusao com apenas 3 pesagens, mas nao ha
nenhum metodo geral para o fazer. Deve tentar-se sempre maximizar
a quantidade de informacao obtida de cada pesagem envolvendo sempre o
numero maximo de moedas e usando a informacao que ja temos acerca delas.
Nuno Mendes
-------------------------------------------------------------------
Never commit yourself! Let someone else commit you.
-------------------------------------------------------------------------
Marco António
> intensidade do susto que atingiu a vaca.
A intensidade do susto nao e' mensuravel e tende para infinito... como se
pode
depreender pelo calculo do limite com a (des)aceleracao a tender para zero.
JCD
12 moedas
A1 A2 A3 A4
B1 B2 B3 B4
C1 C2 C3 C4
Pesa-se grupo A e grupo B
Se A=B, a moeda é do grupo C
Pesa-se A1+A2 vc C1+C2
Se =, falsa é C3 ou C4
Pesa-se A1 com C3
Se = falsa é C3
Se <> falsa é C4
Se <> falsa é C1 ou C2 (Já se sabe se > ou <)
Pesa-se C1 com C2 e já está
Se A>B, a falsa é dos grupos A ou B
Pesa-se A1+A2+A3+B1+B2 vc C1+C2+C3+C4+A4
Se >, falsa é A1, A2 ou A3
Pesa-se A1 vs A2
Se > falsa é A1
Se < falsa é A2
Se = falsa é A3
Se <, falsa é B1,B2 ou A4
Pesa-se B1+A4 vs C1+C2
Se > falsa é A4
Se < falsa é B1
Se = falsa é B2
Se =, falsa é B3 ou B4
Pesa-se B3 vs B4
Se < falsa é B3
Se > falsa é B4
Ufff.
Está certo, ou falhei algum raciocínio?
JCD
JCD
none
<mop8...@Mail.Telepac.pt> wrote:
>Boas
>Na verdade este problemas chama- se "the odd ball problem" e
>feito com bolas de bilhar.
---
Certo.
Neste URL aparece tambem uma referencia ao problema.
http://www.pfccheatsheet.com/puzzle99.htm
Confirmando que esta' correctamente formulado
e que existe efectivamente solucao em tres pesagens.
>Existem pelo menos 42 solucoes nao triviais para o resolver
>em 3 pesagens.
---
Tudo bem.
Mas aonde ?????
>Estas solucoes foram encontradas por um programa de prova automatica
>de problemas chamado OTTER.Podem ver tudo em mcs.anl.gov, ou no artigo
>escrito por Larry Wos.
---
Ok...fartei-me de procurar e apenas encontrei:
http://www-unix.mcs.anl.gov/~wos/
- Puzzles and Their Solutions
- Jobs Puzzle
- Missionaries and Cannibals Puzzle
- Dominoes Puzzle
- Truthtellers Puzzle
- Puzzle of Fifteen
Nada de "the odd ball problem"
Nao podias colocar aqui o URL com a resolucao do problema ??
Desde ja' agradecido.
None
Carlos J. G. Duarte
> Realmente 10s e' pouco tempo mas modestia 'a parte em
> 10s percebi que nao era assim tao simples, pois ja' que
> nao sabemos se a falsa pesa mais ou menos, entao ao
eu sei. vi isso mais tarde. nao em 10s, nem em 20s.
claro que os intelectos superiores conseguem-no em menos tempo.
carlos
Nuno Miguel Mendes
> epa, eu fiz isto 10 segundos, por isso podes ter as reserevasd
> que quiseres, mas acho que com tres e' dificil:
>
> a tecnica e; dividir as moedas em metades iguais:
>
> xxxxxx xxxxxx
>
> sabe-se o grupo de 6 que contem a falsa
Nao, nao sabe!
>
> xxx xxx
>
> sabe-se o grupo de 3
>
> x1 x2
>
> se x1 == x2, entao x3 e' a falsa, a isso foi conseguido com as tres
> pesagens.
>
> se x1 != x2, entao uma delass e' a falsa, mas teria de
> ser feita nova pesagem com a x3, para saber
> qual a falsa.
>
> ...
>
> de notar, que se calhar, podem-se fazer combinacoes de moedas,
> de forma a determinar em menos pesagenss qual a falsa.
> mas par aisso precisava de mais tempo, e estou com uma certa
> pressa :)
>
> carlos
>
>
Nuno Mendes
-------------------------------------------------------------------
One way to stop a runaway horse is to bet on him.
-------------------------------------------------------------------------
Nuno Miguel Mendes
> Sem recorreres a equações para cálculo e com base apenas na lógica,
> conclui-se que são precisas de 4 pesagens, no mínimo, para determinar a
> solução.
Por acaso gostava que me mostrasses essas equacoes a essa logica...
Carlos J. G. Duarte
> =09Sem perda de generalidade suponhamos que a moeda eh mais leve=20
> =09vamos representa/la por # e as restantes por $
perdes generalidade!
> =091a pesagem:
> =09=09$$$$ | $$$$
> =09=09---- ---- de fora: $$$#
> =092a pesagem:
> =09=09As 8 moedas que equilibraram passaram a ser padrao
> =09=09Pegamos em 3 dessas e comparamos com 3 das que ficaram de
> =09=09fora
> =09=09$$$ | $$$
> =09=09--- --- De fora: #
> =09 Ja determinamos a moeda
> =093a pesagem:
> =09=09 #
> =09=09$ | -
> =09=09-
> =09=09E descobrimos que a moeda eh mais leve
que raio de exemplo.
em primeiro, partes logo do principio que a moeda falsa
e' mais leve, o que nao podes fazer, como e' logico.
neste caso, nao e' importante, porque podes pesar uma
das duas ultimas que restam, com uma das "boas", e tiras
as conclusoes.
seja como for, este exemplo e' puramnte academico e
nao prova nada.
se eu tivesse 99 moedas, tb podia dizer que bastava pesar
dois grupos de 45. equilibravam, a 99a. era a falsa,
alguem com paciencia que verificasse todos os outros casos.
na realidade, ainda nao vi qq prova que 3 pesagens cheguem.
carlos
Carlos J. G. Duarte
: Seja Qtotal a quantidade de informacao pretendida
: Q' a quantidade de informacao necessaria para determinar qual eh a
: moeda diferente
: eh mais leve ou mais pesada
:
: Q'= log 12 = 3.58 bit
: Q''= log 2 = 1 bit
: Cada pesagem da-nos um 1 de 3 tipos de informacao:
: a) Desiquilibrio para a esquerda
: b) Desiquilibrio para a direita
: c) Equilibrio
: Logo, cada pesagem da-nos uma quantidade de informacao maxima de
: log 3 = 1.58 bit
: Assim o numero minimo de pesagens eh de (3.58 + 1) / 1.58 = 2.90
nao percebi muito bem a tua fundamentacao para aplicar a teoria
de informacao neste caso.
alem do mais, nao parece bem parametrizada. por exemplo, se
se introduzisse a restricao, de que so se podiam fazer pesagens
de 6 moedas (3+3), a tua derivacao nao sofria alteracao, dado
que nao entra em conta esse dados.
no entanto, a informacao obtida das pesagens ja' variava
(nao de _uma_ pesagem, mas da sua totalidade).
na realidade, apenas entras em conta com a informacao que
cada pesagem fornece (mas falhas ao considerar as diferentes
combinacoes que podem ser formadas), e com a probabilidade
da moeda ser falsa (1/12). tb quanto a probabilidade de
ser mais leve ou pesada (1/2), nao percebi muito bem o fundamento -- se
a quantidade de informacao para determ a moeda, ja' esta' parametrizada,
nao percebo para que adicionar +.
mas so' para confirmar a invalidade do raciocinio exposto, imagina
que o teu problema era a simples determinacao se a moeda
falsa e' mais leve ou pesada (para qq conjunto com mais de duas moedas).
segunda a tua aplicacao da TI, tens :
q=log2 1/2 = 1bit, quantidade de informacao necessaria
i=log2 1/3 = 1.58, quantidade de informacao fornecida com cada pesagem
1/1.58 = 0.63, i.e. o limite minimo teorico, e' de 1 pesagem, quando
realmente, o limite minimo sao 2 pesagens, tendo que com 1, nunca
se conseguirias determinar se a moeda era mais pesada ou leve.
(porque nao conseguias informacao relacional suficiente para
distinguir +pesado de +leve).
carlos
Carlos J. G. Duarte
: On Mon, 12 Oct 1998 12:18:05 GMT, no_...@hotmail.com (none) wrote:
muito inteligente (a serio), mas acho que mesmo assim, as coisas
na funcionam bem.
depois de 'se a>b, a falsa...', o racicionio em geral
parece nao estar muito correcto (mas nao estou para
pensar muito :)).
agora, onde falha claramente, e' no ponto que indico mais abaixo.
: 12 moedas
: A1 A2 A3 A4
: B1 B2 B3 B4
: C1 C2 C3 C4
: Pesa-se grupo A e grupo B
: Se A=B, a moeda é do grupo C
: Pesa-se A1+A2 vc C1+C2
: Se =, falsa é C3 ou C4
: Pesa-se A1 com C3
: Se = falsa é C3
: Se <> falsa é C4
: Se <> falsa é C1 ou C2 (Já se sabe se > ou <)
: Pesa-se C1 com C2 e já está
: Se A>B, a falsa é dos grupos A ou B
: Pesa-se A1+A2+A3+B1+B2 vc C1+C2+C3+C4+A4
: Se >, falsa é A1, A2 ou A3
: Pesa-se A1 vs A2
: Se > falsa é A1
: Se < falsa é A2
: Se = falsa é A3
: Se <, falsa é B1,B2 ou A4
: Pesa-se B1+A4 vs C1+C2
: Se > falsa é A4
: Se < falsa é B1
: Se = falsa é B2
aqui sabe-se que a moeda falsa esta em A ou em B, mas nao se sabe se
e' mais pesada ou leve.
sabe-se que a>b
sabe-se que A1+A2+A3+B1+B2 = C1+C2+C3+C4+A4
assim, de facto a moeda falsa, esta' nas que ficaram de fora, b3 e b4.
mas nao se sabe ainda se a falsa e' mais leve ou pesada.
dai' uma simples pesagem de b3 vs b4 nao adiantar muito.
: Se =, falsa é B3 ou B4
: Pesa-se B3 vs B4
: Se < falsa é B3
: Se > falsa é B4
agora, uma alternativa, e' pesar uma delas, com uma das que se
sabe serem verdadeiras, e concluir sobre a outra:
Pesa-se B3 vs C1
Se =, B4 e' falsa
Se !=, B3 e' falsa
de qq forma, nao confirmei um a um os casos de cima, mas nao
me pareceram estar muito correctos (de A>B para baixo).
--
Carlos Duarte
cd...@algos.inesc.pt
ftp://algos.inesc.pt/pub/users/cdua
JCD
Carlos J. G. Duarte <l38...@alfa.ist.utl.pt> escreveu no artigo
<701urh$qdb$3...@ci.ist.utl.pt>...
> JCD <j...@ip.pt> wrote:
> : On Mon, 12 Oct 1998 12:18:05 GMT, no_...@hotmail.com (none) wrote:
>
> sabe-se que a>b
> sabe-se que A1+A2+A3+B1+B2 = C1+C2+C3+C4+A4
> assim, de facto a moeda falsa, esta' nas que ficaram de fora, b3 e b4.
> mas nao se sabe ainda se a falsa e' mais leve ou pesada.
> dai' uma simples pesagem de b3 vs b4 nao adiantar muito.
>
Claro que se sabe.
Se a1+a2+a3+a4 pesa mais que b1+b2+b3+b4
e a moeda falsa é b3 ou b4, só pode ser mais leve...
Acho mesmo que todas as combinações estão certas. Estive a revê-las e não
encontrei nenhuma falha, mas posso estar a sofrer de algum vício de
raciocínio.
JCD
Carlos J. G. Duarte
> Carlos J. G. Duarte <l38...@alfa.ist.utl.pt> escreveu no artigo
> <701urh$qdb$3...@ci.ist.utl.pt>...
> > JCD <j...@ip.pt> wrote:
> > : On Mon, 12 Oct 1998 12:18:05 GMT, no_...@hotmail.com (none) wrote:
> >
> > sabe-se que a>b
> > sabe-se que A1+A2+A3+B1+B2 = C1+C2+C3+C4+A4
> > assim, de facto a moeda falsa, esta' nas que ficaram de fora, b3 e b4.
> > mas nao se sabe ainda se a falsa e' mais leve ou pesada.
> > dai' uma simples pesagem de b3 vs b4 nao adiantar muito.
> >
> Claro que se sabe.
> Se a1+a2+a3+a4 pesa mais que b1+b2+b3+b4
> e a moeda falsa é b3 ou b4, só pode ser mais leve...
claro -- tendo que a1-a4 eram moedas boas, e a>b, logo a falsa
e' mais leve. sabe-se que esta' em b3 ou b4...
muito inteligente mesmo.
de qq forma, o esquema alternativo tb funcionava bem, dado
que usava uma moeda boa como template.
> Acho mesmo que todas as combinações estão certas. Estive a revê-las e não
> encontrei nenhuma falha, mas posso estar a sofrer de algum vício de
> raciocínio.
bom, nao as revi, mas comeco a acreditar :)
para o caso a<b, sera apenas reverter a demonstracao (trocar
os a's por b's).
carlos
JCD
apresentava resposta sobre se a moeda falsa é mais pesada ou mais leve que
as moedas boas.
A solução completa será:
4 Grupos de Moedas
Grupo A (A1, A2, A3 e A4)
Grupo B (B1, B2, B3 e B4)
Grupo C (C1, C2, C3 e C4)
1ª pesagem
==========
Pesar Grupo A, contra Grupo B.
Podem acontecer 2 coisas:
1A - Tem o mesmo peso - Neste caso a moeda falsa pertence ao grupo C, e as
moedas dos grupos A e B são boas.
1B - Tem peso diferente - Vamos admitir que o grupo A pesa mais que o grupo
B. (Se assim não for trocam-se as letras A pelas B e é a mesma coisa).
Neste caso, ou a moeda falsa pertence ao grupo A, e é mais pesada que as
moedas boas, ou a moeda falsa pertence ao grupo B e é mais leve que as
outras.
2ª pesagem
==========
Caso 1A - Sabemos que a moeda pertence ao grupo C.
Pesamos A1+A2+A3 contra C1+C2+C3
Podem acontecer 3 coisas
A1+A2+A3 > C1+C2+C3 - Neste caso, a moeda falsa é C1, C2 ou C3 e pesa menos
que uma moeda boa.
==> A 3ª pesagem será C1 contra C2.
Se C1 < C2, a moeda falsa é C1 e pesa menos que uma normal
Se C1 > C2, a moeda falsa é C2 e pesa menos que uma normal
Se C1 = C2, a moeda falsa é C3 e pesa menos que uma normal
A1+A2+A3 = C1+C2+C3 - Neste caso a moeda falsa é C4
==> A 3ª pesagem será A1 (ou outra qualquer) contra C4
A1 nunca poderá pesar o mesmo que C4.
Se A1 > C4, a moeda falsa é C4 e pesa menos que uma normal
Se A1 < C4, a moeda falsa é C4 e pesa mais que uma normal
A1+A2+A3 < C1+C2+C3 - Neste caso, a moeda falsa é C1, C2 ou C3 e pesa mais
que uma moeda boa.
==> A 3ª pesagem será C1 contra C2.
Se C1 > C2, a moeda falsa é C1 e pesa mais que uma normal
Se C1 < C2, a moeda falsa é C2 e pesa mais que uma normal
Se C1 = C2, a moeda falsa é C3 e pesa mais que uma normal
Caso 1B - Sabemos que a moeda pertence ao grupo A se for mais pesada que
uma normal, ou pertence ao grupo B se for mais leve que uma normal.
Pesamos A1+A2+A3+B1+B2 contra A4+C1+C2+C3+C4.
De fora ficam apenas B3 e B4.
Mais uma vez podem acontecer 3 coisas
a) A1+A2+A3+B1+B2 pesa o mesmo que A4+C1+C2+C3+C4
Neste caso, a moeda falsa só pode B3 ou B4. Como já sabemos que a moeda
falsa pertence ao grupo B, ela é mais leve que uma moeda normal.
==> A 3ª pesagem seria simplesmente B3 contra B4
Se B3 < B4, a moeda falsa é B3 e pesa menos que uma normal
Se B3 > B4, a moeda falsa é B4 e pesa menos que uma normal
b) A1+A2+A3+B1+B2 pesa mais que A4+C1+C2+C3+C4
Neste caso a moeda falsa é A1, A2 ou A3. Não há nenhuma moeda com hipótese
de ser mais leve no outro prato da balança, e no primeiro prato, as moedas
B1 e B2 não podem ser mais pesadas que as outras.
==> A 3ª pesagem seria A1 contra A2
Se A1 < A2, a moeda falsa é A2 e pesa mais que uma normal
Se A1 > A2, a moeda falsa é A1 e pesa mais que uma normal
Se A1 = A2, a moeda falsa é A3 e pesa mais que uma normal
C) A1+A2+A3+B1+B2 pesa mais que A4+C1+C2+C3+C4
Neste caso a moeda falsa pode ser B1,B2 ou A4. O primeiro prato está mais
leve que o segundo por ter moedas do grupo B, ou porque o segundo prato tem
moedas do grupo A.
==> A 3ª pesagem seria A4+B1 contra C1+C2
Se A4+B1>C1+C2, a moeda falsa seria A4 e pesa mais que o normal.
Se A4+B1<C1+C2, a moeda falsa seria B1 e pesa menos que o normal.
Se A4+B1=C1+C2, a moeda falsa seria B2 e pesa menos que o normal.
=============
Assim todas as hipótese estão mais claras.
JCD
Nuno Miguel Mendes
> Nuno Miguel Mendes (nn...@camoes.rnl.ist.utl.pt) wrote:
>
> > =09Sem perda de generalidade suponhamos que a moeda eh mais leve=20
> > =09vamos representa/la por # e as restantes por $
>
> perdes generalidade!
este exemplo nao era uma prova.
A unica coisa que queria demosntrar era que havia pelo menos uma hipotese
em
que as 3 pesagens funcionavam, alias como demonstrava a prova geral feita
antes do exemplo com coinceitos de teoria da informacao.
Alias, os estudos feitos sobre este problema sobejamente conhecido
demonstram que ha 42conformacoes inicias que permitem a resolucao com
apenas 3 pesagens.
Nas restantes conformacoes nao eh possivel obter o informacao suficiente
por pesagem para some 2,90 em 3 peagens.
Nuno Mendes
-------------------------------------------------------------------
How wonderful opera would be if there were no singers.
-------------------------------------------------------------------------
Nuno Miguel Mendes
> na realidade, ainda nao vi qq prova que 3 pesagens cheguem.
>
Nao ha nenhuma prova geral para este problema. Ha uma minimizacao das
pesagens e ha tb a garatia de que nao sao necessarias mais de 4.
O resto da analise eh estatistica.
Nuno Mendes
-------------------------------------------------------------------
"It's hard to believe that something which is neither seen nor felt can
do so much harm."
"That's true. But an idea can't be seen or felt. And that's what kept
the Troglytes in the mines all these centuries. A mistaken idea."
-- Vanna and Kirk, "The Cloud Minders", stardate 5819.0
-------------------------------------------------------------------------
Nuno Miguel Mendes
> Nuno Miguel Mendes <nn...@camoes.rnl.ist.utl.pt> wrote:
> : Seja Qtotal a quantidade de informacao pretendida
> : Q' a quantidade de informacao necessaria para determinar qual eh a
> : moeda diferente
> : Q'' a quantidade de informacao necessaria para determinar se a moeda
> : eh mais leve ou mais pesada
> :
> : Q'= log 12 = 3.58 bit
> : Q''= log 2 = 1 bit
>
> : Cada pesagem da-nos um 1 de 3 tipos de informacao:
>
> : a) Desiquilibrio para a esquerda
> : b) Desiquilibrio para a direita
> : c) Equilibrio
>
> : Logo, cada pesagem da-nos uma quantidade de informacao maxima de
> : log 3 = 1.58 bit
>
> : Assim o numero minimo de pesagens eh de (3.58 + 1) / 1.58 = 2.90
>
> nao percebi muito bem a tua fundamentacao para aplicar a teoria
> de informacao neste caso.
>
O q?? Trata-se de lidar com probabilidades de acontecimentos - a teroia da
informacao eh sempre aplicavel.
> alem do mais, nao parece bem parametrizada. por exemplo, se
> se introduzisse a restricao, de que so se podiam fazer pesagens
> de 6 moedas (3+3), a tua derivacao nao sofria alteracao, dado
> que nao entra em conta esse dados.
Se introduzisses essa restricao diminuias a entropia do sistema e obtias
menos informacao do que o normal.
O valor que eu dei para a informacao obtida em cada pesagem eh um
majorante, pq geralmente nao se obtem essa quantidade de informacao.
> na realidade, apenas entras em conta com a informacao que
> cada pesagem fornece (mas falhas ao considerar as diferentes
> combinacoes que podem ser formadas), e com a probabilidade
> da moeda ser falsa (1/12). tb quanto a probabilidade de
> ser mais leve ou pesada (1/2), nao percebi muito bem o fundamento -- se
> a quantidade de informacao para determ a moeda, ja' esta' parametrizada,
> nao percebo para que adicionar +.
Pq sao duas coisas que queres saber: qual a moeda e se eh mais pesada ou
mais leve.
> mas so' para confirmar a invalidade do raciocinio exposto, imagina
> que o teu problema era a simples determinacao se a moeda
> falsa e' mais leve ou pesada (para qq conjunto com mais de duas moedas).
> segunda a tua aplicacao da TI, tens :
> q=log2 1/2 = 1bit, quantidade de informacao necessaria
> i=log2 1/3 = 1.58, quantidade de informacao fornecida com cada pesagem
>
esse i eh uma quantidade maxima que nao eh aplicavel neste caso.
Por exemplo, se a pesagem que fizesses consistisse em dividir as moedas em
dois grupos iguais e por cada gruponum prato diferente a quantidade de
informacao obtida era 0!
E devo acrescentar que este exemplo vem na maior parte dos livros sobre
teoria de informacao e exposto exactamente como o fiz.
So que eh preciso compreender melhor os conceitos da teoria antes de ser
possivel compreender o verdadeiro significado das suas provas.
O que eh importante reteer eh que muitas vezes so obtemos minorantes ou
majorantes para as quantidades de informacao obteniveis.
O facto dos acontecimentos serem discretos impede que os resultados
teoricos sejam infaliveis, isto eh, as vezes um resultado que
aparentemente parece sustentar uma tese apresenta apenas uma situcao
optima que nao eh possivel atingir.
Nuno Mendes
-------------------------------------------------------------------
Loose bits sink chips.
-------------------------------------------------------------------------
Carlos J. G. Duarte
> Se introduzisses essa restricao diminuias a entropia do sistema e obtias
> menos informacao do que o normal.
sim, a entropia era diminuida. mas chegas a essa conclusao,
apenas de um ponto de vista pratico.
seguindo a tua derivacao, a entropia do sistema ficaria igual, dado que
as combinacoes nao tinham sido tomadas em conta.
> O valor que eu dei para a informacao obtida em cada pesagem eh um
> majorante, pq geralmente nao se obtem essa quantidade de informacao.
eu sei que era um majorante. no entanto, eu nao vejo
bem as coisas como tu as ves -- i.e. eu nao considero
que os valores apontados sejam referentes as' melhores
combinacoes teoricas de pesagens, mas sim como (estando
a formulacao correcta), a' media de resultados optimos
de todos os eventos possiveis.
grr.. descodificando: experimentas todos os casos possiveis -> N,
para cada caso, associas o numero de pesagens minimo (logo
optimo), para esse evento -> P(i), com i=1..N.
A media dara' os valores que tinhas apontado (cerca de 2.9),
se as contas estiverem correctas.
isto, em oposicao a considerares 2.9 como o numero de pesagens
optimo para _qualquer_ evento.
percebeste a diff?
> Pq sao duas coisas que queres saber: qual a moeda e se eh mais pesada ou
> mais leve.
hm.. nao tinha percebido isso. penso que a ideia era determinar
apenas qual a moeda falsa.
repara que podiamos adcionar uma restricao, em que a balanca
apenas fornecia dois resultados: pesa igual, ou pesa diferente.
nesse caso, ficavas, seguindo o teu modelo,
com a tal media de pesagens optimas: -log2 1/12 / -log2 1/2 ~= 3.58
hmm... talvez: faz algum sentido.
o jcd apresentou uma esquema de resolucao que
aparentemente esta correcto:
|Se A=B, a moeda i do grupo C
| Pesa-se A1+A2 vc C1+C2
| Se =, falsa i C3 ou C4
| Pesa-se A1 com C3
| Se = falsa i C3
| Se <> falsa i C4
| Se <> falsa i C1 ou C2 (Ja se sabe se > ou <)
| Pesa-se C1 com C2 e ja esta
|Se A>B, a falsa i dos grupos A ou B
| Pesa-se A1+A2+A3+B1+B2 vc C1+C2+C3+C4+A4
| Se >, falsa i A1, A2 ou A3
| Pesa-se A1 vs A2
| Se > falsa i A1
| Se < falsa i A2
| Se = falsa i A3
| Se <, falsa i B1,B2 ou A4
| Pesa-se B1+A4 vs C1+C2
| Se > falsa i A4
| Se < falsa i B1
| Se = falsa i B2
| Se =, falsa i B3 ou B4
| Pesa-se B3 vs B4
| Se < falsa i B3
| Se > falsa i B4
|
neste caso, estao discretizados (confirma as contas depois,
se preferires), 11 eventos finais.
todos os restantes, serao reduntantes (argh: linearmente
dependentes!), logo, nao afectam as contas.
o numero de pesagens feitas, por ordem de evento, e':
3+3+2+3+3+3+3+3+3+3+3
isto da' 32/11 ~= 2.9;
assim, talvez a tua formulacao nao esteja assim tao mal :)
e as tres pesagens sejam mesmo possiveis para determinar
todos os casos, coma excepcao de alguns, que podem
la' ir com apenas duas.
assim, das conclusoes tiradas ao longo deste thread, pode-se
resumir a coisa no seguinte:
. a media de pesagens optimas para todos os eventos possiveis, e' de 2.9
. no melhor dos casos, um dado evento resolve-se em 2 pesagens
. no pior dos casos, um dado evento resolve-se em 3 pesagens.
das tres anteriores, conclui-se que qq que seja
o esquema desenvolvido, a proporcao entre eventos
que se resolvem em 3, e eventos que se resolvem
em 2, deve ser aprox de 10:1 (i.e. em cada 11 eventos,
10 resolvem-se em 3 pesagens, e 1 em 2).
carlos
null
[...]
Bravo "JCD" pela resolucao do problema.
Parabens tambem ao Nuno Miguel Mendes <nn...@camoes.rnl.ist.utl.pt>
pela abordagem teorica.(...e porque nao log2(24/3)=3 ?)
Tambem gostei da argumentacao do l38...@alfa.ist.utl.pt (Carlos J. G. Duarte)
Tudo isto so' vem provar que, ao contrario do que por vezes somos levados
a pensar, ainda ha' por ai' muitas meninges irrequietas...
Bom, para quem quiser, aqui vai a minha contribuicao:
Codigo Excel Basic c/ demo da resolucao.(geracao aleatoria de casos)
--------------------------------------------------------------------
Abrir um workbook fazer Insert/Macro/Module e copiar esta tralha toda
la' para dentro. Depois abrir Tools/Macro, seleccionar a subrotina
Main abrir Options e activar uma "Shortcut Key" p.ex "n".
Para correr basta fazer <Ctrl+n>.
Se quiserem o *.xls podem fazer o download no pt.binarios.
Divirtam-se.
'--- copy a partir daqui
Dim ball(1 To 12) As Single
Dim RefWeight, Odddiff, OddWeight As Single
Dim Oddno As Single
Sub Main()
Worksheets(1).Activate
Worksheets(1).Range("A1:z100").Clear
refrow = 1
refcol = 1
Worksheets(1).Cells(refrow, refcol).Value = "The Odd Ball Problem Solution Demo"
Worksheets(1).Cells(refrow, refcol + 1).Value = "Press <Ctrl+n>"
Worksheets(1).Cells(refrow + 1, refcol).Value = "(c) None 17-Oct-1998"
NewSample
Worksheets(1).Cells(refrow + 3, refcol).Value = "Ref_weight"
Worksheets(1).Cells(refrow + 3, refcol + 1).Value = RefWeight
Worksheets(1).Cells(refrow + 4, refcol).Value = "Odd_ball"
Worksheets(1).Cells(refrow + 4, refcol + 1).Value = Oddno
Worksheets(1).Cells(refrow + 5, refcol).Value = "Weight_diff"
Worksheets(1).Cells(refrow + 5, refcol + 1).Value = Odddiff
Worksheets(1).Cells(refrow + 7, refcol).Value = "Ball Id"
Worksheets(1).Cells(refrow + 7, refcol + 1).Value = "Ball Weight"
For i = 1 To 12
Worksheets(1).Cells(refrow + 7 + i, refcol).Value = i
Worksheets(1).Cells(refrow + 7 + i, refcol + 1).Value = ball(i)
Next
OddBall
End Sub
Sub NewSample()
RefWeight = 1
Oddno = Int((12 * Rnd) + 1)
Odddiff = RefWeight * Rnd * (-1) ^ (Int(2 * Rnd + 1))
OddWeight = RefWeight + Odddiff
For i = 1 To 12
ball(i) = RefWeight
Next
ball(Oddno) = OddWeight
End Sub
Sub OddBall()
'First Weighing
'--------------
refrow = 22
refcol = 1
Worksheets(1).Cells(refrow, refcol).Value = "Weighing nº1"
Worksheets(1).Cells(refrow + 1, refcol).Value = "Result"
P1L = "L1(1,2,3,4)"
P1R = "R1(5,6,7,8)"
P11 = "L=R => +/-Odd(9,10,11,12)"
P12 = "L>R => +Odd(1,2,3,4) OR -Odd(5,6,7,8)"
P13 = "L<R => -Odd(1 2 3 4) OR +Odd(5,6,7,8)"
L1 = ball(1) + ball(2) + ball(3) + ball(4)
R1 = ball(5) + ball(6) + ball(7) + ball(8)
P1 = ""
If L1 = R1 Then
P1 = P11
ElseIf L1 > R1 Then
P1 = P12
Else
P1 = P13
End If
Worksheets(1).Cells(refrow, refcol + 1).Value = P1L
Worksheets(1).Cells(refrow, refcol + 2).Value = P1R
Worksheets(1).Cells(refrow + 1, refcol + 1).Value = L1
Worksheets(1).Cells(refrow + 1, refcol + 2).Value = R1
Worksheets(1).Cells(refrow + 1, refcol + 3).Value = P1
'Second Weighing
'--------------
refrow = 25
refcol = 1
Worksheets(1).Cells(refrow, refcol).Value = "Weighing nº2"
Worksheets(1).Cells(refrow + 1, refcol).Value = "Result"
If P1 = P11 Then '"L=R => +/-Odd(9,10,11,12)"
P2L = "L2(9,10,11)"
P2R = "R2(1,2,3)"
P21 = "L=R => +/-Odd=(12)"
P22 = "L>R => +Odd(9,10,11)"
P23 = "L<R => -Odd(9,10,11)"
L2 = ball(9) + ball(10) + ball(11)
R2 = ball(1) + ball(2) + ball(3)
P2 = ""
If L2 = R2 Then
P2 = P21
ElseIf L2 > R2 Then
P2 = P22
Else
P2 = P23
End If
Worksheets(1).Cells(refrow, refcol + 1).Value = P2L
Worksheets(1).Cells(refrow, refcol + 2).Value = P2R
Worksheets(1).Cells(refrow + 1, refcol + 1).Value = L2
Worksheets(1).Cells(refrow + 1, refcol + 2).Value = R2
Worksheets(1).Cells(refrow + 1, refcol + 3).Value = P2
ElseIf P1 = P12 Then '"L>R => +Odd(1,2,3,4) OR -Odd(5,6,7,8)"
P2L = "L2(1,2,3,5,6)"
P2R = "R2(4,9,10,11,12)"
P21 = "L=R => -Odd=(7,8)"
P22 = "L>R => +Odd(1,2,3)"
P23 = "L<R => -Odd(5,6) OR +Odd(4)"
L2 = ball(1) + ball(2) + ball(3) + ball(5) + ball(6)
R2 = ball(4) + ball(9) + ball(10) + ball(11) + ball(12)
P2 = ""
If L2 = R2 Then
P2 = P21
ElseIf L2 > R2 Then
P2 = P22
Else
P2 = P23
End If
Worksheets(1).Cells(refrow, refcol + 1).Value = P2L
Worksheets(1).Cells(refrow, refcol + 2).Value = P2R
Worksheets(1).Cells(refrow + 1, refcol + 1).Value = L2
Worksheets(1).Cells(refrow + 1, refcol + 2).Value = R2
Worksheets(1).Cells(refrow + 1, refcol + 3).Value = P2
Else '"P1 = P13 L<R => -Odd(1,2,3,4) OR +Odd(5,6,7,8)"
P2L = "L2(1,2,5,6,7)"
P2R = "R2(8,9,10,11,12)"
P21 = "L=R => -Odd=(3,4)"
P22 = "L>R => +Odd(5,6,7)"
P23 = "L<R => -Odd(1,2) OR +Odd(8)"
L2 = ball(1) + ball(2) + ball(5) + ball(6) + ball(7)
R2 = ball(8) + ball(9) + ball(10) + ball(11) + ball(12)
P2 = ""
If L2 = R2 Then
P2 = P21
ElseIf L2 > R2 Then
P2 = P22
Else
P2 = P23
End If
Worksheets(1).Cells(refrow, refcol + 1).Value = P2L
Worksheets(1).Cells(refrow, refcol + 2).Value = P2R
Worksheets(1).Cells(refrow + 1, refcol + 1).Value = L2
Worksheets(1).Cells(refrow + 1, refcol + 2).Value = R2
Worksheets(1).Cells(refrow + 1, refcol + 3).Value = P2
End If
'Third Weighing
'--------------
refrow = 28
refcol = 1
Worksheets(1).Cells(refrow, refcol).Value = "Weighing nº3"
Worksheets(1).Cells(refrow + 1, refcol).Value = "Solution"
'"L1(1,2,3,4) R1(5,6,7,8)"
If P1 = P11 Then '"L=R => +-Odd(9,10,11,12)"
'"L2(9,10,11) R2(1,2,3)"
If P2 = P21 Then '"L=R => +/-Odd=(12)"
P3L = "L3(1)"
P3R = "R3(12)"
P31 = "L=R => Never"
P32 = "L>R => -Odd(12)"
P33 = "L<R => +Odd(12)"
L3 = ball(1)
R3 = ball(12)
If L3 = R3 Then
P3 = P31
ElseIf L3 > R3 Then
P3 = P32
Else
P3 = P33
End If
Worksheets(1).Cells(refrow, refcol + 1).Value = P3L
Worksheets(1).Cells(refrow, refcol + 2).Value = P3R
Worksheets(1).Cells(refrow + 1, refcol + 1).Value = L3
Worksheets(1).Cells(refrow + 1, refcol + 2).Value = R3
Worksheets(1).Cells(refrow + 1, refcol + 3).Value = P3
ElseIf P2 = P22 Then '"L>R => +Odd(9,10,11)"
P3L = "L3(9)"
P3R = "R3(10)"
P31 = "L=R => +Odd(11)"
P32 = "L>R => +Odd(9)"
P33 = "L<R => +Odd(10)"
L3 = ball(9)
R3 = ball(10)
If L3 = R3 Then
P3 = P31
ElseIf L3 > R3 Then
P3 = P32
Else
P3 = P33
End If
Worksheets(1).Cells(refrow, refcol + 1).Value = P3L
Worksheets(1).Cells(refrow, refcol + 2).Value = P3R
Worksheets(1).Cells(refrow + 1, refcol + 1).Value = L3
Worksheets(1).Cells(refrow + 1, refcol + 2).Value = R3
Worksheets(1).Cells(refrow + 1, refcol + 3).Value = P3
Else 'P2 = P23 '"L<R => -Odd(9,10,11)"
P3L = "L3(9)"
P3R = "R3(10)"
P31 = "L=R => -Odd(11)"
P32 = "L>R => -Odd(10)"
P33 = "L<R => -Odd(9)"
L3 = ball(9)
R3 = ball(10)
If L3 = R3 Then
P3 = P31
ElseIf L3 > R3 Then
P3 = P32
Else
P3 = P33
End If
Worksheets(1).Cells(refrow, refcol + 1).Value = P3L
Worksheets(1).Cells(refrow, refcol + 2).Value = P3R
Worksheets(1).Cells(refrow + 1, refcol + 1).Value = L3
Worksheets(1).Cells(refrow + 1, refcol + 2).Value = R3
Worksheets(1).Cells(refrow + 1, refcol + 3).Value = P3
End If
'"L1(1,2,3,4) R1(5,6,7,8)"
ElseIf P1 = P12 Then '"L>R => +Odd(1,2,3,4) OR -Odd(5,6,7,8)"
'"L2(1,2,3,5,6) R2(4,9,10,11,12)"
If P2 = P21 Then '"L=R => -Odd=(7,8)"
P3L = "L3(7)"
P3R = "R3(8)"
P31 = "L=R => Never"
P32 = "L>R => -Odd(8)"
P33 = "L<R => -Odd(7)"
L3 = ball(7)
R3 = ball(8)
If L3 = R3 Then
P3 = P31
ElseIf L3 > R3 Then
P3 = P32
Else
P3 = P33
End If
Worksheets(1).Cells(refrow, refcol + 1).Value = P3L
Worksheets(1).Cells(refrow, refcol + 2).Value = P3R
Worksheets(1).Cells(refrow + 1, refcol + 1).Value = L3
Worksheets(1).Cells(refrow + 1, refcol + 2).Value = R3
Worksheets(1).Cells(refrow + 1, refcol + 3).Value = P3
ElseIf P2 = P22 Then '"L>R => +Odd(1,2,3)"
P3L = "L3(1)"
P3R = "R3(2)"
P31 = "L=R => +Odd(3)"
P32 = "L>R => +Odd(1)"
P33 = "L<R => +Odd(2)"
L3 = ball(1)
R3 = ball(2)
If L3 = R3 Then
P3 = P31
ElseIf L3 > R3 Then
P3 = P32
Else
P3 = P33
End If
Worksheets(1).Cells(refrow, refcol + 1).Value = P3L
Worksheets(1).Cells(refrow, refcol + 2).Value = P3R
Worksheets(1).Cells(refrow + 1, refcol + 1).Value = L3
Worksheets(1).Cells(refrow + 1, refcol + 2).Value = R3
Worksheets(1).Cells(refrow + 1, refcol + 3).Value = P3
Else 'P2 = P23 '"L<R => -Odd(5,6) OR +Odd(4)"
P3L = "L3(5)"
P3R = "R3(6)"
P31 = "L=R => +Odd(4)"
P32 = "L>R => -Odd(6)"
P33 = "L<R => -Odd(5)"
L3 = ball(5)
R3 = ball(2)
If L3 = R3 Then
P3 = P31
ElseIf L3 > R3 Then
P3 = P32
Else
P3 = P33
End If
Worksheets(1).Cells(refrow, refcol + 1).Value = P3L
Worksheets(1).Cells(refrow, refcol + 2).Value = P3R
Worksheets(1).Cells(refrow + 1, refcol + 1).Value = L3
Worksheets(1).Cells(refrow + 1, refcol + 2).Value = R3
Worksheets(1).Cells(refrow + 1, refcol + 3).Value = P3
End If
'"L1(1,2,3,4) R1(5,6,7,8)"
Else 'P1 = P13 '"L<R => -Odd(1 2 3 4) OR +Odd(5,6,7,8)
'"L2(1,2,5,6,7) R2(8,9,10,11,12)"
If P2 = P21 Then '"L=R => -Odd=(3,4)"
P3L = "L3(3)"
P3R = "R3(4)"
P31 = "L=R => Never"
P32 = "L>R => -Odd(4)"
P33 = "L<R => -Odd(3)"
L3 = ball(3)
R3 = ball(4)
If L3 = R3 Then
P3 = P31
ElseIf L3 > R3 Then
P3 = P32
Else
P3 = P33
End If
Worksheets(1).Cells(refrow, refcol + 1).Value = P3L
Worksheets(1).Cells(refrow, refcol + 2).Value = P3R
Worksheets(1).Cells(refrow + 1, refcol + 1).Value = L3
Worksheets(1).Cells(refrow + 1, refcol + 2).Value = R3
Worksheets(1).Cells(refrow + 1, refcol + 3).Value = P3
ElseIf P2 = P22 Then '"L>R => +Odd(5,6,7)"
P3L = "L3(5)"
P3R = "R3(6)"
P31 = "L=R => +Odd(7)"
P32 = "L>R => -Odd(5)"
P33 = "L<R => -Odd(6)"
L3 = ball(5)
R3 = ball(6)
If L3 = R3 Then
P3 = P31
ElseIf L3 > R3 Then
P3 = P32
Else
P3 = P33
End If
Worksheets(1).Cells(refrow, refcol + 1).Value = P3L
Worksheets(1).Cells(refrow, refcol + 2).Value = P3R
Worksheets(1).Cells(refrow + 1, refcol + 1).Value = L3
Worksheets(1).Cells(refrow + 1, refcol + 2).Value = R3
Worksheets(1).Cells(refrow + 1, refcol + 3).Value = P3
Else 'P2 = P23 '"L<R => -Odd(1,2) OR +Odd(8)"
P3L = "L3(1)"
P3R = "R3(2)"
P31 = "L=R => +Odd(8)"
P32 = "L>R => -Odd(2)"
P33 = "L<R => -Odd(1)"
L3 = ball(1)
R3 = ball(2)
If L3 = R3 Then
P3 = P31
ElseIf L3 > R3 Then
P3 = P32
Else
P3 = P33
End If
Worksheets(1).Cells(refrow, refcol + 1).Value = P3L
Worksheets(1).Cells(refrow, refcol + 2).Value = P3R
Worksheets(1).Cells(refrow + 1, refcol + 1).Value = L3
Worksheets(1).Cells(refrow + 1, refcol + 2).Value = R3
Worksheets(1).Cells(refrow + 1, refcol + 3).Value = P3
End If
End If
End Sub
'---- copy ate' aqui
Speedy Gonzalez
>Cabecinhas pensadoras
>
>Desafio-os a resolver este problema:(1)
>
>Temos 12 moedas aparentemente iguais,
>das quais uma, sendo falsa, tem um peso
>diferente das outras (nao se sabe se maior se menor).
>
>Recorrendo a uma balanca de pratos iguais e em
>três pesagens apenas, determinar qual a moeda falsa,
>e se pesa mais ou pesa menos.
>
>(1) Nota:
>Não garanto que isto seja possivel com apenas tres pesagens.
>E' precisamente isso que queria confirmar convosco.
>Caso de saiba 'a partida se a moeda falsa e' mais pesada
>(ou mais leve) a coisa torna-se muito facil e ate' ha' varias
>maneiras de chegar la' em apenas tres pesagens.
É possível sim !
E nem preciso explicar, uma vez que só querias saber se era possível
:)
Speedy
------------
Bruno Trindade
>
> A1 A2 A3 A4
> B1 B2 B3 B4
> C1 C2 C3 C4
>
> Pesa-se grupo A e grupo B
>
> Pesa-se A1+A2 vc C1+C2
> Se =, falsa é C3 ou C4
> Pesa-se A1 com C3
> Se = falsa é C3
> Se <> falsa é C4
Sim, mas ficas sem saber se é maior ou menor, o que faz parte dos
requesitos