Parabéns a todos que se desafiaram a solucionar o Giant Puzzle #4! Admiramos imensamente aqueles que se arriscam a pensar fora da caixa e a encontrar soluções criativas para problemas complexos.
Conseguiram resolver esse puzzle: Leonardo Joau, Saul Spatz e Guillermo Wildschut.
O problema
Rodrigo é um colecionador de figurinhas e deseja completar um álbum de futebol que foi lançado. Considere que o álbum possui 680 figurinhas a serem coladas, das quais 80 são holográficas. As figurinhas holográficas são 5 vezes mais raras que as normais, ou seja, a probabilidade de uma delas aparecer em um pacote de figurinha é 1/5 vezes a probabilidade de aparecer uma não-holográfica. Considere que os pacotes contêm 7 figurinhas cada e elas podem aparecer repetidas dentro de um mesmo pacote. Ainda, cada um dos pacotes custa 40 centavos em uma banca de jornal.
a) Calcule o valor esperado gasto por Rodrigo (em reais) para completar o álbum, considerando que ele não faça trocas.
b) Suponha que exista um mercado paralelo de venda de figurinhas individuais, as quais Rodrigo pode escolher separadamente para completar o álbum. Cada figurinha normal custa 30 centavos, enquanto uma holográfica custa 2 reais. Considere que Rodrigo compra pacotes de figurinhas até um ponto em que vale a pena ele comprar todas as restantes individualmente. Calcule o valor esperado gasto por Rodrigo neste caso.
c) Resolva os mesmos problemas dos itens a e b, porém considerando que não podem vir figurinhas repetidas num mesmo pacote.
Observação: expresse suas respostas com 8 casas decimais de precisão.
Solução
a) 874.09642499
b) 199.60637310
c) 869.91971711 e 199.19343404
A melhor forma para chegar nestes valores consistia em resolver um problema de programação dinâmica.
Considere f(n,k) o número esperado de pacotes a serem comprados quando faltam n figurinhas normais e k holográficas.
Considere também p_{i,j;k,l} a probabilidade de uma pessoa que tem um álbum faltando i figurinhas normais e k holográficas que, ao comprar um pacotinho, tem um saldo de figurinhas faltantes de j normais e l holográficas.
Esse valor esperado obedece à seguinte recursão:
A equação acima pode ser rearranjada da seguinte forma:
Assim que faltarem n figurinhas normais e k holográficas para um determinado colecionador, ele deve checar se vale a pena comprar todas as figurinhas restantes no mercado paralelo ou se deve apostar em comprar mais um pacotinho.
Por isso, o valor resultante da recursão acima deve ser armazenado em uma matriz como sendo o menor entre i) a esperança de conseguir as figurinhas faltantes comprando um pacotinho ou ii) comprar tudo no mercado paralelo.
Ainda, dado que a figurinha holográfica é 5 vezes mais rara que a normal, a probabilidade de uma figurinha aleatória ser normal é:
O código em anexo mostra a solução genérica comentada para os itens a e b. O que muda para o item c é a probabilidade de obter uma figurinha repetida normal ou holográfica dentro de um pacotinho, já que deve ser considerada a influência das figurinhas anteriores que já foram retiradas dentro dele. O código em anexo também ilustra como esse problema pode ser resolvido.
{
"cells": [
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"import numpy as np"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"199.60637310437687\n"
]
}
],
"source": [
"# Código para os itens a e b\n",
"\n",
"#Inicialização dos parâmetros do problema. ratio é a razão de raridade entre as figurinhas holográficas e normais\n",
"ratio = 5.0\n",
"\n",
"# n_album é a quantidade de figurinhas do álbum\n",
"n_album = 680.0\n",
"\n",
"# n_hol é a quantidade de holográficas do álbum\n",
"n_hol = 80.0\n",
"\n",
"# packet_price é o preço de cada pacote\n",
"packet_price = 0.4\n",
"\n",
"# normal_price é o preço da figurinha normal no mercado paralelo\n",
"normal_price = 0.3\n",
"\n",
"# hol_price é o preço da holográfica no mercado paralelo\n",
"hol_price = 2.0\n",
"\n",
"# nb_fig é o número de figurinhas por pacote\n",
"nb_fig = 7\n",
"\n",
"# p é a probabilidade de uma figurinha selecionada aleatoriamente ser normal\n",
"p = 1.0 / ((n_album - n_hol) + n_hol / ratio)\n",
"\n",
"# A função abaixo calcula a probabilidade de uma figurinha selecionada aleatoriamente ser\n",
"# normal, dado que faltam n normais e k holográficas\n",
"def probRep(n, k):\n",
" return (1.0 - (ratio * n + k) * p / ratio)\n",
"\n",
"# A função abaixo retorna a probabilidade de uma figurinha aleatória ser uma normal que a\n",
"# pessoa ainda não possui, dado que faltam n normais e k holográficas\n",
"def probNewNorm(n, k):\n",
" return n * p\n",
"\n",
"# A função abaixo retorna a probabilidade de uma figurinha aleatória ser uma holográfica \n",
"# que a pessoa ainda não possui, dado que faltam n normais e k holográficas\n",
"def probNewHolo(n, k):\n",
" return k * p / ratio \n",
"\n",
"# A função abaixo retorna o custo para completar o álbum usando apenas o mercado paralelo,\n",
"# dado que faltam n normais e k holográficas\n",
"def parallelMarketCost(n, k):\n",
" return n * normal_price + k * hol_price\n",
"\n",
"# A função abaixo retorna a probabilidade de retirar curr_norm normais não repetidas e \n",
"# curr_hol holográficas não repetidas em um pacotinho de figurinhas, dado que faltam n \n",
"# normais e k holográficas\n",
"def probTot(n, k, packet_size, curr_val, curr_norm, curr_hol):\n",
" if curr_norm < 0 or curr_hol < 0:\n",
" return 0.0\n",
" if curr_val == packet_size:\n",
" if curr_norm != 0 or curr_hol != 0:\n",
" return 0.0\n",
" return 1.0\n",
" return probNewNorm(n, k) * probTot(n-1, k, packet_size, curr_val+1, curr_norm-1, curr_hol) + probNewHolo(n, k) * probTot(n, k-1, packet_size, curr_val+1, curr_norm, curr_hol-1) + probRep(n, k) * probTot(n, k, packet_size, curr_val+1, curr_norm, curr_hol)\n",
"\n",
"# Quantidade de figurinhas normais e holográficas no álbum, respectivamente\n",
"shape_0 = int(n_album - n_hol)\n",
"shape_1 = int(n_hol)\n",
"\n",
"# f é a matriz que possui o custo para completar o álbum. f[n, k] é o custo quando faltam n-nb_fig normais \n",
"# e k-nb_fig holográficas\n",
"f = np.zeros((shape_0 + 1 + nb_fig, shape_1 + 1 + nb_fig))\n",
"for n in range(0, shape_0 + 1):\n",
" for k in range(0, shape_1 + 1):\n",
" if n == 0 and k == 0:\n",
" continue\n",
" \n",
" # Cálculo do custo para comprar n figurinhas normais e k holográficas no mercado paralelo\n",
" pm = parallelMarketCost(n, k)\n",
" \n",
" # Cálculo do custo para completar o álbum caso a pessoa opte por comprar mais um pacote de figurinhas usando recursão\n",
" pk = 1.0 / (1.0 - (probRep(n, k) ** (1.0 * nb_fig)))\n",
" pz = packet_price\n",
" for r in range(nb_fig+1):\n",
" for s in range(nb_fig+1-r):\n",
" if r == 0 and s == 0:\n",
" continue\n",
" pz += f[n-r+nb_fig, k-s+nb_fig] * probTot(n, k, nb_fig, 0, r, s)\n",
" pz *= pk\n",
" \n",
" # A pessoa optará aqui pela solução que possuir menor valor esperado de custo naquele instante\n",
" f[n+nb_fig, k+nb_fig] = min([pm, pz])\n",
"print(f[-1, -1])"
]
},
{
"cell_type": "code",
"execution_count": 146,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"869.9197171085627\n"
]
}
],
"source": [
"# Código para o item c\n",
"\n",
"#Inicialização dos parâmetros do problema. ratio é a razão de raridade entre as figurinhas holográficas e normais\n",
"ratio = 5.0\n",
"\n",
"# n_album é a quantidade de figurinhas do álbum\n",
"n_album = 680.0\n",
"\n",
"# n_hol é a quantidade de holográficas do álbum\n",
"n_hol = 80.0\n",
"\n",
"# packet_price é o preço de cada pacote\n",
"packet_price = 0.4\n",
"\n",
"# normal_price é o preço da figurinha normal no mercado paralelo\n",
"normal_price = 0.3\n",
"\n",
"# hol_price é o preço da holográfica no mercado paralelo\n",
"hol_price = 2.0\n",
"\n",
"# nb_fig é o número de figurinhas por pacote\n",
"nb_fig = 7\n",
"\n",
"# Dado que faltam n normais para o colecionador, k holográficas, curr_n_album é o número de figurinhas do álbum \n",
"# disponíveis considerando as figurinhas que ele já retirou no pacotinho (como se o universo de figurinhas disponível\n",
"# fosse reduzido) e curr_n_hol é o número de holográficas disponíveis considerando o que ele já retirou no dado\n",
"# pacotinho, a função abaixo calcula a probabilidade de vir uma normal repetida. Note que p_new é igual ao p do\n",
"# código anterior, substituindo o número de figurinhas do álbum por curr_n_album e o número de holográficas por\n",
"# curr_n_hol. Dessa forma, a raridade das holográficas é mantida com relação às não-holográficas.\n",
"def probRepNorm(n, k, curr_n_album, curr_n_hol):\n",
" p_new = 1.0 / ((curr_n_album - curr_n_hol) + curr_n_hol / ratio)\n",
" return ((curr_n_album - curr_n_hol - n) * p_new)\n",
"\n",
"# Código semelhante ao da função anterior, porém calcula a probabilidade de vir uma holográfica repetida\n",
"def probRepHolo(n, k, curr_n_album, curr_n_hol):\n",
" p_new = 1.0 / ((curr_n_album - curr_n_hol) + curr_n_hol / ratio)\n",
" return ((curr_n_hol - k) * p_new / ratio)\n",
"\n",
"# Código semelhante ao da função anterior, porém calcula a probabilidade de vir uma nova normal\n",
"def probNewNorm(n, k, curr_n_album, curr_n_hol):\n",
" p_new = 1.0 / ((curr_n_album - curr_n_hol) + curr_n_hol / ratio)\n",
" return n * p_new\n",
"\n",
"# Código semelhante ao da função anterior, porém calcula a probabilidade de vir uma nova holográfica\n",
"def probNewHolo(n, k, curr_n_album, curr_n_hol):\n",
" p_new = 1.0 / ((curr_n_album - curr_n_hol) + curr_n_hol / ratio)\n",
" return k * p_new / ratio \n",
"\n",
"# Função que retorna o custo de comprar tudo no mercado paralelo\n",
"def parallelMarketCost(n, k):\n",
" return n * normal_price + k * hol_price\n",
"\n",
"# Função recursiva que calcula a probabilidade de se retirar curr_norm normais e curr_hol \n",
"# holográficas não repetidas em um pacotinho, considerando que curr_n_album é o número de\n",
"# figurinhas disponíveis no álbum dado o que já foi retirado e curr_n_hol é o número de holográficas\n",
"def probTot(n, k, packet_size, curr_val, curr_norm, curr_hol, curr_n_album, curr_n_hol):\n",
" if curr_norm < 0 or curr_hol < 0:\n",
" return 0.0\n",
" if curr_val == packet_size:\n",
" if curr_norm != 0 or curr_hol != 0:\n",
" return 0.0\n",
" return 1.0\n",
" return probNewNorm(n, k, curr_n_album, curr_n_hol) * probTot(n-1, k, packet_size, curr_val+1, curr_norm-1, curr_hol, curr_n_album-1, curr_n_hol) + probNewHolo(n, k, curr_n_album, curr_n_hol) * probTot(n, k-1, packet_size, curr_val+1, curr_norm, curr_hol-1, curr_n_album-1, curr_n_hol-1) + probRepNorm(n, k, curr_n_album, curr_n_hol) * probTot(n, k, packet_size, curr_val+1, curr_norm, curr_hol, curr_n_album-1, curr_n_hol) + probRepHolo(n, k, curr_n_album, curr_n_hol) * probTot(n, k, packet_size, curr_val+1, curr_norm, curr_hol, curr_n_album-1, curr_n_hol-1)\n",
"\n",
"# O código abaixo funciona de forma semelhante ao anterior, resolvendo a recursão e calculando o valor\n",
"# gasto para se comprar tudo no mercado paralelo a cada valor de n normais restantes e k holográficas\n",
"shape_0 = int(n_album - n_hol)\n",
"shape_1 = int(n_hol)\n",
"f = np.zeros((shape_0 + 1 + nb_fig, shape_1 + 1 + nb_fig))\n",
"for n in range(0, shape_0 + 1):\n",
" for k in range(0, shape_1 + 1):\n",
" if n == 0 and k == 0:\n",
" continue\n",
" pm = parallelMarketCost(n, k)\n",
" pk = 1.0 / (1.0 - probTot(n, k, nb_fig, 0, 0, 0, n_album, n_hol))\n",
" pz = packet_price\n",
" for r in range(nb_fig+1):\n",
" for s in range(nb_fig+1-r):\n",
" if r == 0 and s == 0:\n",
" continue\n",
" pz += f[n-r+nb_fig, k-s+nb_fig] * probTot(n, k, nb_fig, 0, r, s, n_album, n_hol)\n",
" pz *= pk\n",
" f[n+nb_fig, k+nb_fig] = min([pm, pz])\n",
"print(f[-1, -1])"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.7.6"
}
},
"nbformat": 4,
"nbformat_minor": 4
}