İşçi sayısı problemi

[Metin Can Aydemir]

Problem [Metin Aydemir]: Bir iş yerinde, haftanın beş iş günü çalışılmaktadır, hafta sonları ise tatildir. Her işçi, bir haftada en fazla $2$ gün işe gelmeyebilir. İş yerinde her gün çalışan kişi sayısı sırasıyla $A_1, A_2, A_3, A_4, A_5$ ile gösterilsin. Eğer $$2A_5 \geq A_1 \geq A_2 \geq A_3 \geq A_4 \geq A_5\geq 1$$ şartı sağlanıyor ve yalnızca $A_1, \dots, A_5$ değerlerine bakarak iş yerinde kaç kişinin çalıştığı kesin olarak bilinebiliyorsa, bu durumu sağlayan $(A_1, A_2, \dots, A_5)$ beşlileri neler olabilir?

[yusufardabaykal]

Emin olmamakla beraber (1,1,1,1,1), (2,1,1,1,1), (2,2,1,1,1), (2,2,2,1,1) ve (3,2,2,2,2) beşlilerinde sağlanacağını düşünüyorum.
Latex kullanmayı bilmiyorum kusura bakmayın. Sözlü dille anlatabildiğim kadar anlatacağım.
A1+A2+A3+A4+A5 sayısına y doğal sayısı diyelim. işçi sayımıza da x doğal sayısı diyelim.
bir işçi en fazla 2 gün işe gidemiyorsa bu 3x<=y<=5x yapar. ve A1'den A5'e kadar baktığımızda x değerini öğrenebildiğimiz söyleniyor soruda bu da belli bir y sayısında sadece birer tane a ve x değeri elde edebileceğimizi gösterir. y sayısını ax olarak ele alalım. a bariz şekilde işçilerin işe gitme oranlarının ortalaması oluyor. zaten 3x<=ax<=5x olarak baktığımızda 3<=a<=5 oluyor. Bundan sonra şu şekilde bakabiliriz
x=1      min(y)=3(*)     max(y)=5
x=2    6    10
x=3    9     15
x=4    12    20
x=5    15    25
x=6    18    30
.
.
.
(*) 2A5>=A1>=...>=A5 olduğundan dolayı A5 en küçük 1 olduğunda y minimum 5 gelir.

Bu liste uzar. zaten burada göstermek istediğim y>=5 durumların hangilerinin sadece bir adet x karşılığı olur bunu göstermekti. Listeden alabileceğimiz sayılar 5,6,7,8 ve 11 oluyor. İspatını yapamam ama gerisinde de yoktur. Aralıklar çok büyüyor. Sağlamasını yapalım
5/1 = 5 --> 3<=5<=5 doğru
5/2 = 2.5 --> 3<=2.5<=5 yanlış
y=5 için tek x değeri vardır. x=1
6/1 = 6 --> 3<=6<=5 yanlış
6/2 = 3 --> 3<=3<=5 doğru
6/3 = 2 --> 3<=2<=5 yanlış
y=6 için tek x değeri vardır. x=2
7/1 = 7 --> 3<=7<=5 yanlış
7/2 = 3.5 --> 3<=3.5<=5 doğru
7/3 = 2.33... --> 3<=2.33...<=5 yanlış
y=7 için tek x değeri vardır. x=2
8/1 = 8 --> 3<=8<=5 yanlış
8/2 = 4 --> 3<=4<=5 doğru
8/3 = 2.66... --> 3<=2.66...<=5 yanlış
y=8 için tek x değeri vardır. x=2
11/1 = 11 --> 3<=11<=5 yanlış
11/2 = 5.5 --> 3<=5.5<=5 yanlış
11/3 = 3.66... --> 3<=3.66...<=5 doğru
11/4 = 2.75 --> 3<=2.75<=5 yanlış
y=11 için tek x değeri vardır. x=3

A1'den A5'e kadar artmayan bir şekilde yazmamız gerek hangi gün kaç kişi çalıştığını. Soruda verilmiş zaten bu.
y=5 için (1,1,1,1,1)
y=6 için (2,1,1,1,1)
y=7 için (2,2,1,1,1)
y=8 için (2,2,2,1,1)
y=11 için (3,2,2,2,2)

Yanlışım varsa söyleyin. Hatta benim açıklamam biraz yavan kalmış olabilir. Daha düzenli açıklayacak biri çevirirse güzel olur.

[Metin Can Aydemir]

Çalışan kişi sayısı $K$ olsun. Öncelikle verilen şartlar altında $K=A_1$ olabileceğini gösterelim. $K<A_1$ olamayacağı barizdir çünkü $1.$ gün çalışan kişi sayısı $K$'dan fazla olamaz.

$K=A_1$ durumuna örnek için tersten ilerleyelim.

$1.$ Gün: $A_1$ kişi çalışıyor. Yani $0$ kişi çalışmıyor.
$2.$ Gün: $A_2$ kişi çalışıyor. Yani $A_1-A_2$ kişi çalışmıyor.
$3.$ Gün: $A_3$ kişi çalışıyor. Yani $A_1-A_3$ kişi çalışmıyor.
$4.$ Gün: $A_4$ kişi çalışıyor. Yani $A_1-A_4$ kişi çalışmıyor.
$5.$ Gün: $A_5$ kişi çalışıyor. Yani $A_1-A_5$ kişi çalışmıyor.

$2.$ ve $3.$ gün işe gelmeyen $A_1-A_2$ kişi olsun. $4.$ ve $5.$ gün işe gelmeyen ise $A_1-A_4$ kişi olsun. Bu kişileri çıkartırsak geriye $3.$ gün çalışan $A_2-A_3$ kişi ve $5.$ gün çalışan $A_4-A_5$ kişi kalır. Bunların da $\min\{A_2-A_3,A_4-A_5\}$ kişisi bu iki gün çalışırsa geriye $\max\{A_2-A_3,A_4-A_5\}-\min\{A_2-A_3,A_4-A_5\}$ kişi kalır. Bunlar da $1$ gün çalışan kişiler olsun.

Sonuç olarak bu düzenle $(A_1-A_2)+(A_1-A_4)+\min\{A_2-A_3,A_4-A_5\}$ kişi iki gün işe gelmiyor, $\max\{A_2-A_3,A_4-A_5\}-\min\{A_2-A_3,A_4-A_5\}$ kişi de sadece bir gün işe gelmiyor. Bu sayıların negatif olmadığı barizdir. Her gün işe gelen kişi sayısı $$A_2+A_4-A_1-\max\{A_2-A_3,A_4-A_5\}$$ kişi olacaktır. Eğer bu sayı sıfırdan büyük veya eşitse, oluşturduğumuz sistem ile toplam $K=A_1$ kişinin çalışabileceğini göstermiş oluruz. $$A_2+A_4\geq A_1+\max\{A_2-A_3,A_4-A_5\}$$ $$\iff A_2+A_4\geq A_1+(A_2-A_3)\quad \text{ve}\quad A_2+A_4\geq A_1+(A_4-A_5)$$ $$\iff A_3+A_4\geq A_1\quad \text{ve}\quad A_2+A_5\geq A_1$$ olacaktır. $2A_5\geq A_1$ olduğundan bu eşitsizlikler doğrudur. Dolayısıyla $K=A_1$ olabilir.

Eğer tek bir $K$ değeri olacaksa bu $A_1$ olmak zorundadır. Yani $K=A_1+1$ durumu imkansız olmalıdır. $K=A_1+1$ için aynı çalışan dağıtma yöntemini kullanırsak,

$1.$ Gün: $A_1$ kişi çalışıyor. Yani $1$ kişi çalışmıyor.
$2.$ Gün: $A_2$ kişi çalışıyor. Yani $A_1-A_2+1$ kişi çalışmıyor.
$3.$ Gün: $A_3$ kişi çalışıyor. Yani $A_1-A_3+1$ kişi çalışmıyor.
$4.$ Gün: $A_4$ kişi çalışıyor. Yani $A_1-A_4+1$ kişi çalışmıyor.
$5.$ Gün: $A_5$ kişi çalışıyor. Yani $A_1-A_5+1$ kişi çalışmıyor.

Daha önce yaptığımız gibi $2.$ ve $3.$ gün çalışmayanları birleştirmekle başlayıp devam edersek, iki gün çalışmayan kişi sayısı $(A_1-A_2+1)+(A_1-A_4+1)+\min\{A_2-A_3,A_4-A_5\}$ olacak, sadece bir gün çalışmayan kişi sayısı da $1+\max\{A_2-A_3,A_4-A_5\}-\min\{A_2-A_3,A_4-A_5\}$ olacaktır. Bu sayılar her zaman sıfır veya pozitif olacaktır. Her gün işe gelen kişi sayısı $$A_2+A_4-A_1-\max\{A_2-A_3,A_4-A_5\}-2$$ olmalıdır. Bu sayı negatif değilse $K=A_1+1$ olabilir demektir ki bu da sorudaki kabule bir çelişkidir. Bu yüzden bu sayı negatiftir. Daha öncesinde $$A_2+A_4-A_1-\max\{A_2-A_3,A_4-A_5\}\geq 0$$ olduğunu göstermiştik. Bunu da hesaba katarsak, $$A_2+A_4-A_1-\max\{A_2-A_3,A_4-A_5\}=0\text{ veya }1$$ olmalıdır.

Eğer $A_4-A_5>A_2-A_3$ ise $A_4-A_5\geq 1$ ve $A_2\geq A_4\geq A_5+1$ olacaktır. $$A_2+A_4-A_1-(A_4-A_5)=A_2+A_5-A_1=0\text{ veya }1$$ eşitliğini inceleyelim. Bu eşitsizliği düzenlersek, $$(A_2-A_5)+(2A_5-A_1)=0\text{ veya }1$$ elde edilir. $A_2-A_5\geq 1$ ve $2A_5\geq A_1$ olduğundan eşitlik sağlanmalıdır. $A_1=2A_5$ ve $A_2=A_5+1$ olmalıdır. $A_4-A_5\leq A_2-A_5$ olduğundan $1\leq A_4-A_5=A_2-A_5=1$ olmalıdır ve bu durumda da $A_2=A_3=A_4$ elde edilir. Sonuç olarak, $(A_1,A_2,A_3,A_4,A_5)=(2k,k+1,k+1,k+1,k)$ çözüm adayı elde edilir (bunun gerçekten bir çözüm olup olmadığı en son kontrol edilecektir.)

Eğer $A_2-A_3\geq A_4-A_5$ ise $$A_3+A_4-A_1=0\text{ veya }1$$ olacaktır. Bu durumda da $$(A_3-A_5)+(A_4-A_5)+(2A_5-A_1)=0\text{ veya }1$$ olacağından $(A_1,A_2,A_3,A_4,A_5)=(2k,m,k+1,k,k), (2k,m,k,k,k),(2k-1,m,k,k,k)$ olabilir.

Sonuç olarak $m\in [A_1, A_3]$ olmak şartıyla, tüm çözüm adayları $(A_1,A_2,A_3,A_4,A_5)=(2k,k+1,k+1,k+1,k),(2k,m,k+1,k,k), (2k,m,k,k,k),(2k-1,m,k,k,k)$ formatında olacaktır.

Bunların çözüm olup olmadığını kontrol etmek için $a\geq 1$ ve $K=A_1+a$ için en iyi durumda bile çelişki bulmalıyız. En iyi durumu da olabildiğince çok kişiyi iki gün tatilde tutarak elde edebiliriz.

$(2k,k+1,k+1,k+1,k)$ ve $K=2k+a$ durumunda en iyi durum $a+k-1$ kişinin $2.$ ve $3.$ günler tatil yapması, $a+k-1$ kişinin $4.$ ve $5.$ günler yapması, $1$ kişinin $1.$ ve $5.$ günler yapıp, $a-1$ kişinin sadece $1$. gün tatil yapmasıyla elde edilir. Bu durumda en az $2k+3a-2$ çalışan gerekir ve $a=1$ olursa $K=2k+a\geq 2k+3a-2$ olacağından bu mümkündür. Bu da $K=A_1$ ve $K=A_1+1$ olabileceği anlamına gelir ki, bu da bu adayın çözüm olmadığı sonucunu doğurur.

$(2k,m,k+1,k,k)$ ve $K=2k+a$ durumunda en iyi durum $k+a$ kişinin $4.$ ve $5.$ gün tatil yapması, $2k+a-m$ kişinin $2.$ ve $3.$ gün tatil yapması, $\min\{a,m-k-1\}$ kişinin $1.$ ve $2.$ gün tatil yapması, geri kalan $\max\{a,m-k-1\}-\min\{a,m-k-1\}$ kişinin de tek gün tatil yapmasıdır. Bu durumda en az $$(k+a)+(2k+a-m)+\min\{a,m-k-1\}+(\max\{a,m-k-1\}-\min\{a,m-k-1\})$$ $$=3k+2a-m+\max\{a,m-k-1\}$$ çalışan olmalıdır. $a=1$ durumunda eğer $m>k+1$ ise $$3k+2-m+\max\{1,m-k-1\}=3k+2-m+m-k-1=2k+1$$ olacağından $K=2k+1$ için uygun düzenleme mümkündür. $m=k+1$ durumunda ise $$3k+2a-m+\max\{a,m-k-1\}=2k+3a-1>2k+a=K$$ olacağından en iyi durumda bile $K=2k+a$'dan daha fazla çalışan gerekmektedir. Dolayısıyla, bu durumdan sadece $m=k+1$ uygundur. $$\boxed{(A_1,A_2,A_3,A_4,A_5)=(2k,k+1,k+1,k,k)}$$ bir çözümdür.

$(2k,m,k,k,k)$ ve $K=2k+a$ durumunda en iyi durumda, yukarıdakine benzer şekilde, en az $$3k+2a-m+\max\{a,m-k\}$$ çalışan gerekmektedir. $$3k+2a-m+\max\{a,m-k\}\geq 3k+2a-m+m-k=2k+2a>2k+a=K$$ olduğundan her durumda $K=2k+a$ çalışan imkansızdır. Yani $k\leq m\leq 2k$ için $$\boxed{(A_1,A_2,A_3,A_4,A_5)=(2k,m,k,k,k)}$$ çözümdür.


$(2k-1,m,k,k,k)$ ve $K=2k+a$ durumunda (bu sefer $a\geq 0$'dır) en iyi durumda, yukarıdakine benzer şekilde, en az $$3k+2a-m+\max\{a+1,m-k\}$$ çalışan gerekmektedir. $a\geq 1$ olduğunda $$3k+2a-m+\max\{a+1,m-k\}\geq 3k+2a-m+m-k=2k+2a>2k+a=K$$ olduğundan sadece $a=0$ durumunu incelemeliyiz. $m-k>0$ ise $$3k+2a-m+\max\{a+1,m-k\}=2k=K$$ olacağından hem $K=2k-1$, hem de $K=2k$ istenileni sağlar. Bu da çelişkidir. $m=k$ ise $$3k+2a-m+\max\{a+1,m-k\}=2k+3a+1>2k+a=K$$ olacağından sadece $m=k$ durumu mümkündür. Yani sadece $$\boxed{(A_1,A_2,A_3,A_4,A_5)=(2k-1,k,k,k,k)}$$ çözümdür.

Tüm çözümler, $1\leq k\leq m\leq 2k$ olmak üzere, $(A_1,A_2,A_3,A_4,A_5)=(2k,k+1,k+1,k,k), (2k-1,k,k,k,k), (2k,m,k,k,k)$ formatındadır.