What's New

  • You like Kejut and want to place a link to Kejut in your website? That's easy! Click here!
    Kejut.com
Email:

Random Articles

 

Google Treasure Hunt 2008 is a game by Google to test our ability in solving both technical computer questions and mathematical skills too. It looks that every question needs to be solved using computer, except if you want to manually do it, like using your table calculator, but it may not be able to solve all the questions accurately. The fastest to answer each of the question will get prizes, they said.

Google Treasure Hunt 2008 adalah permainan yang diadakan Google untuk mengetes kemampuan menyelesaikan soal baik teknis komputer maupun teka-teki dengan matematika. Memang sih sepertinya semuanya perlu diselesaikan dengan pake komputer, terlalu susah kalo mau dikerjakan manual, walau kalkulator bisa membantu juga. Yang tercepat dalam menjawab tiap pertanyaan akan dapat hadiah, katanya.

This article discusses all the available 4 questions. Until the writing of this article, 3 questions have been released.

Nah artikel ini akan membahas keseluruhan 4 soal yang ada. Sampe penulisan artikel ini, sudah ada 3 pertanyaan yang dirilis.

Question 1

The first question which marked the beginning of Google Treasure Hunt 2008 was on the Official Google Australia Blog. The Google Treasure Hunt website itself is not on that blog, but on that article we were given a hint:

Pertanyaan pertama yang diterbitkan sekaligus penanda dimulainya Google Treasure Hunt 2008 ada di Official Google Australia Blog. Situs Google Treasure Hunt sendiri bukan di blog itu, tapi di artikel blog itu hanya diberikan suatu petunjuk:

aHR0cDovL3RyZWFzdXJlaHVudC5hcHBzcG90LmNvbS8=

Soon :). 1210550400

It is the URL address of the GTH 2008 website, but it is encoded in base64. For convenience, we can use online decoder like this. Paste it and click "Decode" beside "Base 64", we will get this result:

Itu alamat tempat GTH 2008 diadakan, tapi dikodekan dalam base64. Untuk mudahnya, bisa pakai pendekode online seperti ini. Paste dan klik "Decode" di sebelah "Base 64", maka hasilnya adalah:

http://treasurehunt.appspot.com/

Then how about the number? It is called "unix time", which is the number of seconds passed since the beginning of year 1970 in GMT time zone. 1210550400 seconds since that is May 12, 2008, exactly on the midnight GMT.

Bagaimana dengan angka itu? Itu "unix time", yaitu banyak detik yang telah berlalu sejak 1970-1-1 0:0:0 GMT. 1210550400 detik sejak saat itu adalah 2008-5-12 tepat jam 0 GMT.

After we input our name and email on the GTH website, the first question comes out:

Setelah memasukkan nama dan imel di situs GTH, muncullah pertanyaan pertama. Bunyinya seperti ini.

A robot is located at the top-left corner of a 33 x 69 grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below). Note: The grid below is 7x3, and is used to illustrate the problem. It is not drawn to scale.

How many possible unique paths are there? (Note: Answer must be an exact, decimal representation of the number.)

The numbers 33 and 69 is not fixed, but randomized. Every person gets different numbers.

Angka 33 dan 69 itu tidak tetap, namun diacak, tiap orang bisa dapat angka yang berbeda.

Answer 1

This problem can be solved by trying the small grids first and then finding the relations to get the answer for bigger grids. For example, for 1x1 grid, the starting point and the finishing point will be located at the same cell, so there is only one path from start to finish.

Soal ini dapat diselesaikan dengan cara mencoba dengan panjang dan lebar kisi yang sedikit dulu. Misalnya, untuk kisi 1x1, titik mulai dan titik akhir akan terletak pada kotak yang sama, maka hanya ada satu jalan untuk menyelesaikannya.

How about the 1x2 grid? There is only 1 straight path, so in total there is only 1 path. It is the same for the 2x1 grid, only 1 possible path.

Bagaimana untuk kisi 1x2? Cuma ada 1 jalan lurus, jadi juga ada 1 jalan. Untuk 2x1 pun sama, hanya ada 1 jalan lurus, jadi jawabannya 1.

Now, for 2x2 grid, there are 2 paths, aren't there? See the picture.

Nah, untuk 2x2, ada 2 jalan bukan? Lihat gambar.

How if we added one column to the right, to make it 3x2? We can see that there will be 3 paths.

Bagaimana jika kita tambah 1 kolom ke kanan, jadi 3x2? Bisa diamati bahwa jadi ada 3 jalan.

That was for 3x2. How about 2x3? Of course the answer is the same, there are 3 paths, no need to draw it anymore.

Itu kan untuk 3x2. Kalau untuk 2x3? Tentu saja sama jawabannya, ada 3 jalan, ga usa digambar lagi.

Now let's create a table to indicate the number of possible paths for grids of specific widths and heights.

Sekarang mari buat tabel untuk menyatakan berapa jalan yang mungkin untuk panjang dan lebar tertentu.

Banyak Jalan
Number of ways
Panjang/Width
Height / Lebar   1 2 3
1 1 1 1
2 1 2 3
3 1 3 ?

On the above table, there is not yet an answer for the 3x3 grid. But, examine the following picture!

Di tabel di atas, belum ada jawaban untuk kisi 3x3. Tapi, coba perhatikan gambar di bawah ini!

  • There are only 2 cells that can go to F, which is the green cell and the purple cell.
  • There are 3 paths from S to the green cell (blue arrows).
  • There are 3 paths from S to the purple cell (red arrows).
  • So, to reach F from S, there are 3 (blue arrows then green arrow) + 3 (red arrows then purple arrow) = 6 possible paths.
  • Hanya ada 2 kotak yang bisa menuju F, yaitu dari kotak hijau dan dari kotak ungu.
  • Dari S ke kotak hijau ada 3 jalan (panah biru)
  • Dari S ke kotak ungu ada 3 jalan (panah merah)
  • Maka, untuk mencapai F dari S, ada 3 (panah biru lalu panah ijo) + 3 (panah merah lalu panah ungu) = 6 jalan.

The theory above applies for every cell that is not on the left-most or the top-most.

Teori di atas berlaku untuk setiap kotak yang bukan paling kiri maupun paling atas.

Conclusion: the number of paths to the cell with coordinate (x, y) = number of paths at (x-1, y) + number of paths at (x, y-1).

Kesimpulan: banyak jalan ke kotak dengan koordinat (x, y) = banyak jalan pada (x-1, y) + banyak jalan pada (x, y-1).

So let's continue the table.

Maka mari lanjutkanlah tabel tadi.

Banyak Jalan
Number of ways
Panjang/Width
Height / Lebar   1 2 3 4 5
1 1 1 1 1 1
2 1 2 3 4 5
3 1 3 6 10 15
4 1 4 10 20 35

And so on, until the 33x69 grid. Wow, that's so many, how can I do that? Now it is the time for computer people to act. Java (my hometown island):

Dan seterusnya.. sampe yang 33x69. Banyak amat, gimana caranya? Nah ini saatnya tukang komputer beraksi. Java (pulau kelahiran):

int x = 33;
int y = 69;
BigInteger[][] a = new BigInteger[x][y];

for (int i = 0; i < x; i++) {
    for (int j = 0; j < y; j++) {
        if (i==0 || j==0) {
            a[i][j] = BigInteger.ONE;
        } else {
            a[i][j] = a[i-1][j].add(a[i][j-1]);
        }
    }
}
System.out.println(a[x-1][y-1]);

The answer is: 143012501349174257560226775

Jawaban: 143012501349174257560226775

Mathematics people may have found the formula ^^ which is:

Tukang berhitung mungkin sudah temukan rumusnya ^^ yaitu:

(x-1 + y-1)! / (x-1)! / (y-1)! = 100! / 32! / 68!

Question 2

The second question hint moves to the Official Google Blog, not the Australian anymore. The address of the GTH website is clearly displayed there. Now, the hidden one is the release time:

Petunjuk pertanyaan ke 2 pindah ke Official Google Blog, bukan yang Australia lagi. Alamat GTH sudah diberikan langsung di sana. Kali ini waktu rilisnya yang disembunyikan:

The second puzzle will be appearing soon — to be exact, 936266827 seconds before Y2K38, so keep yer eyes open.

For those who assumes that Y2K38 is Jan 1, 2038, you will get the wrong answer. Y2K is a computer problem in handling years in dates starting from 2000 and so on. Y2K38 is another problem that computers will have on the year 2038. The problem lies on that "unix time" again, which is the number of seconds from 1970-1-1 midnight. When the number of seconds reaches 2147483647, for signed integer that is already the maximum number. That problem will occur on Jan 19, 2038, at 3:14:07. Therefore, let's calculate 936266827 seconds before that, and we find that it is on 2008-5-19 at 17:07:00.

Bagi yang menganggap Y2K38 adalah tanggal 1 Januari 2038, akan dapat hasil yang salah. Y2K adalah masalah komputer dalam menangani penanggalan mulai tahun 2000 dan seterusnya. Y2K38 adalah masalah lain yang akan dialami komputer pada tahun 2038. Masalahnya terletak pada "unix time" tadi, yaitu jumlah detik sejak 1970-1-1 tengah malam. Ketika jumlah detik itu mencapai 2147483647, untuk signed integer itu sudah angka maksimum. Hal itu akan terjadi pada 2038-1-19 3:14:7. Nah maka kita hitung 936266827 detik sebelumnya, yaitu tanggal 2008-5-19 jam 17:7.

Here is a random zip archive for you to download:
GoogleTreasureHunt08_1407866074866096782.zip

Unzip the archive, then process the resulting files to obtain a numeric result. You'll be taking the sum of lines from files matching a certain description, and multiplying those sums together to obtain a final result. Note that files have many different extensions, like '.pdf' and '.js', but all are plain text files containing a small number of lines of text.

Sum of line 1 for all files with path or name containing foo and ending in .txt
Sum of line 4 for all files with path or name containing foo and ending in .pdf
Hint: If the requested line does not exist, do not increment the sum.

Multiply all the above sums together and enter the product below.
(Note: Answer must be an exact, decimal representation of the number.)

Answer 2

As for this, this is reaaally a job for computer people. So I will drop out this island again: Q2.java.

Ini sih benar2 kerjaan tukang komputer. Maka ku keluarkan pulau ini lagi: Q2.java.

Question 3

The 3rd question is mentioned here without any riddle.

Pertanyaan 3 ini diberitau di sini tanpa petunjuk apa-apa.

Below is a diagram of a computer network. The nodes are hosts on the network, and the lines between them are links. A packet is sent out from host P with a destination of 124.43.126.62. Which nodes does the packet pass through on its way to the destination? (include start and final node in your answer)

Here is a network routing table you'll need to determine the path taken:

Node Ip address Routing table entry Routing table entry Routing table entry Default route
A 11.145.244.41 81.109.28.18 => 169.111.143.170 254.228.137.168 => 67.55.199.134 24.106.11.0/24 => 208.171.191.81 124.20.12.146
B 169.111.143.170 11.145.244.41 => 11.145.244.41 35.184.150.233 => 208.171.191.81 36.203.165.0/24 => 124.20.12.146 137.201.180.222
C 137.201.180.222 67.55.199.134 => 169.111.143.170 81.109.28.18 => 114.153.208.62 124.43.126.0/24 => 36.203.165.86 67.55.199.134
D 168.170.249.253 35.184.150.233 => 24.106.11.31 95.46.150.74 => 35.184.150.233 81.109.28.0/24 => 36.203.165.86 137.201.180.222
E 24.106.11.31 24.106.11.31 => 124.43.126.62 95.46.150.74 => 64.173.219.248 11.145.244.0/24 => 95.46.150.74 168.170.249.253
F 95.46.150.74 124.20.12.146 => 24.106.11.31 124.43.126.62 => 124.43.126.62 35.184.150.0/24 => 81.109.28.18 64.173.219.248
G 81.109.28.18 124.20.12.146 => 168.170.249.253 114.153.208.62 => 36.203.165.86 124.43.126.0/24 => 95.46.150.74 35.184.150.233
H 35.184.150.233 35.184.150.233 => 81.109.28.18 11.145.244.41 => 168.170.249.253 114.153.208.0/24 => 36.203.165.86 124.43.126.62
I 124.43.126.62 254.228.137.168 => 64.173.219.248 169.111.143.170 => 35.184.150.233 24.106.11.0/24 => 24.106.11.31 95.46.150.74
J 64.173.219.248 137.201.180.222 => 95.46.150.74 11.145.244.41 => 24.106.11.31 67.55.199.0/24 => 124.43.126.62 36.203.165.86
K 36.203.165.86 168.170.249.253 => 114.153.208.62 169.111.143.170 => 137.201.180.222 114.153.208.0/24 => 35.184.150.233 81.109.28.18
L 114.153.208.62 169.111.143.170 => 208.171.191.81 124.20.12.146 => 67.55.199.134 114.153.208.0/24 => 36.203.165.86 168.170.249.253
M 208.171.191.81 168.170.249.253 => 124.20.12.146 24.106.11.31 => 11.145.244.41 254.228.137.0/24 => 169.111.143.170 114.153.208.62
N 124.20.12.146 124.43.126.62 => 208.171.191.81 11.145.244.41 => 254.228.137.168 124.20.12.0/24 => 11.145.244.41 169.111.143.170
O 254.228.137.168 137.201.180.222 => 67.55.199.134 168.170.249.253 => 114.153.208.62 36.203.165.0/24 => 124.20.12.146 137.201.180.222
P 67.55.199.134 35.184.150.233 => 137.201.180.222 124.43.126.62 => 11.145.244.41 95.46.150.0/24 => 114.153.208.62 254.228.137.168

Answer 3

Does it sound confusing? For me it was confusing. But, if we see it carefully, it is actually easier than the previous questions.

Keliatan membingungkan kah? Kalo bagiku sih iya. Tapi kalo diperhatikan lebih teliti, sebetulnya lebih gampang daripada pertanyaan-pertanyaan sebelumnya.

In the question it is mentioned that the start node is P and the destination is 124.43.126.62. Based on the table, the destination is the node I. Because on every node there is IP address, let's just replace all the contents of the table with the alphabet. It becomes like this:

Di soal dikatakan bahwa mulainya di titik P dan tujuannya di 124.43.126.62. Berdasarkan tabel, tujuannya adalah titik I. Karena setiap titik ada IP masing-masing, marilah kita replace all saja isi tabel itu dengan huruf. Jadi begini:

Node Ip address RTE1 RTE2 RTE3 Default route
A 11.145.244.41 G => B O => P 24.106.11.0/24 => M N
B 169.111.143.170 A => A H => M 36.203.165.0/24 => N C
C 137.201.180.222 P => B G => L 124.43.126.0/24 => K P
D 168.170.249.253 H => E F => H 81.109.28.0/24 => K C
E 24.106.11.31 E => I F => J 11.145.244.0/24 => F D
F 95.46.150.74 N => E I => I 35.184.150.0/24 => G J
G 81.109.28.18 N => D L => K 124.43.126.0/24 => F H
H 35.184.150.233 H => G A => D 114.153.208.0/24 => K I
I 124.43.126.62 O => J B => H 24.106.11.0/24 => E F
J 64.173.219.248 C => F A => E 67.55.199.0/24 => I K
K 36.203.165.86 D => L B => C 114.153.208.0/24 => H G
L 114.153.208.62 B => M N => P 114.153.208.0/24 => K D
M 208.171.191.81 D => N E => A 254.228.137.0/24 => B L
N 124.20.12.146 I => M A => O 124.20.12.0/24 => A B
O 254.228.137.168 C => P D => L 36.203.165.0/24 => N C
P 67.55.199.134 H => C I => A 95.46.150.0/24 => L O

Now it is much easier to see, right?

Nah, lebih gampang kan liatnya.

Then, starting from P, examine the RTEs, check whether there is one that matches with the destination (I or 124.43.126.62). On the RTE3 column, there are "/24"'s, that means the 4th number of the IP is ignored.

  • From P. Destination is I. RTE2: I => A, so we go to A.
  • From A. Destination is still I forever. No RTE that matches, so we go to the Default, so we go to N.
  • From N. RTE1: I => M, so we go to M.
  • From M go to L.
  • From L go to D.
  • From D go to C.
  • From C. RTE3: 124.43.126.0/24 matches 124.43.126.62, so we go to K.
  • And so on, until we arrive at I.

Answer: PANMLDCKGFI.

Lalu, mulai dari P, liatlah tiap RTE, apakah ada yang sesuai dengan tujuan (I atau 124.43.126.62). Kolom RTE3 ada "/24"nya, berarti bilangan ke 4 dari IPnya tak usah dianggap.

  • Dari P. Tujuan I. RTE2: I => A, berarti menuju A.
  • Dari A. Tujuan tetap I terus. Tiada RTE yang cocok. Masuk ke Default, berarti ke N.
  • Dari N. RTE1: I => M, berarti menuju M.
  • Dari M menuju L.
  • Dari L menuju D.
  • Dari D menuju C.
  • Dari C. RTE3: 124.43.126.0/24 cocok dengan 124.43.126.62, berarti menuju K.
  • Dan seterusnya, sampai tiba di I.

Jawaban: PANMLDCKGFI.

Question 4

Not Yet :D

Belom :D

Answer 4

Also Not Yet :D

Belom juga :D

Ending

Do you have any comments? Other methods? Impressions etc? Please write down at the comment section below!

Penutup

Ada komen? Cara lain? Kesan-kesan? Harap tulis di bagian komen di bawah!

Written by: yuku

Cara yang biasanya dipake buat soal no. 1.
Untuk mencapai tujuan butuh jalan ke kanan x-1 langkah dan ke bawah y-1 langkah. Urutan langkah bisa terserah.
Jadi jumlah rute yang ada = permutasi x-1 biji langkah ke kanan dan y-1 biji langkah ke bawah = (x-1 + y-1)!/(x-1)!/(y-1)!


asa [us], 31 May 2008, 17:53 reply
ampun bang.. O-o'

wihu [sg], 1 Jun 2008, 2:25 reply
Informasi berharga untuk anda. Web yang di perkirakan bakal mengalahkan
Yahoo dan Google yang akan lounching pada tgl 1 Juli 2008 akan
membagikan sebagian sahamnya yang sebesar $ 1,000,000.00 kepada siapa
saja yang bergabung menjadi anggotanya (Free) sebelum tgl 1 Juli 2008.
Ayo buruan gabung untuk mendapatkan saham gratis. FREE to JOIN. all the
world.
KLIK Join Disini http://www.WebUpgrade9.com/shodiqfm


sahabat [id], 9 Jun 2008, 4:44 reply
Tidak....
Koq susahnya :p


Denny [id], 15 Aug 2008, 8:05 reply
tanya donk... itu gimana ngejalanin program (Java) nya?

Marcellino [id], 15 Nov 2008, 14:51 reply
...this is awsome....you're so talented to have solutions n poor i :(

Dhru [us], 30 Dec 2010, 10:29 reply