Escrevem-se números de cinco dígitos (inclusive os começados por zero) em cartões. Como 0,1 e 8 não se alteram de cabeça para baixo e como 6 de cabeça para baixo se transforma em 9 , um só cartão pode representar dois números (por exemplo, 06198 e 86190). Qual é o número mínimo de cartões para representar todos os números de cinco dígitos?
Passo 1
Resumindo o problema: queremos representar todos os inteiros de cinco dígitos de 00000 até 99999 usando cartões que podem ser virados de cabeça para baixo. Os dígitos válidos ao virar são
(se mantêm) e
. Cada cartão pode mostrar um número na orientação normal e, ao virar, outro número (se todos os dígitos forem desses). Para minimizar cartões, emparelhamos cada número com seu “involutivo” invertido, salvo quando não for possível ou quando for ponto fixo (número que vira ele mesmo).
Passo 2
Contamos quantos números de cinco dígitos são totalmente formados pelos dígitos
. Como em cada uma das 5 posições há 5 escolhas, o total é
Passo 3
Entre esses
, alguns satisfazem
(ponto fixo). Para isso, nas posições simétricas
e
o par deve ser um dos 5 pares reversíveis
, e o dígito central deve ser
. Logo
Passo 4
Os
elementos de
se partem em órbitas de tamanho 1 (os 75 fixos) ou de tamanho 2 (os demais). O número mínimo de cartões para cobrir
é, pois,
Passo 5
Os outros números (que contêm pelo menos um dígito em
) não se emparelham, pois ao virar geram dígito inválido. Há
destes, cada um exigindo um cartão próprio. Somando tudo:
Resposta
98475