The Art of Counting: Part III – Pigeonhole Principle

Nell’ultima parte, abbiamo parlato del conteggio delle cose con le ripetizioni e sostanzialmente di come dobbiamo solo pensare a partizionare un insieme di oggetti con determinate aste, proprio come in Walmart! Questa volta passeremo a un concetto più nuovo: il Principio di Pigeonhole.

E solo per darti un’idea di quanto sia semplice questo principio nella realtà,

Ma se sei un fanatico delle parole, ecco qui: se n + 1 oggetti sono distribuiti in n caselle, almeno una casella contiene due o più oggetti.

Andiamo subito agli esempi allora.

Esempio 1: le coppie sposate di nuovo

Supponiamo di avere n coppie sposate, quindi 2 persone in totale. Quante persone dobbiamo scegliere almeno in modo tale da avere almeno 1 coppia sposata?

Il modo intuitivo per farlo è senza alcun principio che abbia a che fare con piccioni, corvi o anatre. Pensa al caso peggiore: iniziamo a selezionare le persone una per una e continuiamo a ottenere una persona da ciascuna delle coppie. Questo può andare avanti fino a n volte al massimo perché abbiamo solo n coppie. Quindi la n + 1a persona che scegliamo dovrà alla metà migliore di almeno * qualche * coppia. Quindi dobbiamo scegliere almeno n + 1 persone per ottenere almeno una coppia.

Ora, solo vedere i numeri, n coppie e la risposta essendo n + 1 sopra potrebbe averti dato qualche suggerimento su come possiamo usare il principio del buco del piccione. Il principio è davvero facile da affermare e utilizzare, ma la principale ingegnosità viene utilizzata nella configurazione del problema che ne semplifica l’utilizzo. Devi essere esplicito nel dichiarare quali sono i piccioni e quali sono i buchi? (Cordiali saluti, sto davvero cercando di non far sembrare così sporco)

Quindi in questo caso dato che ci sono n coppie, lasceremo che i nostri buchi siano definiti come coppie e quindi abbiamo n buchi. E i piccioni sono le persone reali 2n . Quindi quando iniziamo a selezionare ogni persona, quella persona viene gettata nel buco corrispondente alla coppia di cui fa parte. Secondo il principio del buco del piccione, dopo n + 1 persone, una scatola deve contenere due persone, ovvero una coppia sposata è stata selezionata.

Questo è stato solo un esempio semplice e sciocco per iniziare.

Esempio 2: Busy Chessmaster

Un maestro di scacchi ha 11 settimane per prepararsi a un torneo che gioca almeno una partita al giorno, ma non più di 12 partite durante una settimana di calendario. Dimostra che c’è una successione di giorni consecutivi in ​​cui il maestro gioca esattamente 21 partite.

Si noti che la domanda non dice che dobbiamo dimostrare che il maestro di scacchi ha giocato 21 partite ogni giorno di quella successione consecutiva, ma che in totale in quella sequenza di giorni consecutivi, ha giocato 21 partite. Questo è importante da capire.

Ora, per prima cosa diciamo che il numero totale di partite giocate dal maestro di scacchi fino al giorno i (ovvero le partite cumulative giocate nel Giorno 1, Giorno 2 … Giorno i) è:

E sì, Medium fa schifo perché non ha supporto per LaTex, quindi dovremo tollerare queste equazioni indifferenti dall’aspetto strano. Dal momento che gioca almeno una partita al giorno, la seguente sequenza conterrà:

Nota che gioca per 11 settimane, quindi ci sono in totale 77 giorni e che non gioca più di 12 partite a settimana, quindi il numero cumulativo di partite non può superare 12 X 11 = 132.

E ora, il trucco principale, poiché la domanda dice che dobbiamo trovare i giorni in cui il maestro gioca esattamente 21 giochi, ne aggiungiamo 21 all’equazione:

Pertanto, la sequenza seguente ha un totale di 154 numeri e ciascuno di questi numeri è inferiore a 153:

Ora, deve essere chiaro che i nostri piccioni sono ognuno di questi sono numeri interi e i buchi sono i numeri da 1, 2,…, 153. Quindi almeno due dei numeri interi sopra saranno nello stesso buco cioè saranno uguali tra loro . E poiché entrambe le singole sequenze (l’originale e quella costruita aggiungendo 21) sono sequenze in costante aumento, i due numeri che possono essere individuali devono provenire da sequenze diverse, ad es.

per alcuni i e j e nota che, i> j . E così dai giorni j + 1, j + 2…. io , il maestro di scacchi deve aver giocato esattamente 21 partite.

Spero che ciò dimostri che il principio del buco del piccione, sebbene facile, è un concetto forte da applicare e richiede molta creatività.

Ora lavoriamo su un esempio simile, che renderà il concetto più chiaro.

Esempio 3: The TV Addict

Uno studente guarda la TV almeno un’ora al giorno per 7 settimane ma non più di 11 ore in una settimana. Prova che esiste un periodo di giorni consecutivi in ​​cui il bambino corrisponde esattamente a 20 ore di TV.

Si noti che la formulazione sarà esattamente come l’ultimo problema. Quindi lascia che il numero totale di ore in cui lo studente ha guardato la TV fino al giorno in cui sarò

Quindi, abbiamo un totale di 49 giorni e il numero massimo di ore che lo studente può guardare la TV è 77 (= 11 ore a settimana x 7 settimane)

Ora, esattamente come il problema precedente, aggiungi 20 l’equazione sopra:

Ora la seguente sequenza ha un totale di 98 numeri interi e il valore massimo che questa sequenza può assumere è 97:

In questo caso i piccioni sono i numeri nella sequenza sopra e i buchi sono i numeri interi da 1, … 97. Quindi per principio del buco del piccione, ci sarà un buco con due numeri interi. Quindi, per alcuni i, j dove i> j:

E così, per il periodo consecutivo di giorni da j + 1, j + 2, …, i, avremo un totale di 20 ore di visione della TV.

QED

Spero che ora non pensi che questo teorema sia troppo stupido! Se non l’hai ancora fatto, controlla le parti una e due! Nella parte successiva parleremo del forte principio del buco del piccione, che è molto più divertente!

Riferimenti:

  1. Appunti ed esercizi di lezione del professor Alexander Yong, MATH 413 nella primavera del 19, UIUC. Puoi anche consultare il suo sito Web.
  2. Brualdi, “Introduzione introduttiva” (5a edizione)