Coleção de cartas

Problemas onde não se procura um resultado exacto mas uma estimativa razoável baseada em ordens de grandeza...

Re: Coleção de cartas

Mensagempor manuelbrandao99 em Sábado Jan 03, 2015 12:36 am

gonced8 Escreveu:Penso que talvez tenha chegado à solução:
A probabilidade de a 1ª carta ser nova é de 1.
A probabilidade de comprar a 2ª carta nova é de 49/50, ou, por outras "palavras", (50-1)/50.
A probabilidade de comprar a 3ª carta nova é de 48/50, (50-2)/50.
Ou seja, a probabilidade de comprar a xª carta nova é de (50-(x-1))/50.
Eu ainda não sabia isto, mas depois de alguma pesquisa, aprendi que a probabilidade de comprar uma carta nova pode ser descrita por uma distribuição geométrica, pois há reposição e a probabilidade vai variando (acho que estou a dizer isto bem).
Ora numa distribuição geométrica, o valor médio ou valor esperado é dado por E(X)=1/P.
Neste caso, este cálculo dar-nos ia quantas cartas teríamos de comprar para obter 1 carta nova, por isso, temos que fazer o cálculo correspondente a cada uma das 50 cartas e depois somar todos. Teríamos:
E(x)=\frac{1}{P} =\frac{1}{\frac{50-(x-1))}{50}}=\frac{50}{51-x}
Em que x representa uma carta nova (quando x=1 representa a 1ª carta nova, x=2 a 2ª carta nova...)
O total de cartas necessárias comprar é dado pela soma dos valores de E(x) , x={1,2,3,...,50}:
E(1)+E(2)+...+E(50)=
=\frac{50}{51-1}+\frac{50}{51-2}+...+\frac{50}{51-50}
=50\times \left (\frac{1}{51-1}+\frac{1}{51-2}+...+\frac{1}{51-50}\right )
=50\times \left (\frac{1}{50}+\frac{1}{49}+...+\frac{1}{1}\right )
=50\times \left (\sum_{i=1}^{50}\frac{1}{i}\right )
=224.96\approx 225
Por isso, se o raciocínio e os cálculos estiverem bem, seria preciso comprar aproximadamente 225 cartas para que se completasse a coleção.


Espero que esteja correto porque eu tinha acabado de chegar a essa conclusão mas faltava-me calcular o somatório de 1/50 a 1/1 e estava a ver se descobria uma fórmula.
Quando vi o teu post em que dizias que seria 1 + 2 + ... + 50 achei que a única coisa que não fazia sentido era ser preciso 2 cartas para obter a 2ª carta nova (e por aí a diante), pois a probabilidade de a obter está longe de ser 1/2 e por isso cheguei a esta tua resposta também.
manuelbrandao99
gluão
gluão
 
Mensagens: 27
Registado: Segunda Jan 14, 2013 12:04 pm

Re: Coleção de cartas

Mensagempor davidpereira em Sábado Jan 03, 2015 11:53 am

Eu cheguei a esse resultado (225) pensando na definição clássica de probabilidade: nºcasos favoráveis/nº casos possíveis. Queremos que os casos favoráveis sejam 1(porque queremos uma carta não repetida) e assim calcula-se o nº de casos possíveis (cartas que supostamente é preciso comprar). Daí dar E(x) = 1/P (acho eu). Somando dá cerca de 225.

Estou confiante neste resultado porque eu pedi ao meu computador que me repetisse a experiência 1 milhão de vezes e calculasse a média dos resultados. Fiz este procedimento umas 4 vezes e o resultado ficou sempre compreendido entre 224,9 e 225,1.
David J. S. Pereira
Avatar do utilizador
davidpereira
gluão
gluão
 
Mensagens: 8
Registado: Sexta Dez 26, 2014 1:53 pm

Re: Coleção de cartas

Mensagempor manuelbrandao99 em Sábado Jan 03, 2015 11:58 am

davidpereira Escreveu:Eu cheguei a esse resultado (225) pensando na definição clássica de probabilidade: nºcasos favoráveis/nº casos possíveis. Queremos que os casos favoráveis sejam 1(porque queremos uma carta não repetida) e assim calcula-se o nº de casos possíveis (cartas que supostamente é preciso comprar). Daí dar E(x) = 1/P (acho eu). Somando dá cerca de 225.

Estou confiante neste resultado porque eu pedi ao meu computador que me repetisse a experiência 1 milhão de vezes e calculasse a média dos resultados. Fiz este procedimento umas 4 vezes e o resultado ficou sempre compreendido entre 224,9 e 225,1.


Gostas de programação? Que linguagem usaste?
manuelbrandao99
gluão
gluão
 
Mensagens: 27
Registado: Segunda Jan 14, 2013 12:04 pm

Re: Coleção de cartas

Mensagempor davidpereira em Sábado Jan 03, 2015 12:21 pm

Sim, gosto de progamação(referi isso na minha apresentação). Para isto usei Python(pensei em programar na máquina de calcular, mas para isto ter valor tinha que fazer um nº de experiências bastante elevado para uma máquina com uns anitos. Mesmo assim o computador demora uma meia hora por milhão[um dual-corezito])
David J. S. Pereira
Avatar do utilizador
davidpereira
gluão
gluão
 
Mensagens: 8
Registado: Sexta Dez 26, 2014 1:53 pm

Re: Coleção de cartas

Mensagempor leandrosilva em Sábado Jan 03, 2015 6:16 pm

gonced8 Escreveu:Penso que talvez tenha chegado à solução:
A probabilidade de a 1ª carta ser nova é de 1.
A probabilidade de comprar a 2ª carta nova é de 49/50, ou, por outras "palavras", (50-1)/50.
A probabilidade de comprar a 3ª carta nova é de 48/50, (50-2)/50.
Ou seja, a probabilidade de comprar a xª carta nova é de (50-(x-1))/50.
Eu ainda não sabia isto, mas depois de alguma pesquisa, aprendi que a probabilidade de comprar uma carta nova pode ser descrita por uma distribuição geométrica, pois há reposição e a probabilidade vai variando (acho que estou a dizer isto bem).
Ora numa distribuição geométrica, o valor médio ou valor esperado é dado por E(X)=1/P.
Neste caso, este cálculo dar-nos ia quantas cartas teríamos de comprar para obter 1 carta nova, por isso, temos que fazer o cálculo correspondente a cada uma das 50 cartas e depois somar todos. Teríamos:
E(x)=\frac{1}{P} =\frac{1}{\frac{50-(x-1))}{50}}=\frac{50}{51-x}
Em que x representa uma carta nova (quando x=1 representa a 1ª carta nova, x=2 a 2ª carta nova...)
O total de cartas necessárias comprar é dado pela soma dos valores de E(x) , x={1,2,3,...,50}:
E(1)+E(2)+...+E(50)=
=\frac{50}{51-1}+\frac{50}{51-2}+...+\frac{50}{51-50}
=50\times \left (\frac{1}{51-1}+\frac{1}{51-2}+...+\frac{1}{51-50}\right )
=50\times \left (\frac{1}{50}+\frac{1}{49}+...+\frac{1}{1}\right )
=50\times \left (\sum_{i=1}^{50}\frac{1}{i}\right )
=224.96\approx 225
Por isso, se o raciocínio e os cálculos estiverem bem, seria preciso comprar aproximadamente 225 cartas para que se completasse a coleção.


Contando que o vendedor não rarefaz a oferta de algumas cartas, o resultado está correto.

Como já disseram, a probabilidade de a primeira carta ser "nova na coleção" é de 50/50, da segunda é 49/50, da terceira 48/50, e assim sucessivamente ...
Para obter uma carta nova na 2ª compra seriam necessárias comprar, em média, 50/49 cartas, na 3ª 50/48...

Como tal, o número de cartas necessárias para completar a coleção será a soma dos 50 termos:
50/50 + 50/49 + 50/48 + ... + 50/3 + 50/2 + 50/1

Ou seja, para um conjunto com N cartas:
(N/N) + (N/N-1) + ... + N/2 + N/1 cartas
Se excluirmos o fator comum N dos numeradores de cada termo será apenas:
N( 1+ 1/2+ 1/3+... 1/N).
A soma dos termos entre parêntesis é a famosa série "harmónica". Quando N se torna grande, adquire um valor aproximado de 0,58 + ln(N).

Assim, quando N se torna "realisticamente grande", o número médio de cartas que seria necessário comprar para completar o conjunto é aproximadamente:
N x [0,58 + ln(N)]
No meu cálculo o resultado foi 224,5, portanto seriam necessárias 225 cartas, a resposta do Gonçalo está correta.
A incerteza do resultado seria de 1,3N, ou seja, 65 cartas.

Aproveitando o problema, deixo mais uma questão enquadrada no problema:
b) Quantas cartas seria possível poupar, em média, caso fosse possível trocar cartas com um amigo de modo a ambos completarem a coleção ?
"Success is going from failure to failure with no loss of enthusiasm" - Winston Churchill
Avatar do utilizador
leandrosilva
bottom-Quark!
bottom-Quark!
 
Mensagens: 33
Registado: Quarta Dez 24, 2014 8:55 pm
Localização: Santa Comba Dão

Re: Coleção de cartas

Mensagempor gonced8 em Sábado Jan 03, 2015 6:27 pm

Como é que chegaste a esse valor para a incerteza?
Gonçalo Raposo
Antigo quarkiano (edições de 2014 e 2015)
-Constants and variables-
Avatar do utilizador
gonced8
bottom-Quark!
bottom-Quark!
 
Mensagens: 99
Registado: Terça Dez 17, 2013 11:06 pm

Re: Coleção de cartas

Mensagempor gonced8 em Sábado Jan 03, 2015 8:24 pm

Estive a pensar na solução deste novo problema e acho que talvez seja apenas necessário adicionar um parâmetro à probabilidade de comprar uma carta nova na coleção.
Nos meus cálculos vou supor que o amigo compra cartas ao mesmo ritmo que o sujeito.
A probabilidade de a 1ª carta ser nova é de 1.
A probabilidade a 2ª carta ser nova é de: P(2)=\frac{49}{50}+\frac{49}{50}\times 2
O pârametro que adicionei suponho que conta com a hipótese do amigo ter uma carta que nós não temos, 49/50, que é a probabilidade de ser nova, multiplicado por 2 que é o nº de cartas do amigo.
Sendo assim, de uma forma geral ficaria: P(n)=\frac{51-n}{50}\times 3
Se fizermos o mesmo que fizemos para o outro problema:
\mu (n)=\frac{50}{153-3n}
1+\mu (2)+\mu(3)+...+\mu(50)=
=1+\sum_{i=2}^{50}\frac{50}{153-3n}
\approx 76
Apenas seria necessário comprar 76 cartas e, por isso, poupava-se 149 cartas.
(Não estou muito confiante desta resolução...)
Gonçalo Raposo
Antigo quarkiano (edições de 2014 e 2015)
-Constants and variables-
Avatar do utilizador
gonced8
bottom-Quark!
bottom-Quark!
 
Mensagens: 99
Registado: Terça Dez 17, 2013 11:06 pm

Re: Coleção de cartas

Mensagempor leandrosilva em Sábado Jan 03, 2015 10:05 pm

gonced8 Escreveu:Estive a pensar na solução deste novo problema e acho que talvez seja apenas necessário adicionar um parâmetro à probabilidade de comprar uma carta nova na coleção.
Nos meus cálculos vou supor que o amigo compra cartas ao mesmo ritmo que o sujeito.
A probabilidade de a 1ª carta ser nova é de 1.
A probabilidade a 2ª carta ser nova é de: P(2)=\frac{49}{50}+\frac{49}{50}\times 2
O pârametro que adicionei suponho que conta com a hipótese do amigo ter uma carta que nós não temos, 49/50, que é a probabilidade de ser nova, multiplicado por 2 que é o nº de cartas do amigo.
Sendo assim, de uma forma geral ficaria: P(n)=\frac{51-n}{50}\times 3
Se fizermos o mesmo que fizemos para o outro problema:
\mu (n)=\frac{50}{153-3n}
1+\mu (2)+\mu(3)+...+\mu(50)=
=1+\sum_{i=2}^{50}\frac{50}{153-3n}
\approx 76
Apenas seria necessário comprar 76 cartas e, por isso, poupava-se 149 cartas.
(Não estou muito confiante desta resolução...)


Creio que existe um erro algures.
O resultado não é bem esse, mas não anda muito longe.
Se quiseres, pensa como caso geral: "Como seria caso fosse mais do que um amigo? "

Quanto à incerteza, creio que é o cálculo do desvio padrão.
Que seria aproximadamente 1,3N. Significaria que há 66% de probabilidades de precisar de colecionar mais ou menos 1,3N acima da média.
Pois ter deixado isto como questão agora que penso, também daria que pensar, provavelmente, se bem que acho mais simples que estes 2.
"Success is going from failure to failure with no loss of enthusiasm" - Winston Churchill
Avatar do utilizador
leandrosilva
bottom-Quark!
bottom-Quark!
 
Mensagens: 33
Registado: Quarta Dez 24, 2014 8:55 pm
Localização: Santa Comba Dão

Re: Coleção de cartas

Mensagempor gonced8 em Sábado Jan 03, 2015 10:40 pm

De momento, não faço ideia como resolver isto. Se calhar, simplesmente não estou a ver a resolução correta, mas vou esperar que mais alguém tente resolver.
Gonçalo Raposo
Antigo quarkiano (edições de 2014 e 2015)
-Constants and variables-
Avatar do utilizador
gonced8
bottom-Quark!
bottom-Quark!
 
Mensagens: 99
Registado: Terça Dez 17, 2013 11:06 pm

Re: Coleção de cartas

Mensagempor leandrosilva em Sábado Jan 03, 2015 11:34 pm

Aconselho que partas da minha solução para conjuntos maiores e tentes incorporar ai as possíveis trocas.

Recordo que o erro na tua resposta é relativamente pequeno, talvez se deva a alguma aproximação ou formulação mais específica no contexto do problema.
Contudo, o raciocínio na tua resolução é bastante bom, diria.
"Success is going from failure to failure with no loss of enthusiasm" - Winston Churchill
Avatar do utilizador
leandrosilva
bottom-Quark!
bottom-Quark!
 
Mensagens: 33
Registado: Quarta Dez 24, 2014 8:55 pm
Localização: Santa Comba Dão

Re: Coleção de cartas

Mensagempor gonced8 em Sábado Jan 03, 2015 11:42 pm

Fiz uma pequena alteração, creio que talvez possa ser isto (?) :
A probabilidade do amigo ter uma carta que nós queremos trocar é de:
p(n)=\frac{1}{50}\times \mu =\frac{1}{50}\times\frac{50}{51-n}=\frac{1}{51-n}
Dado, isso a probabilidade de conseguirmos uma carta nova é nos dada somando essa parcela ao que já sabíamos antes:
P(n)=\frac{51-n}{50}+\frac{1}{51-n}=\frac{n^{2}-102n+2651}{-50n+2550}
O nº de cartas que são necessárias comprar é-nos dado como das outras vezes:
\mu (1)+\mu (2)+...+\mu (50)=
=\sum_{i=1}^{50}\frac{-50i+2550}{i^{2}-102i+2651}
\approx 98.7
Seria então necessário comprar apenas 99 cartas, ou seja, menos 126 cartas do que da outra vez.
É isto ou estou muito longe? Eu sinto que estou a "inventar" muitas coisas...
Gonçalo Raposo
Antigo quarkiano (edições de 2014 e 2015)
-Constants and variables-
Avatar do utilizador
gonced8
bottom-Quark!
bottom-Quark!
 
Mensagens: 99
Registado: Terça Dez 17, 2013 11:06 pm

Re: Coleção de cartas

Mensagempor leandrosilva em Sábado Jan 03, 2015 11:52 pm

Mais um raciocínio interessante.
Creio que por um método parecido seria possível chegar ao mesmo resultado, não gostei muito da adição do (51-n) / 50.
Diria que é como se estivesses a usar "quase" a mesma coisa. Visto que (51-n) / 50 seria a probabilidade de uma carta ser nova no decorrer da série, e 1 / (51-n) seria a probabilidade de existir uma carta que te interesse trocar (ou seja, uma carta nova na tua coleção)

Como disse no post anterior, aconselho a que uses a fórmula que apresentei para casos em que o N é maior, "geral" portanto.
N . [0,58 + ln(N)]

Não estás a "inventar" demasiado diria, estás a levantar hipóteses interessantes com erros em pormenores.
A tua determinação é, em qualquer caso, admirável :D
"Success is going from failure to failure with no loss of enthusiasm" - Winston Churchill
Avatar do utilizador
leandrosilva
bottom-Quark!
bottom-Quark!
 
Mensagens: 33
Registado: Quarta Dez 24, 2014 8:55 pm
Localização: Santa Comba Dão

Re: Coleção de cartas

Mensagempor gonced8 em Domingo Jan 04, 2015 12:34 am

Acho que vou fazer uma pausa e esperar que alguém tente resolver
Gonçalo Raposo
Antigo quarkiano (edições de 2014 e 2015)
-Constants and variables-
Avatar do utilizador
gonced8
bottom-Quark!
bottom-Quark!
 
Mensagens: 99
Registado: Terça Dez 17, 2013 11:06 pm

Re: Coleção de cartas

Mensagempor manuelbrandao99 em Domingo Jan 04, 2015 1:52 am

Vamos analisar a situação com uma espécie de uma tabela. Sejam as cartas numeradas de 1 a 50, então temos primeiro as cartas que o A vai comprando e as cartas que o B vai comprando (onde o A e o B são os amigos de que o problema fala).
Uma possibilidade:

A: 34, 27, 15, 34...,10
B: 28, 12, 28,...,1

Repare-se que B tem 2 (no mínimo) cartas 28. Então ele troca imediatamente com a carta 34. Ou seja, sempre que ambos têm cartas repetidas fazem uma troca.
Na situação média, cada um precisa de 225 cartas para acabar a coleção, o que quer dizer que 225 - 50 = 175 cartas são repetidas. Ora como 175/225 = 0.(7) (aproximado), então se tivermos x cartas, então 0.(7)*x são repetidas. Outra conclusão é que na situação média para o mesmo número de cartas compradas ambos têm o mesmo número de cartas repetidas.
Ao fim de comprarem 100 cartas, 78 são repetidas em cada um (A e B). Se há 78 repetidas, então há 78/2 = 39 "tipos" de carta repetidas. E se houver trocas cada um vai ganhar 39 cartas da coleção. 100 - 78 = 22 e 22+39 = 62. E o "Lucky Number" é 82!
Ou seja acabam a coleção com 82 cartas, portanto pouparam 225-82 = 143 cartas!

Peço desculpa pela leitura desagradável, escrevi à medida que raciocionei. E é bem provável que esteja mal, visto que estou cheio de sono e não vou pensar mais nisto... Se estiver bem porreiro, se não espero que outros possam pegar em alguns dos meus raciocínios.
manuelbrandao99
gluão
gluão
 
Mensagens: 27
Registado: Segunda Jan 14, 2013 12:04 pm

Re: Coleção de cartas

Mensagempor leandrosilva em Domingo Jan 04, 2015 2:14 am

Ao fim de comprarem 100 cartas, 78 são repetidas em cada um (A e B). Se há 78 repetidas, então há 78/2 = 39 "tipos" de carta repetidas. E se houver trocas cada um vai ganhar 39 cartas da coleção.


Supões que todas as cartas repetidas seriam trocadas, nem sempre seria assim, existiriam cartas repetidas que seriam repetidas para ambos.
Creio que esse foi o teu erro.

O resultado final está incorreto de igual modo.
"Success is going from failure to failure with no loss of enthusiasm" - Winston Churchill
Avatar do utilizador
leandrosilva
bottom-Quark!
bottom-Quark!
 
Mensagens: 33
Registado: Quarta Dez 24, 2014 8:55 pm
Localização: Santa Comba Dão

AnteriorPróximo

Voltar para Problemas de Fermi

Quem está ligado

Utilizadores a navegar neste fórum: Nenhum utilizador registado e 2 visitantes

cron