Matematika Diskrit

Yayan Eryk Setiawan, S.Pd.

Bagian Ke-2

Prinsip Pigeonhole memang sederhana: Semua orang segera memahami. Namun demikian, namanya layak, karena kami menggunakannya sangat sering sebagai alat dasar banyak bukti.

Formulasi dengan menggunakan merpati (Pigeons) dan lubang (holes) mereka, ini disebut sebagai Prinsip Pigeonhole.

Kita akan melihat banyak contoh untuk penggunaan Prinsip Pigeonhole, kita membahas salah satu contoh dari penggunaan prinsip pigeonhole.

Kami menembak 50

tembakan pada target

persegi, yang panjang sisinya

adalah 70 cm. Tembakan

kami cukup baik, karena

semua tembakan kami

mencapai target.

Buktikan bahwa ada dua

bulletholes yang lebih dekat

dari 15 cm!

Contoh

Bayangkan bahwa target

kami adalah papan catur

tua.

Terdapat 8 baris dan 8

kolom, sehingga memiliki 64

kotak.

Satu baris dan satu kolom

itu telah hilang, sehingga

memiliki 49 kotak.

Solusi:

Papan menerima 50 tembakan,

sehingga harus ada persegi

yang menerima sedikitnya dua

tembakan (menempatkan

bulletholes di pigeonholes) .

Kami mengklaim bahwa dua

tembakan ini lebih dekat dengan

masing-masing selain 15 cm.

Sisi persegi adalah 10 cm,

diagonalnya adalah sama,

dan (dari Teorema

Pythagoras) panjangnya

adalah √ 200 = 14,1 cm.

Kami menunjukkan bahwa

(*) Dua tembakan tidak

dapat berada pada jarak

lebih panjang dari diagonal.

Hal ini secara intuitif jelas

bahwa dua poin di papan

persegi pada jarak

terbesar adalah titik akhir

dari salah satu diagonal,

Tapi intuisi bisa

menyesatkan; Biarkan

kami membuktikan ini.

Misalkan dua poin P dan

Q yang lebih jauh dari

panjang diagonal.

Misalkan A, B, C, dan D menjadi simpul dari papan persegi. Hubungkan P dan Q oleh bantuan baris, dan membiarkan P’ dan Q’ menjadi dua titik di mana ini garis memotong batas papan persegi (Gambar 2.2).

Maka jarak P’ dan Q’ lebih panjang, sehingga juga lebih panjang dari diagonal.

Gambar 2.2

Kita menganggap P’ terletak di sisi

AB (jika hal ini tidak terjadi, kami

mengubah nama simpul).

Salah satu sudut Q’P’A dan Q’P’B

setidaknya 900; kita bisa

mengasumsikan (lagi tanpa

kehilangan umum) yang Q’P’A

adalah sudut ini.

Kemudian segmen AQ’ adalah sisi

segitiga Q’P’A berlawanan sudut

terbesar, dan itu membuat lebih

panjang dari P’Q’, dan karena itu

lebih panjang dari diagonal.

Kami mengulangi argumen ini untuk

menunjukkan bahwa jika kita

mengganti Q’ oleh salah satu point

terakhir dari sisi itu terletak di, kita

mendapatkan segmen yang lebih

panjang dari diagonal.

Tapi sekarang kita memiliki segmen

kedua yang point terakhir adalah

simpul papan persegi. Jadi segmen

ini baik sisi atau diagonal dari papan

persegi, dan dalam kedua kasus itu

lebih panjang dari diagonal !

Kontradiksi ini menunjukkan bahwa

pernyataan di atas harus benar.

Jadi kita punya dua

tembakan yang lebih

dekat dari 15 cm,

bahkan lebih dekat

dari 14,2 cm.

Kita mengasumsikan bahwa

pernyataan itu tidak benar,

dan kemudian menggunakan

asumsi tambahan ini, kami

berpendapat sampai kami

punya kontradiksi. Bentuk

bukti adalah disebut tidak

langsung, dan ini cukup

sering digunakan dalam

penalaran matematika,

Prinsip Pigeonholes diformulasikan dengan menggunakan merpati (Pigeons) dan lubang (holes) mereka, Prinsip Pigeonhole sederhana dan digunakan sebagai dasar untuk membuktikan.

Prinsip umum Pigeonholes adalah “Jika kita memiliki n kotak dan kami menempatkan lebih dari n objek ke dalam kotak, maka akan ada setidaknya satu kotak yang berisi lebih dari satu objek”.

Jika tidak, mari kita mencoba

latihan berikut !

Dapat kita temukan di New York dua orang memiliki jumlah yang sama dari helai rambut?

Satu akan berpikir bahwa tidak mungkin untuk menjawab pertanyaan ini, karena salah satu bahkan tidak tahu berapa banyak helai rambut yang ada pada kepala diri sendiri, apalagi tentang jumlah helai rambut di setiap orang yang tinggal di New York (jumlah yang pasti dalam dirinya sendiri cukup sulit untuk menentukan). tapi ada beberapa fakta yang kita tahu pasti: Tidak ada yang memiliki lebih dari 500.000 helai rambut (pengamatan ilmiah), dan ada lebih dari 10 juta penduduk New York

Bisakah kita sekarang menjawab

pertanyaan awal kita? Ya. Jika

tidak ada dua orang dengan jumlah

helai rambut yang sama, kemudian

akan ada paling banyak satu orang

yang memiliki 0 helai, paling

banyak satu orang memiliki tepat 1

untai, dan seterusnya. Akhirnya,

akan ada paling banyak satu

Seseorang yang memiliki persis

500.000 helai. Tapi kemudian ini

berarti bahwa ada tidak lebih dari

500.001 penduduk New York.

Buktikan bahwa kita dapat memilih

20 warga New York yang

semuanya memiliki jumlah yang

sama dari helai rambut.