Diễn Đàn MathScopeDiễn Đàn MathScope
  Diễn Đàn MathScope
Ghi Danh Hỏi/Ðáp Thành Viên Social Groups Lịch Ðánh Dấu Ðã Ðọc

Go Back   Diễn Đàn MathScope > Sơ Cấp > Lý Thuyết Số

News & Announcements

Ngoài một số quy định đã được nêu trong phần Quy định của Ghi Danh , mọi người tranh thủ bỏ ra 5 phút để đọc thêm một số Quy định sau để khỏi bị treo nick ở MathScope nhé !

* Nội quy MathScope.Org

* Một số quy định chung !

* Quy định về việc viết bài trong diễn đàn MathScope

* Nếu bạn muốn gia nhập đội ngũ BQT thì vui lòng tham gia tại đây

* Những câu hỏi thường gặp

* Về việc viết bài trong Box Đại học và Sau đại học


Trả lời Gởi Ðề Tài Mới
 
Ðiều Chỉnh Xếp Bài
Old 03-10-2018, 05:26 AM   #1
huynhcongbang
Administrator

 
huynhcongbang's Avatar
 
Tham gia ngày: Feb 2009
Đến từ: Ho Chi Minh City
Bài gởi: 2,408
Thanks: 2,164
Thanked 4,162 Times in 1,377 Posts
Gửi tin nhắn qua Yahoo chát tới huynhcongbang
Về bài số học trong đề thi chọn đội tuyển TPHCM

Mình xin phân tích một số nội dung liên quan đến bài toán này. Các thảo luận liên quan mọi người có thể xem tại đây:
http://mathscope.org/showthread.php?t=51921

Trích:
Nguyên văn bởi MATHSCOPE View Post
T
$\boxed{20}$ [Sài Gòn] Gọi $S$ là tập hợp các hoán vị của 164 số nguyên dương đầu tiên.
  1. Có bao nhiêu hoán vị $\left(a_1,\,a_2,\,\ldots ,\,a_{164}\right)\in S$, thỏa mãn $a_i\ne i\;\forall\,i=\overline{1,\,164}$ và $a_i\equiv i\pmod{41}\quad\forall\,i=\overline{1,\,164}?$
  2. Tồn tại hay không một hoán vị $\left(a_1,\,a_2,\,\ldots ,\,a_{164}\right)\in S$, thỏa mãn với mỗi $i\in\{1,\,2,\,\ldots ,\,164\}$ luôn tồn tại $b_i\in\{0,\,1,\,\ldots ,\,40\}$ sao cho $a_1+a_2+\ldots+a_i\equiv b_i^2\pmod{41}$.
Về câu a của bài toán, có thể thấy rằng các số cùng số dư khi chia cho $41$ sẽ đổi chỗ cho nhau. Số hoán vị không có điểm cố định của $4$ phần tử là $9$, có thể dùng công thức hoặc liệt kê cụ thể ra.
Từ đây suy ra kết quả của câu này là $9^{41}$.

Bài toán sẽ thú vị hơn xíu nếu điều kiện đổi thành $a_i + i$ chia hết cho $41$ hoặc xét một bội lớn hơn của $41$, chẳng hạn $410.$

Về câu b, ngoài 2 cách của anh 2M và bạn chemthan, bài toán có thể tiếp cận nhẹ nhàng hơn như sau, cũng là ý mà tác giả "chế" ra bài này:

Cách 1 (của tác giả). Dùng bổ đề: số nguyên tố $p=3k+2$ sẽ có tính chất $\{1^3,2^3, \ldots, p^3\}$ là hệ thặng dư đầy đủ mod $p$. Khi đó, ta chọn $a_i \equiv i^3 \pmod{41}$ là xong, vì để ý rằng $$1^3+2^3+\cdots+k^3$$ luôn là số chính phương.

Chứng minh bổ đề: Giả sử trong bộ trên có hai số $i\ne j$ sao cho ${{i}^{3}}\equiv {{j}^{3}}(\bmod p)$, suy ra ${{i}^{3k}}\equiv {{j}^{3k}}(\bmod p)$. Theo định lý Fermat nhỏ thì ${{i}^{3k+1}}\equiv {{j}^{3k+1}}(\bmod p)$ nên
$${{i}^{3k+1}}\equiv {{j}^{3k+1}}=j\cdot {{j}^{3k}}\equiv j\cdot {{i}^{3k}}(\bmod p),$$ kéo theo ${{i}^{3k}}(i-j)$ chia hết cho $p$ hay $i\equiv j(\bmod p)$, vô lý vì $i,j\in \{1,2,\ldots ,p\}$ và $i\ne j.$

Cách 2 (của học sinh). Nhận xét $$1+3+5+\cdots+2k-1=k^2$$ nên hoán vị sau đây sẽ thỏa mãn đề bài:
Xếp các số lẻ từ $1$ đến $41$, xếp các số chẵn từ $2$ đến $40$, tiếp tục xếp các số lẻ từ $43$ đến $81$, ... cứ như thế.

Đáp án cho thấy bất kỳ số nguyên tố $p=3k+2$ nào cũng tồn tại hoán vị như thế. Tuy nhiên, lời giải của học sinh cho thấy, các số như thế có rất nhiều. Ta thử phân tích tí xíu về các số thỏa mãn tồn tại hoán vị như thế, tạm gọi là "số đẹp".

Theo cách giải thứ 2, rõ ràng bất kỳ số nguyên dương lẻ $2m+1$ nào cũng là "số đẹp".
Tiếp theo, ta thấy bội của $2m+1$ cũng đẹp, vì rõ ràng ta xếp hết $2m+1$ số đầu xong thì cứ cộng mỗi số cho $2m+1$ rồi xếp đến các số tiếp theo, và cứ thế. Như thế, số nguyên dương không phải lũy thừa của $2$ đều đẹp. Vậy còn lũy thừa của $2$ thì sao?

Số $2$ đẹp, xét hoán vị $1,2$.
Số $n=2^k$ có tổng của tất cả $n$ số là $2^{k-1}(2^k-1)$, số này chia $n$ dư là $2^{k-1}$. Như thế thì với $k$ chẵn, không tồn tại hoán vị thỏa mãn đề bài.
Tuy nhiên, ta có nhận xét rằng nếu $a$ đẹp thì các ước của $a$ cũng đẹp, nhưng vì số $4$ không đẹp nên tất cả các lũy thừa khác của $2$ cũng thế.

Vậy nên tất cả các số đẹp cần tìm là: 2 cùng tất cả các số có ước nguyên tố lẻ.

Mong được trao đổi thêm với mọi người về bài toán này.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________
Sự im lặng của bầy mèo
huynhcongbang is offline   Trả Lời Với Trích Dẫn
The Following 3 Users Say Thank You to huynhcongbang For This Useful Post:
ncthanh (03-10-2018), Thụy An (03-10-2018), tranphongk33 (03-10-2018)
Old 03-10-2018, 02:03 PM   #2
Thụy An
+Thành Viên+
 
Tham gia ngày: Oct 2017
Bài gởi: 73
Thanks: 1
Thanked 52 Times in 37 Posts
Trích:
Nguyên văn bởi huynhcongbang View Post
cũng là ý mà tác giả "chế" ra bài này:

Cách 1 (của tác giả). Dùng bổ đề: số nguyên tố $p=3k+2$ sẽ có tính chất $\{1^3,2^3, \ldots, p^3\}$ là hệ thặng dư đầy đủ mod $p$. Khi đó, ta chọn $a_i \equiv i^3 \pmod{41}$ là xong, vì để ý rằng $$1^3+2^3+\cdots+k^3$$ luôn là số chính phương.

Chứng minh bổ đề: Giả sử trong bộ trên có hai số $i\ne j$ sao cho ${{i}^{3}}\equiv {{j}^{3}}(\bmod p)$, suy ra ${{i}^{3k}}\equiv {{j}^{3k}}(\bmod p)$. Theo định lý Fermat nhỏ thì ${{i}^{3k+1}}\equiv {{j}^{3k+1}}(\bmod p)$ nên
$${{i}^{3k+1}}\equiv {{j}^{3k+1}}=j\cdot {{j}^{3k}}\equiv j\cdot {{i}^{3k}}(\bmod p),$$ kéo theo ${{i}^{3k}}(i-j)$ chia hết cho $p$ hay $i\equiv j(\bmod p)$, vô lý vì $i,j\in \{1,2,\ldots ,p\}$ và $i\ne j.$
Chế quá hay! Anh hoàn toàn ko nghĩ đến tổng các lập phương. Mà chú là tác giả hả?
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
Thụy An is offline   Trả Lời Với Trích Dẫn
Trả lời Gởi Ðề Tài Mới

Bookmarks

Ðiều Chỉnh
Xếp Bài

Quuyền Hạn Của Bạn
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is Mở
Smilies đang Mở
[IMG] đang Mở
HTML đang Tắt

Chuyển đến


Múi giờ GMT. Hiện tại là 11:14 AM.


Powered by: vBulletin Copyright ©2000-2018, Jelsoft Enterprises Ltd.
Inactive Reminders By mathscope.org
[page compression: 49.22 k/53.81 k (8.52%)]