Akademisyenler öncülüğünde matematik/fizik/bilgisayar bilimleri soru cevap platformu
1 beğenilme 0 beğenilmeme
1.4k kez görüntülendi
100 tane oyuncu ve 100 tane sandalye var. Her oyuncunun ve sandalyenin kendine ait bir numarasi var.

Oyuncular 1. oyuncudan sonra sirayla sandalyelere oturacaklar. Eger kendi sayilarina denk dusen sandalye bossa oraya oturacaklar degilse istedikleri yere oturmakta serbestler.

Birinci oyuncu 2. sandalyeye oturduguna gore sonuncu oyuncu hangi sandalyeye veya sandalyelere oturabilir?
Serbest kategorisinde (1.6k puan) tarafından  | 1.4k kez görüntülendi
100 oyuncu yerine 3 oyuncu düşünelim: 2,1,3 ve 2,3,1 durumları mümkün olan tüm durumlar. Burada bu sayı dizilerinde n'inci terim n'inci kişinin oturduğu sandalyeyi gösteriyor.

4 oyuncu için sadece 2,1,3,4 ve 2,3,1,4 ve 2,3,4,1 ve 2,4,3,1 durumları mümkün.

Doğru anlamış mıyım?
5 oyuncu için mümkün olan bütün durumlar:

2,1,3,4,5 ve 2,3,1,4,5 ve 2,3,4,1,5 ve 2,3,4,5,1 ve 2,4,3,1,5 ve 2,4,3,5,1 ve 2,5,3,4,1

Haydaaa...

2,1,3,4,5 nasil oldu ?
2. oyuncu 1. sandalyeye oturunca 3. sandalye bos kaldigi icin 3. oyuncu 3. sandalyeye oturmali

ya ben siralamani anlamadim galiba sayilar oyuncu mu sandalye mi kafam karisti. kural soyle numaram $n$ ise ve $n$ inci sandalye bossa oraya oturmak zorundayim bos degilse herhangi bir sandalyeye oturabilirim
ya benim kafam karisti
2,3,4,5,1 ve 2,4,3,1,5 ve 2,4,3,5,1 ve 2,5,3,4,1

bunlari nasil elde ettin?
5 li durum icin benim elde ettiklerim

2-1-3-4-5

3-1-2-4-5

4-1-2-3-5

5-1-2-3-4

.....
En başta belirttiğim gibi n'inci sayı n'inci kişinin oturduğu sandalye. O yüzden dizi 2 ile başlamalı benim yazdığım şekilde.

Seninkinde n'inci sayı n'inci sandalyeye oturan kişi.

Galiba aynı şeyi söylüyoruz ama.
Tam olarak birbirimizin ters fonksiyonunu söylüyoruz. Hangisi daha iyi bilemedim.
bence çözümler baya değişebilir.

2 ile herhangi biri koltuk sayısını takaslar ise.

oyuncu -sıra

1-2

2-5 (olsun)

3-3

4-4

5-2(olur) aşağı doğru kalanı değişmez.

ancak 5 ,2den farklı bir koltuk seçerse işler karışır.Burada direk kombinasyon hesabı bile yapılabilir sanırım.(ben yapamam)

eksik düşündüğüm yer varsa yüzüme vurun lütfen =)
5'i 1'in kucağına mı oturttun?
ohohohooh hocam canlı yayın,neyse ^^

oyuncu-sıra diye ayırdım gözden kaçmış olabilir.

2-5 =)
Ya anlamadım ben :(

1 numaralı kişiyi 2 numaralı sandalyeye oturttun.

2 numaralı kişiyi 5 numaralı sandalyeye

3 3'e

4 4'e

E bu durumda boş kalan tek sandalye 1 numaralı sandalye. Yani 5 numaralı kişi 1 numaralı sandalyeye oturmak zorunda kaldı?
5 dolu olduğu için ,5.oyuncu üstediği yere oturabilirmiş.

hakları var :)
Aaah haklısın, ne diyeyim :)
veya soruyu her seferinde farklı okuyoruz,sürekli değişik geliyoda olabilir :)

2 Cevaplar

1 beğenilme 0 beğenilmeme
En İyi Cevap

Biraz düzeltme yaptım (* ile işaretli yerlerde):

Çok güzel bir soru.
    Herhangi bir $n\quad (n>1)$ için, böyle bir yerleştirmede, sonuncu kişinin, ya kendi sandalyesine ya da 1. sandalyeye oturmak zorunda olduğunu ispatlayacağız.
    Böyle bir yerleştirme bir permütasyondur: $ \sigma\in S_n,\ \sigma(k)=k. $ kişinin oturduğu sandalyenin numarası.

(Benim notasyonum, OkkesDulgerci ninkinden farklı)
    $ \sigma(1)=2 $ olduğu verilmiş.
    Bunun için önce şunu göstereceğiz:
    Lemma (Önsav): Böyle bir yerleşmede:
    Ya ($ n $. kişi dışındaki) herkes kendi numarasından bir fazla numaralı (ve $ n $. kişi 1.) sandalyeye oturur ya da en az bir kişi kendi sandalyesine oturur ( $\sigma_0=(1,2,3,\ldots,n)\in S_n $ devri olması ya da bir sabit noktası olması).
    (Burada $ \sigma_0 $ yazarken  $ n $ yi gözardı ediyorum)
    
    Daha sonra, sorudaki iddia, tümevarım ile ispatlanacaktır.
    
    Önsavın ispatı: $ \sigma\neq\sigma_0 $ olsun.
    $k=\max\{j:\sigma(i)=i+1\ \forall i< j\}  $ olsun. $ 2\leq k<n $ dir. (*: Daha önce $1\leq k<n$ yazmıştım)
    Bu durumda $ \sigma(k)=1 $ ya da $ \sigma(k)>k+1 $ olur. her iki durumda da $ \sigma(k+1)=k+1 $ olup permütasyonun sabit noktası vardır.
    
    İddianın ispatı:
    $ n=2 $ için iddianın doğruluğu aşikardır, çünki $\sigma=\sigma_0$ olmak zorundadır.
    Bir $ n\geq2 $ için iddiamız doğru olsun.
    $ \sigma\in S_{n+1} $ böyle bir permütasyon olsun.
    $\sigma=\sigma_0$ ise $\sigma(n+1)=1$ olur.
    $ \sigma\neq\sigma_0 $ ise $\sigma$ nın bir sabit bıraktığı  $ 2<k\leq n+1 $ sayısı vardır. $ k=n+1 $ ise zaten $ \sigma(n+1)=n+1 $ olur. $ 2<k<n+1 $ durumunu inceleyelim. (Bu ayırıma gerek de yok aslında)
    Şimdi sabit noktayı silip bir $ \sigma'\in S_{n} $ şöyle oluşturabiliriz:
$ k $ numaralı     kişi ve sandalyeyi çıkarıp, geriye kalan sandalye ve kişilerde, numarası $ k $ dan büyük olanların numarasını 1 azaltırız.
    $ \sigma'(i)=\begin{cases}\sigma(i)&i<k,\sigma(i)<k\\\sigma(i)-1& i<k,\sigma(i)>k\\\sigma(i-1)&i>k,\sigma(i)<k\\\sigma(i-1)-1& i>k,\sigma(i-1)>k\end{cases} $
    Bu permütasyon da (kişi ve sandalyelerde yeni numaralar ile) sorudaki koşulları sağlar (bunu göstermek sıkıcı ama zor değil). Tümevarım hipotezinden, $\sigma'(n)=1$ veya $ \sigma'(n)=n $ dir.
    Buradan (numaralar değiştiği için, burası biraz özen gerektirir) $ \sigma(n+1)=n+1 $ veya $ \sigma(n+1)=1 $ elde edilir. (*: Olası durumların sırasını, yukarıdaki durumlara uyumlu olması için değiştirdim)

(6.1k puan) tarafından 
tarafından düzenlendi
1 beğenilme 0 beğenilmeme

100. kisinin 1. veya 100. sandalyeye oturmasini garantileyebiliriz.. Bunu yapmak cok kolay.

 

1. Durum ) 2. kisi rasgele secim yaptiginda 1. sandalyeyi secerse, kalanlar 3.,4.,5.,....,100. sandalyeye oturmak zorunda.

2. Durum ) 2. kisi rasgele secim yaptiginda 3. sandalyeyi secerse, 3. kisi 4. sandalyeyi secerse,.... yani herkes kendi sandalyesinin sayisinin bir fazlasini secerse,  100. kisi 1. sandalyeyi secmek zorunda kalir.

 

Baska bir durum yok gibi duruyor?

 

____________________________________________________

 

Ekleme:

Biraz otomatik, biraz manuel olarak sunu yaptim. Tam otomatik olmadigi icin az da olsa hatali olma ihtimali vardir.

1. satir sandalye numarasini, 2. satir oturan kisilerin numarasini gosterir. Once 1. kisiyi 2. sandalyeye oturturuz.

Asagidaki resimleri $2\times n$ matris olarak dusunursek hepsinde $2\times2$. elemanin 1 oldugu gorulur ve istenen ön kosulu saglar (Birinci oyuncu 2. sandalyeye oturduguna gore)

n=3 icin:

 

 

n=4 icin:

 

 

n=5 icin:

 

 

n=6 icin:

 

(2.9k puan) tarafından 
tarafından düzenlendi
Belki hangi ihtimalle 1. sandalye hangi ihtimalle son sandalyeye oturdugu da incelenebilir. Birinci oyuncunun diger koltuklara oturma durumu da ayni sonucu verecektir diye tahmin ediyorum ama ilginc bir analiz olabilir gene
"100. kisinin 1. ve 100. sandelyeye oturmasi garanti.. Bunu yapmak cok kolay."
soruya göre bunu nerden çıkarıyoruz tam göremedim sanırım.

2.oyuncu 1. veya 100.sandalyeye oturursa, nasıl bir garantisi olur.ayağı kaymasın ? :)
SilentMary: ben anlamaya başladım galiba. Yukarıda 100 oyuncu için değil de 3,4, ve 5 oyuncu için denedim.
Evet 4 oyuncu icin bakmak yeterli olmali daha sonra her durumun 4 oyunculu duruma reduce oldugunu gorebiliriz
Göremiyorum :(
Toplam durumum $2^{n-2}$ tane  ve $n.$ kisi yarisinda 1. sandalyeye, yarisinda da $n.$ sandalyeye oturuyor gibi duruyor.
bence n i artırarak incelemek mantıksız.n direk olarak 100 seçilip durumlar kontrol edilmeli.2.ye seçtireceğimiz koltuk herşeyi değiştiriyor.ökkeş hocam matematiği çok anlayamadım ona yorum yapmayacağım :)
$n=100$ icin bakilamaz. $2^{98}=316912650057057350374175801344$ cok buyuk sayi.
"n=100 olduğu için çözüm sınırı aşırı büyük,sonuç analitik vede program ile bu değerde çözülmez."

hata kabulü ile ortalama bir çözüm aralığında hesap yapmalıyız.

böylemi özetledik hocam.
@eloi 1'inci oyuncu 2'inci koltuğa değil de (atıyorum) 6'ıncı koltuğa otursun. Bu durumda

2'inci kişi 2'inci koltuğa

3'üncü kişi 3'e

4 4'e

5 5'e

oturmak zorunda. Bu 4 kişiyi oyundan atabiliriz. Bu senaryo 96 kişilik oyunla izomorf. Dolayısıyla evet, 1'inci oyuncu kendi koltuğuna oturmadığı sürece sonuncu oyuncunun iki seçeneği var: birinci koltuk ya da sonuncu koltuk.
@Ozgur, eger 1. kisi baslagincta 6. koltuga oturursa  6,2,3,4,5,1 seklinde tek cozum olur..
@Ozgur ayni olacagini hissetmistim ama gosterememistim guzel oldu :). Olasiliklar da degismiyordur diye hissediyorum
5 kisi varken baslangicta 1. kisi 4. koltuga oturursa yalnizca iki secenek var

{{4, 2, 3, 1, 5}, {5, 2, 3, 1, 4}}

 

Galiba bu butun n ler icin gecerli.

 

Mesela n=100 icin {{99,2,3,4,.....,98,1,100},{100,2,3,4,.....,98,1,99}} olur.
Belki bu durumda soruyu soyle sormak daha eglenceli olabilir.

Birinci oyuncu disinda her oyuncu kendi numarasinin yazdigi sandalye bossa oraya oturmak zorunda, degilse istedigi yere oturabilir. Birinci oyuncu oyunun basinda istedigi sandalyeye oturuyor. Sonuncu oyuncu hangi sandalyelere oturabilir?

 

Sanirim soyle bir genellestirme daha var ama emin degilim. Ilk $k$ oyuncu istedigi yere oturursa, sonuncu oyuncu ya ilk yada son $k$ koltukta oturacak
Burada bir yerde cyclic grup durumu var gibi hissettim
@Okkes 100 kişilik durumdan bahsetmiştim. O zaman 6 numaralı kişi 7 ya da 17 numaralı koltuğa da gidebilir. Ama dediğin gibi 2,3,4 ve 5 kendi koltuklarına gitmek zorundalar. O yüzden onları unutabiliriz. Böylece 96 kişilik duruma indirgemiş oluruz.

Bu arada ben hala bir kanıt bulamadım orijinal soruya genel durumda.
@Ozgur yanilmiyorsam senin yorumundaki ayni mantigi kullanarak sunu da diyemez miyiz
 

birinci ikinci koltuga otursun. ikinci oyuncu 1 e oturursa durum zaten acik. yok eger $k$ ya oturursa oyun 99 kisi ile oynanan oyunun sonucu + birinci koltuga denk. Aradaki koltugu bir sekilde yokedersek soruyu $n=4$ e indirgeyebiliriz
eloi,daha eğlenceli hale getirmek istediğiniz hali ile,sorunun kendi aynı değil mi :D

 

fark nedir ?
Birinci oyuncu daha serbest. Daha estetik duruyor
bir fark göremiyorum ben,yoksa alkolikmiyim

adırvayz

https://www.youtube.com/watch?v=tQjWV9Bhc0g&ab_channel=EURACTIVEURACTIV

0:44
20,200 soru
21,728 cevap
73,275 yorum
1,887,928 kullanıcı