Como obter o maior número com probabilidade 2/3 a partir de uma pilha com três números distintos?

Question

Suponha que alguém tenha escolhido três inteiros distintos e os tenha colocado em uma pilha S em ordem aleatória. Como escrever um pedaço curto de código (sem loops ou recursão) que usa apenas uma comparação e apenas uma variável x, mas isso resulta na variável x armazenando o maior dos três inteiros de Alice com probabilidade de 2/3?

Answer 1

Com o objetivo de ter uma resposta auto-contida será implementada uma pilha e em seguida implementada a solução para a pergunta.
Assim, uma possível implementação da solução em Python é a seguinte:

# Implementando pilha
## Definindo exceção
class Empty(Exception):
    """Erro ao tentar acessar uma lista vazia."""
    pass

## Usando classe para implementar pilha
class ArrayStack:
    '''
    Implementação de uma pilha usando listas.
    '''
    def __init__(self):
        '''Criando uma pilha vazia.'''
        self.__data = []

    def __len__(self):
        '''Retorna número de elementos da pilha.'''
        return len(self.__data)

    def is_empty(self):
        '''Checa se a pilha está vazia.'''
        return len(self.__data) == 0

    def push(self, e):
        '''Adiciona um elemento ao topo da lista.'''
        self.__data.append(e)

    def top(self):
        '''Retorna (mas, não remove) elemento no top da pilha'''
        if self.is_empty(): # Caso a pilha esteja vazia
            raise Empty('Pilha está vazia')
        return self.__data[-1]

    def pop(self):
        '''Remove e retorna elemento do topo da pilha'''
        if self.is_empty():
            raise Empty('Pilha vazia')
        return self.__data.pop()

# Implementação da solução
def maior_num(st):
   x = st.pop()
   if x > st.top():
       return x
   else:
       x = st.top()
       return x

if __name__ == '__main__':
    s = ArrayStack()

    s.push(3)
    s.push(5)
    s.push(2)
    print(maior_num(s))

Comments

A implementação em código está correta. O colega criou uma pilha a partir de uma lista, retirou o último elemento adicionado e o chamou de x, o comparou com o último elemento restante e manteve o maior deles. A única coisa que faltou na resposta foi argumentar porque essa solução está correta em retornar o maior número de uma lista com três números inteiros com probabilidade de 2/3. Isso pode ser comprovado por exaustão. Suponhamos três elementos A, B e C, sendo que A>B>C. Temos então seis possibilidades de pilhas distintas, elencadas abaixo. Usando o método proposto pelo colega, o código retorna o maior número entre os dois últimos adicionados ã pilha, indicados com um igual.

[A,B,C] = A
[A,C,B] = A
[B,A,C] = A
[B,C,A] = B
[C,A,B] = A
[C,B,A] = B

Dessa forma, podemos observar que, das seis soluções, quatro estão corretas, retornando A, enquanto duas estão incorretas, retornando B, o que representa uma probabilidade de acerto de 2/3.