Sari la conținut

Principiul lui Dirichlet (principiul cutiei)

Introducere#

După cum știți, foarte multe principii întâlnite în matematică ajung să fie aplicate și în informatică sub diverse forme. Unul dintre aceste principii, frecvent întâlnit în problemele de matematică de gimnaziu și nu numai este principiul lui Dirichlet, de asemenea cunoscut sub numele de principiul cutiei sau sub denumirea sa din engleză, pigeonhole principle.

Definiție

Dacă avem \(n+1\) obiecte și \(n\) cutii, indiferent cum vom aranja obiectele în cutii, vom avea cu siguranță o cutie care va avea cel puțin două obiecte.

Există foarte multe moduri de a demonstra acest lucru, dar un mod foarte simplu de a face acest lucru este acela de a pleca de la un caz simplu (\(2\) obiecte și \(1\) cutie), caz care este evident, adevărat. Apoi, fiecare obiect adăugat va fi în cutia lui, deci vom avea cu siguranță o cutie cu cel puțin două obiecte.

În informatică, de cele mai multe ori, acest principiu este aplicat atunci când avem de ales două obiecte cu aceeași valoare dintr-o mulțime care are mai multe obiecte decât valori posibile.

În cele ce urmează, vom prezenta diverse exemple de probleme care pot fi rezolvate folosind acest principiu.

Problema exemplu - Binary Number#

Pentru a rezolva această problemă, trebuie să găsim o observație care să ne ajute să aflăm cu ușurință un număr valid. Deoarece există \(2^n\) numere valide, nu putem să le încercăm pe toate. Totuși, ne putem gândi la o formă particulară a numerelor care să ne ajute să aflăm răspunsul mai ușor.

Dacă ne gândim la numerele de forma \(1111\dots10000\dots0\) cu \(n\) cifre, avem \(n+1\) asemenea numere. Datorită acestui fapt, putem scădea mereu din numărul \(1111\dots1\) un număr cu mai puține cifre de aceeași formă cu proprietatea că restul împărțirii la \(n\) a celor două numere este egal.

Pentru a afla aceste resturi, putem construi un vector de resturi parțiale și pentru a afla o soluție, ne putem duce înapoi până când găsim un alt număr cu același rest cu numărul format din \(n\) de \(1\).

Mai jos găsiți implementarea soluției în limbajul C++.

#include <iostream>
using namespace std;

int sp[1000001];

int main() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        sp[i] = (sp[i-1] * 10 + 1) % n;
    }

    for (int i = 0; i < n; i++) {
        if (sp[i] == sp[n]) {
            for (int x = i+1; x <= n; x++) {
                cout << 1;
            }
            for (int x = 1; x <= i; x++) {
                cout << 0;
            }
            cout << '\n';
            return 0;
        }
    }
    return 0;
}

Problema 2 - Subsecv pbinfo#

În mod similar cu problema anterioară, vom putea păstra resturile sumelor valorilor din toate prefixele când împărțim la \(n\), iar atunci când avem un prefix care se repetă, vom afișa cea mai de la stânga subsecvență.

#include <fstream>
using namespace std;

int n, v, remainders[10002], minL = 10001, minR = 10001;
int main() {

    ifstream cin("subsecv.in");
    ofstream cout("subsecv.out");

    cin >> n;
    remainders[0] = 0;
    for (int i = 1; i < n; i++) {
        remainders[i] = -1;
    }
    int sm = 0;
    for (int i = 1; i <= n; i++) {
        cin >> v;
        sm = (sm + v) % n;
        if (remainders[sm] != -1 && remainders[sm] + 1 < minL) {
            minL = remainders[sm] + 1;
            minR = i;
        }
        if (remainders[sm] == -1) {
            remainders[sm] = i;
        }
    }
    cout << minL << " " << minR << '\n';
    return 0;
}

Concluzii#

Acest principiu este unul foarte important, iar cunoștințele de la matematică devin foarte utile în contextul problemelor de algoritmică, în special unele din cele tradițional încadrate în categoria problemelor ad-hoc.

Recomandăm de asemenea urmărirea materialor din resursele suplimentare, chiar dacă unele dintre acestea sunt mai degrabă orientate spre olimpiada de matematică, deoarece fac unele aplicații mai dificile mai ușor de rezolvat.

Probleme suplimentare#

Resurse suplimentare#