Suponha que exista um hotel com infinitos quartos, chamado hotel de Hilbert, e que este esteja lotado. considere e resolva as seguintes situações:
a) Ao chegar 100 hóspedes. Como hospedá-los?
b) Ao chegar um ônibus com infinitos passageiros, como hospedá-los?
c) Ao chegar infinitos ônibus, cada um com infinitos passageiros. Como hospedar esses passageiros?

Passo 1

O enunciado fala do “hotel de Hilbert” com quartos numerados de 1 a infty, todos ocupados, e pede três situações de realocação para caber novos hóspedes. O conteúdo é de infinito numerável e construções de bijeções entre N e Ntimespassa>=iros. Vamos usar injeções simples e a função de emparelhamento (pairing function).

Passo 2

Para acomodar 100 hóspedes a mais, basta deslocar cada hóspede atual do quarto n para o quarto n+100. Isso é uma injeção de N em N e libera precisamente os quartos \r
1,2,dots,100 \r
Então os novos 100 hóspedes ocupam esses quartos livres na ordem que chegarem.

Passo 3

Para um ônibus com infinitos passageiros numerados 1,2,3,dots, primeiro deslocamos cada hóspede atual do quarto n para o quarto 2n. Assim todos os quartos pares ficam ocupados pelos antigos hóspedes, e todos os quartos ímpares 1,3,5,dots ficam livres. Em seguida, damos ao passageiro k do ônibus o quarto ímpar de índice k, isto é, o quarto \r
2k-1

Passo 4

Para infinitos ônibus numerados i=1,2,3,dots, cada um com passageiros j=1,2,3,dots, combinamos as duas ideias:\r
  1. Primeiro deslocamos cada hóspede atual do quarto n para o quarto 2n, liberando todos os quartos ímpares.\r
  2. Em seguida enumeramos todos os passageiros novos por pares (i,j) usando a função de emparelhamento de Cantor, por exemplo \r
pi(i,j)=(i+j-2)(i+j-1)2+j, \r
que é uma bijeção NtimesNtoN. \r
3. Damos ao passageiro j do ônibus i o pi(i,j)-ésimo quarto ímpar, ou seja,\r
quarto = 2,pi(i,j)-1 \r
Isso injeta todos os novos passageiros nos quartos ímpares, sem conflito.

Resposta

(a) Deslocar hóspede do quarto n para n+100; liberar 1,dots,100. \n\r
(b) Deslocar hóspede do quarto n para 2n; passageiro k vai ao quarto 2k-1. \n\r
(c) Deslocar hóspede do quarto n para 2n; numerar novos passageiros por pi(i,j)=(i+j-2)(i+j-1)2+j e colocar o passageiro j do ônibus i no quarto 2,pi(i,j)-1.

Exercícios relacionados