Bulgarian Mathematical Olympiads – Third and Fourth Rounds (1995-2000)

Xin gữi đến các bạn tài liệu tổng hợp đề thi vòng 3 và vòng 4 của Bulgary từ năm 1995 – 2000.
(Các đề này không có các cuốn tuyển tập RMC các năm)

Còn lí do vì sao mình đưa tài liệu này lên thì xem tại đây.

Bulgarian Mathematical Olympiads – 3rd and 4th-Rounds(1995-2000)

Chuyên đề dãy số

Gữi tặng các bạn chuyên đề dãy số của lớp 11A2 – Lê Quý Đôn – Đà Nẵng.

Danh sách các thành viên thực hiên:

Nguyễn Minh Nhật Tường
Nguyễn Phương Giang
Nguyễn Văn Phúc Hưng
Nguyễn Tấn Tài
Nguyễn Thành Long
Nguyễn Thị Kim Cương
Võ Thế Đông An
Võ Huỳnh Duy
Lê Hà My
Hoàng Duy Khánh
Trần Ngọc Chương

Mong các bạn đóng góp để các chuyên đề ngày một hoàng thiện.

Dãy số trong các kì thi Olympic

Tổng quát hóa một bài toán

Cho số nguyên tố p \equiv 1 \pmod{m}, m > 2. Chứng minh:
\prod^p_{t = 1} {\left( t^{m - 1} + t^{m - 2} + \cdots + 1 \right)} \equiv 0 \pmod{p}

Lời giải:

Xét các số có dạng i^m-1 với i \in (2,3,4,...,p-1). Ta giả sử g là căn nguyên thủy modulo p với g\neq 1 (ta chọn được do có đúng \varphi(p-1) căn nguyên thủy)

Khi ấy xét g^k thì do m>2 nên rõ ràng k<p-1 nên g^k \not \equiv 1 \pmod{p} vì ngược lại thì mâu thuẫn do ord_p(g)=p-1.

Do đó g^k \equiv t \pmod{p} suy ra 2\le t\le p-1 (do g^k \not \equiv 1 \pmod{p})

Lúc ấy xét số t^m-1 \equiv (g^k)^m-1 \equiv g^{mk}-1 \equiv g^{p-1}-1 \equiv 0 \pmod{p}.

Như vậy t^m-1 \vdots pt\neq 1 nên (t-1)(t^{m-1}+t^{m-2}+...+t+1) \vdots p.

Mặt khác gcd(t-1,p)=1 nên t^{m-1}+t^{m-2}+...+t+1 \vdots p suy ra \prod^p_{t = 1} {\left( t^{m - 1} + t^{m - 2} + \cdots + 1 \right)} \equiv 0 \pmod{p}

Graph – Learn form a mistake

Tìm số tự nhiên n>4 nhỏ nhất sao cho tồn tại n người thỏa mãn : 2 người quen nhau thì không có người quen chung còn 2 người không quen nhau thì có đúng 2 người quen chung.

Lời giải: (Hansongkyung – Mathscope)

1. Dễ dàng chứng minh được số người quen của mỗi người là bằng nhau (Tổ hợp & Rời rạc – Nguyễn Văn Thông)

2. Bài toán quy về 1 đồ thị có n đỉnh, m cạnh. Ứng với nó, mỗi đỉnh là 1 người, cạnh biểu thị cho sự quen biết giữa 2 người. Và điều kiện của đồ thị này là không có 3 cạnh này tạo thành 1 hình tam giác. Nếu 2 đỉnh không được nối với nhau thì tồn tại duy nhất 2 đỉnh khác cùng được nối với 2 đỉnh kia.

Gọi X là 1 đỉnh bất kì. Giả sử, X được nối với A_1,A_2,\cdots , A_m.

Mặt khác, trong $m$ đỉnh trên thì không có 2 đỉnh bất kì nào được nối với nhau.

-Với m = 1 thì chỉ có 2 đỉnh. Loại.

-Với m \ge 2.
1.Suy ra có duy nhất 1 điểm B_{i,j} \ne X là điểm chung giữa 2 điểm (A_i;A_j).

2. Đỉnh B_{i,j} này cũng không được nối với đỉnh nào khác thuộc tập X. Vì như vậy thì B_{i,j} sẽ có tới 3 người quen chung với X.

3. Nếu A_i được nối với 1 đỉnh C không thuộc tập B_i thì đỉnh C đó sẽ không đc nối với 1 điểm A_k nào thuộc X.

Vì nếu như C cùng được nối với A_i;A_k thì giữa 2 người A_iA_k sẽ cùng quen với người X, người B_{i,k} và người C kia.

Khi đó C sẽ chỉ được nối với A_i và không được nối với các đỉnh nào khác thuộc tập X. Suy ra giữa CX chỉ có mỗi 1 người quen. Vô lí.

\Rightarrow A_i sẽ không được nối với bất cứ điểm nào khác trừ X; B_{i,j} (j \ne i; j =1;m)

Vậy đồ thị đó chỉ chứa điểm X; A_i; B_{i,j}.

Từ những lập luận trên ta có được:

Tập những người không quen với X sẽ là \dfrac{m(m-1)}{2} Vì, với mỗi người trong X sẽ quen với m người khác, bỏ X ra thì còn m-1 người. Mà tập Xm người nên tổng cộng lại sẽ có (m-1)m nhưng vì đây là đồ thị vô hướng, nói các khác, sự quen biết là không có chiều nên ta phải chia cho 2.

Những người quen của Xm người

Thêm X nữa là 1 người.

Vậy tổng số người sẽ là:

n= \dfrac{m(m-1)}{2} + m +1

Giờ ta sẽ xét các trường hợp:

Với m=2 \Rightarrow n =4 loại

Với m=3, 4 ta đều chi ra được sự mâu thuẫn với điều kiện đề bài.

Với m=5 \Rightarrow n =16
Đáp án: n=16

Q.E.D

Một bài Số học – Tổ hợp

Cho tập hợp X=\left \{ 1,2,...,50 \right \}. Tìm số nguyên dương nhỏ nhất k sao cho mọi tập con gồm k phần tử của X đều chứa hai phần tử phân biệt ab sao cho ab chia hết cho a+b

Lời giải: (Stranger0411 – VMF)

Chứng minh k \ge 39
Các cặp số thoả mãn ab chia hết a+b: (3;6);(4;12);(5;20);(6;12);(6;30);(7;42);(8;2);(9;18);(10;15);(10;40);(12;24);(12;36);(14;35);(15;30);(16;48);(18;36);(20;30);(21;28);(21;42);(24;40);(24;48);(30;45);(36;45)

Xét tập M=(6,12,15,18,20,21,24,35,40,42,45,48). Vì 23 cặp trên đều có phần tử thuộc M nên tập X \backslash M không thỏa mãn bài toán. Mà |X \backslash M|=38 \rightarrow k \ge 39

Chứng minh mọi tập có 39 phần tử đều thỏa mãn bài toán:
Xét tập A bất kì gồm 39 phần tử của X.
Chọn 12 cặp số trong 23 cặp trên sao cho các phần tử không trùng nhau: (3;6);(4;12);(5;20);(7;42);(8;2);(9;18);(10;15);(14;35);(18;36);(21;28);(24;40);(30;45)

Ta thấy rằng 12 cặp trên chứa 24 phần tử của X. Nên X chỉ còn lại 26 phần tử.
Vậy ít nhất 13 phần tử của A của phải thuộc 12 cặp trên. Theo nguyên lí Drichlet thì A chứa ít nhất một trong 12 cặp trên. Từ đó tập A thỏa mãn đề bài.

Q.E.D