CN - Em um navio existem 6 barcos e 15 guarnições. Cada barco tem uma guarnição de serviço por dia. Quantos dias, no mínimo, serão necessários para que todas as guarnições tenham ficado de serviço o mesmo número de vezes?
a) 5
b) 6
c) 7
d) 8
e) 15
a) 5
b) 6
c) 7
d) 8
e) 15
Passo 1
O enunciado diz que há
guarnições e, a cada dia,
delas ficam de serviço (uma em cada barco). Queremos descobrir o número mínimo de dias
de modo que todas as
guarnições tenham ficado de serviço exatamente o mesmo número de vezes.
Passo 2
Sejam
o número de dias e
o número de vezes que cada guarnição serviu ao final de
dias. Como em cada dia servem
guarnições, o total de “lugares de serviço” é\r
Por outro lado, esse total também deve ser igual a
guarnições vezes
serviços cada, ou seja,\r
Passo 3
Da equação
seguimos\r
Para que
seja inteiro, é necessário que
seja múltiplo de
. Como
, isso força\r
ou seja,
é múltiplo de
. O menor valor positivo é
, o que dá\r
Passo 4
Ainda precisamos garantir que seja possível distribuir as
guarnições em
dias de forma que cada dia receba exatamente
guarnições e cada guarnição apareça em
dias distintos. Isso equivale a construir um grafo bipartido entre o conjunto de
guarnições (grau
cada) e
dias (grau
cada). As condições de existência (tipo Hall) são satisfeitas, pois há “capacidade” suficiente em cada dia para acomodar qualquer subconjunto de guarnições. Logo, a distribuição é viável.