Đây là đề thi chọn đội tuyển Việt Nam tham dự IMO 2021 (Vietnam TST 2021). Tôi cảm ơn thầy Lê Phúc Lữ đã gửi code.
Author: Nguyễn Trung Tuân
A proof of Fermat’s theorem
Trong bài này chúng tôi sẽ giới thiệu một chứng minh của định lí Fermat nhỏ, chứng minh này của Euler.
Định lí. Cho số nguyên tố và số nguyên
không chia hết cho
Khi đó
Chứng minh. Vì có hai trong các số có cùng số dư khi chia cho
nên tồn tại số nguyên dương
sao cho
và
chọn
nhỏ nhất có tính chất này. Nếu
thì ta có điều cần chứng minh, sau đây ta xét trường hợp
Continue reading “A proof of Fermat’s theorem”
A proof of Pick’s theorem
Hình tạo bởi một đường gấp khúc đóng và không tự cắt được gọi là đa giác đơn. Một tam giác cơ bản là một tam giác trong mặt phẳng tọa độ có các đỉnh là các điểm nguyên đồng thời trên biên và phần trong của nó không còn điểm nguyên nào khác. Định lí Pick cho một cách đơn giản tính diện tích đa giác đơn có các đỉnh nguyên.
Trong chứng minh định lí Pick ta cần dùng công thức tích diện tích của tam giác trong mặt phẳng tọa độ.
Định lí 1. Trong mặt phẳng tọa độ , cho tam giác
Khi đó diện tích của tam giác
bằng
Nói riêng, với mỗi hai điểm
và
ta có diện tích của tam giác
bằng
Định lí 2. Mọi tam giác cơ bản đều có diện tích bằng
Chứng minh. Giả sử là một tam giác cơ bản bất kỳ. Không mất tính tổng quát, xem
trùng với gốc tọa độ
Ta cần chứng minh
với
và
lần lượt là tọa độ của
và
Gọi là điểm sao cho
là hình bình hành. Giả sử
là một điểm nguyên nằm trong hoặc trên biên hình bình hành sao cho
khác các đỉnh. Khi đó
thuộc tam giác
và điểm
đối xứng với
qua tâm hình bình hành là điểm nguyên thuộc tam giác
nhưng khác các đỉnh, không thể xảy ra điều này do
là một tam giác cơ bản. Như vậy hình bình hành
không chứa điểm nguyên nào khác bốn đỉnh của nó.
Giả sử là một điểm nguyên bất kỳ. Vì
và
là hai vector không cùng phương nên tồn tại cặp số thực
để
Gọi
là điểm xác định bởi
Vì
và
thuộc
nên
thuộc hình bình hành
, nhưng
lại là một điểm nguyên, suy ra
phải là một trong bốn đỉnh của hình bình hành. Dễ thấy
và do đó
và
là hai số nguyên.
Gọi và
lần lượt là các vector đơn vị đặt trên
và
. Khi đó theo lập luận trên, tồn tại các cặp số nguyên
và
để
và
Từ hai đẳng thức này ta có
và
suy ra
và
trong đó
do
và
không thẳng hàng. Vì
và
là các số nguyên nên
và
đều là bội của
, do đó
và bởi thế,
Định lí Pick. Cho là một đa giác đơn có các đỉnh là các điểm nguyên,
là số điểm nguyên nằm trong và
là số điểm nguyên nằm trên biên của
. Khi đó ta có đẳng thức
Chứng minh. Chia thành
tam giác cơ bản. Gọi
là tổng các góc trong của tất cả các tam giác cơ bản đó. Ta sẽ tính
theo hai cách. Vì số tam giác là
nên
Tổng tất cả các góc có đỉnh là một điểm nguyên nằm trong bằng
, tổng tất cả các góc có đỉnh là một điểm nguyên nằm trên biên của
nhưng không phải đỉnh của
bằng
và tổng của tất cả các góc có đỉnh là đỉnh của
bằng
, ở đây
là số đỉnh của
. Do đó
.
Suy ra , mà
, suy ra điều phải chứng minh.
Một số đề thi chọn đội tuyển Toán của Hà Nội
Trong tài liệu này tôi sẽ giới thiệu một số đề thi chọn đội tuyển học sinh giỏi toán lớp 12 của Hà Nội, đội tuyển này sẽ tham dự kỳ thi chọn học sinh giỏi quốc gia cùng năm.
USEMO – United States Ersatz Math Olympiad
USEMO là một cuộc thi toán dành cho tất cả học sinh trung học cơ sở và trung học phổ thông Hoa Kỳ. Giống như nhiều cuộc thi, mục tiêu của nó là phát triển sự quan tâm và khả năng trong toán học (chứ không phải là đo lường nó). Tuy nhiên, đây là một trong số ít các cuộc thi cho tất cả học sinh trung học cơ sở và trung học phổ thông Hoa Kỳ.
USEMO được lưu trữ trên trang AoPS. Cuộc thi này không được tài trợ bởi MAA.
Độ khó của các bài toán của cuộc thi tương tự như IMO.
Các bạn có thể tìm hiểu thêm về cuộc thi ở đây, hoặc download.
Sau đây là đề thi của USEMO lần thứ nhất.
USEMO 2019-2020
Ngày thứ nhất
Bài 1. Cho là một tứ giác nội tiếp. Một đường tròn tâm
qua
và
cắt lại
và
lần lượt tại
và
(khác
). Gọi
là trực tâm của tam giác
Chứng minh rằng nếu
đồng quy thì hai tam giác
và
đồng dạng.
Bài 2. Tìm tất cả các ánh xạ thỏa mãn đồng thời hai điều kiện
1) .
2) với mỗi ,
có nghiệm nguyên khi và chỉ khi
có nghiệm nguyên.
Bài 3. Xét một lưới vô hạn các ô vuông đơn vị. Một đa giác bàn cờ là một đa giác đơn có các cạnh nằm dọc theo đường lưới của
Nikolai chọn một đa giác bàn cờ và đố bạn tô một số ô của
màu xanh, sao cho bất kỳ đa giác bàn cờ nào bằng
đều có ít nhất
ô xanh nhưng nhiều nhất là
Hỏi Nikolai có thể chọn
để bạn không thể thực hiện được công việc?
Ngày thứ hai
Bài 4. Chứng minh rằng với mỗi số nguyên tố tồn tại số nguyên dương
sao cho
Bài 5. Cho là một đa giác đều và
là tập đỉnh của nó. Mỗi điểm trong
được tô màu đỏ, trắng hoặc xanh. Một tập hợp con của
được gọi là yêu nước nếu nó chứa một số điểm bằng nhau mang mỗi màu và một cạnh của
được gọi là chói nếu các đầu mút của nó có màu khác nhau.
Giả sử yêu nước và số cạnh chói của
là chẵn. Chứng minh rằng tồn tại một đường thẳng không đi qua bất kỳ điểm nào trong
và chia
thành hai tập con yêu nước khác rỗng.
Bài 6. Cho là một tam giác nhọn với tâm đường tròn ngoại tiếp
và các đường cao
,
,
. Gọi
,
,
lần lượt là trung điểm của
,
,
.
cắt
tại
,
cắt
tại
,
cắt
tại
.
Giả sử cắt
tại
,
cắt
tại
. Chứng minh rằng các đường thẳng qua
,
,
,
lần lượt vuông góc với
,
,
,
đồng quy.
Popoviciu’s theorem
Trong bài này chúng tôi sẽ giới thiệu một công thức tính số nghiệm tự nhiên của phương trình ở đây
là các số nguyên dương thỏa mãn
và
là số tự nhiên.
Định lí. (Công thức Popoviciu) Gọi là số các cặp số tự nhiên
sao cho
, ở đây
là các số nguyên dương thỏa mãn
và
là số tự nhiên. Khi đó
với
là nghịch đảo modulo
của
và
là nghịch đảo modulo
của
.
Chứng minh. Gọi là hàm sinh của dãy số
. Ta có
Vì nên đa thức
có nghiệm là
với bội
và các nghiệm đơn
,
, ở đây
và
Kết hợp với
ta có tồn tại các số phức
sao cho
Để ý đến hệ số của , từ
ta có
Bây giờ ta sẽ đi tìm các số phức từ đẳng thức
Nhân hai vế của với
và cho
ta có
, sau đó nhân hai vế của
với
, để
một bên và cho
ta được
. Theo cùng một cách ta có
Thay vào ta được
Từ ta có
, mà
, suy ra
do đó
chứng minh tương tự ta được
thay hai đẳng thức cuối cùng vào ta có điều cần chứng minh.
Một số trang về Olympic Toán
Tôi có post một số trang về Olympic Toán trên facebook nhưng nó cứ chìm xuống khi đăng một bài khác, vì thế nên tôi lập topic này để lưu các link đó lại.
P. S. Hãy góp link bằng cách comment các bạn nhé! 🙂
Burnside’s lemma
Cho là một tập hợp và
là một nhóm. Ta nói
tác động trên
, hay
là một
tập, nếu có hàm
,
thoả mãn
và
, ở đây
là phần tử đơn vị của
.
Gìơ ta xét một tập
, với mỗi
, ta gọi quỹ đạo của
là tập
. Các quỹ đạo khác nhau của các phần tử trong
làm thành một phân hoạch của
, thật vậy, quan hệ
nếu có
để
là một quan hệ tương đương trên
. Khi
và
là các tập hữu hạn thì ta có thể tính số khối của phân hoạch này theo bổ đề sau đây.
Bổ đề Burnside. Nếu là một
tập hữu hạn (nghĩa là
và
là các tập hữu hạn và
là một
tập) và
là số các quỹ đạo khác nhau của các phần tử trong
thì
, trong đó với mỗi
,
là số phần tử của tập
.
Tôi sẽ không đưa ra chứng minh nào của bổ đề này ở đây, các bạn có thể tìm một chứng minh trong sách Tổ hợp của Ngô Đắc Tân hay sách về lý thuyết nhóm của Rotman. Gìơ ta đi xét các áp dụng của bổ đề này vào giải các bài toán đếm, các bài tập này đều có trong sách của Rotman.
Bài 1. Cho và
là các số nguyên dương. Hỏi có bao nhiêu lá cờ gồm
mảnh sao cho mỗi mảnh mang một trong
màu cho trước?(Ví dụ một lá cờ như vậy là cờ của Pháp gồm
mảnh).
Lời giải. Vì khi ta tô màu một mặt của lá cờ thì mặt sau sẽ được xác định hoàn toàn màu. Nên số lá cờ bằng số cách tô bảng bởi
màu, hai cách tô là như nhau nếu nó ở dạng như hình dưới đây.
(Trong hình trên các
là các màu.)
Gọi là tập các bộ
với
là một trong
màu đã cho với mỗi
. Ký hiệu
là nhóm các hoán vị trên
,
là nhóm con cyclic sinh bởi hoán vị
của
, ở đây
. Ta cho
tác động trên
theo luật
. Như trên đã phân tích, ta chỉ cần đếm số
các quỹ đạo của các phần tử của
theo tác động này là xong. Theo bổ đề Burnside, ta chỉ cần tính
và
. Dễ thấy
theo quy tắc nhân. Để tính
, ta chú ý rằng
không thay đổi khi tác động
nếu và chỉ nếu
, vậy cùng theo quy tắc nhân ta có
. Như thế đáp số của bài toán là
Bài 2. Cho và
là các số nguyên dương. Chứng minh rằng có
cách tô màu bảng vuông
bởi
màu.
Lời giải sơ lược. Lời giải y hệt như trường hợp trên. Ta đánh số các ô của bảng theo kiểu xoáy ốc, chia hai trường hợp chẵn, lẻ cho dễ đánh số. Tập
bây giờ là tập tất cả các bộ
, nhóm
bây giờ là nhóm con cyclic cấp
sinh bởi phép quay
của
.
Chú ý. Khi ta có bài số 5 trong VMO 2010.