Pigeonhole & Herd Immunity

Minggu pagi lalu, saat sedang joging, saya berpapasan dengan seorang remaja bermotor yang menenteng sangkar berisi burung merpati di tangan kirinya, dari kejauhan saya melihatnya berhenti di ujung jalanan yang sepi, kemudian dia melepaskan dan mengamati merpatinya, tak terlihat sedikitpun keraguan jika sekonyong-konyongnya burung itu melarikan diri. Mereka semacam sedang mengasah kemampuan telepati untuk memantapkan ikatan simbiosis satu sama lain. Saat sedang menikmati pemandangan itu, seketika saya teringat dengan prinsip sarang burung merpati (Pigeonhole principle) yang pernah saya baca beberapa tahun lalu. Seketika juga saya teringat dengan masalah vaksinasi Kemenkes sebelumnya.

Pigeonhole principle yang lebih umum dikenal dengan nama Dirichlet’s box principle, adalah sebuah prinsip matematika yang terinspirasi dari sarang burung merpati di mana jika sejumlah n burung diletakkan ke dalam m kontainer di mana n > m, maka sedikitnya satu kontainer harus berisi lebih dari satu burung. Secara formal, jika n > m, maka paling sedikit satu kontainer berisi ⌈n/m⌉ item (pembulatan ke atas). Ide dasar prinsip ini memang sesederhana itu namun implementasinya bisa beragam, mulai dari algoritma untuk optimasi pergerakan, hingga algoritma kompresi.

Jika konsep di atas kita bayangkan dalam kerangka Herd Immunity (kekebalan kelompok) sebagai contoh sederhana terhadap orang yang divaksin (merah) dan tidak divaksin (putih), lalu dipetakan kedua kelompok tersebut ke dalam kotak 3×3 dengan proporsi $\frac{6}{9}$ (6 dari 9 orang divaksin ≈ 67%) maka akan diperoleh variasi best case dan worst case seperti gambar di bawah, yang berarti 3 orang yang tidak divaksin pada kasus terbaiknya akan memperoleh perlindungan dari 6 orang yang divaksin di sekitarnya.

Lebih lanjut jika kita menginginkan imunitas kelompok yang lebih optimal dengan kerangka yang sama di mana setiap orang dapat berinteraksi paling sedikit ke satu orang yang belum divaksin secara horizontal, vertikal, atau diagonal maka ada 8 dari 9 orang yang divaksin (gbr A). Namun, jika kerangka ini kita jejerkan kebentuk horizontal/vertikal 1×9, jumlah orang yang divaksin dengan kriteria serupa hanya 6 dari 9 orang (gbr B). Gambar C belum memenuhi kriteria optimal karena masih dapat dioptimasi seperti pada gambar B.

Dengan pemahaman dari kotak 3×3 atau 1×9 di atas, secara intuitif harusnya kita sudah dapat menemukan pengali untuk memperoleh jumlah kotak optimal pada kotak berdimensi lain. contoh:

Namun, kedua pengali di atas hanya cocok digunakan pada kasus terbatas ketika dimensi kotak memiliki kelipatan yang sama atau berdimensi (baris atau kolom) satu dengan sisa pembagian 0 atau 1.

Pada contoh kotak berdimensi 2×13 atau 4×7, pengali $^8/_9$ tidak menghasilkan jawaban yang tepat karena jawaban yang seharusnya adalah 21 untuk 2×13 dan 22 untuk 4×7.

Untuk menyederhanakan permasalahan sebelumnya, lewat gambar di atas kita coba rumuskan kondisi umum dari kotak satu baris dan x kolom. Sesuai dengan persyaratan awal yang kita ajukan di mana setiap orang 🟥 berinteraksi paling sedikit ke satu orang ⬜ , maka setiap ada 2 orang 1 di antaranya harus divaksin, demikian juga jika ada 3 orang, akan selalu ada 2 orang yang divaksin.

Pada kondisi (I) di mana n=3 dan n=4 jumlah orang yang divaksin sama sehingga dapat kita rumuskan bahwa ketika $n \bmod 3 \in \{0, 1\}$ maka banyaknya orang yang divaksin adalah $2\lfloor\frac{n}{3}\rfloor$.

Pada kondisi (II) di mana n=5 jumlah orang yang divaksin adalah 2 orang dari 3 kelompok pertama ditambah 1 dari 2 kelompok kedua sehingga dapat kita rumuskan bahwa ketika $n \bmod 3 = 2$ maka banyaknya orang yang divaksin adalah $1 + 2\lfloor\frac{n}{3}\rfloor$.

Rumusan selengkapnya seperti ditunjukkan fungsi $v_1(n)$ berikut, di mana $v_1$ menyatakan jumlah orang yang divaksin (vaccinated) pada dimensi 1 (satu baris atau satu kolom dengan $n$ orang), dan $\lfloor \cdot \rfloor$ adalah fungsi pembulatan ke bawah:

Sejauh ini kita sudah mempunyai ide untuk mendapatkan jumlah orang yang harus divaksin pada konstruksi baris atau kolom berdimensi 1. Selanjutnya, untuk konstruksi berdimensi lebih besar kita membutuhkan pendekatan lain yang masih berbasis pada kondisi baris atau kolom berdimensi 1.

Dengan melihat sekilas pada baris dan kolom pertama pada gambar di atas, terdapat 3 orang yang tidak divaksin pada baris pertama, dan 2 orang yang tidak divaksin pada kolom pertama yang jika kita refleksikan akan menghasilkan jumlah keseluruhan orang yang tidak divaksin, dengan kata lain keseluruhan jumlah orang yang tidak divaksin adalah perkalian antara jumlah orang yang tidak divaksin pada baris dan kolom pertama, demikian kita mendapatkan jumlah orang yang divaksin dengan mengurangkan perkalian baris kolom keseluruhan dengan hasil perkalian baris kolom orang yang tidak divaksin, di mana untuk mendapatkan jumlah orang yang tidak divaksin kita dapat mengurangkan masing-masing baris/kolom dengan hasil dari fungsi $v_1(n)$.

Rumusan selengkapnya seperti ditunjukkan fungsi $V(m, n)$ berikut, di mana $V$ menyatakan jumlah total orang yang divaksin (Vaccinated) pada grid berukuran $m \times n$ ($m$ baris dan $n$ kolom):

Agar lebih interaktif, pada program sederhana di bawah telah saya implementasikan algoritma dari persamaan fungsi $V(m,n)$ dan $v_1(n)$ sebelumnya.

Sebagai contoh sederhana jika kita ambil contoh dari populasi penduduk Indonesia tahun 2020 — sebanyak 273.523.615, lalu kita ujikan dalam 2 skenario berbeda di mana:

• A : Penduduk dijejerkan dalam satu baris (1×273.523.615)
• B : Penduduk dipetakan dalam bidang simetris 16538×16538 ($\lfloor\sqrt{273.523.615}\rfloor = 16538$)

Maka akan didapat hasil masing-masing:

• 182.349.076 orang (67% populasi) pada percobaan A
• 243.112.275 orang (89% populasi) pada percobaan B
• Dengan rataan A & B sebesar 212.730.675 orang (78% populasi)

// Fungsi v_1(n): menghitung jumlah orang yang divaksin pada dimensi 1
function v_1(n) {
  let result;
  let remainder = n % 3;

  if (remainder == 0 || remainder == 1) {
    result = Math.floor(n / 3) * 2;
  } else {
    result = 1 + Math.floor(n / 3) * 2;
  }

  return result;
}

// Fungsi V(m,n): menghitung jumlah orang yang divaksin pada grid m×n
function V(m, n) {
  let count = 0;
  let v_m = v_1(m);
  let v_n = v_1(n);
  let dimension = m * n;

  if (dimension == 1) {
    count = 0;
  } else if (m == 1) {
    count = v_n;
  } else if (n == 1) {
    count = v_m;
  } else {
    count = dimension - (m - v_m) * (n - v_n);
  }

  return count;
}

// Fungsi utama untuk menghitung herd immunity
function herd_immunity(m, n) {
  let result = V(m, n);

  return result;
}