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

[thuan192]

BÀI 34:  Cho bàn cờ vua n x n ô.Dán mếp trái và mép phải của bàn cờ với nhau,sao cho mặt bàn cờ quay ra ngoài,ta thu được một bàn cờ hình trụ.Tiếp tục dán mép trên và mép dưới của bàn cờ hình trụ ta sẽ thu được một bàn cờ hình xuyến.Hỏi trên bàn cờ hình xuyến ấy có thể xếp được tối đa bao nhiêu quân vua sao cho quân nọ không ăn được quân kia?

[bachhammer]

Bài 35: Cho 2014 điểm trong mặt phẳng sao cho bao lồi của chúng là một bát giác là 8 điểm của hệ điểm đã cho. Biết không có điểm nào thẳng hàng và bát giác bao lồi ấy có diện tích không vượt quá 1,5 cm^2. Chứng minh rằng tồn tại ba điểm thuộc hệ trên sao cho diện tích tam giác tạo bởi 3 điểm ấy không vượt quá 1/2014 cm^2.......

[LNH]

Bài 25: (UK 2007) Ở nước Hexagonia, 6 thành phố được kết nối bởi hệ thống đường sắt sao cho giữa hai thành phố bất kỳ có đường sắt nối trực tiếp. Vào ngày chủ nhật, một số đoạn đường đóng cửa để sửa chữa. Luật đường sắt quy định là mọi thành phố phải có thể đến được từ một thành phố khác (không nhất thiết trực tiếp) trong mọi thời điểm. Có bao nhiêu cách đóng một vài đoạn đường để yêu cầu này được thoả mãn?

Ta đưa về việc đếm số đồ thị liên thông được tạo từ $6$ đỉnh

Đặt mỗi thành phố là một điểm và đoạn đường nối hai thành phố là một cạnh.

Xin phát biểu một bổ đề quen thuộc (nhưng không biết chứng minh ):

Nếu $G$ là một đồ thị không liên thông thì $\overline{G}$ (đồ thị bù của $G$) là một đồ thị liên thông

Gọi $X,Y$ lần lượt là tập hợp các đồ thị liên thông và không liên thông được tạo từ $6$ đỉnh

Xét ánh xạ $f:Y\rightarrow X$, $f\left ( G \right )=\overline{G}$

Dễ dàng nhận thấy đây là một song ánh

Suy ra $\left | X \right |=\left | Y \right |$

Mặt khác $\left | X\cup Y \right |=2^6$, $\left | X\cap Y \right |=0$

Vậy $\left | X\right |=2^5$

Có $2^5$ cách chọn thoả mãn ycdb

[AnnieSally]

Bài 36: Cho $A_1,...,A_{100}$ là một tập các tập con của $\begin{Bmatrix} 1,2,3,4,5,6 \end{Bmatrix}$ sao cho với mọi $i, j, k$ phân biệt, ta có $|A_i\cup A_j\cup A_k|\geq 5.$ Tìm giá trị nhỏ nhất của $\sum_{i=1}^{100}|A_i|$ 

Bài này quen k lenhathoang1998? Nhớ hồi đó wá vui hơn bây giờ nhìu  

[AnnieSally]

$1$ bài tập về dùng phương pháp đồ thị nhé

Bài 37: ($TST$ Hong Kong $1999$) Các học sinh được phát bài kiểm tra, mỗi môn một bài, trong $n$ ($n\geq 3$) môn học. Biết rằng với mỗi môn học bất kì có đúng $3$ học sinh đạt điểm tối ưu, còn với hai môn tùy ý thì có $1$ học sinh đạt điểm tối ưu cho mỗi môn trong cả hai môn đó. Hãy xác định $n$ bé nhất sao cho từ các điều kiện có thể suy ra có đúng $1$ học sinh đạt điểm tối ưu cho mỗi môn trong $n$ môn học.

Bài viết đã được chỉnh sửa nội dung bởi AnnieSally: 02-11-2013 - 20:25

[LNH]

$1$ bài tập về dùng phương pháp đồ thị nhé

Bài 37: ($TST$ Hong Kong $1999$) Các học sinh được phát bài kiểm tra, mỗi môn một bài, trong $n$ ($n\geq 3$) môn học. Biết rằng với mỗi môn học bất kì có đúng $3$ học sinh đạt điểm tối ưu, còn với hai môn tùy ý thì có $1$ học sinh đạt điểm tối ưu cho mỗi môn trong cả hai môn đó. Hãy xác định $n$ bé nhất sao cho từ các điều kiện có thể suy ra có đúng $1$ học sinh đạt điểm tối ưu cho mỗi môn trong $n$ môn học.

Nhận xét: Nếu có một học sinh đạt điểm tối ưu trong $4$ môn thì sẽ đạt điểm tối ưu trong $n$ môn

Vậy ta chỉ cần tìm $n$ nhỏ nhất sao cho tồn tại một học sinh đạt điểm tối ưu ở $4$ môn

Xét đồ thị $G=\left ( V,E \right )$ với các đỉnh là học sinh, $2$ học sinh có điểm tối ưu chung ở một môn thì sẽ được nối với nhau bởi một cạnh

Ta thấy $2$ tam giác bất kì đều có ít nhất một đỉnh chung

Xét ba điểm $X_1,X_2,X_3$ lập thành một tam giác

Ta cần xây dựng số $n$ nhỏ nhất sao cho tồn tại bậc của một trong $3$ đỉnh trên lớn hơn hoặc bằng $4$

Ta có: $\left \lfloor \frac{n-2}{3} \right \rfloor+1\geq 4$

$\Leftrightarrow n\geq 8$

Vậy $n_{min}=8$

[dinhthanhhung]

Bài 29:Trong một phòng thi gồn có 9 thí sinh được xếp ngồi xung quanh một bàn tròn.TRong ngân hàng đề có 9 loại đề khác nhau mỗi loại có nhiều bản.Một cách phát đề được coi là hợp lệ nếu mỗi thí sinh được nhận chỉ một đề và hai thí sinh ngồi cạnh nhau thì nhận được hai loại đề khác nhau.Hỏi có tất cả bao nhiêu cách phát đề hợp lý?

 

Bài này giải bằng truy hồi . Cách giải ở đây: http://diendantoanho...òn/#entry479746

p/s: Mãi mà không nghĩ ra ...

[LNH]

Lâu quá không đăng, topic đóng bụi dày cộm rồi

Bài 38: Gọi $f\left ( a,b,c \right )$ là số các cách để điền vão các ô trong bảng $a\times b$ bằng các số trong $\left \{ 1;2;...;c \right \}$ sao cho trong bất kì ô nào, số nằm trong ô đó đều lớn hơn hoặc bằng số ở ô trên nó và số ở ô bên trái nó. Chứng minh rằng: $f\left ( a,b,c \right )=f\left ( c-1,a,b+1 \right )$

Bài 39: Đặt $21$ điểm trên đường tròn. Chứng minh rằng: có ít nhất $100$ cặp điểm tạo ra cung nhỏ hơn hoặc bằng $120^0$

[dinhthanhhung]

 

Bài 39: Đặt $21$ điểm trên đường tròn. Chứng minh rằng: có ít nhất $100$ cặp điểm tạo ra cung nhỏ hơn hoặc bằng $120^0$

 

Xét graph đỉnh là $21$ điểm trên, $2$ đỉnh nối với nhau nếu cung tạo bởi chúng lớn hơn $120^0$ .

Dễ thấy đây là graph 3-free nên số cạnh tối đa là $\left \lfloor \frac{21^2}{4} \right \rfloor=110$

Do đó số cặp đỉnh tạo cung nhỏ hơn hoặc bằng $120^0$ là $C_{21}^{2}-110=100$

Bài viết đã được chỉnh sửa nội dung bởi LNH: 23-06-2014 - 14:38

[LNH]

Bài 40: Cho $A$ là tập gồm $n$ phần tử, $A_1,...,A_m$ là các tập con có $3$ phần tử thoả mãn $\left | A_i \cap A_j \right |\leq 1, \forall i \neq j$. Chứng minh rằng: $\exists T \subset A$ thoả mãn: $\overline{\exists }$ $i$ sao cho $A_i\subseteq T,\left | T \right |\geq \left \lfloor \sqrt{2n} \right \rfloor$

Bài 41: Cho một bảng hình chữ nhật kích thước $2\times n$. Mỗi ô ta viết một số thực dương sao cho tổng $2$ số ở cùng cột đều bằng $1$. Chứng minh rằng: ta có thể bỏ mỗi cột một số sao cho tổng các số còn lại ở cùng một hàng không quá $\frac{n+1}{4}$

[quocbaolqd11]

 

Bài 40: Cho $A$ là tập gồm $n$ phần tử, $A_1,...,A_m$ là các tập con có $3$ phần tử thoả mãn $\left | A_i \cap A_j \right |\leq 1, \forall i \neq j$. Chứng minh rằng: $\exists T \subset A$ thoả mãn: $\overline{\exists }$ $i$ sao cho $A_i\subseteq T,\left | T \right |\geq \left \lfloor \sqrt{2n} \right \rfloor$

Gọi $T'$ là tập không chứa $A_i$ sao cho $|T'|$ đạt max. Như vậy, với bất kì tập $T''=T \cup \{x\}$ thì $T''$ chứa $A_i$. 
Giờ ta sẽ đếm số bộ $(A_i,m,n)=k$ với $m \neq n \in T'$ và $m,n \in A_i$. Vì  $|A_i \cap A_j| \le 1$ nên:
                                                                $k \le C_{|T'|}^{2}$  
Mà với mỗi $p \in A\setminus T'$, ta xác định được duy nhất một phần tử thuộc bộ $(A_i,m,n)$. Vậy nên:
                                                                $k \ge n-|T'|$ 
Từ đó, ta có: $C_{|T'|}^{2} \ge n-|T'|$. Giải bpt, ta được đpcm.

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

[bangbang1412]

 

 

 

Gọi $T'$ là tập không chứa $A_i$ sao cho $|T'|$ đạt max. Như vậy, với bất kì tập $T''=T \cup \{x\}$ thì $T''$ chứa $A_i$. 
Giờ ta sẽ đếm số bộ $(A_i,m,n)=k$ với $m \neq n \in T'$ và $m,n \in A_i$. Vì  $|A_i \cap A_j| \ge 1$ nên:
                                                                $k \le C_{|T'|}^{2}$  
Mà với mỗi  $p \in A\T'$, ta xác định được duy nhất một phần tử thuộc bộ $(A_i,m,n)$. Vậy nên:
                                                                $k \ge n-|T'|$ 
Từ đó, ta có: $C_{|T'|}^{2} \ge n-|T'|$. Giải bpt, ta được đpcm.

 

$|A_{i}\cup \A_{j}|\leq 1$ mà

[bangbang1412]

Bài 42: ( thực ra là biến thể của một bài IMO chế thế này để lập ma trận cho dễ ) Cho tập $S$ gồm $n$ điểm sao cho $P\in S$ thì có ít nhất $k$ điểm để mỗi điểm cách $P$ một khoảng là $x$ , không có $3$ điểm nào thẳng hàng . Giả sử tồn tại tập trên chứng minh. 

                                                                     $k \leq 1 +\left \lfloor \sqrt{2n} \right \rfloor$

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

[LNH]

Bài 43: Cho bảng ô vuông $n \times n$ được tô bằng $2$ màu trắng và đen. Giả sử tồn tại tập $A$ khác rỗng gồm các hàng sao cho bất kì cột nào cũng chứa một số chẵn ô trắng thuộc $A$. Chứng minh rằng: Tồn tại tập $B$ khác rỗng gồm các cột sao cho bất kì hàng nào đều có số chẵn ô trắng thuộc $B$.

[shinichigl]

Bài 44 (Thuật toán) Có hai đống đá có $n$ hòn và đống kia có $k$ hòn. Cứ mỗi phút một máy tự động lại chọn một đống có số hòn đá là chẵn và chuyển một nửa số hòn đá của đống đá được chọn sang đống kia. Nếu cả hai đống đều có số hòn đá là chẵn thì máy sẽ chọn ngẫu nhiên một đống. Nếu trong hai đống số hòn đá đều là lẻ thì máy sẽ ngừng làm việc. Hỏi tồn tại bao nhiêu cặp sắp thứ tự $(n,k)$, với $n$ và $k$ là các số tự nhiên không vượt quá $2013$, để máy tự động sau một khoảng thời gian hữu hạn sẽ dừng?

Bài viết đã được chỉnh sửa nội dung bởi shinichigl: 07-09-2014 - 19:07

[shinichigl]

Bài 45 (Thuật toán) Cho hai đống đá, một đống có $a$ hòn đá, đống kia có $b$ hòn đá. Hai người chơi, mỗi người đến lượt mình được lấy một hòn đá từ một trong hai đống, hoặc lấy phần nguyên của một nửa số hòn đá từ đống thứ nhất, hoặc lấy phần nguyên một nửa số hòn đá từ đống thứ nhất, hoặc lấy phần nguyên một nửa số hòn đá từ đống thứ hai, hoặc lấy từ hai đống số hòn đá như nhau. Người lấy được hòn đá cuối cùng là người chiến thắng. Hãy tìm tất cả các cặp $(a,b)$ trong đó $a\leq 8,b\leq 13$ sao cho người đi sau có chiến thuật thắng.

Bài viết đã được chỉnh sửa nội dung bởi shinichigl: 07-09-2014 - 19:24

[Near Ryuzaki]

Topic dạo này vắng quá T.T Em ủng hộ $1$ số bài :

Bài 46. Cho $6$ số nguyên dương tùy ý . Chứng minh rằng luôn có thể chọn được $2$ bộ $3$ số mà trong mỗi bộ, từng đội một đều là nguyên tố cùng nhau hoặc đều không nguyên tố cùng nhau.

Bài viết đã được chỉnh sửa nội dung bởi sieusieu90: 23-10-2014 - 13:03

[khanghaxuan]

Topic dạo này vắng quá T.T Em ủng hộ $1$ số bài :

Bài 46. Cho $6$ số nguyên dương tùy ý . Chứng minh rằng luôn có thể chọn được $2$ bộ $3$ số mà trong mỗi bộ, từng đội một đều là nguyên tố cùng nhau hoặc đều không nguyên tố cùng nhau.

Từ bài toán trên , ta có thể quy về bài toán sau : Cho  6 điểm trên mặt phẳng , mỗi cạnh được tô bởi 2 màu , chứng minh rằng luôn tồn tại 3 cạnh được tô cùng 1 màu . 

(Bài toán này chứng minh không quá khó )

[khanghaxuan]

Topic đóng bụi quá dày rồi ! 

Làm một bài để '' quét dọn '' 

Bài 47 : ( pp truy hồi )  Tìm số hoán vị của tập $A={1,2,...,n}$ sao cho mỗi hoán vị đều thỏa : $2.(a_{1}+a_{2}+...+a_{n})\vdots k$ ( với $k\in {1,2,...,n}$ ) 

[LNH]

Topic đóng bụi quá dày rồi ! 

Làm một bài để '' quét dọn '' 

Bài 47 : ( pp truy hồi )  Tìm số hoán vị của tập $A={1,2,...,n}$ sao cho mỗi hoán vị đều thỏa : $2.(a_{1}+a_{2}+...+a_{n})\vdots k$ ( với $k\in {1,2,...,n}$ ) 

Lâu rồi mới có người quét dọn

Bài này là IMOSL 2008

http://www.artofprob...4446f0#p1472110