Đến nội dung

Hình ảnh

IMO 2022

imo 2022 olympiad quốc tế toán quốc tế

  • Please log in to reply
Chủ đề này có 8 trả lời

#1
hoangvipmessi97

hoangvipmessi97

    Binh nhì

  • Thành viên mới
  • 15 Bài viết

Ngày thi thứ nhất

Bài 1: Ngân hàng Oslo có phát hành hai loại tiền xu: đồng vàng (kí hiệu bởi A) và đồng bạc (kí hiệu bởi B). Mai có $n$ đồng vàng và $n$ đồng bạc được sắp xếp thành một dãy tùy ý. Một dãy con gồm các đồng xu liên tiếp thuộc cùng một loại được gọi là một chuỗi. Với số nguyên dương cố định $k \leq 2n$, Mai thực hiện liên tiếp các bước chuyển như sau: cô ta xác định chuỗi dài nhất có chứa đồng xu thứ $k$ từ bên trái và chuyển tất cả các đồng xu của chuỗi này về phía trái của hàng. Ví dụ, nếu $n=4$ và $k=4$, bắt đầu với cách xếp AABBBABA, quá trình thực hiện các bước chuyển như sau:

AABBBABA $\rightarrow$ BBBAAABA $\rightarrow$ AAABBBBA $\rightarrow$ BBBBAAAA $\rightarrow$ BBBBAAAA $\rightarrow$ ...

Xác định tất cả các cặp $(n,k)$ với $1 \leq k \leq 2n$ sao cho với mọi cách sắp xếp ban đầu, đến một lúc nào đó trong quá trình thực hiện các bước chuyển, $n$ đồng xu ở bên trái của hàng sẽ thuộc cùng một loại.

 

Bài 2: Gọi $\mathbb{R}^+$ là tập các số thực dương. Tìm tất cả các hàm số $f: \mathbb{R}^+ \rightarrow \mathbb{R}^+$ sao cho với mọi $x \in \mathbb{R}^+$ có đúng một giá trị $y \in \mathbb{R}^+$ thỏa mãn

$xf(y)+yf(x) \leq 2$.

 

Bài 3: Cho $k$ là một số nguyên dương và $S$ là một tập hữu hạn các số nguyên tố lẻ. Mi muốn xếp các phần tử của $S$ quanh một vòng tròn sao cho tích của hai số cạnh nhau bất kì có thể biểu diễn được dưới dạng $x^2 + x + k$ với $x$ nguyên dương nào đó. Biết rằng, hai cách xếp nhận được từ nhau qua phép quay và phép phản chiếu (đối xứng trục) được coi là như nhau. Chứng minh rằng Mi có nhiều nhất một cách xếp như vậy.

 

 

Ngày thi thứ hai

Bài 4: Cho ngũ giác lồi $ABCDE$ với $BC=DE$. Giả sử rằng có một điểm $T$ nằm trong $ABCDE$ sao cho $TB=TD,\ TC=TE$ và $\angle ABT=\angle TEA$. Đường thẳng $AB$ cắt các đường thẳng $CD$ và $CT$ lần lượt tại các điểm $P$ và $Q$, trong đó các điểm $P,B,A,Q$ nằm theo thứ tự trên đường thẳng. Đường thẳng $AE$ cắt đường thẳng $CD$ và $DT$ lần lượt tại các điểm $R$ và $S$, trong đó các điểm $R,E,A,S$ nằm theo thứ tự trên đường thẳng. Chứng minh rằng các điểm $P,S,Q,R$ nằm trên một đường tròn.

 

Bài 5: Tìm tất cả các bộ số nguyên dương $(a,b,p)$ với $p$ nguyên tố và

$a^p=b!+p$.

 

Bài 6: Cho số nguyên dương $n$. Một cao nguyên Nordic là một bảng $n \times n$ chứa tất cả các số nguyên từ $1$ đến $n^2$ sao cho mỗi ô vuông chứa đúng một số. Hai ô vuông được gọi là kề nhau nếu chúng có một cạnh chung. Ô vuông chỉ kề với các ô vuông chứa số lớn hơn số nằm trong đó được gọi là một thung lũng. Một con đường dốc là một dãy các ô vuông (có thể chỉ gồm một ô) thỏa mãn đồng thời các điều kiện:

(i) Ô vuông đầu tiên trong dãy là một thung lũng,

(ii) mỗi ô vuông tiếp theo trong dãy kề với ô vuông đứng trước nó,

(iii) các số được viết trên các ô vuông trong dãy có giá trị tăng dần.

Như là một hàm số của $n$, xác định giá trị nhỏ nhất có thể của số con đường dốc trong một cao nguyên Nordic.


Bài viết đã được chỉnh sửa nội dung bởi hoangvipmessi97: 15-07-2022 - 19:32


#2
Hoang72

Hoang72

    Thiếu úy

  • Điều hành viên OLYMPIC
  • 539 Bài viết

Câu 2 là một bài toán khá hay:

Với mỗi $x>0$, xét số $y_0>0$ sao cho $xf(y_0) +y_0f(x)\leq 2$.

Giả sử $y_0\neq x$.
Do tính duy nhất của $y_0$ nên $xf(x).2>2\Rightarrow xf(x) >1$
$\Rightarrow f(x)>\frac{1}{x}$.
Tương tự với $y_0$, ta cũng có $f(y_0)>\frac{1}{y_0}$.
Từ đó $xf(y_0) + y_0f(x)  > \frac{x}{y_0} + \frac{y_0}{x}>2$, vô lí.
Do đó $y_0=x$ hay $f(x)\leq \frac{1}{x},\forall x\in\mathbb R^+$. (1)
Suy ra $f(x)y + f(y)x>2,\forall x,y\in\mathbb R^+;x\neq y$. (*)
Nếu tồn tại $x>y$ mà $f(x) \geq  f(y)$ thì $f(x)y + f(y)x < 2f(x).x \leq 2$, vô lí.
Do đó $f$ là hàm giảm nghiêm ngặt.
Giả sử $\exists a>0: f(a) \neq \frac{1}{a}$.
Khi đó thay $x=a; y=\frac{1}{f(a)}$ vào (*) ta có:
$f\left(\frac{1}{f(a)}\right)> \frac{1}{a}$.
Mặt khác sử dụng (1) ta có:
$\frac{1}{f(a)} \geq a\Rightarrow f\left(\frac{1}{f(a)}\right) \leq f(a) \leq \frac{1}{a}$, mâu thuẫn.
Vậy $f(x)=\frac{1}{x},\forall x\in\mathbb R^+$.


#3
Nesbit

Nesbit

    ...let it be...

  • Quản lý Toán Ứng dụng
  • 2409 Bài viết

Không lẽ lực lượng VMF không còn giải nổi đề này sao? KietLW9 chém ngay bài hình làm gương anh xem nào!


Không đọc tin nhắn nhờ giải toán.

 

Góp ý về cách điều hành của mod

 

 


#4
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3903 Bài viết

Không lẽ lực lượng VMF không còn giải nổi đề này sao? KietLW9 chém ngay bài hình làm gương anh xem nào!

Nhờ sự trợ giúp của máy tính anh tìm được kết quả của bài 6
$f(n)= n^2+(n-1)^2$
Dựa vào đó đang nghĩ cách chứng minh đây :))
P/s: “Già” rồi nên đầu óc kém linh hoạt, dựa dẫm công nghệ quá mà! :))

#5
Hoang72

Hoang72

    Thiếu úy

  • Điều hành viên OLYMPIC
  • 539 Bài viết

Bài 5:

Xét hai trường hợp:

$\bullet$ $b\geq p$: Khi đó $a$ chia hết cho $p$.

Nếu $a\geq 2p$ thì $a^p>(2p)!+p>b!+p$, loại.

Do đó $a = p$.

Khi đó $b! = p^p - p$.

+) Nếu $p=2$ thì $b = 2$, $a=2$, thoả mãn.

+) Nếu $p=3$ thì $b = 4$, $a=3$, thoả mãn.

+) Xét $p>2$: Khi đó $p$ lẻ.

Dễ thấy nếu $b=p$ thì $b!<p^p-p$ (vô lí) nên $b\geq p+1$.

Vì $2\mid p+1$ nên $p+1 = \frac{p+1}{2} . 2 \mid p!$

$\Rightarrow (p+1)^2\mid b!$

$\Rightarrow (p+1)^2\mid p^{p-1} - 1$.

Đặt $p-1=2k$. Ta có $p^{p-1} - 1 = p^{2k} - 1 = (p^2-1)[(p^2)^{k-1} + ... + 1]\vdots (p+1)^2$.

Ta cần có $(p-1)[(p^2)^{k-1} + ... + 1]\vdots (p+1)$.

Mặt khác, $p^2\equiv 1\pmod{p+1}\Rightarrow (p^2)^{k-1} + ... + 1\equiv k\pmod {p+1}$.

Dẫn đến $((p^2)^{k-1} + ... + 1, p+1) = (k,p+1) \in\{1;2\}$, đồng thời $(p-1,p+1)=2$.

Từ đó ta có $4\vdots p+1\Rightarrow p=3$. (loại)

$\bullet$ $b<p$: Khi đó $(a,p) = (b,p) = 1$.

+) $a>b\Rightarrow a^p = a . a ... a > b! . a > p + b!$, vô lí.

+) $a\leq b\Rightarrow a\mid b!\Rightarrow a\mid p$, vô lí.

Vậy bài toán có 2 đáp số: $(a,b,p)\in \{(2;2;2), (3;4;3)\}$.


Bài viết đã được chỉnh sửa nội dung bởi Hoang72: 17-07-2022 - 15:35


#6
Hoang72

Hoang72

    Thiếu úy

  • Điều hành viên OLYMPIC
  • 539 Bài viết

Bài 1: Chủ yếu là xây dựng được phản ví dụ:

Kí hiệu $A_h$ là xâu gồm toàn các chữ cái $A$ được lặp lại $h$ lần.

$n\in\{1;2\}$ là hai trường hợp tầm thường nên ta không cần xét đến.

Do đó ta chỉ xét $n\geq 3$.

Xét các trường hợp:

$\bullet$ $k=2n$: Ta chọn xâu $ABAB...AB$, không thoả mãn.

$k\leq n-1$: Ta chọn xâu $A_{n-1}B_{n-1}AB$, không thoả mãn.

$\bullet$ $k \geq  \left \lfloor \frac{3n}{2} \right \rfloor+ 1$: Khi đó, đặt $x = 2n - (k-1); y = (k-1) - n$, thì $x\leq y$ và $x+y=n$.

Xét xâu $A_yB_yA_xB_x$ có $n$ kí tự $A$, $n$ kí tự $B$.

Do $2y+x=k-1<k$ nên ở bước thứ nhất, xâu $B_x$ được đảo lên đầu. Tương tự, xâu $A_x$ cũng được đảo lên đầu. Ở bước tiếp theo, do $2x+y\leq 2y+x<k$ nên xâu $B_y,A_y$ cũng lần lượt được đảo lên đầu. Cứ thế lặp lại liên tục, ta thấy không thoả mãn.

$\bullet$ $n\leq k\leq \left \lfloor \frac{3n}{2} \right \rfloor$: Gọi điểm phân biệt của một xâu là số các xâu dài nhất gồm các kí tự giống nhau liên tiếp khi tách từ xâu đó.

Do nếu tồn tại một xâu nào gồm $n$ kí tự liên tiếp đứng ở đầu thì $n$ kí tự tiếp theo là xâu gồm kí tự còn lại, nên ta thu được xâu mới thoả mãn.

Do đó khi chưa hoàn tất thì không tồn tại xâu $A_k$ hoặc $B_k$ đứng ở đầu.

Ta chứng minh rằng cứ sau hữu hạn bước thì điểm phân biệt của một xâu bị giảm.

Giả sử điều ngược lại. Thế thì đến thời điểm nào đó, các xâu bị đảo lên đầu đều là các xâu ở cuối.

Ở một thời điểm nào đó, nếu xâu bị đảo lên là $K_x$ với $K\in\{A;B\}$ thì $2n-x < k\Rightarrow x> 2n-k$.

Do đó xâu lúc này chỉ gồm các xâu liên tiếp có độ dài lớn hơn $2n-k$.

Mặt khác, $2(2n-k)\geq n$ nên xâu lúc này chỉ chứa một xâu có dạng $AA...A$, và tương tự một xâu có dạng $BB...B$, vô lí.

Dẫn đến tồn tại nhiều thời điểm xâu bị đảo lên đầu không ở cuối, tức số điểm phân biệt của xâu bị giảm.

Từ đó ta thấy đến một thời điểm nào đó, số điểm phân biệt của xâu là $2$. Ta có kết quả bài toán.

Câu 3 và câu 6 mình thấy khá khó nên hi vọng được nhìn thấy lời giải của mọi người ạ.


Bài viết đã được chỉnh sửa nội dung bởi Hoang72: 17-07-2022 - 16:25


#7
Nesbit

Nesbit

    ...let it be...

  • Quản lý Toán Ứng dụng
  • 2409 Bài viết

Nhờ sự trợ giúp của máy tính anh tìm được kết quả của bài 6
$f(n)= n^2+(n-1)^2$
Dựa vào đó đang nghĩ cách chứng minh đây :))
P/s: “Già” rồi nên đầu óc kém linh hoạt, dựa dẫm công nghệ quá mà! :))

Bài số 6 hay thật. Em tò mò không biết anh Thanh dùng máy tính kiểu gì, có thể dựa vào đó để tìm được một lời giải "bằng tay" chăng?


Không đọc tin nhắn nhờ giải toán.

 

Góp ý về cách điều hành của mod

 

 


#8
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3903 Bài viết

Bài số 6 hay thật. Em tò mò không biết anh Thanh dùng máy tính kiểu gì, có thể dựa vào đó để tìm được một lời giải "bằng tay" chăng?

Đại khái dùng để mò kết quả thôi em. Code dạng như sau:
Input
Nhập kích thước mảng n (dùng để thử dần)
Tạo kiểu tập hợp S={1,2,..,n^2}
Các biến phụ v.v…
Mặc định phần tử a(1,1)=1 (Cái này là võ đoán chỉ duy nhất 1 là thung lũng
S:= S-{a(1,1)}
Tạo bảng
Cho i,j chạy từ 1 đến n
Lặp randomize
a(i,j)=random(n^2+1)
S:= S-a(i,j)
Nếu a(i,j) không thuộc S thì quay lại random

Đếm số đường dốc ghi vào D

Lặp lại random
… điều kiện kết thúc lặp
Nói chung cũng khá dài, với lại khi thử với n=5 thì đơ máy luôn :))
Reset nóng và thế là công sức code 1 tiếng đồng hồ đi tong! :))

Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 21-07-2022 - 04:06


#9
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3903 Bài viết
Từ tâm mỗi hình vuông $1\times 1$ của bảng $n\times n$ ô vuông ta đặt vào $n^2$ điểm. Các điểm này được nối với nhau nếu hai hình vuông chứa hai điểm đó có cạnh liền kề. Như vậy ta đưa bài toán về việc xét:
Đồ thị phẳng $(C_n)$ với $n^2$ đỉnh, $2n(n-1)$ cạnh (và tất nhiên có $n^2+1$ mặt, ta không xét đến.)
Mỗi đỉnh của $(C_n)$ là một số nguyên dương phân biệt trong $\{1,2,…,n^2\}$
Trên mỗi cạnh $AB$ bất kỳ của đồ thị $(C_n)$ ta đặt mũi tên vào đỉnh $B$ nếu số ở đỉnh $B$ lớn hơn số ở đỉnh $A$ và ngược lại.
Một đỉnh mà không có mũi tên nào thì chính là thung lũng.
Như vậy số $1$ luôn là thung lũng dù nằm bất kỳ điểm nào.
Giả sử có duy nhất đỉnh $A$ chứa số $1$ là thung lũng trong $(C_n)$
Ta phải chứng minh rằng từ $A$ có thể đi đến mọi đỉnh khác theo chiều mũi tên
Khi đó số con đường dốc tối thiểu chính là số mũi tên hay chính là số cạnh của đồ thị, cộng thêm chính bản thân đỉnh $A$ cũng là một con đường dốc.
Như vậy số cần tìm là $d_{min}=2n(n-1)+1$
Nếu có từ $2$ thung lũng trở lên, ta phải chỉ ra rằng số con đường dốc $d$ sẽ không nhỏ hơn $d_{min}$

Nói thường dễ hơn là làm :D
Mình tin rằng chỉ cần chỉ ra được một cách sắp xếp các số thoả $d_{min}=2n(n-1)+1$ thì bài toán sẽ được giải quyết.

Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 21-07-2022 - 13:41






Được gắn nhãn với một hoặc nhiều trong số những từ khóa sau: imo, 2022, olympiad, quốc tế, toán quốc tế

1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh