Vulnerabilidade no protocolo de mictório

Vulnerabilidade no protocolo de mictório
Randall Munroe
XKCD, a webcomic of romance, sarcasm, math and language
(Publicado originalmente: 2 de setembro de 2009)
Quando um cara vai ao banheiro, qual mictório ele escolhe? A a maioria está familiarizada com o
Protocolo Internacional de Escolha de Mictório. Ele é discutido exaustivamente em outros lugares,
mas a premissa básica é que o primeiro cara escolhe um mictório extremo e cada um que chegar
escolhe o mictório que o coloca mais longe de qualquer outra pessoa urinando. Pelo menos um
mictório de intervalo é exigido ou Esquisitice se implanta.
I.
APRESENTAÇÃO DO PROBLEMA
Vamos olhar para a eficiência
desse protocolo em acomodar todos em mictórios aceitáveis. Para
alguns números de mictórios, este
protocolo leva a uma acomodaçào
eficiente. Se há cnco mictórios, eles
se preencherão como na Fig. 1(a).
Os primeiros dois caras pegam as
extremidades e o terceiro pega o do meio. Neste ponto,
os mictórios estão congestionados — nenhum cara pode
urinar sem Esquisitice. Entretanto, é bastante eficiente:
mais de 50% dos micitórios são usados.
na Fig. 1(c). Então uma fileira de oito mictórios apresenta uma eficiência maior que uma fila de sete e uma
fila de cinco é melhor que as duas.
II.
DESENVOLVIMENTO DO MODELO
Isso leva a uma questão: qual é a fórmula geral para
o número de caras que vão preencher N mictórios se
eles chegarem um a um e seguirem o Protocolo? Seria possı́vel escrever um programa recursivo simples para
resolver esse problema, mas também há uma expressão
fechada. Se f (N ) é o número de caras que podem usar
N mictórios, então, para N > 2,
¶
µ
3
f (N ) = 1+2blog (n−2)−1c +max 0, n − 2blog n−2c − 1 .
2
(a)5 mictórios
O protocolo é vulnerável à produção de resultados
ineficientes para alguns números de mictório. Alguns
números permitem empacotamento eficiente e outros levam a uma ocupação esparsa. Se graficarmos a eficiência
f (N )/N , obtemos a Fig. 2
(b)7 mictórios
(c)8 mictórios
Figura 1: Efeito do número de mictórios na acomodação de
usuários
Por outro lado, se há sete mictórios, eles não se prenche de maneira tão eficiente, como mostra a Fig. 1(b).
Deveria haver espaço para quatro caras sem Esquisitice,
mas uma vez que o terceiro cara seguiu o protocolo e escolheu o mictório do meio, não há opções para o quarto,
que provavelmente vai usar uma cabine — ou a pia.
Para oito mictórios, o protocolo funciona melhor, como
Figura 2: Eficiência de ocupação em função do número de
mictórios
Isso sgnifica que alguns números grandes de mictórios
vão ser ocupados eficientemente (50%) e outros ineficientemetne (33%). Os “melhores” números de mictórios,
correspondentes aos picos no gráfico, são da forma
N = 2k + 1 e os piores são dados por N = 32 2k + 1.
2
III.
DISCUSSÃO
Assim, se você pretende que os usuários ocupem eficientemente seus mictórios, deve haver 3,5,8,17 ou 33 deles
e se você pretende tomar vantagem do protocolo para maximizar a esquisitice, deve haver 4, 7, 13 ou 25 mictórios.
Esses cálculos sugerem outras aplicações. Rapazes: se
vocês entrarem em um banheiro com um número esquisito de mictórios vazios, em vez de ocupar um da extremidade, você pode ocupar um que esteja a um terço
[1] Munroe, R, Urinal protocol vulnerability http://blag.xkcd.
com/2009/09/02/urinal-protocol-vulnerability/,XKCD
blag post (2009)
da largura. Isso vai quebrar a série esquisita em duas
séries ótimas, transformando o pior caso num caso ideal.
Por outro lado, se você quiser criar Esquisitice e o banheiro tem um número não esqisito de mictórios, você
pode ocupar aquele a um terço da largura e converter
uma fila ótima em duas filas esquisitas.
E, claro, se você quiser tornar as coisas realmente esquisitas, sugiro que imprima este artigo e tente explicá-lo
para o cara urinando do seu lado.