DERS-10 EBOB-EKOK PROBLEMLERİ-1

PAYLAŞTIRMA PROBLEMLERİ


İlk soru türümüzde uzunluğu, hacmi veya ağırlığı verilmiş bir kaç çeşit maddenin eşit parçalara bölünmesi veya eşit kaplara paylaştırılması problemi üzerine duracağız.

 

Hemen bir örnek soru ile başlayalım.

80 ve 104 litrelik farklı kalitedeki iki çeşit zeytinyağı, birbirine karışmayacak ve artmayacak şekilde eşit hacimli şişelere konularak satılacaktır. Her bir şişenin hacmi en fazla kaç litre olabilir?

Bu soruda şekildeki gibi farklı miktarda zeytinyağlarımız var. 80 litre olana A, 104 litre olana B diyelim.

Yağ şişeleri

Bu yağları eşit hacimde şişelere aktaracağımız için A türünden doldurulmuş şişe sayısı, B’den daha az olacaktır. Burada bizim amacımız, A ve B’yi paylaştıracağımız her bir şişenin hacmini bulmak. Aslında, bunun için birden çok alternatifimiz bulunmakta.

Örneğin, her biri 1 litre olan şişelere, her iki zeytinyağını da hiç artmayacak şekilde paylaştırabiliriz. Bu durumda, A için 80 şişe ve B için 104 şişe kullanmamız gerekir.

Paylaştırmayı, 2 litrelik şişelerle de yapabiliriz. Eğer 2 litreliklerden kullanırsak, A için 40 ve B için 52 şişe kullanmamız gerekir.

Fakat, 3 litrelik şişelerden kullanamayız. Çünkü, A zeytinyağını 3 litrelik şişelere paylaştırdığımızda, 26 şişe tam dolar (toplam 26x3 litre=78 litre) ve 2 litre zeytinyağımız artar. Benzer şekilde, B yağı 34 şişeyi tam doldurur ve 2 litre yağ açıkta kalır.

1 ve 2 litrelik şişeleri kullanabilip, 3 litrelik olanları kullanamamızın nedeni, 1 ve 2 sayılarının 80 ve 104’ü kalansız bölüp, 3’ün ise bu sayıları bölememesidir. Başka bir değişle, 1 ve 2’nin 80 ve 104’ün ortak böleni olup 3’ün olmamasıdır.

Soruda bizden istenilen şey, en büyük hacimli şişe olduğu için, en büyük ortak böleni yani EBOB’u bulmamız gerekir. 80 ve 104’ün EBOB’u,

EBOB

yukarıdaki ortak bölen listesinden

$$EBOB(80, 104)=2 \times2\times2=8$$

çıkar. Bu nedenle, sorudaki şartlara uyan en büyük şişe boyutu 8 litredir.


Eğer soruda, bizden en az şişe sayısını istiyorsa, önce EBOB kullanarak en büyük hacimli şişelerin hacmini bulup, daha sonra toplam hacmi EBOB’a bölebiliriz. Örneğin, bu soru için toplamda $104+80=184$ litre yağımız ve $8$ litrelik şişelerden kullandığımızdan, en az

$${184\over 8}=23$$

eşit hacimli şişe kullanmamız gerekir.


Aynı sorunun 2 yerine 3 veya daha fazla çeşit maddenin karşıtırılmadan küçük kaplara paylaştırılma problemleriyle de karşılaşabiliriz.

Sırasıyla 60, 90 ve 115 kilogram olan nohut, fasulye ve bulgurun tümü, birbirine karıştırılmadan eşit ağırlıkta paketlenecektir. En az kaç paket kullanılmalıdır?

Bir önceki soru mantığını bu defa üç çeşit ürün için kullanacağız. Bu soruda da, gene ürünlerin hiç artmaması için paketlerin ağırlığının hem 60 hem 90 hem de 115’in çarpanı (böleni) olması gerekir. Olası ağırlıklar (bölenler) arasındaki en fazlasını EBOB ile buluruz.

EBOB

$EBOB (60, 90, 115)=5$ olduğu için, en fazla $5$kg’lık paketler kullanılabilir. Toplamda, $60+90+115=265$kg bakliyat olduğu için, en az $265/5=53$ paket kullanılmalıdır.


Çubuk, kereste vs gibi uzunluğu verilmiş katı cisimleri en büyük uzunlukta eşit parçalara bölme de bu kategoride yer alır. Aşağıdaki örneği inceleyelim.

10, 12 ve 14 metre keresteler, hiç artmayacak şekilde, en büyük uzunluğa sahip eşit parçalar halinde kesilmek isteniyor. Kesme işlemi sonucunda kaç parçaya sahip oluruz?

EBOB

Ortak bölenler listesinden, EBOB(10, 12, 14)=2 buluruz. Bu nedenle her bir parçanın boyu en fazla $2$m olabilir. Toplam $10+12+14=36$ metre kereste olduğuna göre, $36m/2m=18$ parçaya sahip oluruz.