Três peças de tecido medem, respectivamente,
e 8 m . Desejando cortá-los em pedaços de mesmo comprimento, qual deverá ser o comprimento para que os retalhos tenham o maior tamanho possível e portanto, sejam cortados no menor número possível de partes?
Passo 1
O enunciado dá três comprimentos de tecido e pede que os cortemos em pedaços todos do mesmo comprimento, sendo esse comprimento o maior possível (para que o número de peças seja o menor possível). Os dados são:
- primeiro tecido:
, - segundo tecido:
, - terceiro tecido:
.
A pergunta é: qual deve ser o comprimento de cada pedaço (um número em metros) de modo que todos os três tecidos possam ser cortados exatamente em pedaços desse comprimento e esse comprimento seja o maior possível?
Passo 2
Ideia-chave (explicada devagar e com exemplos): para cortar cada tecido em pedaços iguais sem sobra, o comprimento escolhido deve dividir exatamente cada um dos comprimentos dados. Ou seja, se chamarmos esse comprimento de
, precisamos de
tal que
Em termos matemáticos,
deve ser um divisor comum de
e
. Como queremos o maior possível, estamos procurando o máximo divisor comum (MDC, também chamado de GCD) desses três números.
Como encontrar o MDC de maneira prática e eficiente? Usamos o algoritmo de Euclides, que se baseia numa propriedade simples: se
e
são inteiros com
, então qualquer divisor comum de
e
também divide o resto
da divisão de
por
; assim
. Repetindo esse passo (dividindo o maior pelo menor e substituindo) até o resto ser zero, o último divisor não nulo é o MDC. Não precisa decorar além disso — funciona com divisões por subtração disfarçada.
Passo 3
Aplicando o algoritmo de Euclides aos dois primeiros comprimentos
e
:
Faço a divisão inteira de
por
:
O resto é
. Pelo algoritmo,
.
Agora divido
por
:
O resto é
, então o MDC dos dois primeiros é o último divisor não nulo, que é
. Assim
Passo 4
Agora preciso do MDC de todos os três números. Já tenho
. Então o MDC dos três é
. Faço a divisão:
O resto é
, portanto
Passo 5
Interpretação final e verificação: o maior comprimento
que divide simultaneamente
e
é
. Isso significa que é possível cortar cada tecido em pedaços de
sem sobrar nada. Para checar:
-
pedaços, -
pedaços, -
pedaço.
Qualquer comprimento maior que
não pode dividir
, logo não serviria para o terceiro tecido; portanto
é realmente o maior possível. Usar o MDC garante também o menor número total de pedaços, porque comprimentos menores produziriam mais pedaços.