Güvercin Deliği İlkesi Problemi - Daire

Question

Aşağıdaki talimatla bir ev ödevi problemi üzerinde çalışıyorum:

Büyük bir şovda oturmuş ve söyleme dairesinde farklı isimler taşıyan 2 n öğrencilik bir sınıf olduğunu varsayalım . Öğretmen ödevini geri verir, ancak çemberdeki her öğrenciye başka bir öğrencinin ödevi verilir. Bu nedenle sınıf, ödevini sağında oturan öğrenciye vermeyi kabul eder. Bir kez daha isimler yanlış. Bunu ilk n kez yaptıklarında, hepsinde yanlış adlandırılmış ödev var. Yani hepsinde, her öğrencinin başka birinin ev ödeviyle eşleştirildiği n + 1 konfigürasyonu vardır). Ödevleri sağlarına geçirmeye devam ederlerse, sonunda 3 öğrencinin kendi isimleriyle ev ödevlerini aldığı bir konfigürasyona ulaşacaklarını gösterin.

Güvercin deliği prensibiyle birkaç sorun yaşadım, ancak bu bana istisnai olarak daha fazla sorun çıkarıyor. Yani, iki ayrı durumlarda gösterdik hem burada = 2n 4. Büyük harfler bir sınıf büyüklüğü hem de sonuç çocuk ve küçük harf, karşılık gelen ödevler vardır.

4 sınıfı ile test edin

Yukarıdaki başlangıç ​​konfigürasyonuyla, üç öğrencinin aynı anda sadece iki tane olmak üzere doğru ödevini aynı anda aldığı bir yer olmasını sağlayamadım. Ayrıca görünen kısıtlamaların hiçbirini bozmadım:

1. Her öğrenci ödevini başlangıçta almıyor
2. Her öğrencinin 1 tur geçtikten sonra ödevi yoktur

Çizimlerdeki ikinci durum, sol taraftaki öğrencinin ödevini yaptığında ne olacağını örneklemektir, yani sadece bir geçiş gerektirir. Ancak, sorunun buna izin verilmediğini söylediğinden oldukça eminim

Bu nedenle sınıf, ödevini sağında oturan öğrenciye vermeyi kabul eder. Bir kez daha isimler yanlış.

Yani, ilk geçişten sonraki turda hiç kimsenin ödevinin olmadığından emin olması gerekir. Sorunun önerdiği şeyin doğru olduğuna inanıyorum, ancak onu anlamakta ve Pigeonhole ilkesini uygulamakta güçlük çekiyorum. Çocukların "delikleri" ve onun "güvercinleri" ödev mi ve eğer öyleyse, delikteki bir güvercin kadar basit değil , doğru delikte doğru güvercin olduğu durumda nasıl hesaplanır ? Herhangi bir yardım memnuniyetle karşılanacaktır.

Answer 1

Tam bir performans sergilersek $2n - 1$geçer, sonra herkes ödevini tam olarak bir kez gördü. Biliyoruz ki ilk$n$ ilk geçer $n + 1$konfigürasyonlar, kimse ödevini görmedi. Kalanlara devam edersek$n - 1$konfigürasyonları ve en fazla 2 öğrenci ev ödevlerini her konfigürasyonda görür, en fazla kaç öğrenci ev ödevini gördü? Bu, daha önce söylediklerimizle nasıl çelişiyor?

Answer 2

İşte ona nasıl yaklaşabileceğiniz. Boşlukları kendiniz doldurun.

Genellikle PP uygularken, deliklerin ve güvercinlerin ne olduğu konusunda net olmak çok önemlidir. Bunları tanımlamak genellikle harika bir başlangıçtır, bu nedenle:
Delikler "Öğrencilere ev ödevlerinin dönüşümlü olarak verildiği konfigürasyonlar olsun$k$Zaman".
güvercinler olalım 'Öğrenci doğru ev ödevi' vardır.

Bu tanımların kullanılacak doğru tanımlar olduğunu varsayarak, PP'nin nasıl çalıştığını inceleyelim:
Kaç tane güvercin var?
3 güvercin ile bir delik olmasını sağlamak için sahip olabileceğimiz maksimum delik sayısı nedir?
En fazla bu kadar deliğimiz olduğunu gösterebilir miyiz? Hayır ise, delikleri (veya güvercinleri) nasıl değiştirebiliriz?

---

Tam delik sayısının ne olduğu konusunda bazı belirsizlikler var.

• Delik sayısı ise $n-1$ (var olduğu anlamına gelir $n+1$ tamamen uyumsuz konfigürasyonlar), daha sonra PP doğrudan çalışır.
• Delik sayısı ise $n$ (var olduğu anlamına gelir $n$tamamen uyumsuz yapılandırmalar), o zaman soru yanlıştır. Özellikle, ifade bile doğrudur$n$ ve garip için yanlış $n$. Bu, 1) "tam olarak 2 kağıt eşleşiyor" ile çelişki ile kanıtlanabilir.$n$ eşittir "ve 2)" için tam olarak 2 kağıt eşleşmesi için bir vaka oluşturma $n$ garip".