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

[bangbang1412]

Bài $1$ : Cho $n$ nam sinh và $n$ nữ sinh xếp thành một hàng , người ta tìm cách cắt thành $2$ khúc sao cho mỗi khúc có số nam sinh bằng số nữ sinh . Gọi $A$ là số trường hợp không cắt được và $B$ là số trường hợp chỉ cắt được theo một cách duy nhất . Chứng minh $B=2A$

Bài $2$ : Cho $m,n \in N^{*}$ . CMR số cách biểu diễn $n$ dưới dạng tổng  của những số nguyên dương không lớn hơn $m$ bằng số cách bieur diễn $n$ dưới dạng không ít hơn $m$ số nguyên dương .

Bài $3$ : Có bao nhiêu miền trên mặt phẳng được chia bằng $n$ hình tròn mà $3$ đường không giao nhau tại $1$ điểm , hai đường bất kỳ giao nhau tại $2$ điểm.

Bài $4$ : Cho một đường tròn , ta vẽ một đường kính , tại mỗi mút đường kính ta đánh số $1$ , tiếp tục lấy các điểm chính giữa $2$ cung chia bởi đường kính ban đầu và đánh số $2$ tại mỗi mút , ở bước thứ $3$ lấy các điểm chính giữa chia bởi $2$ đường kính kia và đánh mỗi mút số $3$ . Cứ làm như vậy đến bước thứ $n$ . Tính tổng số các các số được đánh trên đường tròn sau $n$ bước ?

Bài $5$ : Cho các số $a_{i}$ nhận hai giá trị $0,1$ . Gọi $S_{n}$ và $P_{n}$ là số các giá trị lần lượt chẵn lẻ của tổng $S=\sum _{i=1}^{n} a_{i}$ . Tính $\frac{S_{n}}{P_{n}}$

Bài viết đã được chỉnh sửa nội dung bởi bangbang1412: 27-06-2014 - 19:21

[hxthanh]

 

Bài $1$ : Cho $n$ nam sinh và $n$ nữ sinh xếp thành một hàng , người ta tìm cách cắt thành $2$ khúc sao cho mỗi khúc có số nam sinh bằng số nữ sinh . Gọi $A$ là số trường hợp không cắt được và $B$ là số trường hợp chỉ cắt được theo một cách duy nhất . Chứng minh $B=2A$

Bài này ta thấy ngay là phải xây dựng song ánh.

- Xét trường hợp chỉ cắt được 1 cách duy nhất thành hai phần X và Y, nếu ta lấy đối xứng qua điểm cắt ta được hai phần X' và Y' cũng là một trường hợp chỉ cắt được 1 cách duy nhất

- Đổi chỗ 2 phần X và Y ta được một trường hợp không cắt được, tương tự đổi chỗ hai phần X' và Y' ta cũng được một trường hợp không cắt được.

Từ đây suy ra điều phải chứng minh.

 

Bài $2$ : Cho $m,n \in N^{*}$ . CMR số cách biểu diễn $n$ dưới dạng tổng  của những số nguyên dương không lớn hơn $m$ bằng số cách biểu diễn $n$ dưới dạng tổng của không quá $m$ số nguyên dương .

Có lẽ đề là như vậy!

Biểu diễn $n$ gồm các số hạng, mỗi số hạng không quá $m$ bằng một hàng các số 1 ta được một bảng có $k$ hàng và nhiều nhất là $m$ cột các số 1. Đổi cột cho hàng ta được một bảng có $k$ cột và không quá $m$ hàng, mỗi hàng này là một số hạng.

Từ đó ta có điều phải chứng minh.

[bangbang1412]

Bài này ta thấy ngay là phải xây dựng song ánh.

- Xét trường hợp chỉ cắt được 1 cách duy nhất thành hai phần X và Y, nếu ta lấy đối xứng qua điểm cắt ta được hai phần X' và Y' cũng là một trường hợp chỉ cắt được 1 cách duy nhất

- Đổi chỗ 2 phần X và Y ta được một trường hợp không cắt được, tương tự đổi chỗ hai phần X' và Y' ta cũng được một trường hợp không cắt được.

Từ đây suy ra điều phải chứng minh.

 

 

Có lẽ đề là như vậy!

Biểu diễn $n$ gồm các số hạng, mỗi số hạng không quá $m$ bằng một hàng các số 1 ta được một bảng có $k$ hàng và nhiều nhất là $m$ cột các số 1. Đổi cột cho hàng ta được một bảng có $k$ cột và không quá $m$ hàng, mỗi hàng này là một số hạng.

Từ đó ta có điều phải chứng minh.

thấy giải thích rõ bài song ánh được không thầy 

[hxthanh]

Có một sự nhầm lẫn không hề nhỏ trong lập luận của bài 1 Rất tiếc!

[Karl Heinrich Marx]

Đây là một ý tưởng mới nghĩ ra của em không rõ có đúng không thầy Thanh kiểm tra giúp xem.

Trước hết đây là cách mình nhìn nhận bài toán. Thường những cái gì mà 2 đầu cân đối với nhau em thường liên tưởng đến ý tưởng hình dung đồ thị hàm số liên tục.

Cụ thể ta đặt $T(i),G(i)$ lần lượt là số trai và gái kể từ trái sang. Xét $f(i)=T(i)-G(i)$. Khi đó $f(0)=f(2n)=0$. Ta đánh dấu lên hệ tọa độ những điểm $f(i)$ và nối những điểm kề nhau lại, sẽ tạo ra một đồ thị liên tục nối giữa 2 điểm trên trục hoành. Và nếu tạo ra một đồ thị kiểu như thế nối 2 điểm $(0;0)$ và $(2n;0)$ ta có tương ứng 1 cách xếp chỗ.

Những cách xếp tạo ra được đúng 1 lần cắt thì tức là đồ thị này cặt trục hoành tại đúng 1 điểm, khi đó tại 1 điểm cắt ta hình dung sẽ có 2 dạng đồ thị, một là 2 nhánh so với điểm cắt cùng nằm một phía với trục hoành và hai là 2 nhánh nằm ở 2 phía khác nhau.Nếu mà 2 đồ thị ở 2 dạng khác nhau mà lấy phần bên phải so với điểm cắt của đồ thị này đối xứng qua trục hoành thu được đồ thị kia thì ta gọi 2 đồ thị này là cùng cặp.

Bây giờ ta chỉ ra cách tạo ra một đồ thị thuộc loại A tức là ko cắt trục hoành. Tại điểm cắt, nếu 2 nhánh nằm khác phía với trục hoành thì ta lấy đối xứng phần nằm bên phải điểm cắt qua trục hoành, còn nếu 2 nhánh nằm cùng phía thì giữ nguyên, khi đó ta sẽ được một đồ thị có 2 nhánh nằm cùng phía điểm cắt, ta lấy điểm cắt dịch lên hoặc kéo xuống 2 đơn vị sao cho cùng phía với đồ thị, khi đó ta sẽ tạo ra đc 1 đồ thị hoàn toàn nằm về 1 phía ko cắt trục hoành thỏa mãn. Và 2 đồ thị cùng cặp thì chỉ cho ra 1 đồ thị thuộc loại A nên $B=2A$.

Diễn đạt theo ngôn ngữ tổ hợp ta có thể diễn đạt cách chuyển từ loại B sang A như thế này. Giả sử ta cắt được đúng 1 lần ở điểm $2p$. Khi đó nếu $2p$ và $2p+1$ khác giới tính thì ta giữ nguyên trạng thái, nếu $2p$ và $2p+1$ cùng giới tính thì từ vị trí $2p+1$ trở đi ta thay bạn nam bằng bạn nữ và ngược lại nữ bởi nam. Khi đó 2 kiểu này loại B ta đều thu được bạn $2p$ và $2p+1$ khác giới tính. Bây giờ chỉ cần đổi chỗ 2 bạn này là sẽ tạo ra 1 cách xếp loại A (điều này phải chứng minh, phần này mình nhác nghĩ quá, chiếu theo cách nghĩ đồ thị ta thấy nó sẽ rõ ràng hơn)

Lập luận thế này thì cũng phải chỉ ra mỗi cách loại A phải biến đc thành 2 cách loại B nữa, cái này chắc dựa theo trên mà làm ngược lại.

[Karl Heinrich Marx]

Hôm nay mình xem lại thì có vẻ lời giải này không đúng rồi. Mình nghĩ cách tiếp cận này khả thi nhưng cần phải chỉnh lại cách tạo ra song ánh, cần dịch chuyển điểm cắt theo 1 cách khác, cách dịch chuyển này không tạo ra song ánh. Hi vọng có bạn nào đầu tư suy nghĩ giúp chỗ này.

Bài 2 có một cách giải như thế này, với mỗi cách biểu diễn $n$ dưới dạng tổng không quá $m$ số, ta sắp xếp các số trong cách biểu diễn từ bé tới lớn, vẽ ra các cột với mỗi cột có số ô vuông đơn vị bằng với số xuất hiện trong biểu diễn các cột theo thứ tự từ bé đến lớn. Sau đó quay cầm tờ giấy quay 90 độ nhìn ngang sang sẽ được một cách biểu diễn tương ứng với các số không vượt quá $m$. Bài này còn có thể giải theo hàm sinh nhưng mình thấy cách giải này hay hơn khi đọc được mình thấy rất ấn tượng với nó và nó gợi ra một cách nhìn mới trong giải toán,  bạn cố gắng vẽ ra để hiểu hơn về cách giải này.

Bài viết đã được chỉnh sửa nội dung bởi Karl Heinrich Marx: 29-06-2014 - 19:34

[bangbang1412]

Hôm nay mình xem lại thì có vẻ lời giải này không đúng rồi. Mình nghĩ cách tiếp cận này khả thi nhưng cần phải chỉnh lại cách tạo ra song ánh, cần dịch chuyển điểm cắt theo 1 cách khác, cách dịch chuyển này không tạo ra song ánh. Hi vọng có bạn nào đầu tư suy nghĩ giúp chỗ này.

Bài 2 có một cách giải như thế này, với mỗi cách biểu diễn $n$ dưới dạng tổng không quá $m$ số, ta sắp xếp các số trong cách biểu diễn từ bé tới lớn, vẽ ra các cột với mỗi cột có số ô vuông đơn vị bằng với số xuất hiện trong biểu diễn các cột theo thứ tự từ bé đến lớn. Sau đó quay cầm tờ giấy quay 90 độ nhìn ngang sang sẽ được một cách biểu diễn tương ứng với các số không vượt quá $m$. Bài này còn có thể giải theo hàm sinh nhưng mình thấy cách giải này hay hơn khi đọc được mình thấy rất ấn tượng với nó và nó gợi ra một cách nhìn mới trong giải toán,  bạn cố gắng vẽ ra để hiểu hơn về cách giải này.

 

http://www.artofprob...?f=41&t=555984 

Đây là lời giải trên mathlinks , em thì chưa đủ khả năng tiếng anh để giải cả bài nên anh Karl Heinrich Marx , thầy hxthanh , anh LNH ,....... ai đó có thể dịch cho em được không ạ .

[Karl Heinrich Marx]

http://www.artofprob...?f=41&t=555984 

Đây là lời giải trên mathlinks , em thì chưa đủ khả năng tiếng anh để giải cả bài nên anh Karl Heinrich Marx , thầy hxthanh , anh LNH ,....... ai đó có thể dịch cho em được không ạ .

Đọc bài viết này em cần có một ít hiểu biết về số Catalan, và cái này anh quên tên gọi nhưng nó nói về số đường đi từ điểm (0;0) đến điểm $(m,n)$. Thực ra cách nhìn nhận của tác giả bài này với cách anh nêu ở trên không khác gì nhau cả, người này nêu ra B là số cách đi từ điểm (0;0) đến (n,n) mà có đi qua đường chéo, còn A thì không. Số Catalan có rất nhiều song ánh và số cách đi từ (0,0) đến (n,n) mà luôn nằm dưới đường chéo là một trong số đó. Anh này đưa về cách đếm số đường đi chỉ chạm vào đường chéo đúng 1 lần và k vượt qua nó bằng số đường đi k chạm vào đường chéo. Cách anh nói ở trên thì trục hoành cũng tương tự như đường chéo vậy. Có điều ở đây anh cố gắng xây dựng song ánh mà không được còn họ thì đếm để chỉ ra 2 tập có số phần tử bằng nhau. Giờ toán học mai một nhiều trong anh rồi, không còn đủ kiên nhẫn để xem thằng kia nó đếm như thế nào nữa, em hãy nhờ cao nhân khác chỉ dẫn nhá!