Axler’s Linear Algebra Done Right, Exercise 1C-24

Problem
A function f:\mathbb{R} \rightarrow \mathbb{R} is called even if

    \[   f(-x) = f(x)\]


for all x \in \mathbb{R}. A function f:\mathbb{R} \rightarrow \mathbb{R} is called odd if

    \[   f(-x) = -f(x)\]


for all x \in \mathbb{R}. Let U_e denote the set of real-valued even functions on \mathbb{R} and let U_o denote the set of real-valued odd functions on \mathbb{R}. Show that:

    \[   \mathbb{R}^\mathbb{R}=U_e \oplus U_o\]



Proof. To show that U_e + U_o is a direct sum, it is sufficient to prove that U_e \cap U_o = {0}. Let f \in U_e \cap U_o. Hence, f(x) = f(-x) = -f(-x) for all x \in R, which only happens for f(x) = 0. Hence, U_e + U_o is a direct sum.

Let g \in \mathbb{R}^\mathbb{R}. The equation \mathbb{R}^\mathbb{R}=U_e \oplus U_o means that g can be written as the sum of an odd function o and an even function e. Or in other words, for all x \in \mathbb{R}:

(1)   \begin{equation*}    g(x) = o(x) + e(x)\end{equation*}

and also:

(2)   \begin{equation*}    g(-x) = o(-x) + e(-x)\end{equation*}


By the definition of the odd and even functions, (2) can be written as:

(3)   \begin{equation*} g(-x) = -o(x) + e(x)\end{equation*}


The system of linear equations (1) and (3) has a unique solution o(x) = (g(x) - g(-x)) / 2 and e(x) = (g(x) + g(-x)) / 2. Hence, g can always be uniquely written as the sum of an odd function and an even function. \qed

Pinter’s Book of Abstract Algebra Chapter 11, Exercise D5


Problem
Let G be a group and let a, b \in G. Prove the following:
Let \operatorname{ord}(a)=n, and suppose a has a kth root, say a=b^k. Then \langle a\rangle=\langle b\rangle iff k and n are relatively prime.

Proof. Consider the cyclic subgroup of \mathbb{Z}_{10}. For a = 2 and b = 1, we have a = b^2, n = 5, and \gcd(2, 5) = 1. However, \langle 1 \rangle = \mathbb{Z}_{10} but \langle 2 \rangle consists of all even numbers of \mathbb{Z}_{10}. Hence \langle a \rangle \neq \langle b \rangle. A contradiction. \qed

Protected: Programmer Bermain Truf

This content is password protected. To view it please enter your password below:

DP Bitmask

Untuk menjelaskan konsep DP Bitmask, saya gunakan salah satu contoh soal di SPOJ yang saya rasa adalah contoh straight-forward yang bisa langsung dicoba implementasinya oleh pembaca.
Continue reading

Problem Development Process

Artikel ini dulu saya tulis sebagai guideline dalam persiapan soal di TOKI. Tetapi saya rasa artikel ini juga akan berguna bagi rekan-rekan yang ingin mempersiapkan kompetisi-kompetisi pemrograman. Semoga bisa sedikit banyak membantu meningkatkan kualitas kompetisi pemrograman di Indonesia.

Tahap-tahap pemrosesan sebuah soal yang sudah cukup ideal menurut saya dan biasa saya terapkan, saya jelaskan sebagai berikut.
Continue reading

OSK – Persiapan

Note: Catatan ini ditulis seminggu sebelum OSK 2013

Banyak di antara kita yang karena satu-dua hal baru bisa mulai mempersiapkan diri untuk mengikuti OSK minggu depan. Tentu saja persiapan yang baik seharusnya dari jauh-jauh hari. Dulu saya mempersiapkan diri selama kurang lebih satu tahun, dan menghabiskan sangat banyak waktu. Tetapi, kalau memang tidak memungkinkan, bukan berarti kita tidak bisa melakukan ‘perlawanan’. Karena ada beberapa yang minta advice, saya coba rangkum di sini. Semoga membantu.
Continue reading

Seni Membuat Bug, untuk Kompetisi Pemrograman

Peringatan: Apabila Anda tidak mengerti bug itu apa, silakan cari tahu dulu sebelum membaca lebih lanjut. Kesalahpahaman isi artikel ini akibat mengabaikan peringatan ini bukan kesalahan penulis.

Pada note ini penulis paparkan tips-tips rahasia bagaimana membuat program penuh bug berdasarkan pengalaman penulis maupun pengamatan penulis terhadap orang-orang di sekitar penulis.
Continue reading

Debugging pada Kontes Pemrograman

Debugging dan implementasi adalah dua hal yang tidak bisa dipisahkan. Seberapa baik kita bisa melakukan debugging sangat (meskipun bukan seluruhnya) tergantung dari seberapa baik kita melakukan implementasi. Jadi, tips-tips debugging akan dimulai dari bagaimana melakukan implementasi agar program kita bisa di-debug dengan baik. Berikut ini beberapa pegangan saya waktu implementasi (towards debuggable code) ketika kontes. Tentu saya tidak berharap semua orang setuju atau cocok dengan tips-tips ini:
Continue reading