Neste artigo eu falei de uma charada com baldes com água. Agora desafio-te a mostrares que há situações em que a charada é impossível de resolver!
Tens \(n\) baldes e cada um tem capacidade para \(c_i\) litros de água, \(i = 1, \cdots, n\). Queres mexer nos baldes de maneira tal que consegues fazer com que um balde tenha exatamente \(t\) litros de água, sabendo que as três coisas que podes fazer são:
Prova que, se \(t\) não for um múltiplo do maior divisor comum dos vários \(c_i\), \(i = 1, \cdots, n\) então é impossível que um balde contenha exatamente \(t\) litros de água.
Por exemplo, se os baldes tiverem capacidades \(4\) e \(6\) e \(t = 3\), então não há sequência de movimentos que permita ter exatamente \(3\) litros de água num dos baldes, já que o maior divisor comum de \(4\) e \(6\) é \(\texttt{mdc}(4, 6) = 2\) e \(3\) não é um múltiplo de \(2\).
Pensa um pouco... e tenta resolver o problema! Pega numa folha e num lápis e puxa pela cabeça!
Se precisares de clarificar alguma coisa, não hesites em perguntar na secção de comentários em baixo.
Uma solução possível passa por usar um bom invariante que se aplica à quantidade de água que cada balde contém em qualquer altura. Para facilitar a minha explicação, vamos dizer que o máximo divisor comum dos \(c_i\), \(i = 1, \cdots, n\) é \(\texttt{mdc}(c_1, \cdots, c_n) = d\) e vamos dizer ainda que a quantidade de água que o balde \(i\) tem se chama \(w_i\). O que eu vou mostrar é que, independentemente das jogadas que façamos, \(w_i\) é sempre um múltiplo de \(d\) para qualquer \(i\) (que se escreve \(d | w_i\) e que se lê _"\(d\) divide \(w_i\)"_).
No início todos os baldes estão vazios, o que significa que temos \(w_1 = \cdots = w_n = 0\) e \(0\) é um múltiplo de \(d\) portanto começamos bem. Agora vou mostrar que as três jogadas existentes preservam a propriedade \(d | w_i\ \forall i\).
Acabei de mostrar que, independentemente do que façamos, a quantidade de água em cada balde é sempre múltipla de \(d\), logo se \(t\) não for um múltiplo de \(d\) então é impossível fazer com que um balde tenha exatamente \(t\) litros de água...
Não te esqueças de subscrever a newsletter para receberes os problemas diretamente na tua caixa de correio, e deixa a tua reação a este problema em baixo.
Espero que tenhas aprendido algo novo! Se sim, considera seguir as pisadas dos leitores que me pagaram uma fatia de pizza 🍕. O teu pequeno contributo ajuda-me a manter este projeto grátis e livre de anúncios aborrecidos.