Đến nội dung

Hình ảnh

Topic nhận đề Tổ hợp - rời rạc


  • Chủ đề bị khóa Chủ đề bị khóa
Chủ đề này có 11 trả lời

#1
E. Galois

E. Galois

    Chú lùn thứ 8

  • Quản lý Toán Phổ thông
  • 3861 Bài viết

Chuyển nhanh đến:
1) Điều lệ
2) Đăng kí thi đấu
3) Lịch thi đấu và tổng hợp kết quả

Topic này dùng để BTC nhận đề thi từ các toán thủ thi đấu.

Điều 3. Phương thức thi đấu, cách tính điểm:
a. Phương thức thi đấu:

- Trước mỗi trận, các toán thủ nộp đề cho BTC, BTC chọn 1 đề thi đấu. Đề thi được chọn là của toán thủ nào thì toán thủ đó gọi là toán thủ ra đề.Toán thủ ra đề không phải làm bài. (BTC đảm bảo nguyên tắc mỗi toán thủ chỉ được chọn đề nhiều nhất 1 lần). Toán thủ đã được chọn đề 1 lần thì những trận sau đó không cần phải nộp đề nữa.
- Trong trường hợp đến hết ngày thứ Tư hàng tuần mà không có toán thủ nào nộp đề, BTC sẽ chỉ định toán thủ có SBD nhỏ nhất (chưa có đề được chọn) phải ra đề.
...

b. Cách tính điểm
...

+ Nếu ra đề sai, đề không đúng chủ đề định sẵn, đề vượt quá cấp học hoặc không giải được đề mình ra, toán thủ ra đề được −30 điểm.
+ Nếu đến lượt mà không ra đề được −20 điểm.
+ Ra đề mà không post đáp án đúng thời gian được −10 điểm
...


Điều 6. Quy định đề bài:
a. Nội dung:
-
Mỗi bộ đề bao gồm 1 câu không copy nguyên văn từ đề thi Olympic quốc gia trở lên.
b. Hình thức:
- Đề bài được gõ Latex rõ ràng.



BTC yêu cầu các toán thủ nộp đề về Tổ hợp - rời rạc. Đề cần nộp cùng đáp án

Các toán thủ khi thi đấu, cứ yên tâm rằng, sau khi đánh máy là đề đã được lưu, BTC đã nhận được đề của bạn, có điều bạn không nhìn thấy được mà thôi. Bạn nên mừng vì điều này, như thế các toán thủ khác không thể biết trước đề của bạn được.

Bạn cũng nên sử dụng chức năng xem trước của diễn đàn để sửa các lỗi Latex trước khi gửi bài, vì gửi rồi sẽ không xem và sửa lại được nữa.

1) Xem cách đăng bài tại đây
2) Học gõ công thức toán tại: http://diendantoanho...oạn-thảo-latex/
3) Xin đừng đặt tiêu đề gây nhiễu: "Một bài hay", "... đây", "giúp tớ với", "cần gấp", ...
4) Ghé thăm tôi tại 
http://Chúlùnthứ8.vn

5) Xin đừng hỏi bài hay nhờ tôi giải toán. Tôi cực gà.


#2
TNP

TNP

    Lính mới

  • Thành viên
  • 2 Bài viết
Đề bài:Cho 2013 ô vuông xếp thành một hàng, ta tô mỗi ô bằng mỗi màu xanh hoặc đỏ sao cho số cặp ô cùng màu bằng số cặp ô khác màu. Nếu ô đầu tiên là ô đỏ tính từ trái sang phải thì ô cuối cùng màu gì? Tại sao?(Mỗi cặp ô bao gồm hai ô vuông liên tiếp nhau)
Đáp án:Tô 1007 ô đầu tiên màu đỏ, ô thứ 1008 màu xanh, ô thứ 1009 màu đỏ,... ta tiếp tục tô xen kẽ như thế đến hết 2013 ô, ta sẽ có bộ 2013 ô thỏa mãn và dễ thấy ô cuối cùng là màu đỏ.
Bây giờ gọi $A$ là số cặp ô cùng màu, $B$ là số cặp ô khác màu, khi ta tô 2013 ô như trên ta có $A=B$ hay $A-B=0$. Kí hiệu ô thứ $k$ là $s_k$ tính từ trái sang phải.Chọn một ô $s_i(i \epsilon N, 2 \leq i \leq 2012)$, nếu ta đổi màu ô đó thì giá trị của $A$ sẽ tăng hoặc giảm 2 đơn vị và giá trị của $B$ sẽ giảm hoặc tăng 2 đơn vị tương ứng với $A$, như vậy qua mỗi lần đổi màu $s_i(i \epsilon N, 2 \leq i \leq 2012)$, giá trị của $A-B$ sẽ tăng hoặc giảm 4 giá trị.
Xét $s_{2013}$, với $s_{2013}$ là màu đỏ thỏa giá trị thì nếu ta đổi màu $s_{2013}$, $A$ sẽ tăng một hoặc giảm một đơn vị và $B$ sẽ giảm hoặc tăng một đơn vị tương ứng, như thế, ta thấy rằng nếu ta đổi $s_{2013}$ từ đỏ thành xanh, giá trị của $A-B$ luôn chia 4 dư 2, không thể nào bằng 0, vậy $s_{2013}$.
Đề xuất hướng mở rộng:với ý tưởng tương tự, ta sử dụng quy nạp và có thể chứng minh được với mọi số lẻ ô vuông, ô đầu và ô cuối cùng màu.

#3
cool hunter

cool hunter

    Thiếu úy

  • Thành viên
  • 544 Bài viết
ĐỀ
Cho 2n điểm trên mặt phẳng, trong đó không có 3 điểm nào thẳng hàng. CMR: những điểm này có thể phân thành n cặp sao cho các đoạn thẳng nối chúng không cắt nhau.
Đáp án:
Đầu tiên ta phân cặp các điểm mọt cách ngẫu nhiên & nối chúng lại vs nhau. Gọi S là tổng các đoạn thẳng được nối. Do ta hữu hạn cách phân cặp nên tập giá trị của S là hữu hạn. Nếu có hai đoạn thẳng CD & AB cắt nhau tại O thì ta thay AB,CD =AC,BD. Vì: $ AB +CD=(AO +OB) +(CO +OD) =(AO +OC) +(BO +OD) >AC +BD$ theo bđt tam giác, nên nếu cặp đoạn thẳng nao` đó giao nhau, ta có thể thay thế cách nối để S giảm xuống. Vì S chỉ có hữu hạn các giá trị nên 1 lúc nao` đó quá trình phải dừng. Và khi đó sẽ ko có các cặp đoạn thẳng giao nhau (đpcm)

Thà đừng yêu để giữ mình trong trắng

Lỡ yêu rôì nhất quyết phải thành công

                                                                 


#4
Math Is Love

Math Is Love

    $\mathfrak{Forever}\ \mathfrak{Love}$

  • Thành viên
  • 620 Bài viết
Toán thủ doxuantung97 xin ra đề:
Đề bài:
Chứng minh rằng:$\sum ^{n}_{k=0}(C^{k}_{n})^{2}=C^{n}_{2n}$.
Đáp án:
Đặt $P(x)=(x+1)^{2n}$
Theo khai triển Newton,ta có:
$P(x)=(x+1)^{2n}=\sum ^{2n}_{k=0}C^{k}_{2n}x^{k}$ (do lũy thừa của 1 luôn bằng 1)
Vậy hệ số của $x^{n}$ trong P(x) là $C^{n}_{2n}$ (1)
Mặt khác:$P(x)=(x+1)^{n}(x+1)^{n}=(\sum ^{n}_{k=0}C^{k}_{n}x^{k})(\sum ^{n}_{h=0}C^{h}_{n}x^{h})$
$\Rightarrow P(x)=\sum _{0\leqslant k,h\leqslant n}C^{k}_{n}C^{h}_{n}x^{k+h}$
Vậy hệ số của $x^{n}$ trong P(x) là $\sum _{0\leqslant h,k\leqslant n;k+h=n}C^{k}_{n}C^{h}_{n}=\sum ^{n}_{k=0}C^{k}_{n}C^{n-k}_{n}$
Ta thấy $C^{k}_{n}=C^{n-k}_{n}$ nên hệ số của $x^{n}$ trong P(x) là $\sum ^{n}_{k=0}C^{k}_{n}C^{n-k}_{n}=\sum ^{n}_{k=0}(C^{k}_{n})^{2}$ (2)
Từ (1) và (2) ta có đpcm

Hình đã gửi


#5
TNP

TNP

    Lính mới

  • Thành viên
  • 2 Bài viết
Bài đề nghị số 2 của TNP:Cho một hình vuông ABCD được chia thành 64 ô vuông bằng nhau. Chúng ta sẽ lát hình vuông bằng các domino 2x1 sao cho không có domino nào chờm lên nhau và toàn bộ diện tích của hình vuông đều được phủ kín bởi các domino. Ta gọi các domino có cạnh dài hơn song song với AD và BC là "nằm dọc", các domino có cạnh dài hơn song song với AB và CD là "nằm ngang". Chứng minh rằng hình vuông ABCD chỉ được lát bởi các domino thỏa các yêu cầu trên khi và chỉ khi số domino nằm dọc và số domino nằm ngang đều là số chẵn.
Giải:
Ta đánh số các ô vuông như sau:
13131313
22222222
13131313
22222222
13131313
22222222
13131313
22222222
(xin lỗi vì em không biết tạo một cái table dùng câu lệnh latex thế nào, hi vọng các anh hiểu)
Bây giờ, mọi domino nằm ngang đều phủ các ô có số 1 và số 3 hoặc là 2 ô có số 2, như vậy domino nằm ngang đều phủ các ô có tổng giá trị là 4, là một số chẵn.
Mặt khác, các domino nằm dọc lại phủ các ô mà tổng 2 ô đó đều là 3 hoặc 5, là một số lẻ.
Mà tổng giá trị các số nằm trong mỗi ô là 128, vậy nhất định số ô nằm dọc phải là số chẵn, mà ta cần 32 domino để phủ bàn cờ, vậy số ô nằm ngang cũng là số chẵn, ta có đpcm.

#6
Math Is Love

Math Is Love

    $\mathfrak{Forever}\ \mathfrak{Love}$

  • Thành viên
  • 620 Bài viết
Toán thủ MO37 xin phép ra lại đề: (Đề trước hình như có trong 1 đề thi HSG nên em xin phép ra đề khác):
Đề bài:
Ta viết n số nguyên dương:1;2;3;...;n trên một đường tròn theo chiều kim đồng hồ.Hỏi có bao nhiêu cách chọn ra k số trên đường tròn sao cho trong k số đó không có bất kì 2 số nào đứng cạnh nhau trên đường tròn$(2\leqslant k\leqslant \frac{n}{2})$.
Đáp án:
Gọi $A={x_{1};x_{2};...;x_{n}}: \left\{\begin{matrix} x_{i+1}-x_{i}\geqslant 2\\ x_{1};x_{2};...;x_{n}\in {1;2;...;n} \end{matrix}\right.$
$B={x_{1};x_{2};...;x_{n}}: \left\{\begin{matrix} x_{1}=1;x_{k}=n\\ x_{i+1}-x_{i}\geqslant 2\\ x_{1};x_{2};...;x_{n} \in {1;2;...;n} \end{matrix}\right.$
G là tập cách chọn thỏa mãn yêu cầu đề bài thì:
$|G|=|A\B|=|A|-|B|$ (vì B $\subset$ A)
Đặt:
$y_{1}=x_{1}$
$y_{2}=x_{2}-1$
$y_{3}=x_{3}-2$
....
$y_{k}=x_{k}-(k-1)$
Gọi C={$y_{1};y_{2};...;y_{k}$}:
$\left\{\begin{matrix}
y_{1};y_{2};...;y_{k}\in Z^{+}\\
1\leqslant y_{1}< y_{2}< ...<y_{k}\leqslant n-(k-1)
\end{matrix}\right.$(do $x_{k}\leqslant n$)
Xét ánh xạ:
$f: C \rightarrow A$
$(x_{1};x_{2};...;x_{k})x \mapsto(y_{1};y_{2};...;y_{k})$

Nhận xét: Dễ thấy $f$ là song ánh vì với mỗi giá trị của tập $(x_{1};x_{2};...;x_{k})$ xác định duy nhất giá trị của tập $(y_{1};y_{2};...;y_{k})$ và ngược lại.
Vậy $|A|=|C|=C^{k}_{n-(k-1)}=C^{k}_{n-k+1}$
Bây giờ ta chỉ việc tính |B|.
Dễ thấy vì $x_{1}=1;x_{n}=n$ là hằng số nên trong việc tính B ta không cần xét đến $x_{1};x_{n}$.
Tương tự công thức tính |A|,ta có
$|B|=C^{k-2}_{(n-4)-(k-2)+1}$
Vậy nên |G|=|A|-|B|=$C^{k}_{n-k+1}-C^{k-2}_{n-k-1}=\frac{n}{n-k}C^{k}_{n-k}$
Vậy số cách chọn thỏa mãn là:$\frac{n}{n-k}C^{k}_{n-k}$ cách.
P/S:Phần tập hợp trong hệ em gõ trong dấu{} rồi nhưng không hiện.Mong BGK thông cảm và sửa lại dùm em.

Hình đã gửi


#7
Joker9999

Joker9999

    Thiếu úy

  • Thành viên
  • 659 Bài viết
Chia tập các số nguyên dương N* thành 2 tập rời nhau A và B. Chứng minh rằng với mọi n nguyên dơng luôn tồn tại các số nguyên dương a và b lớn hơn n thỏa mãn:
Tập {a,b,a-b} là con của A hoặc B
Lời Giải
Giả sử k tồn tại a,b thỏa mãn bài toán.
+) Xét số phần tử của A nhỏ hơn dương vô cùng. Gọi m là phần tử lớn nhất khi đó ta có
với mọi a>m thì 2a+3,a+1,a+2 thuộc B, vô lí
+) Xét số phần tử của A là dương vô cùng=> B cũng vậy
xét x,y,z thuộc A sao cho x>y>z>n và y-z>n. Khi đó ta có:
x+y,y+z,z+x thuộc B=> y-z thuộc A, vô lí
Vậy ta có đpcm.

<span style="font-family: trebuchet ms" ,="" helvetica,="" sans-serif'="">Nỗ lực chưa đủ để thành công.


.if i sad, i do Inequality to become happy. when i happy, i do Inequality to keep happy.

#8
LeHoangAnh1997

LeHoangAnh1997

    Binh nhì

  • Thành viên
  • 14 Bài viết
Đề bài:
Trong một hình vuông có diện tích bằng $1$,ta đặt $5$ đa giác sao cho mỗi đa giác này đều có diện tích bằng $\frac{1}{2}$.Chứng minh rằng tồn tại $2$ đa giác mà có diện tích phần chung lớn hơn $\frac{1}{5}$
Đáp án:
Đầu tiên,ta phát biểu BĐT "Nội suy-Ngoại suy" như sau:
$\sum ^{2m}_{k=1}(-1)^{k+1}.\sum _{1\leq i_1<i_2<...<i_k\leq n}|\bigcap ^k_{j=1}A_{i_j}|\leq |\bigcup ^n_{i=1}A_i|\leq \sum ^{2m+1}_{k=1}(-1)^{k+1}.\sum _{1\leq i_1<i_2<...<i_k\leq n}|\bigcap ^k_{j=1}A_{i_j}|$. Cái này có thể tham khảo ở đây
$\Rightarrow |\bigcup ^n_{i=1}A_i|\geq \sum ^n_{i=1}|A_i|-\sum _{1\leq i< j\leq n}|A_i\cap A_j|$
Quay lại bài toán:
Gọi $A_1;A_2;A_3;A_4;A_5$ là tập hợp các điểm thuộc phần diện tích của $5$ đa giác trên.
Gọi $M_k=\sum _{1<i_1<i_2<...<i_k\leq 5}|A_{i_1}\cap A_{i_2}\cap ...\cap A_{i_k}|$ với $1\leq k\leq 5$
Đặt:
$A_1\cap A_2=B_2$
$A_1\cap A_3=B_3$
$A_1\cap A_4=B_4$
$A_1\cap A_5=B_5$
Nhận xét:$B_2;B_3; B_4;B_5\subset A_1$ và $B_2\cup B_3\cup B_4\cup B_5=A_1$
Áp dụng BĐT "Nội suy-Ngoại suy",ta có:
$|\bigcup ^5_{i=2}B_i|\geq \sum _{i\geq 2}|A_1\cap A_i|-\sum _{2\leq i<j\leq 5}|A_1\cap A_i\cap A_j|+\sum _{2\leq i<j<k\leq 5}|A_1\cap A_i\cap A_j\cap A_k|-|A_1\cap ...\cap A_5|$
Thiết lập các BĐT tương tự với $A_2;...;A_5$,ta thu được:
$\sum ^5_{i=1}A_1\geq 2M_2-3M_3+4M_4-5M_5\Rightarrow M_1\geq 2M_2-3M_3+4M_4-5M_5$ $(1)$
Vì $5$ đa giác xếp trong hình vuông diện tích bằng $1$ nên
$1\geq |A_1\cup ...\cup A_5|$
Áp dụng công thức bù trừ,ta thu được:
$1\geq |A_1\cup ...\cup A_5|=M_1-M_2+M_3-M_4+M_5$
$\Leftrightarrow 3M_2\geq 3M_1+3M_3-3M_4+3M_5-3$ $(2)$
Từ $(1)$ và $(2)$ $\Rightarrow 3M_2+M_1\geq 3M_1+2M_2+3M_3+M_4-2M_5-3$
$\Rightarrow M_2\geq 2M_1+M_4-2M_5-3$
$\Rightarrow M_2\geq (2M_1-3)+(M_4-2M_5)$
$\Rightarrow M_2\geq (2.5.\frac{1}{2}-3)+(M_4-2M_5)$
$\Rightarrow M_2\geq 2+(M_4-2M_5)$
Nhận xét:$M_4=C^4_5.M_5\Rightarrow M_4-2M_5>0$
$\Rightarrow M_2>2 \Rightarrow C^2_5|A_m\cap A_n|>2\Rightarrow 10.|A_m\cap A_n|>2$
Vậy tồn tại $p,q\in \left \{ 1;2;3;4;5 \right \}:|A_p\cap A_q|>\frac{1}{5}$
Ta có đpcm.
P/s:Bài này em gõ Latex nhìn loạn quá nên nhầm chỗ nào thì nhờ anh sửa giúp em.!

#9
namcpnh

namcpnh

    Red Devil

  • Hiệp sỹ
  • 1153 Bài viết
Đề của toán thủ namheo1996.

Cho bảng hình chữ nhật kẻ ô vuông có $2010$ hàng,$2011$ cột.Ký hiệu $(m,n)$ là ô vuông nằm ở giao của hàng thứ $m$ và cột thứ $n$.Tô màu các ô vuông của bảng theo quy tắc:lần thứ nhất tô 3 ô vuông $(r,s)$, $(r+1,s+1)$, $(r+2,s+2)$ với $r,s$ là 2 số cho trước thoả mãn $1\leq r\leq 2008,1\leq s\leq 2009$.
Từ lần thứ 2,mỗi lần tô đúng 3 ô chưa có màu nằm cạnh nhau trong cùng 1 hàng hoặc cùng 1 cột.Hỏi bằng cách đó có thể tô được hết các ô vuông của bảng hay không?

Bài giải:

Giả sử bằng cách tô của bài ta có thể tô màu được hết tất cả các ô vuông cảu bảng đã cho ,khi đó tổng số lần tô sẽ là $2011.670$.

Điền các số vào các ô vuông của bảng theo 2 cách: Tại ô $(m,n)$ điều số $m.n$.Gọi $S$ là tổng số tất cả các số đã điền,ta có:

$S=(1+2+3...+2010)(1+2+3+...+2011)\equiv 0$ (mod 3).

Mặt khác gọi $S_i$ là tổng của 3 số nằm tại 3 ô vuông ở lần thứ $i$ ($1\leq i\leq 2011.670$).

Ta thấy $S_1=rs+(r+1)(s+1)+(r+2)(s+2)$

Và $S_i=ab+(a+1)b+(a+2)b$

$(2\leq i\leq 2011.670)$, $(1\leq a\leq 2009;1\leq b\leq 2011;a,b\in \mathbb{N}^{*})$

=>$S_1\equiv 2$ (mod 3)
$S_i\equiv 0$ (mod 3)

=>$S=S_1+S_2+S_3+...+S_{2011.670}\equiv 2$ (mod 3) => vô lí.

Vậy không thể tô màu hết tất cả các ô vuông của bảng theo cách tô đã được chỉ ra trong đề bài.

Cùng chung sức làm chuyên đề hay cho diễn đàn tại :

Dãy số-giới hạn, Đa thức , Hình học , Phương trình hàm , PT-HPT-BPT , Số học.

Wolframalpha đây


#10
cool hunter

cool hunter

    Thiếu úy

  • Thành viên
  • 544 Bài viết
đề bài:
Giả sử trong tập hợp hữu hạn X chọn ra 50 tập hợp con $A_{1};A_{2};...;A_{50}$ sao cho mỗi tập con chứa hơn 1 nửa phần tử của tập hợp X. CMR: có thể tìm được tập con $B\subset X$ không chứa nhiều hơn 5 phần tử và có ít nhất một phần tử chung cho các tập hợp $A_{1};A_{2};...;A_{50}$.
lời giải:
Giả sử số các phần tử trong tập X =n. Mỗi tập con được chọn $A_{1};A_{2};...;A_{50}$ chưa không ít hơn $\frac{n}{2}$ phần tử, nên tổng các phầnt tử của các tập hợp này vượt quá $50.\frac{n}{2}=25n$. Theo nguyên lí Dirichle thì tồn tại 1 phần tử của X thuộc không ít hơn 26 tập con đã chọn.
Tương tự ta chứng minh được với giá trị bất kì k<50 giữa các tập $A_{i1};A_{i2};...;A_{ik}$ có thể chọn ra không ít hơn $\left \lfloor \frac{k}{2} \right\rfloor+1$ tập hợp chứa cùng 1 phần tử. Ta lấy phần tử của tập X mà nó thuộc không ít hơn 26 tập ( phần tử này sẽ là một trong 5 phần tử của tập B). Ta loại ra 26 tập mà chưa phần tử đang xét. Khi đó tìm được một phần tử thuộc ít nhất 13 từ 24 tập còn lại. Ta loại 13 tập này, khi đó giữa 11 tập còn lại tìm được một phần tử thuộc không ít hơn 5 trong số các tập hợp. Đối với 5 tập còn lại tìm được 1 phần tử thuộc không ít hơn 3 trong số chúng. Và cuối cùng tồn tại một phần tử thuộc 2 tập cuối cùng. Như vậy ta tìm được không nhiều hơn 5 phần tử của tập X ( có thể ít hơn vì một vài phần tử sẽ trùng nhau), chúng sẽ taọ thnàh tập B. Ngoài ra một tập bất kì từ $A_{1};A_{2};...;A_{50}$ chưa ít nhất 1 trong các phần tử đó.

Thà đừng yêu để giữ mình trong trắng

Lỡ yêu rôì nhất quyết phải thành công

                                                                 


#11
huy thắng

huy thắng

    Hạ sĩ

  • Thành viên
  • 97 Bài viết
Trong hệ trục tọa độ Oxy vẽ 20 đường thẳng song song với Ox và 20 đường thẳng song song với Oy( sao cho mỗi đường thẳng cách nhau 1 đơn vị) tìm số hình chữ nhật và hình vuông tạo bởi các đường thẳng đó.

Hình đã gửi


#12
Joker9999

Joker9999

    Thiếu úy

  • Thành viên
  • 659 Bài viết
Đề bài:Tìm các số tự nhiên $x$ thoả mãn: nếu $1$ số tự nhiên chia hết cho số $x$ thì số được tạo bởi các chữ số của số đó theo thứ tự ngược lại cũng chia hết cho $x$.

<span style="font-family: trebuchet ms" ,="" helvetica,="" sans-serif'="">Nỗ lực chưa đủ để thành công.


.if i sad, i do Inequality to become happy. when i happy, i do Inequality to keep happy.




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

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