Đến nội dung

Hình ảnh

Chứng minh rằng với mọi số nguyên dương $n$ thì luôn tồn tại một hoán vị $(a_0,a_1,...,a_{n-1})$ "tốt"

- - - - -

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

#1
Dracule Mihawk 123

Dracule Mihawk 123

    Lính mới

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

Bài 3 (HCM TST 2022-2023, vòng 1)

Với mỗi số nguyên dương $n$, hoán vị $(a_0,a_1,...,a_{n-1})$ của $0,1,...,n-1$ là "tốt" nếu $a_i+i$ là số chính phương.

a) Chứng minh rằng với $n=2023$, trong một hoán vị tốt $(a_0,a_1,...,a_{n-1})$ luôn tồn tại ít nhất một chỉ số $i$ sao cho $a_i+i$ chia hết cho $9$.

b) Chứng minh rằng với mọi số nguyên dương $n$ thì luôn tồn tại một hoán vị tốt.


Bài viết đã được chỉnh sửa nội dung bởi Dracule Mihawk 123: 13-06-2023 - 12:37


#2
Konstante

Konstante

    Hạ sĩ

  • Thành viên
  • 97 Bài viết

Bài này tưởng phức tạp mà chợt nghĩ ra thì thấy đơn giản.

 

1) Chứng minh phản chứng, giả sử $3 \nmid a_i + i$ với mọi $i$ thế thì $a_i + i \equiv 1 \pmod 3$ với mọi $i$ (do $a_i + i$ là chính phương), do vậy

 

$$\sum\limits_{i=0}^{2023-1} (a_i + i) \equiv 2023 \equiv 1 \pmod 3$$

 

Nhưng vì

 

$$\sum\limits_{i=0}^{2023-1} (P(i) + i) = 2 \times \sum\limits_{i=0}^{2023-1} i = 2022 \times 2023 \equiv 0 \pmod 3$$

 

Nên ta có mâu thuẫn.

 

2) Ý tưởng là xây dựng từ cuối bằng quy nạp. Chọn $k$ là số nhỏ nhất sao cho $k^2 \geq n-1$, với mọi giá trị i thỏa mãn $k^2 - n +1 \leq i \leq n-1$, đặt hoán vị $a_i = k^2 - i$, do vậy $a_i + i = k^2$. Bài toán bây giờ quy về xây dựng hoán vị tốt cho $n' = k^2 -n+1$, hiển nhiên là $n' < n$.

 

Ví dụ $n=12$:

 

  1. chọn $k=4$ (vì $4^2 \geq 12 - 1 > 3^2$),
  2. đặt $a_i = 16 - i$ với $5 \leq i \leq 11$.

Xây dựng tiếp cho $n=5$:

  1. chọn $k=2$ (vì $2^2 \geq 5 - 1 > 1^2$),
  2. đặt $a_i = 4 - i$ với  $0 \leq i \leq 4$.

Ta thu được hoán vị tốt:

 

$$\Bigl(\begin{matrix}0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ 4 & 3 & 2 & 1 & 0 & 11 & 10 & 9 & 8 & 7 & 6 & 5\end{matrix}\Bigr)$$

 






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

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