Bài toán kết nối facebook


Hôm nay, xin kể với các bạn về "bài toán kết nối facebook"!

Bài toán này nói rằng nếu bạn chọn bất kỳ 6 người nào trên facebook, thì trong 6 người này, bạn có thể chọn ra được 3 người mà, hoặc là, cả 3 người này đều là friend của nhau, hoặc là, trong 3 người này không có ai là friend của ai cả.

Ví dụ, như hình dưới đây, ở phía bên trái chúng ta có 6 bạn: An, Bảo, Cường, Chi, Dũng và Đạt. Nếu như hai bạn là friend của nhau trên facebook thì chúng ta kết nối họ lại bằng một đường màu tím, còn nếu họ không là friend thì chúng ta nối lại bằng đường màu xanh.

Chúng ta thấy rằng trong 6 bạn này, chúng ta có thể chọn ra 3 bạn là An, Dũng và Chi, cả 3 bạn này đều là friend của nhau bởi vì họ được nối bởi các đường màu tím. Trường hợp 3 bạn Đạt, Bảo và Cường cũng vậy.
Còn trong ví dụ phía bên phải, chúng ta có 6 bạn: Kim, Lan, Mai, Nam, Nga và Nhi. Chúng ta có thể chọn ra được 3 bạn là Nga, Mai và Nam, trong 3 bạn này không có ai là friend của ai cả bởi vì các bạn này được nối bởi các đường màu xanh. Ba bạn Nhi, Nam và Mai cũng vậy.

Tổng luỹ thừa và định lý Wolstenholme


Kỳ trước chúng ta đã học cách tìm công thức tính tổng các luỹ thừa $$S_k(n) = 1^k + 2^k + 3^k + \dots + n^k.$$
Hôm nay chúng ta sẽ xem xét các tính chất chia hết của $S_k(n)$. Chúng ta sẽ chứng minh rằng nếu $p$ là một số nguyên tố và $k$ không chia hết cho $p-1$ thì $$S_k(p-1) = 1^k + 2^k + 3^k + \dots + (p-1)^k = 0 \pmod{p}.$$

Đồng thời chúng ta cũng sẽ tìm hiểu về $$S_{-k}(n) = \frac{1}{1^k} + \frac{1}{2^k} + \frac{1}{3^k} + \dots + \frac{1}{n^k}.$$

Có một định lý trong số học liên quan đến tính chia hết của $S_{-k}(n)$, đó là Định lý Wolstenholme.
Định lý Wolstenholme. Nếu $p$ là một số nguyên tố $>3$ thì $$S_{-1}(p-1) = \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{p-1} ~=_{Q} ~0 \pmod{p^2} $$ và $$S_{-2}(p-1) = \frac{1}{1^2} + \frac{1}{2^2} + \frac{1}{3^2} + \dots + \frac{1}{(p-1)^2} ~=_{Q} ~0 \pmod{p}.$$

Chúng ta sẽ chứng minh một tính chất tổng quát hơn, đó là nếu $p$ là một số nguyên tố và $k$ không chia hết cho $p-1$ thì $$S_{-k}(p-1) = \frac{1}{1^k} + \frac{1}{2^k} + \frac{1}{3^k} + \dots + \frac{1}{(p-1)^k} ~=_{Q} ~0 \pmod{p}.$$

Tổng luỹ thừa


Hôm nay chúng ta sẽ học về công thức tính tổng các luỹ thừa $$S_k(n) = 1^k + 2^k + 3^k + \dots + n^k .$$


Công cụ chính mà chúng ta sẽ dùng là nhị thức Newton sau đây $$(x+y)^k = x^k + {k \choose 1} x^{k-1} y + {k \choose 2} x^{k-2} y^2 + {k \choose 3} x^{k-3} y^3 + \dots + {k \choose {k-1}} x y^{k-1} + y^k.$$


Thuật toán Euclid


Kỳ trước chúng ta đã học về bổ đề Bezout. Hôm nay chúng ta sẽ học về thuật toán Euclid. Thuật toán này dùng để xác định các hệ số trong đẳng thức Bezout.

Trước hết chúng ta phát biểu bổ đề Bezout. 

Bổ đề Bezout. Nếu $d$ là ước số chung lớn nhất của hai số nguyên $a$ và $b$ thì sẽ tồn tại hai số nguyên $x$ và $y$ sao cho $$d = a ~x + b ~y.$$

Thuật toán Euclid mục đích đi tìm ước số chung lớn nhất $d$ của hai số $a$ và $b$, và xác định hai giá trị của $x$ và $y$ trong đẳng thức Bezout $$d = a ~x + b ~y.$$

Ý tưởng của thuật toán Euclid rất đơn giản và tự nhiên.

Bổ đề Bezout


Hôm nay chúng ta sẽ học về một kết quả rất hay trong số học, đó là bổ đề Bezout. Bổ đề này phát biểu như sau.

Bổ đề Bezout. Nếu $d$ là ước số chung lớn nhất của hai số nguyên $a$ và $b$ thì sẽ tồn tại hai số nguyên $x$ và $y$ sao cho $$d = a x + b y.$$

Muốn xác định giá trị của hai số $x$ và $y$ trong bổ đề Bezout, chúng ta có thể dùng thuật toán Euclid. Chúng ta sẽ học về thuật toán này vào kỳ sau.


Chứng minh lại định lý Wilson


Kỳ trước chúng ta đã học về modulo cho số hữu tỷ. Để miêu tả ứng dụng của nó, hôm nay chúng ta sẽ chứng minh lại Định lý Wilson bằng cách sử dụng ngôn ngữ modulo.

Định lý Wilson là một định lý nổi tiếng trong số học. Định lý này được phát biểu như sau.

Định lý Wilson. Nếu $p$ là một số nguyên tố thì $$(p-1)! = -1 \pmod{p}.$$

Modulo cho số hữu tỷ II


kỳ trước, chúng ta đã giới thiệu về khái niệm modulo cho số hữu tỷ. Hôm nay, chúng ta tiếp tục học về khái niệm này.

Đầu tiên, chúng ta ôn lại một vài ví dụ và định nghĩa: $$\frac{14}{5} =_{Q} ~0 \pmod{7}, $$ $$ \frac{16}{55} =_{Q} ~\frac{9}{55} =_{Q} ~\frac{2}{55} \pmod{7},$$ $$\frac{1}{4} =_{Q} ~\frac{8}{4} =_{Q} ~2 \pmod{7}, \dots$$
Định nghĩa. Cho $n$ là một số nguyên, và $\alpha$, $\beta$ là hai số hữu tỷ. Chúng ta nói rằng $\alpha$ và $\beta$ bằng nhau modulo $n$, và viết $$\alpha =_{Q} ~\beta \pmod{n}$$ khi và chỉ khi tồn tại một số nguyên $k$ nguyên tố cùng nhau với $n$ sao cho $k(\alpha - \beta)$ là một số nguyên và $$k(\alpha - \beta) = 0 \pmod{n}.$$

Modulo cho số hữu tỷ


Mấy tháng trước, chúng ta đã đọc một loạt bài về modulo. Đó là modulo cho số nguyên. Xin nhắc lại định nghĩa như sau.

Định nghĩa. Cho $n$, $a$, $b$ là các số nguyên. Chúng ta nói rằng $a$ và $b$ bằng nhau modulo $n$, và viết $$a = b \pmod{n}$$ khi và chỉ khi $a-b$ là một bội số của $n$.

Ví dụ như $$8 = 0 \pmod{4},$$ $$9 = 1 \pmod{4},$$ $$-5 = -1 = 3 = 7 \pmod{4}, \dots $$

Hôm nay, xin giới thiệu với các bạn một khái niệm mới về modulo cho số hữu tỷ. Trước khi đi vào chi tiết của định nghĩa, chúng ta sẽ liệt kê một vài ví dụ cho các bạn thấy ngay được modulo số hữu tỷ là như thế nào.

Ví dụ về modulo cho số hữu tỷ: $$\frac{8}{5} =_{Q} ~0 \pmod{4}, $$ $$ -\frac{12}{55} =_{Q} ~0 \pmod{4},$$ $$\frac{29}{15} =_{Q} ~\frac{25}{15} = \frac{5}{3} \pmod{4}$$

Chứng minh Định lý Wilson bằng công thức nội suy


Kỳ trước chúng ta đã học về hai công thức nội suy cho đa thức, đó là công thức nội suy Newtoncông thức nội suy Lagrange. Cả hai công thức này đều có thể dùng để chứng minh Định lý Wilson.

Ở đây, chúng ta chỉ trình bày một cách chứng minh định lý Wilson sử dụng công thức nội suy Newton. Xin dành cho các bạn phần còn lại, đó là chứng minh Định lý Wilson sử dụng công thức nội suy Lagrange.

Định lý Wilson là một định lý nổi tiếng trong số học. Định lý này nói rằng nếu $p$ là một số nguyên tố thì số $(p−1)!+1$ sẽ chia hết cho $p$.

Đa thức nội suy Lagrange


Hôm nay chúng ta sẽ tiếp tục học về công thức nội suy cho đa thức. Kỳ trước, chúng ta đã học về công thức nội suy Newton, hôm nay chúng ta học thêm một công thức nội suy khác gọi là công thức nội suy Lagrange.

Chúng ta sẽ dùng ví dụ sau đây $$P(x) = 2x^2 - 3x + 3$$

Chúng ta thấy rằng $P(x)$ là một đa thức bậc hai và chúng ta có thể tính được $$P(1) = 2, ~~P(2) = 5, ~~P(3) = 12.$$

Bài toán đa thức nội suy là bài toán ngược, tức là, cho biết $P(1) = 2$, $P(2) = 5$, và $P(3) = 12$, tìm lại đa thức $P(x)$.

Đa thức nội suy Newton


Hôm nay chúng ta sẽ học về công thức nội suy cho đa thức.

Giả sử chúng ta có đa thức sau đây $$P(x) = 2x^2 - 3x + 3$$

Cho $x$ một vài giá trị, chúng ta tính được giá trị của $P(x)$ như sau $$P(1) = 2 - 3 + 3 = 2,$$ $$P(2) = 8 - 6 + 3 = 5,$$ $$P(3) = 18 - 9 + 3 = 12, \dots$$

Câu hỏi đặt ra là, nếu ngược lại, chúng ta biết được $$P(1) = 2, ~~P(2) = 5, ~~P(3) = 12,$$ liệu chúng ta có thể tìm lại được đa thức $P(x)$ hay không?

Câu trả lời là được. Công thức đa thức nội suy giúp cho chúng ta tìm lại được đa thức $P(x)$. Hôm nay chúng ta sẽ học về công thức nội suy Newton, kỳ sau chúng ta sẽ học về công thức nội suy Lagrange.

1 = 2012 = 2013


các bài trước, chúng ta đã học về cách chứng minh bằng quy nạp và đã dùng phương pháp này để giải một số bài toán. Chúng ta có thể thấy rằng phương pháp chứng minh bằng quy nạp rất tiện dụng trong việc giải toán. Hôm nay, chúng ta sẽ xem xét hai cách chứng minh bằng quy nạp dẫn đến một kết quả sai là $$1 = 2012 = 2013$$ Các bạn thử chỉ ra xem cách chứng minh này sai ở đâu nhé.


Nhị thức Newton


Hôm trước chúng ta đã học về tam giác Pascal và cách khai triển nhị thức Newton dựa vào các hệ số trong tam giác Pascal. Nhân dịp học về quy nạp, chúng ta sẽ chứng minh bằng quy nạp

  • công thức của tam giác số Pascal $$p_{n,k} = {n \choose k} = \frac{n!}{k! (n-k)!}$$
  • và định lý khai triển nhị thức Newton $$(x+y)^n = x^n + {n \choose 1} x^{n-1} y + {n \choose 2} x^{n-2} y^2 + \dots + {n \choose {n-2}} x^{2} y^{n-2} + {n \choose {n-1}} x y^{n-1} + y^n$$

Quy nạp III


Hôm nay chúng ta giải tiếp một vài bài toán bằng phương pháp quy nạp.


Bài toán 7. Để ý rằng $$\cos 2 \alpha = 2 \cos^2 \alpha - 1$$
Chứng minh rằng có thể viết $\cos n\alpha$ thành một đa thức của biến $\cos \alpha$.


Quy nạp II


Hôm nay chúng ta tiếp tục giải tiếp một số bài toán bằng phương pháp quy nạp.

Bài toán 4. Chứng minh rằng $$1 \times 2 \times 3 + 2 \times 3 \times 4 + \dots + n (n+1)(n+2) = \frac{1}{4} n(n+1)(n+2)(n+3).$$


Quy nạp


Hôm nay chúng ta sẽ học về phép quy nạp toán học. Thông thường, chúng ta sẽ dùng quy nạp để chứng minh một phát biểu nào đó đúng với mọi số tự nhiên.

Để tiện cho việc diễn đạt, chúng ta sẽ gọi $P(n)$ là một phát biểu nào đó liên quan đến biến số tự nhiên $n$. Chứng minh bằng quy nạp sẽ gồm các bước sau.

Bước 1: gọi là bước khởi điểm. Chúng ta sẽ chứng minh $P(n)$ đúng cho trường hợp đầu tiên là $n=0$.

Bước 2: gọi là bước quy nạp. Bước này là bước quan trọng nhất. Ở bước này, 
  • chúng ta giả sử rằng $P(n)$ đúng cho các trường hợp $0 \leq n \leq k$, 
  • với giả thiết đó, chúng ta sẽ chứng minh $P(n)$ cũng đúng với trường hợp $n=k+1$. 

Từ hai bước này, theo nguyên lý quy nạp toán học, chúng ta sẽ kết luận rằng $P(n)$ sẽ đúng với mọi số tự nhiên $n$.


Bộ số Pitago

Trong hình học có một định lý rất quen thuộc gọi là Định lý Pitago, nói rằng trong một tam giác vuông thì bình phương cạnh huyền bằng tổng bình phương của hai cạnh góc vuông.
Định lý Pitago: $BC^2 = AB^2 + AC^2$

Vì vậy mà phương trình $$x^2 + y^2 = z^2$$ được gọi là phương trình Pitago và nghiệm $(x,y,z)$ của phương trình này được gọi là bộ số Pitago. Lẽ dĩ nhiên chúng ta chỉ quan tâm đến nghiệm số nguyên.

Hôm nay chúng ta sẽ cùng nhau giải phương trình Pitago. Chúng ta sẽ chứng minh rằng phương trình này có vô số nghiệm.

Định lý Wilson


Hôm nay xin giới thiệu với các bạn một định lý liên quan đến số nguyên tố, đó là Định lý Wilson. Định lý này nói rằng nếu $p$ là một số nguyên tố thì số $(p-1)! + 1$ sẽ chia hết cho $p$.

Ở đây, ký hiệu $n!$ có nghĩa là $$n! = 1 \times 2 \times 3 \times \dots \times n.$$

Ví dụ,
  • $1! + 1 = 2$ chia hết cho $2$
  • $2! + 1 = 3$ chia hết cho $3$
  • $4! + 1 = 25$ chia hết cho $5$
  • $6! + 1 = 721$ chia hết cho $7$

Một vài bài toán về số nguyên tố


Kỳ trước, chúng ta đã học về số nguyên tố, và Định lý Euclid cho chúng ta biết rằng tồn tại vô hạn các số nguyên tố. Kỳ này, chúng ta tiếp tục xem xét về số nguyên tố. Các nhà toán học nổi tiếng như Fermat, Euler, Gauss rất thích thú tìm hiểu về các số nguyên tố. Có nhiều bài toán về số nguyên tố, phát biểu thì rất đơn giản, nhưng đến nay vẫn chưa ai tìm ra được lời giải.


Định lý Euclid về số nguyên tố


Tiếp tục câu chuyện về số nguyên tố, hôm nay chúng ta sẽ chứng minh rằng tồn tại vô số các số nguyên tố. Đây chính là Định lý Euclid về số nguyên tố. Định lý này có một cách chứng minh rất là đơn giản, nhưng cách chứng minh này có lẽ là một trong những chứng minh hay nhất trong toán học.


Số nguyên tố


Hôm nay chúng ta sẽ tìm hiểu về số nguyên tố - những viên gạch cơ bản của số học.

Số nguyên tố là một số tự nhiên lớn hơn 1không chia hết cho số nào cả, ngoại trừ nó chia hết cho 1 và chia hết cho chính nó. Ví dụ như 2, 3, 5, 7, 11, 13 là số nguyên tố. Số 9 không phải là số nguyên tố vì nó chia hết cho 3. Số 2012 không phải là số nguyên tố vì nó chia hết cho 2.

Điểm Fermat của hình tam giác II

Kỳ trước chúng ta đã tìm hiểu về bài toán hình học Fermat, đó là cho một tam giác $ABC$, tìm điểm $M$ sao cho $MA + MB + MC$ là ngắn nhất.
bài toán Fermat: tìm điểm $M$ sao cho $MA + MB + MC$ là ngắn nhất

Điểm Fermat của hình tam giác


Kỳ trước ở chuổi bài về modulo chúng ta đã tìm hiểu câu chuyện về nhà toán học Fermat với bài toán nổi tiếng $$x^n + y^n = z^n.$$

Hôm nay chúng ta sẽ xem xét về một bài toán hình học mang tên ông. Như chúng ta đã biết, Fermat không phải là một nhà toán học chuyên nghiệp, mà là một luật sư. Ông làm toán cho vui, và những công trình của ông mà chúng ta biết được ngày hôm nay là nhờ căn cứ vào những thư từ trao đổi giữa ông và bạn bè, cũng như những ghi chép ngẫu nhiên của ông trên những trang sách mà ông đã đọc. Nổi tiếng nhất dĩ nhiên là bài toán $x^n + y^n = z^n$ cùng với lời chú thích "tôi đã tìm ra lời giải tuyệt đẹp nhưng lề sách không đủ chỗ để viết ra" mà ông đã ghi bên lề cuốn sách của Diophantus.

Bài toán hình học mà chúng ta sẽ xem xét hôm nay bắt nguồn từ một lá thư mà Fermat đã gởi cho nhà toán học người Ý, Torricelli. Trong thư ông Fermat đố ông Torricelli tìm ra một điểm mà có tổng khoảng cách đến ba đỉnh của một hình tam giác là bé nhất. Bài này thì ông Torricelli giải được, vì vậy mà bây giờ có người gọi điểm đó là điểm Fermat, có người thì gọi nó là điểm Torricelli.
bài toán Fermat: tìm điểm $M$ sao cho $MA + MB + MC$ là ngắn nhất

Bài toán về tìm khoảng cách ngắn nhất và một tính chất của hình elíp


Hôm nay chúng ta sẽ xem xét hai bài toán mà mới nhìn vào thì chúng ta thấy chúng có vẻ không liên quan gì đến nhau. Bài thứ nhất là một bài toán tìm khoảng cách ngắn nhất còn bài thứ hai thì về tính chất của đường tiếp tuyến hình elip.

Trước hết chúng ta xem xét về hình elip. Hình elip là hình sau đây.


với mọi điểm $P$ trên hình elip thì $PF_1 + PF_2 = \ell$

Hãy xem xét trường hợp đặc biệt


Tôi muốn chia xẻ với các bạn một kinh nghiệm mà tôi đã học được. Đó là khi đối diện với một bài toán mà chúng ta chưa biết phải làm như thế nào, thì việc đầu tiên chúng ta có thể làm là xem xét các trường hợp đặc biệt của bài toán. Xem xét các trường hợp đặc biệt giúp chúng ta dần dần hiểu rõ bài toán hơn. Để minh hoạ, chúng ta sẽ làm một vài bài toán.

modulo - Phần 6


Chúng ta cùng nhắc lại định nghĩa về modulo. Hai số $a$ và $b$ gọi là bằng nhau theo modulo $n$ nếu $a-b$ là một bội số của $n$, và chúng ta dùng ký hiệu $a = b \pmod{n}$. Ví dụ như $9 = 1 \pmod{8}$ và $14 = -2 \pmod{8}$.

Bình thường chúng ta hình dung các số nguyên nằm trên một trục số và chúng ta làm các phép tính cộng trừ nhân chia trên đó, chẳng hạn như $2 + 7 = 9$, $2 \times 7 = 14$, v.v...
trục số của chúng ta

modulo - Phần 5


Hôm nay chúng ta sẽ cùng nhau học về Định lý Fermat "nhỏ". Chúng ta sẽ thấy rằng định lý nhỏ Fermat rất là tiện dụng trong khi làm các phép tính toán modulo. Định lý này phát biểu như sau. Với mọi số nguyên tố $p$ và với mọi số nguyên $a$ không chia hết cho $p$ thì 
$$ a^{p-1} = 1 \pmod{p} . $$

Ví dụ:
  • Với $p=7$ và $a=3$, $$3^6 = 1 \pmod{7}$$
  • Với $p=13$ và $a=2014$, $$2014^{12} = 1 \pmod{13}$$
  • Với $p=29$ và $a=15$, $$15^{28} = 1 \pmod{29}$$

modulo - Phần 4


Nếu nói về những nhà toán học nổi tiếng qua mọi thời đại thì cần phải nhắc đến Pierre de Fermat. Chúng ta đọc tên ông trong tiếng Việt là Fẹcma. Ông là nhà toán học người Pháp, sống vào thời thế kỷ thứ 17.


Nếu nói về ông thì phải nhắc đến bài toán Fermat của ông. Bài toán đã từng làm điên đầu cho những nhà toán học cỡ hàng đầu thế giới cho đến những em học sinh phổ thông. Cái lý do mà bài toán này có quá nhiều người biết đến, cũng như có quá nhiều người đủ mọi lứa tuổi tham gia giải, là vì nó được phát biểu rất đơn giản, một em học sinh cấp 2 là đã có thể hiểu được.

Bài toán Fermat là như sau. Chứng minh rằng với mọi số $n \geq 3$ thì phương trình sau không có nghiệm
$$
x^n+y^n=z^n
$$

Nghiệm ở đây là nghiệm khác không vì chỉ cần $x$, $y$ hay $z$ bằng 0 thì phương trình trở thành tầm thường rồi.

modulo - Phần 2


Trong bài trước chúng ta đã học về khái niệm modulo. Hai số $a$ và $b$ được gọi là bằng nhau modulo $n$, ký hiệu $a = b \pmod{n}$, khi mà $a-b$ chia hết cho $n$.

Ví dụ $15 = 3 \pmod{4}$ và $99 = -1 \pmod{10}$.


modulo - Phần 1


Trong bài này chúng ta sẽ học về khái niệm modulo. Hai số $a$ và $b$ được gọi là bằng nhau modulo $n$ nếu $a$ và $b$ có cùng số dư khi chia cho $n$. Hay nói cách khác, là $(a-b)$ chia hết cho $n$. Chúng ta sẽ viết $a = b \pmod{n}$.

Ví dụ như, $5 = 9 \pmod{2}$, $-1 = 3 \pmod{2}$, $-2 = -8 \pmod{2}$. Rõ ràng theo modulo 2 thì một số $a$ bất kỳ sẽ hoặc là $a=0 \pmod{2}$ khi nó là số chẳn, hoặc là $a=1 \pmod{2}$ khi nó là số lẽ. 

Không gian 4 chiều là gì?


Trong toán học chúng ta thường nghe nói đến không gian 4 chiều, 5 chiều, v.v..., vậy thì chiều thứ 4 và chiều thứ 5 nằm ở đâu, làm sao chúng ta có thể tưởng tượng ra những chiều này.

Phép nhân thời đồ đá


Xin kể với các bạn một phương pháp làm phép tính nhân của người cổ đại. Tôi không còn nhớ phương pháp này tên gọi là gì và được phát minh ra từ thời nào. Thôi, chúng ta tạm gọi là phương pháp "làm tính nhân thời đồ đá" vậy!


Định lý Morley

Cho một hình tam giác $ABC$. Các đường chia ba góc $A$, $B$, $C$ của tam giác cắt nhau tại các điểm $A'$, $B'$, $C'$ như hình vẽ dưới đây. Chứng minh rằng tam giác $A'B'C'$ là một tam giác đều. Đây gọi là định lý Morley.