FORTY + TEN + TEN = SIXTY

Oktober 16, 2010

FORTY + TEN + TEN = SIXTY

Filed under: Puzzle — Hendra Jaya @ 9:12 am

Problem :

$\begin{array}{lllllr}F&O&R&T&Y\\&&T&E&N\\&&T&E&N\\-&-&-&-&-&+\\S&I&X&T&Y\end{array}$

Curahan Hati :

Penulis berusaha sebisa mungkin untuk menghindari penggunaan programming ketika menyelesaikan teka-teki ini. Untuk itu penulis memanfaatkan sebesar-besarnya teknik pertidaksamaan dan teori bilangan, khususnya algoritma pembagian dan kekongruenan bilangan. Penulis mengasumsikan pembaca sudah cukup paham mengenai pertidaksamaan. Jika pembaca menemui kesulitan dalam algoritma pembagian ataupun kekongruenan bilangan, penulis menyarankan untuk membaca tulisan tentang algoritma pembagian dan kekongruenan bilangan terlebih dahulu.

Pra-pembahasan :

Secara umum, di dalam setiap variabel berlaku pertidaksamaan $0\leq A\leq 9$ .

Jika kita asumsikan $A<B$ maka berlaku pertidaksamaan $0\leq A<B\leq 9$ . Pertidaksamaan ini dapat dipecah menjadi $0\leq A\leq 8$ dan $1\leq B\leq 9$ . Akibatnya nilai $A+B$ akan berada di rentang $1\leq A+B\leq 17$ .

Sekarang, karena $A<B$ , maka :

$\begin{array}{rlrllll}&&A&<&B\\(A+B)&+&A&<&B&+&(A+B)\\2A&+&B&<&2B&+&A\\2A&+&B&<&A&+&2B\end{array}$

Nilai $2A+B$ berada di rentang $1\leq 2A+B\leq 25$ .
Nilai $A+2B$ berada di rentang $2\leq A+2B\leq 26$ .

Jika kita lupakan asumsi awal $A<B$ , maka nilai $A+2B$ akan berada di rentang $1\leq A+2B\leq 26$ .
Perhatikan bahwa persamaan $A+2B=1$ hanya mungkin terjadi jika $B<A$ .
Sebaliknya, persamaan $A+2B=26$ hanya mungkin terjadi jika $A<B$ .

Dengan demikian carry yang mungkin dihasilkan oleh bentuk $A+2B$ adalah $C=\{0,1,2\}$

Pembahasan

Sekarang, perhatikan bahwa $Y$ kongruen dengan $Y+2N$ dalam modulo 10. Secara matematis : $Y\equiv Y+2N\text{(modulo 10)}$

Dengan memanfaatkan sifat :

$\begin{array}{lrlll}&a&\equiv& b&\text{(modulo\ n)}\\&p&\equiv& q&\text{(modulo\ n)}\\\rightarrow&a+p&\equiv& b+q&\text{(modulo\ n)}\end{array}$

Kita peroleh $0\equiv 2N\text{(modulo\ 10)}$ atau jika dinyatakan dalam algoritma pembagian menjadi $2N = 10.p$

Mengingat $0\leq N\leq 9$ dan $0\leq 2N\leq 18$ maka himpunan nilai yang mungkin untuk p adalah $P=\{0,1\}$ . Alhasil, nilai $2N$ yang mungkin adalah $\{0,10\}$ . Sehingga himpunan nilai yang mungkin untuk N adalah $\{0,5\}$ . Lebih jauh lagi, duplet yang memungkinkan untuk N dan carry adalah $<N, carry>=\{<0, 0>,<5,1>\}$

Selanjutnya, berlaku pula kekongruenan $T\equiv carry+T+2E\text{(modulo\ 10)}$ yang mengakibatkan $0\equiv carry+2E\text{(modulo\ 10)}$ . Atau jika dinyatakan dalam algoritma pembagian menjadi $carry + 2E = 10.q$ .

Perhatikan bahwa sisi kanan dari persamaan adalah genap. Dengan demikian, sisi kiri juga harus genap. Karena bentuk $2E$ adalah genap, maka genap atau ganjilnya sisi kiri hanya tergantung kepada carry. Fakta ini memaksa kita untuk meng-eliminasi duplet $<5, 1>$ . Kabar yang baik tentunya. Karena dengan demikian kita bisa memastikan bahwa $N=0$ dan tidak ada carry yang dibawa.

$\begin{array}{lllllr}F&O&R&T&Y\\&&T&E&0\\&&T&E&0\\-&-&-&-&-&+\\S&I&X&T&Y\end{array}$

Sebelumnya sudah dibahas bahwa $carry + 2E = 10.q$ dan $0\equiv carry+2E\text{(modulo\ 10)}$ . Dengan men-substitusikan nilai 0 ke dalam carry kita peroleh $2E = 10.q$ dan $0\equiv 2E\text{(modulo\ 10)}$ .

Berapa nilai E yang mungkin? Alih-alih “tembak langsung” ke nilai E, kita akan berputar melalui senjata awal kita, yaitu pertidaksamaan dan kekongruenan bilangan.

Seperti yang sudah-sudah, nilai $2E$ berada di rentang $0\leq 2E\leq 18$ . Di rentang ini, hanya ada dua buah nilai yang kongruen dengan 0 dalam modulo 10, yaitu 0 dan 10. Kedua nilai ini membantu kita untuk menyimpulkan bahwa nilai yang mungkin untuk E adalah $\{0, 5\}$ . Mengingat 0 sudah dipakai, maka nilai E yang mungkin hanyalah $\{5\}$ dan dengan demikian kita peroleh $E=5$ dan $q=1$ .

$\begin{array}{lllllr}&&1&&\\F&O&R&T&Y\\&&T&5&0\\&&T&5&0\\-&-&-&-&-&+\\S&I&X&T&Y\end{array}$

Seperti sudah dibahas pada pra-pembahasan bahwa $0\leq A+B\leq 17$ , kita dapat menarik kesimpulan bahwa penjumlahan dua buah variabel yang berbeda akan menghasilkan carry 0 ataupun carry 1.

Sebagai konsekuensinya, penjumlahan O dan I pun dapat menghasilkan carry 0 ataupun carry 1. Jika tidak menghasilkan carry (yakni carry 0), akan mengakibatkan $F=S$ yang tentu saja tidak valid karena F dan S adalah dua buah variabel yang berbeda

Dengan demikian penjumlahan O dan I pasti memberikan carry 1. Sehingga berlaku persamaan $F+1=S$

$\begin{array}{lllllr}1&&1&&\\F&O&R&T&Y\\&&T&5&0\\&&T&5&0\\-&-&-&-&-&+\\S&I&X&T&Y\end{array}$

Selanjutnya, kita akan coba “taklukkan” variabel O dan I.

Pada pra-pembahasan sudah dibahas bahwa bentuk $A + 2B$ berada di rentang $1\leq A+2B\leq 26$ atau dengan menambahkan 1 kepada setiap bagian pertidaksamaan kita peroleh $2\leq 1+A+2B\leq 27$ . Fakta ini menolong kita untuk “menebak” carry yang mungkin dibawa pada nilai $1+R+2T$ .

Saat ini, kita hanya bisa menyimpulkan bahwa carry yang mungkin dibawa pada penjumlahan $1+R+2T$ adalah $C = \{0,1,2\}$ .

Jika $carry=0$ , maka :
$\begin{array}{lllllll}0&+&O&=&10&+&I\\&&O&=&10&+&I\end{array}$ .

Persamaan di atas menyatakan bahwa O kongruen dengan I dalam modulo 10, secara matematis $O\equiv I(modulo\ n)$ . Hal ini tidak bisa kita terima karena artinya variabel O “kembar” dengan variabel I.
Jika $carry=1$ , maka :
$\begin{array}{lllllll}1&+&O&=&10&+&I\\&&O&=&9&+&I\end{array}$

(Lagi-lagi) Pertidaksamaan akan kita gunakan untuk memeriksa :

$\begin{array}{llrl}0&\leq&O\leq&9 \\ 0& \leq&9+I\leq&9\\-9&\leq&I\leq&0\end{array}$

Pertidaksamaan berhasil membantu kita “mempersempit” kemungkinan dan menyimpulkan bahwa nilai I yang mungkin adalah $I=0$ . Mengingat 0 sudah dipakai, maka kasus ini pun tidak bisa kita terima
Jika $carry=2$ , maka :
$\begin{array}{lllllll}2&+&O&=&10&+&I\\&&O&=&8&+&I\end{array}$

Biarkan pertidaksamaan beraksi :

$\begin{array}{llrl}0&\leq&O\leq&9 \\ 0& \leq &8+I\leq&9\\-8&\leq&I\leq&1\end{array}$

Akhirnya. Kasus $carry=2$ memberikan hasil yang dapat diterima, yaitu $I=1$ . Dengan demikian variabel O pun dapat dipecahkan, yaitu $O=9$ .

Dari sini, kita peroleh :

$\begin{array}{lllllr}1&2&1&&\\F&9&R&T&Y\\&&T&5&0\\&&T&5&0\\-&-&-&-&-&+\\S&1&X&T&Y\end{array}$

Kesimpulan $carry=2$ dan $O=9$ ini sangat mempermudah kita untuk memecahkan variabel T. Mari kita bergerak dengan pertidaksamaan (lagi…)

Karena nilai 9 sudah diambil oleh O, maka berlaku $B\leq 8$
Karena nilai 8 sudah diambil oleh B, maka berlaku $A\leq 7$
Kedua premis di atas membawa kita kepada $A+2B\leq 23$ atau, dengan menambahkan 1 pada kedua sisi, kita peroleh $1+A+2B\leq 24$

Bagaimana dengan batas bawah (lower bound) dari nilai $1+R+2T$ ? Karena sebelumnya sudah kita pastikan bahwa nilai $1+R+2T$ akan menelurkan $carry=2$ , maka batas bawah untuk nilai $1+R+2T$ adalah 20. Secara matematis $20\leq 1+R+2T\leq 24$ .

Ingat bahwa X kongruen dengan $1+R+2T$ di dalam modulo 10. Dengan mengambil pertidaksamaan $20\leq 1+R+2T\leq 24$ , secara implisit kita menyatakan bahwa $0\leq X\leq 4$ . Rentang nilai X sebenarnya dapat kita persempit dengan mengingat bahwa 0 dan 1 sudah tidak bisa dipakai. Sehingga rentang nilai yang lebih tepat untuk X adalah $2\leq X\leq 4$

Rentang nilai X yang sudah dipersempit itu meng-implikasikan bahwa rentang nilai $1+R+2T$ pun dapat dipersempit menjadi $22\leq 1+R+2T\leq 24$ . Atau jika disederhanakan menjadi $21\leq R+2T\leq 23$

Sekarang, karena nilai 0, 1, 5 dan 9 sudah tidak bisa dipakai, maka berlaku $2\leq R\leq 8$ dimana $R\neq 5$ .
Secara komputatif, $min(R) = 2$ dan $max(R) = 8$ .

Mari kita lihat apa yang akan terjadi kepada pertidaksamaan jika kita mengambil nilai R minimum dan maksimum

Untuk R minimum, yaitu $R=2$ :
$\begin{array}{llrll}21&\leq&R+2T&\leq&23\\21&\leq&2+2T&\leq&23\\19&\leq&2T&\leq&21\end{array}$
Untuk R maximum, yaitu $R=8$ :
$\begin{array}{llrll}21&\leq&R+2T&\leq&23\\21&\leq&8+2T&\leq&23\\13&\leq&2T&\leq&15\end{array}$

Dari sini dapat disimpulkan bahwa $2T$ berada di rentang $13\leq 2T\leq 21$ .

Dengan hanya memandang bilangan-bilangan genap kita pertajam sedikit pertidaksamaannya menjadi $14\leq 2T\leq 20$ . Selanjutnya pertidaksamaan dapat disederhanakan menjadi $7\leq T\leq 10$ . Mengingat nilai 9 dan 10 tidak bisa dipakai, pertidaksamaan dapat dipertajam lagi menjadi $7\leq T\leq 8$ .

Pertidaksamaan ini sangat menolong kita untuk menyimpulkan bahwa himpunan nilai yang mungkin untuk T adalah $\{7,8\}$ .

Berikutnya kita akan periksa setiap kasus untuk T.

Untuk $T=7$ :
$\begin{array}{lllllr}21&\leq&R+2T&\leq&23\\21&\leq&R+14&\leq&23\\7&\leq&R&\leq&9\\7&\leq&R&\leq&8&\text{Angka 9 sudah tidak bisa dipakai}\end{array}$

Karena $T=7$ , maka nilai yang mungkin untuk R hanyalah 8.

Jika kedua nilai ini kita substitusikan, kita peroleh $1+R+2T=21$ . Nilai ini akan menyebabkan $X=1$ yang tidak valid karena 1 sudah dipakai. Hal ini termaktub dalam pertidaksamaan. Ingat bahwa tadi kita sudah mempersempit rentang X menjadi $2\leq X\leq 4$
Untuk :
$\begin{array}{lllllr}21&\leq&R+2T&\leq&23\\21&\leq&R+16&\leq&23\\5&\leq&R&\leq&7\\6&\leq&R&\leq&7&\text{Angka 5 sudah tidak bisa dipakai}\end{array}$

Dua nilai yang memungkinkan untuk R adalah $\{6,7\}$ .
1. Untuk $R=6$ kita peroleh $1+R+2T=23$ . Artinya $X=3$ . Logis.
2. Untuk $R=7$ kita peroleh $1+R+2T=24$ . Artinya $X=4$ . Logis.

Saat ini, kita punya dua triplet yang mungkin untuk $<R,T,X>$ , yaitu $\{<6,8,3>,<7,8,4>\}$

Triplet $<6,8,3>$ :
$\begin{array}{lllllr}1&2&1&&\\F&9&6&8&Y\\&&8&5&0\\&&8&5&0\\-&-&-&-&-&+\\S&1&3&8&Y\end{array}$

Triplet ini menyisakan tiga bilangan yang belum dipakai, yaitu $\{2,4,7\}$ . Sayangnya, ketiga nilai yang tersisa ini tidak ada yang dapat dipergunakan untuk memenuhi persamaan $F+1=S$ . Sehingga triplet ini gagal memberikan solusi.
Triplet $<7,8,4>$ :
$\begin{array}{lllllr}1&2&1&&\\F&9&7&8&Y\\&&8&5&0\\&&8&5&0\\-&-&-&-&-&+\\S&1&4&8&Y\end{array}$

Triplet ini menyisakan tiga bilangan yang belum dipakai, yaitu $\{2,3,6\}$ . Nilai yang “masuk” untuk persamaan $F+1=S$ adalah $2+1=3$ . Dengan demikian triplet ini memberikan solusi dimana $F=2$ , $S=3$ dan $Y=6$ .