Chủ đề này có 1 trả lời

[lehoan]

Tìm số nguyên dương $n$ nhỏ nhất sao cho tồn tại song ánh $f: \{1,2,...,n\} \to \{1,2...,n\}$ sao cho với mọi $1\le i\le n-1$ thì

$|f(i+1)-f(i)|\in \{7,9\}$

Hãy tổng quát hóa bài toán:

[tanlsth]

Em nghĩ khi tổng quát thay $ 7,9 $ bởi $ p,q \in N*, (p,q)=1 $ thì kết quả sẽ là $ n_{min}=p+q $.
Để chứng minh ta sử dụng đồ thị.
2 đỉnh được nối với nhau khi nó có trị tuyệt đối của hiệu thuộc tập $ \{p,q\} $
Trước hết ta sẽ chứng minh với $ n=p+q $ thì thỏa mãn
Ta đánh hướng cho đồ thị theo 1 chiều cố định từ trái qua phải. Hiệu của một cạnh là lấy số ở đầu mút phải trừ đầu mút trái. Xét một chu trình có độ dài lớn nhất.
Khi đó trong chu trình chỉ có thể có 2 loại cạnh có hiệu là $ \{p,-q\} $ hoặc $ \{-p,q\} $
Giả sử chỉ có loại $ \{p,-q\} $ thì giả sử có $ m $ loại cạnh $ p $ và $ k $ loại cạnh $ q $. Do tổng các cạnh bằng $ 0 $ nên $ mp-kq=0 $ suy ra $ k \vdots p, m \vdots q $ suy ra $ k+m \geq p+q $ hay $ k+m=p+q $ hay tồn tại 1 chu trình đi qua tất cả các đỉnh của đồ thị.
Lấy chu trình này làm song ánh ta có điều phải chứng minh
Từ chứng minh này ta cũng chứng minh được $ n $ không thể bé hơn $ p+q $ vì từ $ $
Ta có điều phải chứng minh.