Solução do Giant Puzzle #4 – Colecionador

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

As respostas para o Giant Puzzle #4 são as seguintes:

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.

Código
{
 "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
}
Acesse aqui o Giant Puzzle mais recente!

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *