Descobrindo o polinômio

18 \18\UTC março \18\UTC 2010

Tenho um polinômio P, com coeficientes inteiros e não-negativos. Você pode me perguntar o valor de P(x) para qualquer número x algébrico. Quantas perguntas são suficientes para que você seja capaz de descobrir os coeficientes de P? Como proceder?

Edição: note que você não sabe qual é o grau do polinômio.

(Baseado no post A puzzle about polynomials (God Plays Dice))


Sapo Colinear

31 \31\UTC julho \31\UTC 2009

Problemópolis é um lugar curioso. Além de reis enófilos cruéis, mesas de bilhar enigmáticas e funcionários públicos, há um lago infinito em todas as direções, com pedras uniformemente espaçadas num arranjo quadriculado infinito. Isto é: Problemópolis tem um lago isomorfo ao plano \mathbb{Z}\times\mathbb{Z}.

Um sapo está sentado na pedra (0,0), e a cada segundo pula para uma pedra diretamente ao leste ou ao norte. Isto é, se o sapo está na pedra (m,n), no segundo seguinte ele estará na pedra (m+1,n) ou (m,n+1).

Joãozinho observa o sapo por algum tempo e nota que, em certo momento, o sapo já visitou três pedras colineares. Observa mais um pouco, e nota que o sapo visitou quatro pedras colineares (não necessariamente incluindo as três primeiras). Joãozinho então se pergunta: será que, se eu olhar por bastante tempo, o sapo visitará k pedras colineares, qualquer que seja k?


Degustadores Facínoras 2

23 \23\UTC julho \23\UTC 2009

Outro atentado da rainha vizinha contra o rei malvado (ver problema Degustadores Facínoras). Novamente, uma única garrafa da adega real foi comprometida, e novamente não se sabe exatamente qual… Desta vez, porém, os tempos estão mais difíceis, e o rei possui apenas 240 garrafas e cinco prisioneiros (os quais estão disponíveis para sacrifício). Sabendo que o veneno pode levar até um mês para se manifestar, como o rei deve proceder para identificar a bebida envenenada em até dois meses (*)?

(*) Despreze gastos de tempo com “logística”. Considere relevante apenas o tempo necessário para o veneno fazer efeito.

O problema foi proposto pelo brunoargento no twitter (aqui e aqui).


Dominó

21 \21\UTC janeiro \21\UTC 2009

A rotina de Zé Problemildo, funcionário público aposentado, é socializar com seus amigos da terceira idade ali na Praça dos Problemas, não muito longe da prefeitura da cidade. O principal divertimento dessa turma é, pasmem, jogar dominó. Jogo vai, jogo vem, Zé resolveu inovar com uma brincadeira boba. Ele pegava uma peça de dominó ao acaso e via só um dos números. Em seguida, tentava adivinhar qual era o número escondido. Depois de repetir o processo algumas vezes, perguntou-se qual seria a chance de os dois números coincidirem. Eis a questão, caros leitores: qual é essa probabilidade?

Nota: o problema é fácil mesmo.


Tijolando

16 \16\UTC dezembro \16\UTC 2008

O padrão de tijolo de Problemópolis é de 2 por 1 pés, medidos segundo os do rei-prefeito da cidade. Enfadado, o dito cujo baixa uma lei nova: todas as casas serão compostas de quatro paredes retangulares, de x por y pés, cobertas inteiramente por tijolos padrão. Só que, em um parágrafo adicionado sorrateiramente por um vereador da oposição em uma seção esvaziada, a lei obriga que não haja duas paredes com o mesmo padrão de tijolos na cidade.

Leia o resto deste post »


Nimópolis

9 \09\UTC dezembro \09\UTC 2008

Nim é um jogo muito interessante. A versão simples dele é a seguinte: há várias pilhas de moedas sobre uma mesa e dois jogadores, cada um retira alternadamente um número de moedas maior ou igual a 1 de uma só pilha. Aquele que tirar a última moeda sobre a mesa, perde. A parte fácil do problema de hoje é a seguinte. Dadas 7 pilhas de moedas, a primeira com uma moeda, a segunda com duas, …, a última com sete, desenvolva uma estratégia para ganhar o jogo.

Leia o resto deste post »


Porta dos problemáticos

2 \02\UTC dezembro \02\UTC 2008

Este é meu post de estréia em Problemópolis. Agradeço o convite para participar da equipe.

O programa de TV de maior audiência de Problemópolis é o “Porta dos Problemáticos”. O apresentador, Sérgio Problemandro, apresenta ao participante três portas. Uma contém o maníaco da serra elétrica, outra a Dilma Rousseff e a outra o Problemation VVII com todos os jogos de Rock Hero e Guitar Band, e uma guitarra, um baixo, uma bateria, um teclado e um vocoder, um cravo e um alaúde (para o Baroque Monster Pack) todos USB3.

Sérgio pede que o participante escolha uma porta, aleatoriamente. Depois que ele faz a escolha, o apresentador abre uma das portas com monstros. Sobram duas portas, e Sérgio Problemandro pergunta: você quer trocar de porta?

O problema é: trocar de porta é vantajoso, desvantajoso ou tanto faz? Por quê?

Dica: Inicialmente, a chance do Problemation estar na porta escolhida é de 1/3.

***

Esse problema é bastante conhecido, e talvez você já saiba a resposta. Mesmo assim, tente provar a sua resposta e, se estiver muito fácil, generalize para P portas e N = P-1 escolhas.