Các bài toán về nguyên lý Dirichlet

2002 All-Russian MO, Grade 9, Problem 5 There are eight rooks on a chessboard, no two attacking each other. Prove that some two of the pairwise distances between the rooks are equal. (The distance between two rooks is the distance between the centers of their cell.) China TST 2005

Nhận xét

Đăng nhận xét

Bài đăng phổ biến từ blog này

Các bài toán về thặng dư toàn phương

Tài liệu về thặng dư toàn phương Định lý Một số là thặng dư bậc hai của mọi số nguyên tố không là ước của nó là một số chính phương. Vì mọi lũy thừa lẻ của 2 là một số không thặng dư của 3, chúng ta có thể giả sử rằng một số như vậy chứa một thừa số lẻ. Gọi \(N\) là một thặng dư bậc hai của mọi số nguyên tố không là ước của nó, và \(N = j^2 n\), trong đó \(n\) không chứa các thừa số chính phương. Khi đó \(n\) là một thặng dư bậc hai của cùng các số nguyên tố như \(N\). Đặt \(n = p_1 p_2 \dots p_r\) và hơn nữa, gọi \(a\) là một số không thặng dư bậc hai của \(p_1\) (\(p_1\) lẻ) và \(b_i\) là một thặng dư bậc hai của \(p_i\), \((i=2,\dots,r)\). Các đồng dư \(x \equiv 1 \pmod{4}\), \(x \equiv a \pmod{p_1}\), \(x \equiv b_i \pmod{p_i} \equiv 1 \pmod{8}\) nếu \(p_i = 2\), \((i = 2, \dots, r)\), khi đó luôn có một nghiệm \(s\), vì các mô-đun là nguyên tố cùng nhau. Có vô số giá trị số nguyên tố cho nghiệm tổng quát \(x = 4kn + s\). Chọn một số không là ước của ...
Đọc thêm

Các bài toán về dãy số nguyên

LaTeX in HTML Bổ đề quan trọng (Biểu thức cổ định của dãy tuyến tính cấp hai) Cho dãy số \( (a_n) \) xác định bởi \[ a_{n+2} = aa_{n+1} - a_n +b\quad \forall n \in \mathbb{N}. \] Khi đó, biểu thức \( a_{n+1}^2 - a_n a_{n+2}-ba_{n+1} \) luôn nhận giá trị không đổi. Chứng minh. Thật vậy, ta có biến đổi sau \[ \begin{align} x_{n+1}^2 - x_n x_{n+2} - b x_{n+1} &= x_{n+1}(x_{n+1} - b) - x_n(a x_{n+1} - x_n + b) \\ &= x_{n+1}(a x_n - x_{n-1}) - x_n(a x_{n+1} - x_n + b) \\ &= x_n^2 - x_{n-1} x_{n+1} - b x_n \end{align} \] Đẳng thức trên đúng với mọi \( n \geq 0 \) nên \[ x_{n+1}^2 - x_n x_{n+2} - b x_{n+1} = x_1^2 - x_0 x_2 - b x_1 = \text{const.} \] Bổ đề quan trọng (Về sự tuần hoàn của các số dư) Cho dãy số nguyên \(\{x_n\}\) xác định bởi công thức truy hồi \[ x_{n+k} = a_1 x_{n+k-1} + \ldots + a_k x_n \] và \(k\) số hạng đầu tiên nguyên. Kh...
Đọc thêm

Căn nguyên thủy và ứng dụng

Giới thiệu Chúng ta đã thấy rằng với bất kỳ số nguyên dương \( n \) và bất kỳ số nguyên \( a \) nguyên tố cùng nhau với \( n \), cấp modulo \( n \) của \( a \) là ước của \( \varphi(n) \) và đặc biệt nó không thể vượt quá \( \varphi(n) \). Trong phần này, chúng ta quan tâm đến việc đặc trưng hóa những số \( n \) mà đạt được giới hạn này, tức là những số \( n \) mà tồn tại \( a \) sao cho \( \gcd(a,n) = 1 \) và \( \text{ord}_n(a) = \varphi(n) \). Hãy đặt tên cho những số \( a \) như vậy. Định nghĩa Cho \( n \) là một số nguyên dương. Một số nguyên \( a \) được gọi là căn nguyên thủy modulo \( n \) nếu \(\gcd(a, n) = 1\) và \(\operatorname{ord}_n(a) = \varphi(n)\). Ví dụ \(1\) là căn nguyên thủy mod \(2\), \(2\) là căn nguyên thủy mod \(3\), \(3\) là căn nguyên thủy mod \(4\), \(2\) và \(3\) là căn nguyên thủy mod \(5\), \(5\) là căn nguyên thủy mod \(6\), ... Tính chất Tính chất 1 Nếu \( a \) là một căn nguyên thủy modulo \( n \) và nếu \( b \equiv a \pmod{n} \), thì \( b ...
Đọc thêm