Latihan 4.6 Latihan

1.

Anda diberikan suatu daftar berisi \(n\) bilangan bulat yang masing-masing memiliki nilai mutlak paling besar \(100n\text{.}\) Berapa banyak operasi yang diperlukan untuk melakukan tugas-tugas berikut? Dalam menjawab pertanyaan ini, yang terutama ingin kita ketahui adalah apakah diperlukan \(\log n\text{,}\) \(\sqrt{n}\text{,}\) \(n\text{,}\) \(n^2\text{,}\) \(n^3\text{,}\) \(2^n\text{,}\) … langkah. Dengan kata lain, abaikan konstanta pengali.

Tentukan apakah bilangan \(2n+7\) terdapat dalam daftar.
Tentukan apakah terdapat dua bilangan dalam daftar yang jumlahnya \(2n+7\text{.}\)
Tentukan apakah terdapat dua bilangan dalam daftar yang hasil kalinya \(2n+7\text{.}\) Soal ini lebih rumit daripada yang mungkin tampak! Mengurutkan bilangan-bilangan bulat dalam daftar dapat membantu Anda.
Tentukan apakah terdapat suatu bilangan \(i\) sedemikian sehingga semua bilangan dalam daftar berada di antara \(i\) dan \(i+2n+7\text{.}\)
Tentukan barisan terpanjang bilangan bulat berurutan yang terdapat dalam daftar.
Tentukan banyaknya bilangan prima dalam daftar.
Tentukan apakah terdapat tiga bilangan bulat \(x\text{,}\) \(y\text{,}\) dan \(z\) dari daftar sedemikian sehingga \(x+y=z\text{.}\)
Tentukan apakah terdapat tiga bilangan bulat \(x\text{,}\) \(y\text{,}\) dan \(z\) dari daftar sedemikian sehingga \(x^2+y^2=z^2\text{.}\)
Tentukan apakah terdapat tiga bilangan bulat \(x\text{,}\) \(y\text{,}\) dan \(z\) dari daftar sedemikian sehingga \(xy=z\text{.}\)
Tentukan apakah terdapat tiga bilangan bulat \(x\text{,}\) \(y\text{,}\) dan \(z\) dari daftar sedemikian sehingga \(x^y=z\text{.}\)
Tentukan apakah terdapat dua bilangan bulat \(x\) dan \(y\) dari daftar sedemikian sehingga \(x^y\) merupakan bilangan prima.
Tentukan barisan aritmetika terpanjang dalam daftar. Suatu barisan \((a_1, a_2,\dots,a_t)\) merupakan barisan aritmetika apabila terdapat konstanta \(d\neq 0\) sedemikian sehingga \(a_{i+1}=a_i+d\) untuk setiap \(i=1,2, \dots, t-1\text{.}\)
Tentukan banyaknya jumlah berbeda yang dapat dibentuk dari anggota-anggota daftar. Sebarang banyak bilangan bulat dari daftar boleh digunakan sebagai suku dalam jumlah tersebut.
Tentukan banyaknya hasil kali berbeda yang dapat dibentuk dari anggota-anggota daftar. Sebarang banyak bilangan bulat dari daftar boleh digunakan sebagai faktor dalam hasil kali tersebut.
Tentukan bilangan bulat \(m\) yang membuat daftar memuat setidaknya \(10\%\) dari bilangan-bilangan bulat dalam \(\{1,2,\dots,m\}\text{.}\)

2.

Jika Anda harus memasukkan \(n+1\) merpati ke dalam \(n\) sarang, setidaknya dua merpati harus dimasukkan ke sarang yang sama. Apa yang terjadi jika Anda harus memasukkan \(mn+1\) merpati ke dalam \(n\) sarang?

3.

Perhatikan himpunan \(X=\{1,2,3,4,5\}\) dan andaikan Anda memiliki dua sarang. Andaikan pula Anda memiliki \(10\) merpati, yaitu subhimpunan-subhimpunan beranggota \(2\) dari \(X\text{.}\) Dapatkah Anda memasukkan \(10\) merpati ini ke dalam dua sarang sedemikian sehingga tidak ada subhimpunan beranggota \(3\text{,}\) \(S=\{a,b,c\}\subset X\text{,}\) yang semua merpati dari \(S\) masuk ke sarang yang sama? Selanjutnya, jawablah pertanyaan yang sama jika \(X=\{1,2,3,4,5,6\}\) dengan \(15 = C(6,2)\) merpati.

4.

Misalkan \(n=10,000\text{.}\) Seorang teman memberi tahu Anda bahwa ia memiliki suatu keluarga rahasia subhimpunan dari \(\{1,2,\dots,n\}\text{,}\) dan jika Anda berhasil menebaknya dengan tepat, ia akan memberi Anda satu juta dolar. Anda merasa mengetahui keluarga subhimpunan yang dimaksudnya, dan keluarga itu memuat tepat separuh dari semua subhimpunan, i.e., keluarga tersebut memiliki \(2^{n-1}\) subhimpunan. Bahaslah cara menyampaikan dugaan Anda kepada teman tersebut sebagai upaya memenangkan hadiah.

5.

Misalkan \(N\) menyatakan himpunan bilangan bulat positif. Jika \(f:N\rightarrow N\) adalah suatu fungsi, misalkan \(E(f)\) merupakan fungsi yang didefinisikan oleh \(E(f)(n) = 2^{f(n)}\text{.}\) Tentukan \(E^5(n^2)\text{.}\)