Đến nội dung

Hình ảnh

Các bài toán trong box Tổ hợp rời rạc chưa có lời giải.

- - - - -

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

#1
gogo123

gogo123

    Trung sĩ

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

Topic này dùng để tổng hợp các bài toán chưa có lời giải trong box Tổ hợp-rời rạc. Các bạn không thảo luận giải bài trong topic này mà hãy bấm vào đường link dẫn đến topic đó.

Những bài đã có lời giải sẽ được tô đỏ.

Bài 1: Cho $n$ là số nguyên dương lớn hơn 1.Tìm tất cả bộ số nguyên $(a;b;c;d)$ thỏa mãn :
$$a^{n}=b^{n}+c^{n}+d^{n}+2005$$

Bài 2: Trong 1 hội nghị có 41 người nam và nữ.Trong số 31 người bất kì luôn tìm được 1 đôi nam nữ quen nhau.Chứng minh rằng trong số 41 người đó luôn tìm được 12 đôi nam nữ quen nhau.

Bài 3: Cho 1 hình chữ nhất có $S=1$.Bên trong có 5 điểm phân biệt sao cho không có 3 điểm nào thẳng hàng và có thể nằm trên biên hình chữ nhật. Chứng minh rằng tồn tại ít nhất 2 tam giác có $S=\frac{1}{4}$(các tam giác có đỉnh là 3 trong 5 điểm trên).

Bài 4: Cho $A_{i}$ là những tập hợp hữu hạn phần tử

$$\left|\bigcup_{i=1}^N A_i\right|= \sum_{1\leq k \leq N}|A_k| - \sum_{1\leq i_1 < i_2 \leq N} |A_{i_1}\cap A_{i_2}|+ \cdots +(-1)^{N-1}|A_1\cap A_2\cap \cdots\cap A_N|$$

Trong đó $\Large\left|X\right|$ là số các phần tử của tập hợp $\Large X$.

Bài 5: Cho đa giác lồi $2n$-đỉnh: $a_1,...,a_{2n}$, P là một điểm nằm trong đa giác nhưng không nằm trên đường chéo nào. CMR số tam giác có các đỉnh trong $a_1,...,a_{2n}$ chứa điểm P là một số chẵn.

Bài 6: Cho 1 từ có $n$ âm tiết (VD: từ "đi chơi” có 2 âm tiết). Hỏi có bao nhiêu cách nói lái từ này trong 2 trường hợp :
-Mọi cách nói lái đều có thể chấp nhận.
- Có 1 số từ chỉ có thể nhận dấu sắc và dấu năng ( VD:dep, sat, gac…..).

Bài 7: Cho $n$-giác . Một số đường chéo của $n$-giác thỏa mãn 3 tính chất sau:
1) Không có 2 đường chéo nào cắt nhau (trong đoạn)
2) $n$-giác bị chia thành các tam giác
3) Số đường chéo xuất phát từ mỗi đỉnh đều là số chẵn ( có thể là 0 )
CMR: $3|n$.

Bài 8: Một tập hợp gồm 1985 phần tử là 1985 số tự nhiên đầu tiên được chia làm 6 tập hợp.CM trong 1 tập có chứa ít nhất 3 phần tử(không nhất thiết phân biệt) thỏa mãn số lớn nhất bằng tổng 2 số còn lại.

Bài 9: Cho $n$ là số tự nhiên, $(n>2)$
Xét các từ gồm $n$ chữ $n$ chữ $B$
Từ $x_1x_2...x_{2n}$ gọi là thuộc$S(n)$ nếu có đúng 1 đoạn khởi đầu chứa lượng chữ $B$ giống nhau
Tính:$ lim \dfrac{S(n)}{R(n)} $

Bài 10:
Trong một hình chữ nhật 1999x2000 .Ở ô $(i,j)$ ghi số 3x2 hoặc 5x2 rồi đổi dấu tất cả các số ở tất cả các ô trong hình chữ nhật.Hỏi sau một số chẵn lần thực hiện tổng các số trong bảng có thể là 1998 đuợc không?

Bài 11: Có thể phủ được hay không một bảng hình chữ nhật kích thước 5x7 bằng những hình thuớc thợ ba ô sao cho mỗi ô đều được phủ bởi một số lượng như nhau những hình thước thợ ?

Bài 12: Tìm số nguyên dương $ x_1,x_2,...,x_n,a_1,a_2,...,a_{n-1}$ với $ a_1<a_2<...<a_{n-1}$ thỏa mãn $ x_1x_2...x_n=1980 $ và $ x_i+\dfrac{1980}{x_i} \forall i=1,2,...,n-1 $

Bài 13: Chứng minh rằng không thể dùng 25 tấm domino cỡ 1x4 để phủ kín bảng vuông 10x10.

Bài 14: Đối với 1 đồ thị hữu hạn ta có thể xóa 1 cạnh tùy ý trong 1 vòng 4 cạnh tùy ý. Với đồ thị đầy đủ $n$ đỉnh thì việc xóa cạnh có thể kết thúc sau ít nhất bao nhiêu lần?

Bài 15: Xác đinh tất cả các giá trị của $m, n$ sao cho hinh chữ nhật $m . n$ có thể lát khít kín bởi các hock:
**
*
***

Bài 16: Tìm hằng số $C$ nhỏ nhất sao cho với mọi đồ thị hữu hạn $G$ ta có
$$g^{3}(G)\le{c\cdot{f^4(G)}}$$
trong đó $g(G)$ và $f(G)$ lần lượt là số các tứ diện, số các tam giác trong G

Bài 17: Tại 1 trường ĐH có 10001 SV, các SV tham gia các CLB, 1 SV có thể tham gia nhiều CLB, các CLB nghiên cứu các môn KH, 1CLB có thể nghiên cứu nhiều môn KH.Có $k$ môn KH. Biết rằng:
i) mỗi cặp SV tham gia cùng nhau đúng 1 CLB
ii) không có SV nào tham gia 2 CLB nghiên cứu cùng 1 môn KH
iii) mỗi CLB có lẻ SV tham gia
iv) CLB có $2m+1$ SV thì nghiên cứu đúng $m$ môn KH
Tính $k$.

Bài 18: Người ta điền số vào 441 ô vuông của bảng vuông 21*21 sao cho tại mỗi hàng và mỗt cột có không quá 6 giá trị khác nhau được điền vào. Chứng minh rằng có một số xuất hiện ở ít nhất 3 hàng và ít nhất 3 cột của bảng vuông này.

Bài 19:
Câu 1)
Cho 1 điểm $M$ không thuộc đường thẳng $d$. CM không tồn tại tập điểm ${A_{i}}$ vô hạn thuộc $d$ thỏa mãn :
-Khoảng cách $ A_{i} A_{j} \in \mathbb{Z}$
-$MA_{i} \in \mathbb{Z}$
Câu 2)
Như trên thay $d$ bởi mặt phẳng $(P)$.

Bài 20: Cho đường gâp khúc khép kín $n$ đoạn thẳng:
Tìm $n$ để đường gâp khúc tự căt mỗi đoạn thẳng của mình tại $k$ điểm ($k$ cho trước)
Với mỗi $k$ và $n$ ,tìm số giao điểm.

Bài 21: Tìm $k$ để tồn tại đường gâp khúc khép kín $n$ cạnh , tự cắt nhau $k$ lân` (với $n$ cho trước)

Bài 22: Với $m$ là số nguyên dương,cho $s(m)$ là tổng các chữ số của $m$.Với $f(n)$ là số $k$ nhỏ nhất sao cho tồn tại một tập $S$ gồm $n$ số nguyên dương thỏa mãn $X$ của $S$.Chứng minh rằng tồn tại các hằng số dương $0<C_1<C_2$ với $C_1lg(n) \leq f(n) \leq C_2lg(n), \forall n \geq 2 $.

Bài 23: Viết $n$ số tự nhiên trên một đường tròn.Tìm $n$ sao cho với mọi dãy gồm n số tự nhiên ta luôn tìm được hai số cạnh nhau sao cho sau khi xoá chúng đi các số còn lại có thể chia thành hai tập hợp có tổng các phần tử bằng nhau.

Bài 24: Cho bảng vuông $2n \cdot 2n ( n\in N,n \geq 2 ) $ . Ta điền $2n^2 $ số tự nhiên từ $1 \to 2n^2 $ vào bảng, mỗi số lặp lại hai lần.
Chứng minh rằng tồn tại một cách chọn $2n^2$ số tự nhiên từ $1 \to 2n^2$ ,mỗi số một lần sao cho trên mỗi hàng và mỗi cột luôn có ít nhất 1 số được chọn.

Bài 25: Giả sử rằng có 18 ngọn hải đăng trên vịnh BaTư ,mỗi ngọn trong chúng có thể chiếu sáng được một góc $ 20^0$.Chứng minh rằng có thể chọn hướng chiếu sáng của chúng sao cho toàn mặt vịnh BaTư được chiếu sáng.

Bài 26: Giả sử có n điểm phân biệt trên mặt phẳng. Có vòng tròn với bán kính r và tâm O trên mặt phẳng. Ít nhất một trong các điểm nằm trong vòng tròn. Chúng ta làm các hướng dẫn sau đây. Tại mỗi bước chúng ta di chuyển O đến trọng tâm của các điểm trong vòng tròn. Chứng minh rằng vị trí của O là không đổi sau khi một số hữu hạn bước.

Bài 27: Cho $k$ là số nguyên dương và $S_n=\left \{1,2,...,n \right \},(n \geq 3) $. Hàm $f:S_n^k \to S_k$ thỏa mãn: nếu $a,b \in S_n^k$ và chúng khác nhau ở tất cả các vị trí thì $f(a) \neq f(b)$. Chứng minh rằng có $i \in \left \{1,2,...,k \right \}$ sao cho:
$$f(a_1,a_2,...,a_k)=a_i ,\forall a=(a_1,a_2,...,a_k)\in S_n^k$$.

Bài 28: Cho $(O)$ bán kính 1,và $F$ là hình lồi đóng nằm trong $C$(Nghĩa là:Nếu $P,Q$ là các điểm của $F$ thì đoạn thẳng $PQ$ nằm trong $F$;tất cả các điểm biên của $F$ nằm trong $F$;tất cả các điểm của $F$ nằm trong đường tròn $C$.).Hơn nữa giả sử rằng từ mỗi điểm của $C$ có thể vẽ được hai tia tiếp tuyến của $F$ mà góc giữa chúng bằng $60^0$.Chứng minh rằng $F$ là hình tròn bán kính $\frac{1}{2}$.

Bài 29: Cho 100 điểm là đỉnh của đa giác đều 100 cạnh nội tiếp đường tròn. Lấy trong đó ra 20 điểm, 10 điểm tô màu đỏ, 10 điểm tô màu xanh. Chứng minh rằng tồn tại 2 cặp điểm có độ dài bằng nhau, 1 cặp cùng màu đỏ, 1 cặp cùng màu xanh.

Bài 30: Cho $n$ số $d_1,d_2,...,d_n$.
Tìm điều kiện cần và đủ để các số này là bậc của 1 đồ thị
a)$n$ đỉnh
b)có giả thuyết a và là Đồ thị liên thông.
c)có giả thuyết a và có đường đi khép kín đến các đỉnh.


Bài viết đã được chỉnh sửa nội dung bởi dark templar: 02-04-2013 - 18:10

LKN-LLT


#2
dark templar

dark templar

    Kael-Invoker

  • Hiệp sỹ
  • 3788 Bài viết
Spoiler


Bài 31: "Từ" được định nghĩa là một số có 10 chữ số chỉ gồm các số 0 và 1. Một "phép biến đổi" một từ là chọn một số các chữ số liên tiếp trong từ sao cho tổng của chúng là số chẵn rồi đảo ngược các số đó. Hai từ được gọi là "đồng nghĩa" nếu sau một số lần dùng phép biến đổi từ này có thể biến thành từ kia.
Tìm số lớn nhất các từ đôi một không đồng nghĩa.

Bài 32: CMR mọi số tự nhiên đều là tổng của 3 số tam giác
( $n= \dfrac{t(t+1)}{2}$ là số tam giác)

Bài 33: Cho $A=\{x_1;x_2;...;x_n\}$ và không có một số số nào trong A có tổng bằng 0.
Chứng minh rằng có thể phân hoạch $\mathbb{N^*}$ thành hữu hạn tập hợp $A_1;A_2;..;A_{k}$ với $|A_i|=+\infty$ sao cho với bất kì $a_1;a_2;...;a_n$ cùng thuộc 1 tập $A_{i}$ nào đó thì
$\sum\limits_{i=1}^nx_ia_i$ khác 0.

Bài 34: Có bao nhiêu cách xếp 8 con xe lên bàn cờ 8x8 ô sao cho không có 2 con xe nào ăn nhau và không có con xe nào nằm trên 1 trong 2 đường chéo của bàn cờ ?

Bài 35:
1)Cho $X=\{1,2,...,50 \}$ , $k$ là số nguyên dương sao cho mọi tập con gồm $k$ phần tử của $X$ đều có chứa 2 phần tử khác nhau $a,b$ của $X$ sao cho $ab$ chia hết cho $a+b$ .Chứng minh $k>38$.
2)Cho $X=\{1,2,...,2003 \}$, $n$ nguyên dương sao cho 1 tập con gồm $n$ phần tử của $X$ luôn có 1 phần tử là lũy thừa của 2 hoặc có 2 phần tử có tổng là lũy thừa của 2 . CM $n>998$.
3)Cho $X=\{1,2,...,2004 \}$, $n$ nguyên dương sao cho nếu loại bớt khỏi $X$ $n$ phần tử thì tập hợp còn lại không có phần tử nào là tích của 2 phần tử khác . CM $n>42$.
4)Cho $X=\{1,2,...,n \}$, $k$ nguyên dương sao cho trong mọi tập con chứa $k$ phần tử đều có ít nhất 2 số mà 1 trong 2 số đó là bội của số kia . CM $k> \left\lfloor \frac{n+1}{2} \right\rfloor$.

Bài 36: Tập các số nguyên dương đã được phân hoạch thành hai phần $A,B$.Chứng minh rằng với mọi số nguyên dương $n$ tồn tại các số nguyên phân biệt $a,b>n$ sao cho tập $\{a;b;a+b \}$ chứa trong $A$ hoặc $B$.

Bài 37: Hãy tìm số $k$ lớn nhất sao cho tồn tại $k$ số thuộc $\{1;2;..;n\}$ và một số bất kì trong $k $ số đó không là ước của $k-1$ số còn lại.

Bài 38: Vô hạn ô xếp từ trí qua phải.Đánh số các ô 1,2,3,...
Rải các viên sỏi vào các ô.
Quy tắc chuyển sỏi như sau:
- Nếu ô $N$ và $N+1$ đều có sỏi thì chuyển tất cả sỏi ở 2 ô này sang ô $N+2$.
-Nếu ô $N+1$ có 2 viên mà ô $N$ và $N+2$ không có sỏi thì chuyển 2 viên đó vào 2 ô $N$ và $N+2$.
Chứng minh rằng:
1.Trò chơi kết thúc sau hữu hạn bước.
2.Nếu tồn tại $n$ ô liên tiếp mỗi ô có 1 viên thì trò chơi kết thúc sau $k< n$ bước.

Bài 39: Cho tập $M$ gồm $n$ số nguyên dương phân biệt .Tìm tất cả $n$ để tồn tại hàm $f(x;x)=0.$
2) $f(x;y)=0$ thì tồn tại $z\in M ;z \notin \left\{x;y \right\}$ sao cho
$$f(x;z)=f(z;y)=1 $$

Bài 40: Trong mỗi ô vuông của hình chữ nhật m*n ta viết các số tự nhiên. Một lần ta có thể cộng vào cùng một số nguyên k vào các số ở 2 ô kề nhau sao cho các số sau khi cộng vào là các số nguyên không âm. Tìm điều kiện cần và đủ để tồn tại các cộng sao cho kết quả đạt được là tất cả các ô đều chứa số 0.

Bài 41: Cho $m;n;p;q$ là các số nguyên dương và đặt $X=\{ 1;2;...;q \}.$
$M$ và $N$ là các tập con của $X$ thỏa mãn $|M|=m;|N|=n$ và với mọi $i;j$ mà $0\leq i;j\leq q-1$ thì $|(M+i)\cap (N+j)|=p$. Chứng minh rằng:
$$mn=pq$$
Với kí hiệu $$A+i=\{ x+i (mod \ \ q) | x \in A \}$$

Bài 42:100 người tham gia thi quốc tế trong đó có:
85 người giỏi tóan
75 người giỏi ngọai ngữ
70 người giỏi tiếng Pháp
80 người giỏi kinh doanh
Hỏi có bao nhiêu người đủ cả 4 yêu cầu trên ?

Bài 43: Đặt $S=\{1,2,...,n \}$, $k$ là số nguyên dương cho trước. $T=\{(a_1,...,a_{k}) \ge S \}$.
Tìm $d$ nhỏ nhất sao cho với mọi tập con $d$ phần tử của $T$ đều tồn tại hai bộ $(a_1,...,a_{k})$ và $(b_1,...,b_k)$ sao cho $a_{i} ;b_{i}>0 (i=1,2,...,k)$.

Bài 44:
Bài toán 1:
Cho $n;m;p$ là các số nguyên dương và $n+1$ là bội của $m$.Tính số bộ $(a_1;a_2;..;a_p)$ thỏa mãn $(a_1;a_2;..;a_p)$ trong đó $1\le a_i\le n \quad \forall i=1;2;..;p$ và
$a_1+a_2+...+a_p\vdots m$
Bài toán 3:(Bài toán mở)
Cho $m;n;p$ là các số nguyên dương.Hãy tính số bộ số có tính chất như trên.

Bài 45: Cho $S$ là tập gồm $n$ phần tử. Bây giờ bạn chọn ra từ $S$ một bộ các tập con của $S$. (Có thể chọn tùy ý không phụ thuộc vào bất cứ tiêu chuẩn nào).Tìm $k$ nhỏ nhất sao cho với mọi tập con $k$ phần tử nào của $S$ đều bao hàm một trong các tập con của bộ tập con đã đặt ra ở trên.
Ví dụ: Cho $S$ là tập các số nguyên dương từ 1 đến 15. Tìm $k$ nhỏ nhất sao cho với mọi tập con $k$ phần tử của $S$ đều tồn tại 3 phần tử đôi một phân biệt mà tích của chúng là chính phương.
Bài toán nêu ra ban đầu rất gần với bài toán sau:tìm 1 tập con của $S$ có giao khác rỗng với mỗi tập con trong bộ tập con đã đặt ra. Câu hỏi đặt ra là có tìm được hay không một thuật toán để xác định các giá trị đó ?

Bài 46: $1 \leq j\leq i$ là các số nguyên.Chứng minh rằng:
$$ \sum\limits_{p=0}^{j} (-1)^pC_i^pC_{i+j-p-1}^{j-p}=0$$

Bài 47: Với mỗi cặp số khác nhau $(x,y)$ của tập hữu hạn phần tử $X$ ta gán cho một số là
$f(x,y)$ bằng 0 hoặc 1 sao cho $x_1,...,x_n$ thỏa mãn:$ f(x_1,x_2)=...=f(x_n,x_1)$

Bài 48: Tại 1 buổi khiêu vũ có 78 chàng trai va 91 cô gái tham dự. Biết rằng cứ 105 người có ít nhất 2 người cùng khiêu vũ với nhau 1 bài nào đó. Hỏi điệu valse có tối đa bao nhiêu cặp nhảy?
(1 cặp nhảy phải gồm 1 nam và 1 nữ ,cấm chơi nam-nam, nữ-nữ)

Bài 49: Cho 1 ngũ giác nguyên,CMR trong hoặc trên biên của ngũ giác nhỏ tạo bởi các đường chéo của ngũ giác lớn tồn tại 1 điểm nguyên.

Bài 50: Cho đơn đồ thị đầy đủ $K_{n}$.Tô màu các cạnh bằng 1 trong $m$ màu, mỗi màu dùng ít nhất 1 lần, sao cho với 1 đỉnh bất kì, có đúng $k$ màu khác nhau để tô cho các cạnh xuất phát từ điểm đó. Tìm điều kiện của $k,m,n$.

Bài 51: $ \forall n \in \mathbb{N} \setminus \{0,1\}$.CM:Với tất cả các tập gồm $2n-1$ số nguyên dương có thể chọn ra $n$ số có tổng chia hết cho $n$.

Bài 52: Một CLB có $2.n$ thnàh viên(TV),cứ $n+k(k >1)$ TV bất kì thì có 1 cặp M-F quen nhau.Chứng minh rằng có thể lấy $n-k+1$ cặp M-F rời nhau từ TV của CLB này. (M:Male-Nam;F:Female -Nữ)

Bài 53: Cho $n=2k-1, k \ge 6$.
$T$ là tập tất cả các bộ $n$ số $\{x_1,...,x_n\}$, $x_i=0,1$
với $2^{k}$ phần tử thỏa mãn:
cho $x \in T$, tồn tại duy nhất $y \in S$ sao cho $d(x;y) \ge 3$.
CMR $n=23$.

Bài 54: Giả sử tại mỗi điểm trong số các điểm $1,2,3,...,n$ trên trục số thực có đặt 1 quân cờ. Được phép chuyển dịch một quân cờ sang trái 1 điểm (nếu như ở đó không có quân cờ). Ví dụ từ điểm 1 chuyển dịch quân cờ sang điểm 0, sau đó từ điểm 2 chuyển dịch quân cờ sang điểm 1, v.v... Dễ thấy sau $n^2$ bước đi ta chuyển hết các quân cờ đến các điểm $-n+1,-n+2,...,-1,0$. Hỏi có tất cả bao nhiêu cách di chuyển quân cờ ?

Bài 55: Trong hình vuông cạnh 1 cho 59 điểm tuỳ ý. CMR trong các điểm ấy luôn tồn tại 3 điểm là đỉnh của 1 tam giác có $S \ge \frac{1}{100}$.

Bài 56: Kí hiệu $S_n=\{1;2;...;n\}$.
Hãy tìm số nguyên dương $k$ nhỏ nhất để với mọi tập con có $k$ phần tử của $S_{n}$ thì có hai phần tử là bội của nhau.
Bài toán mở rộng hơn 1 chút.
Tim số nguyên dương $k$ nhỏ nhất để với mọi tập con cớ $k$ phần tử của $S_{2^m.n}$ thì có $m+1$ phần tử $x_0;x_1;...;x_m$ mà $x_i|x_{i+1} \forall i=0;1;...;m$.

Bài 57: Cho số nguyên dương $n >2$.
Hãy tìm số các số nguyên $a$ thỏa mãn điều kiện:
Tồn tại song ánh $f:\{1;2;...;n\} \to \{1;2;...;n\}$ mà $|f(i)-i|=a \forall i=\overline{1;n}$.

Bài 58: Trong một cuộc hội thảo quốc tế có n thành viên tham gia $(n>2)$.
Họ biết tổng cống 14 ngôn ngữ và biết :
1) Cứ 3 thành viên bất kì thì nói chung 1 ngoại ngữ
2) Mỗi ngoại ngữ có không quá nửa số thành viên nói được.
Hãy tìm số $n$ nhỏ nhất có thể được.

Bài 59: Tìm chu vi nhỏ nhất của đa giác 32 cạnh có các đỉnh nguyên.

Bài 60: Có 100 người đến từ 25 quốc gia.Mỗi nước 4 người và họ ngồi trên một cái bàn tròn .CMR ta có thể chia họ thành 4 nhóm sao cho mỗi nhóm có 25 người của 25 quốc qia khác nhau và không có ai cùng nhóm ngồi cạnh nhau trên bàn tròn.

Bài viết đã được chỉnh sửa nội dung bởi dark templar: 16-03-2013 - 19:14

"Do you still... believe in me ?" Sarah Kerrigan asked Jim Raynor - Starcraft II:Heart Of The Swarm.

#3
dark templar

dark templar

    Kael-Invoker

  • Hiệp sỹ
  • 3788 Bài viết
Tiếp nào...

Bài 61: Cho $n>2$ là số tự nhiên . Trên mỗi ô vuông của mạng lưới nguyên có ghi một số tự nhiên. Một đa giác gọi là chấp nhận được nếu nó có diện tích là $n$ và các cạnh của nó nằm trên các đường thằng của mạng lưới nguyên. Tổng các số của các ô vuông đơn vị chứa trong đa giác chấp nhận được gọi là giá trị của đa giác đó.
Chứng minh rằng nếu các giá trị của mọi cặp đa giác chấp nhận được đồng dạng với nhau mà bằng nhau thì tất cả các số được viết trong các ô vuông đơn vị đều bằng nhau.

Bài 62: Kí hiệu $S$ là tập hợp các cặp số tự nhiên $(a;b)$ sao cho tích $a^{a}b^{b}$ có 98 chữ số 0 trong hệ thập phân. Hãy tìm tất cả các cặp số tự nhiên $(a,b)$ thuộc $S$ sao cho tích $ab$ nhỏ nhất.

Bài 63: Cho $n$ điểm $ P_1;P_2;...;P_n$ theo thứ tự đó trên 1 đường thẳng. Chúng ta tô màu mỗi điểm bởi 1 trong 5 màu trắng, đỏ, xanh lá cây, xanh nước biển, và màu tím. Một cách tô màu được gọi là chấp nhận được nếu với 2 điểm liên tiếp $ P_i;P_{i+1} (i=1;2;...n-1) $ thì cả 2 điểm cùng màu hoặc có ít nhất 1 trong 2 điểm được tô màu trắng. Hỏi có bao nhiêu cách tô màu chấp nhận được.

Bài 64: Chứng minh rằng: từ hình chữ nhật kích thước 1*$\sqrt{2}$ ,không thể cắt ra hữu hạn hình vuông.

Bài 65: Chứng minh rằng từ hình vuông cạnh 1 không thể cắt làm hai hình vuông cạnh $a,b$ mà $a+b>1$.

Bài 66: Trên đường tròn cho 1984 số 1 và -1. Biết số các số -1 lớn hơn 661
Chứng minh rằng có ít nhất 1 số 1 thõa mãn tổng một số số bất kỳ tính từ số 1 đó theo hai chiều đều dương.

Bài 67: Cho số nguyên dương $n$.Xét $T$ là tập các điểm nguyên $(x;y;z)$ trong không gian tọa độ mà có $x+y+z<n$ và $(x;y;z)$ tô đỏ thì tất cả các điểm $(x;y;z)$ mà $f(n)=g(n)=h(n)$ có luôn đúng không ?
(Đây là bài toán trong không gian của bài 1 IMO 42)

Bài 68: Cho 1 hình vuông cạnh 1.Tìm hình ngũ giác đều có cạnh lớn nhất nằm trong hình vuông đó.

Bài 69: Cho một hình vuông cạnh 1,từ đó cắt ra 2 hình vuông cạnh $a,b$.Chứng minh $a+b$ không lớn hơn 1.

Bài 70: Gọi $S$ là tập hợp nào đó gồm $n$ điểm trong mặt phẳng.Khoảng cách ngắn nhất giữa hai điểm thuộc $S$ là $d$.Chứng tỏ rằng tồn tại một tập con không ít hơn $\frac{n}{7}$ phần tử sao cho mỗi cặp điểm của tập con đó có khoảng cách không nhỏ hơn $d\sqrt{3}$.

Bài 71: Trong một kì thi toán, trong 6 bài toán được đưa ra cho các thí sinh, cứ mỗi hai trong số những bài toán này đều có nhiều hơn $\frac{2}{5}$ tổng số thí sinh giải được. Ngoài ra, không có thí sinh nào giải được cả 6 bài toán. Chứng minh rằng có ít nhất 2 thí sinh giải được đúng 5 bài toán.

Bài 72: Cho một bảng 8x8. Người ta xếp $n$ quân Domino vào bảng sao cho không có 2 quân nào đè lên nhau và không thể xếp thêm được bất cứ quân nào nữa. Hỏi rằng số $n$ nhỏ nhất là bao nhiên để điều này xảy ra.

Bài 73: Chứng minh rằng không thể có nhiều hơn 4096 dãy nhị phân độ dài 24 sao cho hai dãy bất kì trong đó có ít nhất tám vị trí khác nhau.

Bài 74: $a_1,a_2,...,a_n$ và $k\in\{0,1,...,n-2\}$.Chứng minh rằng :
$$\sum\limits_{i=1}^{n}a_i^k(-1)^{i-1}C_{n-1}^{i-1}=0.$$

Bài 75: Các hình vuông của bảng $m.n$ được đánh số từ 1 đến $mn$ sao cho các hình vuông được đánh số $i$ và $i+1$ luôn luôn có một cạnh chung.Chứng minh rằng tồn tại $k$ sao cho các hình vuông được đánh số$k$ và $k+3$ có một cạnh chung.

Bài 76: Xét tập hợp A thỏa mãn: $A \subset \{1;2;...;N\};|A| \le 2\left\lfloor \sqrt{n} \right\rfloor+1$.
CMR: tồn tại tập hợp A thỏa mãn với mọi $i \in [1,n-1]$ mà ta có thể viết $A_p-A_q =i$
Trong đó $A_p;A_q$ là tập hợp con của tập hợp A.

Bài 77: Tìm một đồ thị con Euler của đồ thị ban đầu G. Tập nhãn trên các cạnh của đồ thị đó là tập nhãn của đồ thị G, và không có 2 cạnh nào có nhãn trùng nhau.

Bài 78: Giả sử có $n$ đấu thủ tham gia một giải bóng bàn với lịch thi đấu cho trước. Thắng 1 thua 0. Chứng minh rằng $d_1;d_2;...;d_n$ là số điểm của các đấu thủ nếu và chỉ nếu $d_1+d_2+...+d_n=\dfrac{n(n-1)}{2}$ và với mọi $X\subset\{1;2;..;n\}$ thì số trận đấu giữa các đấu thủ trong tập này không vượt quá$\sum\limits_{i\in X}d_i$.

Bài 79: Có các loại đồng xu mệnh giá 1 (xu) ,2 (xu), ...,$k$ (xu).Một Số tiền là $n$ (xu).
Có bao nhiêu cách đổi $n$ (xu) thành các loại xu trên?

Bài 80: Trong 1 cuộc thi hoa hậu.Mỗi giám khảo được chọn ra 10 ứng cử viên.Một nhóm được gọi là ưng ý với 1 GK nếu có người ông ta đề cử.Biết Cứ 6 người (Hoa hậu) bất kì luôn chọn được 2 GK ưng ý!.CMR: Có thể chọn đựoc nhóm 10 hoa hau ưng ý với tất cả.

Hay ta có thể phát biểu bài toán lại dưới dạng sau (lehoan):
Cho $X=\{1;2;...;n\}$.Giả sử $j$ mà $A_j=\{i\}$
CMR: tồn tại $i_1;i_2;..;i_{10}$ phân biệt mà $|\bigcup\limits_{j=1}^{10}A_{i_j}|=X$.

Bài 81: Cứ 5 điểm bất kì thì tồn tại 2 đường thẳng dể chứa 5 điểm này,khi đó chứng minh rằng $n$ điểm này có thể nằm trên 2 đt thôi (chú ý là chỉ đúng với $n \ge 9$,$n=8$ có phản ví dụ)

Bài 82: Cho hình vuông n*n.Hãy tính số cách điền các chữ số 1 và -1 vào để tổng các hàng ngang , dọc đều bằng 0.

Bài 83: Cho 16 số nguyên dương phân biệt <100. Cmr ta có thể tìm được 4 số $a,b,c,d$ sao cho $a+b=c+d$.Tổng quát cho $n$ lớn bất kì.

Bài 84: CMR 1 quân mã không thể đi qua mỗi ô đúng một lần trong bảng 4*n

Bài 85: Mỗi ô vuông của bảng $m.n$ đã được tô bởi một trong hai màu đen,trắng.Mỗi ô vuông đen kề với một số lẻ các ô vuông đen.Chứng minh số ô đen là số chẵn.(Hai ô được gọi là kề nhau nếu chúng khác nhau và có một cạnh chung) và có thể có nhiều nhất là bao nhiêu ô đen ?

Bài 86: Chứng minh rằng với mỗi $n$ nguyên dương thì :
$$\sum\limits_{i=0}^n(-1)^{i}C_{2n-i}^i4^{n-i}=2n+1$$

Bài 87: Tìm số cạnh lớn nhất của một đồ thị $n$ đỉnh mà trong đó không có chu trình $k$ cạnh nào?

Bài 88: Cho các số nguyên dương $a_1,a_2,a_3,..........a_{2005}$ thỏa:
$$a_1+a_2+a_3+.......+a_{2005}=a_1a_2........a_{2005}$$
Tìm max của $a_1+a_2+a_3+.............+a_{2005}$.

Bài 89: Chứng minh rằng :
$$\sum_{i=0}^{2k} C_{2(n-k)}^{n-i}>2\sum_{i=k+1}^{2k+1} C_{2k+1}^{i}.C_{2n-2k-1}^{n}$$

Bài 90: Xếp 7 ngôi sao vào bảng ô vuông 4*4, chứng minh rằng tồn tại hàng và cột có số ô chứa ngôi sao bằng nhau. Chứng minh rằng điều nay không đúng với số ngôi sao nhỏ hơn 7.

Bài viết đã được chỉnh sửa nội dung bởi dark templar: 16-03-2013 - 20:14

"Do you still... believe in me ?" Sarah Kerrigan asked Jim Raynor - Starcraft II:Heart Of The Swarm.

#4
namcpnh

namcpnh

    Red Devil

  • Hiệp sỹ
  • 1153 Bài viết

Tiếp tục.....

Bài 91 : Cho các số dương $a_1;a_2;...;a_7$, $b_1;b_2;...;b_7$ thỏa: $a_i+b_i \le 2$. CMR luôn tồn tại hai số $k$ khác $m$ sao cho: $$|a_m-a_k|+|b_m-b_k| \le 1$$.

$ biết
2) $|A_{j}|=|A_{i}|.|A_{i}\cap A_{j}|$Tính $\left | \bigcup_{i=1}^{167}A_{i} \right |$

Bài 93: Cho bàn cờ vua $8\times 8$, loại bỏ 2 ô khác màu bất kì trong bàn cờ. Chứng minh có thể lát bàn cờ bằng 31 hình chữ nhất kích thước $1\times 2$.

Bài 94:Cho tập hợp $P=\left \{ 1,2,...,2013 \right \} $. Tìm m nhỏ nhất sao cho mỗi tập con có m phần tử của $P $ tồn tại ít nhất hai số $p,q$ thỏa số này là bội số kia.

Bài 95: Có bao nhiêu cách lát đường đi kích thước $3\times 2n$ bằng các viên gạch có kích thước $1 \times 2$?

Bài 96: Chứng minh rằng $\boxed{\sum_{k=1}^{n}(-1)^{k+1}\binom{2n+1}{k}(2n-2k+1)^{2j+1}=(2n+1)^{2j+1}}$ với $j=0,\ldots,n-1$.

Bài 97:

Bài toán 1:
Mỗi điểm trong mặt phẳng gắn $1$ số thực, tâm đường tròn nộp tiếp của mọi tam giác được gắn số bằng trung bình cộng $3$ số ở đỉnh. CMR: Tất cả các số gắn ở mỗi điểm bằng nhau
Bài toán 2:
Mỗi điểm trong mặt phẳng được tô bởi $1$ tròng $3$ màu. Chứng minh rằng tồn tại $1$ tam giác cân hoặc tam giác có $3$ góc thoả tổng $2$ góc này gấp đôi góc còn lại có $3$ đỉnh cùng màu.

Bài 98 : Có bao nhiêu số tự nhiên chi hết cho $3$ gồm $n$ chữ số sao cho các chữ số thuộc tập hợp $X=\left \{ 2,3,7,9 \right \}$

Bài 99 : Cho $p$ là số nguyên tố và $a$ là số nguyên dương. Ta chia đường tròn thành $p$ cung bằng nhau. Hỏi có bao nhiêu cách tô các cung bằng $a$ màu?(Hai cách tô có thể thu được từ nhau qua phép quay được coi là giống nhau)

Bài 100: Đặt 1 quân cờ lên 1 ô vuông của một bàn cờ lớn vô hạn (mỗi ô vuông kích thước 1 cm x 1 cm). Quân cờ di chuyển theo quy tắc sau:
+ Nước thứ nhất, đi 1 ô lên trên.
+ Các nước có số thứ tự lẻ thì đi lên trên hoặc xuống dưới, các nước có số thứ tự chẵn thì đi sang trái hoặc sang phải.
+ Ở nước thứ n, quân cờ đi n ô theo hướng đã chọn ở trên.
Quân cờ di chuyển k bước sao cho khoảng cách từ tâm ô vuông xuất phát đến tâm ô vuông đích là nhỏ nhất. Tính khoảng cách nhỏ nhất này?

Bài 101: Bài 102[/url]: Đặt 1 quân cờ lên 1 ô vuông của một bàn cờ lớn vô hạn (mỗi ô vuông kích thước 1 cm x 1 cm). Quân cờ di chuyển theo quy tắc sau:
+ Nước thứ nhất, đi 1 ô lên trên.
+ Các nước có số thứ tự lẻ thì đi lên trên hoặc xuống dưới, các nước có số thứ tự chẵn thì đi sang trái hoặc sang phải.
+ Ở nước thứ n, quân cờ đi n ô theo hướng đã chọn ở trên.
Quân cờ di chuyển k bước sao cho khoảng cách từ tâm ô vuông xuất phát đến tâm ô vuông đích là nhỏ nhất. Tính khoảng cách nhỏ nhất này?

Bài 103: Có 10 cái khăn hình vuông diện tích mỗi khăn là 1và một cái bàn hình vuông có diện tích bằng 5.Chứng minh có thể phủ kín cái bàn này bởi 2 lớp khăn.(Các khăn có thể kề mép nhau nhưng không được đứt đoạn)

Bài 104:Cho $p_1,p_2,p_3,...,p_n$ là số nguyên tố và a là số nguyên dương. Ta chia đường tròn thành $p_1p_2p_n$ cung bằng nhau. Hỏi có bao nhiêu cách tô các cung bằng a màu?(Hai cách tô có thể thu được từ nhau qua phép quay được coi là giống nhau)

Bài 105: Cho $n$ và $a$ là số nguyên dương. Ta chia đường tròn thành $n$ cung bằng nhau. Hỏi có bao nhiêu cách tô các cung bằng $a$ màu?(Hai cách tô có thể thu được từ nhau qua phép quay được coi là giống nhau)

Bài 106: Cho bảng $k*k$ và $n$ là một số nguyên dương cho trước. Tìm các cách tô màu không như nhau khi tô mỗi ô bởi một trong $n$ màu(Hai cách tô có thể thu được từ nhau qua phép quay được coi là giống nhau)

Bài 107:Trong 1 căn phòng có 2n+1 người ,sao cho với n người bất kì luôn tồn tại 1 người quen với tất cả n người đó.Chứng minh có 1 người quen với tất cả mọi nguời trong phòng này.

Bài 108: Cho bảng hình chữ nhật kích thước $m$ x $n$ ($m,n \in \mathbb{Z^+}$) và các số nguyên dương $p \le m$ và $q \le n$. Người ta điền các số $1,2,3, ..., m$ x $n$ vào các ô trong bảng. Một số tự nhiên trong bảng được gọi là "xấu" nếu nó nhỏ hơn $p$ số cùng cột và $q$ số cùng hàng. Đếm số cách xếp sao cho các số xấu có trong bảng là nhỏ nhất và hãy chỉ ra 1 cách xếp như vậy.

Bài 109: Cho $A$ là 1 tập hợp hữu hạn các số thực dương.$ B =\{x/y|x,y\in A\} $,$ C =\{xy|x,y\in A\} $.CMR
$ |A|\cdot|B|\le|C|^2 $

Bài 110: Ngài Sir Alex Ferguson di chuyển xung quanh trên các điểm lưới theo các quy tắc sau từ điểm $ (x,y) $ bất kì ông có thể di chuyển đến $1$ trong các vị trí sau $ (y,x) $, $ (3x,-2y) $,$ (-2x,3y) $,$ (x+1,y+4) $và $ (x-1,y-4) $.CMR nếu ông ta bắt đầu đi từ $ (0,1) $ thì không bao giờ đến được điểm$ (0,0) $

Bài 111: Cho $n$ đồng xu có bán kính lần lượt là $r_1$, $r_2$,$...$, $r_n$ được đặt xung quanh một vòng tròn sao cho mỗi đồng xu tiếp xúc với hai đồng xu cạnh nó và tiếp xúc với vòng tròn. Ký hiệu vòng tròn đó là $\left ( O,R \right )$. Xây dựng thuật toán tìm độ dài bán kính $R$.

Bài 112: Chứng minh đẳng thức: $$\sum_{k=0}^n(-2)^k{n+k\choose 2k}=(-1)^{\left\lfloor\frac{n+1}{2}\right\rfloor}$$

Bài 113 : Chứng minh rằng với mọi số nguyên dương $n$ ta có $$\binom{2n}{n}\vdots (n+1)$$

Bài 114: Tìm cặp số tự nhiên $n,k$ sao cho $$\binom{3n}{n}=(3n)^k$$

Bài 115: Có 10 người muốn đi từ A đến B cách nhau 1000 km. Họ chỉ có một chiếc xe 2 chỗ ngồi (kể cả chỗ ngồi của người lái xe). Hỏi cần ít nhất bao nhiêu thời gian để cả 10 người đến B.Biết vận tốc xe là 100(km/h),vận tốc đi bộ là 5(km/h)

Bài 116: Có 100 người tham gia thi, đề thi gồm 5 câu hỏi. Số người làm đúng câu 1,2,3,4,5 lần lượt là 80, 72, 84, 88, 56. Biết rằng phải làm đúng ít nhất 3 câu mới đỗ. Hỏi có ít nhất bao nhiêu người thi đỗ

Bài 117:Cho số nguyên dương n>10.Tìm m nguyên dương lớn nhất thoả mãn điều kiện:Tồn tại m tập con $A_{i}$ của tập A={1,2,3....,2n},mỗi tập con gồm n phần tử sao cho $\left | A_{i}\cap A_{j}\cap A_{k} \right |\leq 1$ với mọi $1\leq i< j< k\leq n$

Bài 118: Xét bài tóan sau: cho 6 màu phân biệt. Hỏi có bao nhiêu cách tô màu 6 mặt hình 1 lập phương bằng 5 trong số 6 màu trên sao cho không có 2 mặt nào có cạnh chung được tô cùng màu ? ( chú ý các cách tô được xem là lặp nếu ta quay quanh trục 1 mặt phẳng hoặc lật ngược 1 cách tô bất kì ).
đáp số bài toán này như thế này:
$\binom{6}{5}.\binom{5}{1}.\frac{1}{2}.(4-1)!$.

Bài 119: Cho 27điểm phân biệt trên mặt phẳng không có 3 điểm nào thẳng hàng .
4 điểm trong chúng lập thành các đỉnh của hình vuông đơn vị ; 23 đỉnh
còn lại nằm trong hình vuông trên . Chứng minh rằng tồn tại 3 điểm
riêng biệt X;Y;Z sao cho [XYZ ] ≤ 1/48 .

Bài 120:
Chứng minh rằng một đa giác lồi có đường kính $d$ luôn được phủ bởi $1$ hình tròn có bán kính $\frac{d}{\sqrt{3}}$
Mình không hiểu tại vì sao ở đoạn chứng minh cho đa giác ($\geq{4}$ cạnh) người ta lại nói là giao của ba hình tròn bất kì trong các hình tròn tạo bởi tâm là các đỉnh và bán kính $\frac{d}{\sqrt{3}}$.

To be continued...........


Bài viết đã được chỉnh sửa nội dung bởi dark templar: 06-04-2013 - 11:45

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


#5
namcpnh

namcpnh

    Red Devil

  • Hiệp sỹ
  • 1153 Bài viết

Tiếp nào .........

Bài 121:Trên bàn; người ta đặt $20$ tấm thẻ ; ghi số từ $1$ đến $20$
Với 1 bước ; người ta chọn ra $2$ tấm thẻ có sai biệt nhiều hơn $1$ đơn vị ; sau đó viết lại số trên $2$ thẻ này theo cách : Trừ 1 đơn vị từ thẻ có giá trị lớn hơn và cộng 1 đơn vị vào thẻ có giá trị nhỏ hơn để được 2 thẻ mới.
Hãy tính số bước tối đa có thể thực hiện :)

Bài 122: Có thể chia 1 hình vuông thành 8 tam giác cân nhọn?

Bài 123 :Cho $t,k,m$ là các số nguyên dương $t>\sqrt{km}$. Chứng minh
$$\dbinom{2m}{0}+\dbinom{2m}{1}+\cdots+\dbinom{2m}{m-t-1}<\dfrac{2^{2m}}{2k}$$

Bài 124:Một cuộc họp có n đôi vợ chồng tham gia.Hai người bất kì đều nói chuyện với nhau.Các cuộc nói chuyện được chia thành k nhóm thỏa:
i) 2 vợ chồng không bao giờ cùng nhóm;
ii) 2 người bất kì đều có duy nhất 1 nhóm để 2 người đều thuộc nhóm đó
CMR: k$\geq $2n(n$\geq$ 4)

Bài 125:Có 9 ô vuông được đánh số từ 1 tới 9, mỗi ô có 1 viên bi. Thực hiện trò chơi như sau: mỗi lần lấy 2 viên bi ở hai ô vuông khác nhau rồi chuyển sang ô kề với ô chứa nó nhưng theo chiều ngược nhau. Hỏi sau 1 số hữu hạn bước ta có thể nhận được kết quả sau hay không?
a) Cả 9 viên đều nằm trong 1 ô
b) Không có ô nào mang thứ tự lẻ
c) 5 viên bi nằm ở ô số 9

Bài 126 :Trong đường tròn bán kính $R = 11$ có $27$ điểm. Chứng minh rằng ta luôn tìm được $3$ điểm lập thành tam giác có diện tích nhỏ hơn $1,325$.

Bài 127:Cho số nguyên dương $m \ge 3$. Một tập $S$ được gọi là tốt nếu tồn tại những phần tử ${s_1},{s_2},...,{s_m}$ thỏa mãn ${s_1}+{s_2}+...+{s_{m-1}}={s_m}$. Xác định số nguyên dương $f(m)$ nhỏ nhất sao cho một trong 2 phân hoạch A và B của tập ${ 1,2,...,f(m) }$ là 1 tập tốt.

Bài 128:Đếm số hình vuông $n*n$, trong đó các ô vuông con $1*1$ được điền các số $0,1$ sao cho mỗi hàng, mỗi cột có tổng các số là chẵn.

Bài 129:Cho a là số nguyên có 4 chữ số trong hệ thập phân. Ta lập số b bằng cách viết a theo thứ tự giảm dần, c là số viết a theo thứ tự tăng dần
Đăt T(a)=b-c
VD: T(2001)=2100-12=2088
Chứng minh rằng nếu a không là số có 4 chữ số như nhau thì dãy a,T(a), T(T(a)),... sẽ dừng lại ở 6174

Bài 130:Một lớp học có 10 học sinh có điểm tổng kết đôi một khác nhau. Họ quyết định giúp nhau học tập. Mỗi bạn có thể có 1 người giúp mình môn Văn hoặc 1 người giúp mình môn Toán hoặc cả 2 người hoặc không có ai giúp. Biết rằng 1 người có thể giúp được người khác nếu điểm tổng kết của họ cao hơn người kia và chỉ có bạn có điểm thấp nhất là không giúp đỡ ai. Hỏi có bao nhiêu cách phân công giúp nhau học tập.

Bài 131:Với 1 số tự nhiên B thì C là số viết các chữ số của B theo thứ tự ngược lại. (VD: B=12345 thì C=54321);
1 số tự nhiên x được gọi là số sướng nếu B chia hết cho x thì C cũng chia hết cho x.( VD:x=1);
Tìm các số x là số sướng.

Bài 132: Cho 53 số nguyên dương phân biệt có tổng không lớn hơn 2004. Chứng minh rằng luôn tìm được 6 số trong 53 số đã cho thỏa mãn : 6 số này chia được thành 3 cặp số, mỗi cặp đều có tổng bằng 53.

Bài 133:$P_1,P_2,...P_k$ are subsets of $\left \{ 1,2,...,n \right \}$ thỏa mãn;

1) $|P_i|\geq2$ với $i=1,2,...,k$
2) Nếu$|P_i\cap{P_j}|\geq2$ thì $|P_i|\neq|P_j|$ for $\forall i\neq{j}$ và $i,j \in \left \{ 1,2,...,n \right \}$.
Chứng minh rằng $k\leq(n-1)^2$.(Chú ý rằng $|A|$ là số lượng phần tử của tập $A$) ( Đề bằng tiếng Anh, mình dịch để các bạn không giỏi tiếng Anh đọc :D)

Bài 134:Tính trung bình cộng của các số $N$ gồm $n$ ($n>1$) chữ số thoả mãn các điều kiện:
i) $N$ gồm các chữ số $1$, $2$, $4$, $5$ và hiệu hai chữ số liên tiếp luôn lớn hơn $1$.
ii) $N$ chia hết cho $11$.

Bài 135:Bộ bài tây $52$ lá được sắp một cách ngẫu nhiên thành $13$ cột và $4$ dòng. Lật ngữa quân bài.
Thầy Hoàng Xuân Thanh nói với thầy Hoàng Ngọc Thế:
" Bây giờ tôi cho thầy sắp bài tuỳ ý ; miễn là theo cách trên ; sau đó sẽ thực hiện các bước; mỗi bước tôi chuyển vị trí của $2$ con bài có chung phần số. Ví dụ: $2$ bích đổi chỗ $2$ cơ ; $\mathcal{K}$ rô đổi chỗ $\mathcal{K}$ nhép..... Và sau một hữu hạn các bước thì mỗi cột sẽ có đủ $4$ chất cơ - rô - nhép -bích."
Thầy Thế cho là thầy Thanh bốc phét và đánh cuộc 500K .
Theo các bạn; ai sẽ là người thắng trong trò này?

Bài 136:Cho hai dãy tập hợp $(A_{n})$ và $B_{n}$ thoả mãn:
$A_{1}=\varnothing$, $B_{1}={0}$, $A_{n+1}=${$x+1|x\in{B_{n}}$}, $B_{n+1}=(A_{n}\cup{B_{n}})$ \ $(A_{n}\cap{B_{n}})$, $\forall{n\geq{1}}$. Chứng minh rằng với $n=2^k,\forall{k\in{\mathbb{N}}}$ thì $B_{n}=0$.
Giải thích vì sao làm như vậy.

Bài 137: Cho A=$\left \{ 1;2;3;...;n \right \};n$ nguyên dương.Tìm số bộ k phần tử $\left ( a_{1},a_{2},...a_{k}, \right )$ với $a_{i}$ thuộc A,i=1,..k, thỏa mãn
1.$a_{i}< a_{j}$(với mọi i<j;i,j=1,2,..k)
2.$a_{i}$-i chia hết cho 3(với mọi i=1,2,..k)

Bài 138:Cho tập hợp $X$ gồm một số các số nguyên thảo mãn:
(1) $\forall a,b\in{X}$, ta có $a+b\in X$
(2) $X$ có chứa số âm và số dương. Chứng minh rằng: mọi $a,b\in{X}$, ta luôn có $a-b\in X$.

Bài 139: Cho tập $S$ có $2000$ phần tử, gọi $ S_1;S_2;...;S_{50}$ là các tập con của $S$ thoả mãn đk:
$\left\{\begin{matrix} |S_i|=100 \forall i\overline{1..50} & \\ S_1\cup S_2\cup....\cup S_{49}\cup S_{50}=S & \end{matrix}\right.$CMR: tồn tại 2 tập con $ S_i; S_j ( i \neq j; i,j \in \overline{1..50} )$ mà $ |S_i \cap S_j| \geq 4 $.

Bài 140: Bên trong đường tròn $ (T) $ bán kính 1 ta đặt 1 số hữu hạn đường tròn nhỏ sao cho tổng độ dài đường kính của chúng là $ 3995$. gọi $MN $ là 1 dây cung bất kì của $(T) $. CMR tồn tại 1 dây cung của $(T) $ song song với $MN $ và cắt ít nhất $1998$ hình tròn nhỏ.

Bài 141:Trên 1 vòng tròn có 12 vị trí từ 1 tới 12 nối tiếp nhau theo chiều kim đồng hồ. đặt các số $ 1,2,...,12 $ lên 12 vị trí đó 1 cách ngẫu nhiên. CMR ta luôn tìm được 3 số liền nhau trong mỗi cách xếp đó mà tổng của chúng lớn hơn hoặc bằng 20.

Bài 142:Cho $A=\{1,2, \dots ,n \}$. Tìm số các hoán vị $(a_1, a_2, \dots , a_n)$ của A thỏa điều kiện với mọi $i<j<k$ thì không tồn tại $a_i>a_j>a_k$.

Bài 143:Việt Dũng có 2 hàng cây giống nhau cần được trồng đối diện nhau. Mỗi hàng cây đều gồm có 10 cây táo, 9 cây xoài, 8 cây mận và 7 cây mít. Một cách trồng gọi là "hợp phong thủy" nếu 2 cây khác hàng, đối diện nhau thì luôn luôn khác loại. Đếm số cách trồng "hợp phong thủy" mà Việt Dũng có thể triển khai.

Bài 144: Chứng minh rằng : với mọi chia tập $ X= {1 ; 2 ; 3 ; 4 ; 5 ; 6 ; 7 ; 8 ; 9} $ thành hai tập con, luôn có 1 trong 2 tập đó chứa 3 số sao cho tổng của 2 trong 3 số đó bằng 2 lần số còn lại.

Bài 145: Tồn tại hay không 2 tập vô hạn A, B chứa các số nguyên không âm sao cho với số không âm $c$ bất kì nào đó, đều tìm được $a \in A , b \in B$ sao cho $c = a + b$.

Bài 146: Cho n dây cung trên một đường tròn. Các đầu mút được đánh số từ 1 đến 2n. Hãy chọn ra một tập lớn nhất các dây cung sao cho không có hai dây cung nào cắt nhau?

Bài 147:Có m đội bóng, mỗi đội đều đá với $m-1$ đội còn lại ($2$ đội khác nhau đá với nhau đúng $11$ trận), thằng thì được $2$ điểm, hoà được $1$ điểm, thua không có điểm nào. Hỏi sự chênh lệch tối đa giữa điểm của $2$ đội có thứ hạng liên tiếp

Bài 148:Có 100 tấm thẻ khác nhau được đánh số từ 1 đến 100, toàn bộ 100 tấm thẻ này được đặt trong 3 cái hộp phân biệt nhau (mỗi hộp phải chứa ít nhất 1 tấm thẻ). Hỏi có bao nhiêu cách sắp xếp 100 tấm thẻ ấy vào trong 3 hộp nói trên để cho nếu ta chọn ngẫu nhiên 2 hộp, rồi lại rút ngẫu nhiên 1 tấm thẻ ở mỗi hộp được chọn, thì từ tổng của 2 thẻ này (tức là tổng của 2 số được đánh trên chúng) ta có thể suy ra được hộp thứ 3 không được chọn?

Bài 149:Tại mỗi đỉnh của một đa giác đều n cạnh có một con chim đang đậu. Bỗng nhiên chim vụt cánh bay xa rối 1 phút sau trở lại. Khi chúng quay lại, mỗi đỉnh cũng có một con chim đậu, nhưng không nhất thiết giống vị trí trước đó. Hỏi với số n nào ta có thể luôn tìm được 3 con chim sao cho tam giác tạo bởi 3 vị trí ban đầu của chúng là cùng loại (tam giác nhọn, tam giác 1 góc tù hoặc tam giác vuông) với tam giác tạo bởi 3 vị trí sau cùng của chúng?

Bài 150:Chứng minh rằng với mõi số nguyên dương $n$ ; ta có :
$ \sum_{k=0}^{n-1}(-1)^{n-1-k}3^{k}\binom{3n}{k}\binom{3n-k-2}{n-1-k}=\sum_{k=0}^{n-1}\binom{3n}{k}(n-k)2^{k}$

To be continued...........


Bài viết đã được chỉnh sửa nội dung bởi dark templar: 06-04-2013 - 09:58

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


#6
dark templar

dark templar

    Kael-Invoker

  • Hiệp sỹ
  • 3788 Bài viết

Xin thông báo luôn là các bạn nào đã đưa lời giải cho các bài toán trong topic này thì mong các bạn hãy thông báo là Bài [...] đã có lời giải để cho các ĐHV Olympiad tổng hợp cho dễ dàng hơn.

**********

Bài 151: Tìm m lớn nhất sao cho $k \le m$, với mọi tập $l_1,...,l_k \le n-1$ thì luôn tồn tại một hoán vị của {1,2,...,n} mà với mọi i= 1,2,...,k đều không chứa $l_i$ phần tử liên tiếp là thuộc $A_i$.

 

Bài 152: Cho $6 \le |A| <+\infty$, sao cho nếu $a,b,c,d,e,f$ là 6 số bất kì phân biệt thuộc A thì $ab + cd + ef$ cũng thuộc A. Tìm giá trị lớn nhất của số các phần tử của tập A thỏa mãn điều kiện trên ?

 

Bài 153: Cho đa thức $P(x)$ thỏa mãn :

  1. $\deg P(x) \le 2n$.
  2. $\forall k \in \mathbb{Z}$ và $k \in [-n;n]$ thỏa mãn $P(k) \le 1$.

Chứng minh $\forall x \in [-n;n]$ thì $P(x) \le 4^{n}$.

(Đề bài bằng tiếng Anh,mình đã dịch sang tiếng Việt).

 

Bài 154: Trên bảng cho 1 số số 1, 1 số số 2 và 1 số số 3.Mỗi lần ta thực hiện một thuật toán là : xóa 2 số 1,3 thay bởi 1 số 2 và tương tự với các trường hợp còn lại.CMR: nếu sau khi thực hiện thuật toán trên mà trên bảng chi cong 1 số thì số này ko phụ thuộc vào cách xóa của ta.

 

Bài 155: Trên bảng cho 1 số số thực,mỗi một lần ta lấy 2 số thực trên bảng là $u$ và $v$ nào đó,xóa 2 số này đi và thêm vào bảng số $uv-u-v$. CMR: Với mọi cách xóa thì số cuối cùng còn lại trên bảng đều như nhau.

 

Bài 156: Định nghĩa tập $f:R_{mn} \to \{-1,0,1\}$ với tính chất sau :Với mỗi bốn điểm không nhỏ hơn $3$ ta có $(m,n)$ của các số nguyên dương .Xác định số các hàm như vậy trên $R_{mn}$.

 

Bài 157: Có $n^2$ quả bóng và $n$ cái giỏ. Tô $n^2$ quả bóng bằng $n$ màu khác nhau ( có đủ $n$ màu; mỗi màu không nhất thiết phải tô cho $n$ quả) Chứng minh rằng ta có thể chia $n^2$ quả bóng vào $n$ giỏ, mỗi giỏ có $n$ quả và trong mỗi giỏ thì số màu bóng không quá $2$

 

Bài 158: Cho $n$ là số nguyên dương cố định. Các điểm $A_1,A_2,...,A_{2n}$ cùng nằm trên một đường thẳng. Tô màu mỗi điểm đó bởi màu xanh ha màu đỏ tùy theo thủ tục sau: vẽ $n$ đường tròn đôi một phân biệt , mỗi một đường tròn có đường kính là $A_iA_j$ với $A_k$ nằm trên đúng một đường tròn. Các điểm trên cùng một đường tròn thi được tô màu giống nhau.Xác định số cách tô màu $2n$ điểm này khi ta thay đổi $n$ đường tròn và sự phân bố các màu.

 

Bài 159: $m$ lớn nhất sao cho:Với $n$ túi ,mỗi túi chứa một vài quả cầu,mỗi quả cầu có khối lượng là một lũy thừa nguyên của $2$(trong một túi khối lượng các quả cầu không cần thiết phải phân biệt),và tổng khối luợng của tất cả các quả cầu trong mỗi túi là bằng nhau,thì tồn tại ít nhất $m$ quả cầu có cùng khối lượng trong tất cả các quả cầu đã được chứa trong $n$ túi.

 

Bài 160: Cho tập hợp $A=(1,2,..,3n)$ với $n$ nguyên dương .Chứng minh rằng có thể chia tập $A$ thành các tập con mỗi tập gồm $n$ số và chúng đôi một không có phần tử chung .Chứng minh rằng luôn tồn tại một số thuộc tập này bằng tổng của hai số thuộc hai tập còn lại.

 

Bài 161: Có $n$ học sinh và $n$ bài toán. Biết mỗi bài toán đều có đúng $k$ học sinh giải được. Hãy tìm $k$ nhỏ nhất để chắc chắn có hai học sinh giải được số bài như nhau.

 

Bài 162: Có 9 con cờ domino giốnng nhau 2x1 xếp trên một khung 3x6 .( mỗi ô vuông trong khung có đánh số khác nhau). Hỏi có bao nhiêu cách xếp cờ đomino vào khung sao cho mỗi cách khác nhau khi cả 9 quân cờ cùng lúc không trùng vào vị trí cũ.

 

Bài 163: Có 5 ngôi nhà có màu khác nhau. Trong mỗi ngôi nhà có một người, những người này có quốc tịch khác nhau. 5 người này uống các loại nước kháu nhau, chơi các môn thể thao khác nhau và sở hữu các con vật khác nhau.


1) Người Phần Lan nuôi 1 con chó
2) Người Anh sống trong ngôi nhà màu đỏ
3) Người Đan Mạch uống trà
4) Người có ngôi nhà màu xanh lá cây uống cà phê
5) Người chơi Tennis có một con vẹt
6) Người sống trong ngôi nhà giữa uống sữa
7) Người có ngôi nhà màu vàng là vận đọng viên xe đạp
8) Người Pháp sống trong ngôi nhà đầu tiên
9) Người chơi bóng đá sống bên cạnh người nuôi con mèo
10) Ngôi nhà màu xanh lá cây nằm sát bên trái ngôi nhà màu trắng
11) Người có con ngựa sống ben cạnh vận động viên xe đạp
12) Người chơi Hockey thích uống bia
13) Người Pháp sống bên cạnh ngôi nhà màu xanh da trời
14) Người Đức là vận động viên điền kinh
15) Hàng xóm của người chơi bóng đá thích uống nước

Hỏi: Ai là người nuôi cá. Giải thích.

 

Bài 164: Cho $n>2$ là số nguyên dương. Đặt $M=\{1;2;...;n\}$ Chứng minh rằng tồn tại hàm $(x;y)=1$ thì $u<f(x)$ thì tồn tại $y$ mà $(x;y)=1$ và $f(y)=u$.

 

Bài 165: Lực lượng A (ký hiệu $|A|$).Nếu $|A| \Rightarrow |B|$ và $|B| \Rightarrow |A|$ thì $|A|=|B|$.

 

Bài 166: Cho $p$ là nguyên tố,và $p$ và chúng cho các số dư khác nhau khi chia cho $p$.Đặt $(b)_p$ là số dư khi chia $b$ cho $p$.Chứng minh $|S|<\dfrac{2p}{k+1}$.

 

Bài 167: 1) Cho 1 đa giác đều 2n đỉnh. Xác định số tam giác cân có các đỉnh là đỉnh của đa giác.

2) cho 1 đa giác n đỉnh. Xác định số tam giác có các đỉnh là đỉnh của đa giác và các cạnh là đường chéo của đa giác.

 

Bài 168: $A=\{1,2,...,2002\}$ và $M=\{1001,2003,3005\}$.$B$ là một tập con không rỗng của $A$.$B$ được gọi là một $M$-tập tự do nếu tổng của mỗi hai số trong $B$ không nằm trong $M$.Nếu $A_1,A_2$ là các $M$-tập tự do,chúng ta gọi cặp thứ tự $(A_1,A_2)$ là một $M$-phân hoạch của $A$.Tìm số các $M$-phân hoạch của $A$.

 

Bài 169: Chúng ta gọi một ma trận là ma trận nhị phân nếu các phần tử của nó bằng $0$ hoặc $1$.Một ma trận nhị phân được gọi là tốt nếu nó thỏa mãn đồng thời hai điều kiện sau đây:

(1)Tất cả các phần tử nằm phía trên đường chéo chính,không bao gồm đường chéo chính là bằng nhau.
(2)Tất cả các phần tử nằm phía dưới đường chéo chính,không bao gồm đường chéo chính là bằng nhau.

Cho một số nguyên dương $m$.Chứng minh:Có tồn tại số nguyên dương $M$,sao cho với mỗi số nguyên $n>M$ và một $n$x$n$ ma trận nhị phân $A_n$,chúng ta có thể chọn các số nguyên $i_1,i_2,...,i_{n-m}$ của $A_n$,thì ma trận nhị phân $B_m$ còn lại là tốt.

 

Bài 170: Cho $R_1,R_2$ là các quan hệ trên tập hợp A sao cho $R_1 \subset R_2 $.

i) nếu R1 phản xạ thì R2 phản xạ
ii) // R2 // R1 ///
iii)nếu R1 đối xứng thì R2 đối xứng
iv)// R2 /// R1 //
v)nếu R1 phản xứng thì R2 phản xứng
vi) R2 // R1 //
vii) R1 bắc cầu thì R2 bắc cầu
viii) R2 // R1 //

 

Bài 171: Trên đường thẳng có 2003 điểm tô một trong 4 màu xanh,đỏ tím vàng.Chứng minh tồn tại 1 đoạn thẳng có cả 4 màu trên, trong đó,có hai màu xuất hiện ít nhất hai lần,còn hai màu còn lại xuất hiện đúng 1 lần.Và có thể có nhiều hơn 1 đoạn thẳng có tính chát như vậy hay ko,chứng minh?

 

Bài 172: Với các số nguyên dương $t,a,b$, một trò chơi $\(t,a,b\)$ là một trò chơi gồm hai người như sau: ban đầu, số $t$ được viết trên một cái bảng. Trong lượt chơi đầu tiên, người chơi thứ nhất thay $t$ bằng $t-a$ hoặc $t-b$. Sau đó, người chới thứ hai trừ hoặc $a$ hoặc $b$ từ số đó, và viết kết quả lên bảng, xóa số cũ. Sau đó, người chơi thứ nhất lại trừ hoặc $a$ hoặc $b$ từ số viết trên bảng, và cứ tiếp tục như vậy. Người chơi nào mà viết một số âm lên bảng trước là người thua cuộc. Chứng minh rằng tồn tại vô hạn giá trị của $t$ sao cho người chơi đầu có chiến thuật chiến thắng với mọi cặp $\(a,b\)$ mà $a+b=2005$.

 

Bài 173: Cho bảng vuông 2005x2005. Tìm số nguyên dương $k$ lớn nhất sao cho với mọi cách điền số vào bảng mà thỏa mãn các điều sau:

i) mỗi ô vuông con được điền 1 số nguyên không âm.
ii) Tổng các số trên mỗi hàng và mỗi cột đều $\ge 1$

iii) Tổng tất cả các số trên bảng bằng $k$.
thì ta chọn được một số ( không quá 2005) hàng và cột mà tổng các số viết trong các hàng được chọn bằng tổng các số viết trong các cột được chọn.

 

Bài 174: $n$ là nguyên dương và $|S|=2^n+1$.Cho $f$ là hàm từ tập các tập con hai phần tử của $S$ tới $\{0,1,...,2^{n-1}-1\}$ sao cho với mỗi $f(\{x,y\}),f(\{y,z\}),f(\{z,x\})$ sẽ bằng tổng hai số còn lại.Chứng minh có tồn tại $f(\{a,b\})=f(\{b,c\})=f(\{c,a\})=0$.

 

Bài 175: Có $n$ người, biết rằng:

(a) Trong ba người bất kỳ thì có hai người quen người còn lại.
(b) Trong bốn người bất kỳ thì có hai người không quen những người còn lại.
Tìm giá trị lớn nhất của $n$.
Ở đây ta giả sử rằng, nếu $A$ quen $B$ thì $B$ quen $A$.

 

Bài 176: Cho 2 nhóm người A và B.CMR:Tồn tại 1 trong 2 tập con C của A (ít nhất 1 phần tử ) hoặc 1 tập con D của B sao cho : số người trong D ( C) mà mỗi người trong A ( B ) quen có cùng tính chẵn lẻ.

 

Bài 177: Cho một đồ thị G sắc số n (n $ \ge $ 4).Có thể hay không vẽ vào trong G một đồ thị đầy đủ ?

 

Bài 178: $S=\{(x,y)|x=1,2,...,1993,y=1,2,3,4\}$.Nếu $T$(Các hình vuông trong $T$ có các đỉnh đều thuộc $S$).Tìm giá trị lớn nhất có thể của $|T|$.

 

Bài 179: Cho $2m$-giác lồi $A_1A_2...A_{2m}$ và điểm $P$ không nằm trên đường chéo nào.Chứng minh số tam giác có 3 đỉnh trong $2m$ đỉnh mà chứa $P$ là số chẵn.

 

Bài 180: Cho tam giác đều ABC với độ dài mỗi cạnh là N. Chia tam giác đều thành các tam giác đều có cạnh 1. Bắt đầu ở tam giác chứa đỉnh A, mỗi lần thì bước sang tam giác bên cạnh ( có cạnh chung) sao cho không có tam giác nào được đến 2 lần. Hãy tìm và chứng minh số tam giác lớn nhất mà có thể đến được.

 

 

 


Bài viết đã được chỉnh sửa nội dung bởi dark templar: 06-04-2013 - 16:42

"Do you still... believe in me ?" Sarah Kerrigan asked Jim Raynor - Starcraft II:Heart Of The Swarm.




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

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