Descobrindo o polinômio

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

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 .

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

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ó

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

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.

Nimópolis

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.

Porta dos problemáticos

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.

Lemmings

Hoje, tenho dois problemas meio relacionados. O primeiro, Lemmings, vem do site do William Wu, é meu velho conhecido, e possui uma das soluções mais bonitas e surpreendentes que já vi. De fato, quando alguém me pede um exemplo das “epifanias” que experimentamos ao resolver problemas como os deste site, é no Lemmings que penso primeiro. Aqui vai.

Ache x …

Dado este quadrado de lado 1, qual o valor de x?

Partições de Inteiros

Este problema trata de partições de números inteiros, que é apenas um termo técnico significando “jeito de escrever um número como soma de outros números”. Por exemplo, 2+3 é uma partição de 5. Como a adição é comutativa, convencionamos que 3+2 e 2+3 são “a mesma” partição de 5; por exemplo, 4 tem cinco partições no total (cada linha abaixo conta como uma partição só):

1+1+1+1

2+1+1 = 1+2+1 = 1+1+2

2+2

3+1 = 1+3

4