ICPC Math Quiz: Blue and Red Balls

Lagi iseng buka FB Fan Page ICPC News, ternyata ketemu posting Quiz. gambarnya saya upload dibawah:

Cukup banyak yang menjawab, dan ada juga yang membuktikan jawabannya. Beberapa saat saya intip jawaban mereka, kalau baca pembuktian mereka ribet-ribet sih (ribet bacanya kalo di komentar, haha). Akhirnya karena penasaran, saya buat pembuktian sendiri aja, selain itu saya buatkan juga rancangan solusi DP-nya (ini bisa diselesaikan dengan DP. hehe.. kalau males buktiin ya tinggal buatin aja program DP nya, solusinya langsung nemu).

Soal tersebut berbunyi kurang lebih seperti ini:

Terdapat 21 bola biru dan 23 bola merah di dalam sebuah kantong, selain itu terdapat 22 bola merah di luar kantong tersebut. Kamu dapat memilih tepat dua bola di dalam kantong tersebut secara acak.

Jika bola yang terambil adalah bola dengan warna yang berbeda , taruh bola biru ke dalam kantong (bola lainnya, keluarkan).
Jika warnanya sama (apapun itu), keluarkan kedua bola tersebut lalu masukkan bola merah ke dalam kantong.

Teruslah mengambil bola hingga hanya tersisa satu bola.

Apakah warna bola yang tersisa tersebut?

Observasi dan Pembuktian

Sekarang kita rincikan dulu kasus-kasus pengambilan yang mungkin terjadi:

Pengambilan bola dengan warna yang berbeda.
Pengambilan sepasang bola biru.
Pengambilan sepasang bola merah.

Pada pengambilan pertama, ketiga kasus diatas masih memungkinkan untuk terjadi.

kemung- kinan	bola BIRU	bola MERAH	bola MERAH (outs. bag)	terambil
keadaan awal	21	23	22
1	19 (-2)	24 (+1)	21 (-1)	(BIRU - BIRU)
2	21	22 (-1)	23 (+1)	(MERAH - MERAH)
3	21	22 (-1)	23 (+1)	(BIRU - MERAH)

* Dapat dilihat pada pengambilan yang mengandung BOLA BIRU:

Pengambilan BIRU-MERAH akan membuat bola BIRU dikembalikan lagi, itu artinya bola biru tidak akan berkurang pada kasus ini.
Pengambilan BIRU-BIRU tidak akan membuat bola BIRU dikembalikan, artinya bola BIRU akan berkurang jumlahnya sebesar 2.
Dengan nilai (jumlah) awal bola BIRU yang ganjil, maka pengurangan bola BIRU sebesar 2 akan mengakibatkan bola BIRU tetap ganjil.

* Pada bola MERAH, Nilai (jumlah) bola memenuhi sembarang bilangan bulat H (H≥0).

* Lalu kita lihat lagi, jumlah bola merah di luar kantong tidak akan habis (merah > 0), kenapa?
Kasus yang membuat kita mengurangi bola di luar kantong adalah saat dua bola biru terambil (pembuktiannya sudah jelas). Lalu kita umpamakan semua kasus yang terjadi adalah "pengambilan dua bola biru" (umpamakan kasus ini akan terus berulang hingga tidak ada lagi PASANGAN bola biru yang dapat diambil), maka kondisi bola saat itu adalah:

bola BIRU	bola MERAH	bola MERAH (outs. bag)
1	23 + [floor(19/2)]	22 - [floor(19/2)]

atau

bola BIRU	bola MERAH	bola MERAH (outs. bag)
1	32	13

Kesimpulan: MINIMUM bola diluar kantong adalah 13.

Untuk mensimpllifikasi permasalahan ini, pada observasi selanjutnya kita tidak perlu memperhatikan jumlah bola yang ada di luar kantong. Observasi selanjutnya adalah dengan memilih nilai bola terkecil yang MUNGKIN.

a. BIRU < MERAH (dengan BIRU adalah nilai terkecil)

kemungkinan	BIRU	MERAH	terambil
keadaan awal	1	M₁
1	1	M1-1	(BIRU - MERAH)
2	1	M1-1	(MERAH - MERAH)

kesimpulan 1: dengan kasus acak bola yang berkurang hanya bola merah, dan saat bola biru = 1 dan bola merah = 1, hanya SATU kasus yang memenuhi (terambil bola biru-merah) dan itupun TETAP akan mengurangi bola merah. Hasil akhirnya hanya ada SATU bola BIRU.

b. BIRU = MERAH (dengan BIRU = MERAH = M2, dan M2 pasti ganjil)

kemungkinan	BIRU	MERAH	terambil
keadaan awal	M₂	M₂
1	M2	M2-1	(BIRU - MERAH)
2	M2	M2-1	(MERAH - MERAH)
3	M2-2	M2+1	(BIRU - BIRU)

c. BIRU > MEAH (dengan BIRU adalah nilai terkecil)

kemungkinan	BIRU	MERAH	terambil
keadaan awal	3	M₃
1	3	M3-1	(BIRU - MERAH)
2	3	M3-1	(MERAH - MERAH)
3	1	M3+1	(BIRU - BIRU)

kesimpulan 2: dengan kasus acak bola biru tidak akan bertambah, melainkan hanya tetap atau berkurang, (kita tidak perlu memperhatikan bola merah). Saat nilai nilai blue = 1, hanya ada 2 kasus yang memenuhi (terambil dua bola merah, atau terambil bola biru-merah), namun tetap kasus ini tidak akan mengurangi bola biru namun akan mengurangi bola merah. Saat bola merah habis, yang tersisa hanya satu bola BIRU.

Jawaban dari semua observasi tadi adalah: "Biru adalah bola terakhir yang tersisa"

Formulasi DP

Permasalahan ini juga dapat kita formulasikan dalam DP (Dynamic Programming). Berikut adalah formulasi DP yang saya buat:

\(\begin{equation} solve(b,r,o) = \left\{ \begin{array}{lll} 1 & \mbox{if } b = 1 \wedge r = 0 \\ -1 & \mbox{if } b = 0\wedge r = 1 \\ solve(b-2,r+1,o+1) & \mbox{if } b \geq 2 \\ solve(b,r-1,o+1) & \mbox{if } r \geq 2 \\ solve(b-2,r+1,o+1) & \mbox{if } b \geq 1 \wedge r \geq 1 \end{array} \right. \end{equation}\) \\ \(\ b = bola \ biru \\ r = bola \ merah \\ o = bola \ merah\ diluar\ kotak \)

Formulasi yang saya buat menggunakan pendekatan model Top-Down Dynamic Programming. Fungsi diatas berjalan recursively hingga basecase ditemui, yaitu:

Saat nilai r=1 dan b=0, akan mengembalikan nilai -1 yang menandakan bola terakhir adalah bola merah (r)
Saat nilai r=0 dan b=0, akan mengembalikan nilai 1 yang menandakan bola terakhir adalah bola biru (b)

Solusi C++
// Solution by MVA

#include <cstdio>
#include <cstring>

#define S_BLUE 21
#define S_RED 22
#define S_RED_OUT 22

using namespace std;

int DP[S_BLUE+1][S_RED+1];

int solve(int blue, int red, int red_out) {

  if(DP[blue][red] != 0) return DP[blue][red];
  else if(blue == 1 && red == 0) return DP[blue][red] = 1; // blue
  else if(blue == 0 && red == 1) return DP[blue][red] = -1; // red

  int sol = 0;
  int count = 0;

  if(blue >= 2) {
    sol += solve(blue-2, red+1, red_out-1); //blue-blue
    count++;
  }

  if(red >= 2) {
    sol += solve(blue, red-1, red_out+1); //red-red
    count++;
  }

  if(blue >= 1 && red >= 1) {
    sol += solve(blue, red-1, red_out+1); //different colors
    count++;
  }

  if(sol == count) {
    return DP[blue][red] = 1;
  } else if(count + sol == 0) {
    return DP[blue][red] = -1;
  } else {
    return 0;
  }

}

int main() {
  memset(DP,0,sizeof(DP));
  int ans = solve(S_BLUE,S_RED,S_RED_OUT);
  printf("%d",ans);
  return 0;
}

Output
1

le Journal de MVA

Pages

9/15/2013