Đến nội dung

whatever2507 nội dung

Có 32 mục bởi whatever2507 (Tìm giới hạn từ 30-03-2020)



Sắp theo                Sắp xếp  

#523759 Saudi Arabia IMO Team Selection Test 2014

Đã gửi bởi whatever2507 on 10-09-2014 - 15:35 trong Thi HSG Quốc gia và Quốc tế

Bài 1 ngày 1. Gọi Sultan là S cho dễ  :). Giả sử số ban đầu là $a$.

Bước 1. S chọn $2$, nếu chưa được thì ta có số $a-2$ lẻ.

Bước 2. S chọn $3$, nếu chưa được thì ta có số $a-5$ chẵn và chia $3$ dư $b (b=1$ hoặc $2)$.

Bước 3. S chọn $5$, nếu chưa được thì ta có số $a-10$ lẻ và chia $3$ dư $b-2$.

Bước 4. S chọn $9$, nếu chưa được thì ta có số $a-19$ chẵn và chia $3$ dư $b-2$.

Bước 5. S chọn $6$, nếu chưa được tức là $b \neq 2$ hay $b=1$, bây giờ ta có số $a-25$ chẵn và chia $3$ dư $2$.

Bước 6. S chọn $4$ nếu chưa được tức là $a-25 \equiv 2 (mod4)$ và bây giờ ta có số $a-29$ chia $3$ dư $1$ và chia $4$ dư $2$.

Bước 7. S chọn $10$, nếu chưa được thì ta còn số $a-35$ chia hết cả $3$ và $4$.

Bước 8. S chọn $12$ và chiến thắng.




#461086 Danh sách đội tuyển các trường và các tỉnh đi thi quốc gia năm 2014

Đã gửi bởi whatever2507 on 31-10-2013 - 16:51 trong Thi HSG Quốc gia và Quốc tế

Số 2 là Đỗ Tuấn Mạnh em ơi.



#432338 Topic về tổ hợp, các bài toán về tổ hợp

Đã gửi bởi whatever2507 on 02-07-2013 - 18:25 trong Tổ hợp và rời rạc

 

Đáp số của cả $2$ TH đều là $d \le 10\sqrt{2}$, dùng chung $1$ lập luận và chỉ hơi khác nhau cách đưa quân cờ thỏa mãn :).

 

Bài 4 (Tô màu - Nguồn: Đề thi HSG lớp 10 THPT chuyên KHTN). Cho một bảng ô vuông kích thước $m \times n$. Người ta muốn tô màu các ô vuông con của bảng, mỗi ô vuông con chỉ được tô bởi 1 trong 2 màu Xanh hoặc Đỏ theo quy tắc sau:

i) Tất cả các ô vuông con ở cạnh của bảng đều được tô màu Đỏ.
ii) Không có hình vuông kích thước $2 \times 2$ nào của bảng mà $4$ ô vuông con được tô cùng màu.
iii) Không có hình vuông kích thước $2 \times 2$ nào của bảng mà hai ô ở mỗi đường chéo đều được tô cùng màu.
Hỏi người ta có thể thực hiện cách tô màu như trên trong các trường hợp với bảng ô vuông kích thước:
$a) 2012 \times 2013?$
$b) 2012 \times 2014?$

 

 Để giải hoàn chỉnh và chặt chẽ bài này ra thì khá dài, thế nên mình chỉ post ý tưởng của câu b ra mọi người thực hiện tính toán nhé :). (Còn câu a cách xây dựng thì hoàn toàn không khó  :P ).

 

Gợi ý câu 4b)  Giả sử tồn tại cách tô màu thoả mãn điều kiện. Xét các giao điểm của các đường thẳng vuông góc nhau bên trong bảng vuông là các điểm nguyên trên mặt phẳng toạ độ với toạ độ $(i,j) (1 \le i \le 2011, 1 \le j \le 2013)$. Gọi $x_{ịj}$ là số đoạn thẳng đơn vị (đoạn thẳng độ dài $1$) nằm trong hình vuông $4 \times 4$ có tâm là điểm $(i,j)$ mà ngăn cách giữa $2$ ô cùng màu, $y_{ịj}$ là số đoạn thẳng đơn vị nằm trong hình vuông $4 \times 4$ có tâm là điểm $(i,j)$ mà ngăn cách giữa $2$ ô khác màu, $X$ là số đoạn thẳng đơn vị nằm trong bảng vuông $2012 \times 2014$ ngăn cách giữa $2$ ô cùng màu, $Y$ là số đoạn thẳng đơn vị nằm trong bảng vuông $2012 \times 2014$ ngăn cách giữa $2$ ô khác màu. Ta tính $X-Y$ theo $2$ cách.

Để ý rằng $x_{ij}=y_{ij} \forall i,j$.

Đầu tiên ta tính $X-Y$ theo tổng $\sum_{i \equiv j (mod2)} (x_{ij}-y_{ij})$ sau đó theo tổng  $\sum_{i \not\equiv j (mod2)} (x_{ij}-y_{ij})$. Có vẻ ta thấy $2$ tổng này bằng nhau và bằng $0$ nhưng với mỗi cách đếm thì có một số cạnh chưa được tính (các cạnh này toàn nằm giữa các ô vuông đỏ trên biên nên dễ đếm thôi), và 2 cách đếm cho ta số cạnh chưa được tính khác nhau nên suy ra mâu thuẫn :).




#432160 Topic về tổ hợp, các bài toán về tổ hợp

Đã gửi bởi whatever2507 on 01-07-2013 - 22:18 trong Tổ hợp và rời rạc

 

Bài 3 (Toán trò chơi-Nguồn: Tournament of the Towns). Trên bảng ô vuông $20$x$20$ mỗi ô có $1$ quân cờ. $A$ chọn một số thực $d$ và $B$ phải đưa mỗi quân cờ đi tới ô cách ô ban đầu nó đứng một khoảng cách ít nhất là $d$ (khoảng cách giữa $2$ ô được tính theo khoảng cách tâm của $2$ ô đó) và mỗi ô chỉ có thể có $1$ quân cờ. Hỏi với điều kiện gì của $d$ thì $B$ có thể thao tác thoả mãn điều kiện trên?

Hỏi tương tự với bảng $21$x$21$

Bài này chỉ dùng duy nhất $1$ nhận xét, tiếc là chưa ai giải.

Giải bài 3. $*$ TH bảng $20 \times 20$:

Xét toạ độ các ô (được tính ở tâm ô) là $(i, j) \forall 1 \le i, j \le 20$. Xét ô $(10, 10)$, giả sử sau bước chuyển quân cờ ở ô này chuyển đến ô $(a,b) (1 \le a,b \le 20, a, b$ không đồng thời bằng $10)$, khi đó khoảng cách giữa $2$ ô là: $\sqrt{(a-10)^2+(b-10)^2} \ge d$.

Do $1 \le a,b \le 20$ nên $|a-10| \le 10, |b-10| \le 10 \Rightarrow d \le 10\sqrt{2}$.

Cách chuyển quân: Các quân ở các ô $(i, j)$ đến ô $(i', j')$ với $\begin{cases} i'=i+10 & \text{ if } i \le 10\\ i'=i-10 & \text{ if } i > 10 \end{cases}$.

 

$*$ TH bảng $21 \times 21$: Lập luận tương tự với ô $(11,11)$, cách xây dựng mọi người tự tìm nhé :).




#431953 Topic về tổ hợp, các bài toán về tổ hợp

Đã gửi bởi whatever2507 on 30-06-2013 - 23:17 trong Tổ hợp và rời rạc

Bài 9: (tập hợp,Germany 1970) Cho tập $M$ có $22222$ phần tử .Hỏi $M$ có hay không 50 tập con thoả mãn :

 1/Mỗi phần tử của $M$ là phần tử của ít nhất 1 trong các tập con.

 2/Mỗi tập con đều có $1111$ phần tử.

 3/Với 2 tập $M_i;M_j (i \neq j)$ có ${M_i} \cap {M_j}$ 22 phần tử.

Giải bài 9. Gọi các phần tử của $M$ là $a_1 \rightarrow a_{22222}$. Giả sử tồn tại $50$ tập con $M_i (1 \le i \le 50)$ thoả mãn $3$ yêu cầu trên. Ta đếm số cách chọn $2$ tập $M_i, M_j (i \neq j)$ kèm theo $1$ phần tử $a_k$ thuộc $M_i \cap M_j$. Gọi số cách chọn này là $S$.

Có $C^2_{50}$ cách chọn $2$ tập $M_i, M_j (i \neq j)$ và $22$ cách chọn phần tử $a_k$ thuộc $M_i \cap M_j$.

$\Rightarrow S=22.C^2_{50}=26950$.

 

Mặt khác, giả sử $a_i$ thuộc $r_i ( \forall 1 \le i \le 22222)$ tập $M_j$. Khi đó dễ CM được $$\sum_{i=1}^{22222}r_i= \sum_{i=1}^{50} |M_i|=50.1111=55550$$.

 

Có $22222$ cách chọn phần tử $a_i$ bất kỳ, và có $C^2_{r_i}$ cách chọn 2 tập $M_j, M_k$ sao cho $a_i \in M_j \cap M_k$ (coi $C^2_1=0$).

$\Rightarrow S=\sum_{i=1}^{22222} C^2_{r_i}$

$=\sum_{i=1}^{22222} \frac{r_i(r_i-1)}{2}$

$=\frac{1}{2}(\sum_{i=1}^{22222}r_i^2 - \sum_{i=1}^{22222}r_i)$

$\geq \frac{1}{2} (\frac{(\sum_{i=1}^{22222} r_i)^2}{22222}-\sum_{i=1}^{22222} r_i)$ (BĐT C-S)

$=\frac{55550^2-22222.55550}{2.22222}>26950=S$ (mâu thuẫn).

Vậy không tồn tại $50$ tập con của $M$ thoả mãn đề bài.




#431944 Topic về tổ hợp, các bài toán về tổ hợp

Đã gửi bởi whatever2507 on 30-06-2013 - 22:29 trong Tổ hợp và rời rạc

Bài 12: (Bất biến) Trong một ngày chủ nhật mỗi học sinh trong bảy học sinh có ba lần đi đến hiệu sách. Biết rằng hai học sinh bất kì trong số đó có gặp nhau tại hiệu sách. Chứng minh rằng có mội thời điểm mà trong hiệu sách có mặt cùng lúc 3 học sinh. (trong 7 học sinh nói trên)

Giải bài 12. Gọi $7$ bạn học sinh này là $X_1 \rightarrow X_7$, xét $3$ thời điểm $A_1, A_2, A_3$ mà học sinh $X_1$ đi đến hiệu sách. Do cả $6$ học sinh khác đều có gặp $X_1$ nên mỗi người trong số họ phải đến hiệu sách vào ít nhất $1$ trong $3$ thời điểm kể trên, theo nguyên lý Dirichlet thì tồn tại $2$ học sinh $X_i$ và $X_j (2 \le i,j \le 7, i \neq j)$ đến vào cùng $1$ thời điểm $A_i$. Do đó $3$ học sinh $X_i, X_j, X_1$ cùng có mặt tại hiệu sách cùng $1$ thời điểm nên ta có đpcm.

 

Có vẻ bài trên chỉ cần $5$ học sinh là đủ nhỉ? :)




#431866 Topic về tổ hợp, các bài toán về tổ hợp

Đã gửi bởi whatever2507 on 30-06-2013 - 18:37 trong Tổ hợp và rời rạc

Mình cũng hơi kém phần tổ hợp rời rạc này, nên cũng muốn được học tập trao đổi kinh nghiệm. Mình xin đưa ra một bài nho nhỏ:

Bài 8: (phương pháp tự do, không câu nệ cách giải) Trên một sân chơi có 10 em bé đứng. Biết rằng khoảng cách giữa các em bé đôi một khác nhau và mỗi em bé cầm trong tay một quả bóng (quả bóng là một trong bốn màu đỏ, vàng, lam, lục). Sau hiệu lệnh của chị phụ trách, mỗi em đưa quả bóng của mình cho bạn đứng gần nhất. Hỏi rằng có ít nhất bao nhiêu em bé còn có bóng trong tay?

4 màu để làm gì nhỉ?  :)).

Giải bài 8. Ta CM còn ít nhất 2 em bé có bóng. Gọi vị trí 10 em bé đứng lần lượt là $A_1 \rightarrow A_{10}$

Giả sử tồn tại cách đứng sao cho sau khi chuyển bóng thì còn đúng 1 em bé có bóng. Giả sử chỉ có em $A_1$ còn bóng.

Xét các góc $\angle A_jA_1A_i (\forall 2 \le i, j \le 10, i \neq j)$, theo nguyên lý Dirichlet tồn tại 1 góc nhỏ hơn $60^o$, WLOG giả sử là $\angle A_2A_1A_3 < 60^o$. Khi đó tồn tại một trong 2 góc $\angle A_1A_2A_3$ hoặc $\angle A_2A_3A_1$ lớn hơn $60^o$ và lớn hơn $\angle A_2A_1A_3$. Giả sử $\angle A_2A_1A_3< \angle A_1A_2A_3$, khi đó $A_2A_3<A_1A_3$ do vậy $A_3$ sẽ đưa bóng cho $A_2$ chứ không phải $A_1$ (mâu thuẫn).

Vậy có ít nhất 2 em còn cầm bóng.

Cấu hình sau đảm bảo có đúng 2 em cầm bóng là $A_1$ và $A_6$.

Hình gửi kèm

  • HInh.png



#431857 Topic về tổ hợp, các bài toán về tổ hợp

Đã gửi bởi whatever2507 on 30-06-2013 - 17:54 trong Tổ hợp và rời rạc

Nhưng $S(n)>0$  mà bạn, với lại $S(n)$ đúng hơn là số nguyên dương, làm sao mà âm được

VD nhé, nếu có ngày mà ở phòng $1$ và $2$ có người thì họ sẽ chuyển sang phòng $0$ và $3$, thì $S(n)$ lúc này bằng $0$ thì sao thực hiện phép chia xuống mẫu được :).

 

 

 

 

Bài 4 (Tô màu - Nguồn: Đề thi HSG lớp 10 THPT chuyên KHTN). Cho một bảng ô vuông kích thước $m \times n$. Người ta muốn tô màu các ô vuông con của bảng, mỗi ô vuông con chỉ được tô bởi 1 trong 2 màu Xanh hoặc Đỏ theo quy tắc sau:

i) Tất cả các ô vuông con ở cạnh của bảng đều được tô màu Đỏ.
ii) Không có hình vuông kích thước $2 \times 2$ nào của bảng mà $4$ ô vuông con được tô cùng màu.
iii) Không có hình vuông kích thước $2 \times 2$ nào của bảng mà hai ô ở mỗi đường chéo đều được tô cùng màu.
Hỏi người ta có thể thực hiện cách tô màu như trên trong các trường hợp với bảng ô vuông kích thước:
$a) 2012 \times 2013?$
$b) 2012 \times 2014?$

 

 

Bài 3 (Toán trò chơi-Nguồn: Tournament of the Towns). Trên bảng ô vuông $20$x$20$ mỗi ô có $1$ quân cờ. $A$ chọn một số thực $d$ và $B$ phải đưa mỗi quân cờ đi tới ô cách ô ban đầu nó đứng một khoảng cách ít nhất là $d$ (khoảng cách giữa $2$ ô được tính theo khoảng cách tâm của $2$ ô đó) và mỗi ô chỉ có thể có $1$ quân cờ. Hỏi với điều kiện gì của $d$ thì $B$ có thể thao tác thoả mãn điều kiện trên?

Hỏi tương tự với bảng $21$x$21$

 

 

Bài 3 và 4 vẫn chưa có lời giải nhé mọi người :)




#431724 Topic về số học, các bài toán về số học.

Đã gửi bởi whatever2507 on 30-06-2013 - 00:42 trong Số học

Sao lại sửa đề vậy mấy bạn ! Đề đúng là (m,n,k) = 1.

Đúng là nếu (m, n, k)=1 thì sẽ cần thêm bước sau để bài toán chặt chẽ hơn: Giả sử tồn tại $p$ nguyên tố và $p|m, p|n$, khi đó do $p|k^2$ và $p$ nguyên tố nên $p|k$ suy ra $(m,n,k) \ge p >1$(mâu thuẫn) nên $(m,n)=1$ :).

 

Bài 16 Cho $n$ là số nguyên dương. Kí hiệu $\pi (n)$ là số các số nguyên tố không vượt quá $n$. Chứng minh rằng:

$\pi (n)\leq \frac{n}{2}-1$ với mọi $n\geq 14$

Giải bài 16. Ta CM quy nạp theo $n$: $\pi (n)\leq \frac{n}{2}-1$ với mọi $n\geq 14 (*)$

  • $(*)$ đúng với $n=14, 15$.
  • Giả sử (*) đúng với $n \ge 15$, ta Cm nó đúng với $n+2$.

Thật vậy, trong 2 số $n+1$ và $n+2$ luôn có $1$ số chẵn, số này $\ge 15$ nên không thể là số nguyên tố.

$\Rightarrow \pi (n+2)\leq \pi(n)+1 \le \frac{n}{2}-1+1 = \frac{n+2}{2}-1$

Vậy ta có $(*)$ đúng với $n+2$ và ta có đpcm.




#431721 Topic về tổ hợp, các bài toán về tổ hợp

Đã gửi bởi whatever2507 on 29-06-2013 - 23:49 trong Tổ hợp và rời rạc

Giải bài 5

Gọi $S(n)$ là tích số thứ tự phòng của tất cả mọi người ngày thứ $n$

Như vậy ta có

$\frac{S(n+1)}{S(n)}=\frac{n(n+1)}{(n-1)(n+2)}=\frac{n^{2}+n}{n^{2}+n-2}< 1$

$\Rightarrow S(n+1)<S(n)$

Như vậy $S(n)$ là một đơn biến. Do $S(n)$ giảm và $S(n)>0$ nên việc chuyển phòng sẽ dừng sau một số ngày

 

------------------------------------------

Lời giải này chưa chặt chẽ vì có thể mẫu bằng $0$ hoặc âm thì chưa thể đánh giá được.

 

 

 

Bài 7 (bất đẳng thức tổ hợp)

Gọi $X=\left \{ 1,2,...,2003 \right \}$. Lấy số tự nhiên $n\geq 1$ và $n\leq 2003$ sao cho nếu lấy tập hợp con gồm $n$ phần tử của $X$, thì ta có thể tìm được một phần tử là lũy thừa của $2$ hoặc $2$ phần tử có tổng là lũy thừa của $2$. Chứng minh rằng: $n\geq 999$

Giải bài 7. Xét tập $A=\left \{ 5, 6, 7, 12, 13, 14, 15, 21, 22, 23, 24, 28, 29, 30, 31, 37, 38, 39, 44\right \}$ và $B=\left \{n|n \in \mathbb{N}, 1025 \le n \le 2003\right \}$.

Xét tập $C=A \cup B$. Dễ thấy $|C|=998$.

Các phần tử trong $B$ nằm giữa $2^{10}$ và $2^{11}$ nên không thể là luỹ thừa của $2$ và  $\forall x \neq y; x, y \in B$ thì $2^{11} < x+y < 2^{12}$ nên tổng $x+y$ cũng không thể là luỹ thừa của $2$.

Với $x \in A$ và $y \in B$ thì $1030 \le x+y \le 2047$ nên tổng $x+y$ cũng không là luỹ thừa của $2$.

Dễ kiểm tra các phần tử của $A$ không là luỹ thừa của $2$ và tổng của $2$ số bất kỳ trong số chúng cũng vậy.

$\Rightarrow \forall n \le 998$ ta chỉ cần lấy một tập con $n$ phần tử của $C$ thì tập này sẽ không có phần tử nào và cũng không có tổng của $2$ phần tử nào là luỹ thừa của $2$.

$\Rightarrow n \geq 999$.

 

 

 




#431546 Topic về tổ hợp, các bài toán về tổ hợp

Đã gửi bởi whatever2507 on 29-06-2013 - 11:39 trong Tổ hợp và rời rạc

 

Với bài này có lẽ ta phải chia bàn cờ ra 4 phần.
Cái đáp số hơi lằng nhằng, không biết có đúng không.

Đáp số của cả $2$ TH đều là $d \le 10\sqrt{2}$, dùng chung $1$ lập luận và chỉ hơi khác nhau cách đưa quân cờ thỏa mãn :).

 

Bài 4 (Tô màu - Nguồn: Đề thi HSG lớp 10 THPT chuyên KHTN). Cho một bảng ô vuông kích thước $m \times n$. Người ta muốn tô màu các ô vuông con của bảng, mỗi ô vuông con chỉ được tô bởi 1 trong 2 màu Xanh hoặc Đỏ theo quy tắc sau:

i) Tất cả các ô vuông con ở cạnh của bảng đều được tô màu Đỏ.
ii) Không có hình vuông kích thước $2 \times 2$ nào của bảng mà $4$ ô vuông con được tô cùng màu.
iii) Không có hình vuông kích thước $2 \times 2$ nào của bảng mà hai ô ở mỗi đường chéo đều được tô cùng màu.
Hỏi người ta có thể thực hiện cách tô màu như trên trong các trường hợp với bảng ô vuông kích thước:
$a) 2012 \times 2013?$
$b) 2012 \times 2014?$



#431525 Topic về tổ hợp, các bài toán về tổ hợp

Đã gửi bởi whatever2507 on 29-06-2013 - 10:15 trong Tổ hợp và rời rạc

Topic này có nên thêm cả phần đồ thị vào không nhỉ? :))

Giải bài 1. Số giao điểm: Xét một tứ giác bất kỳ lập thành từ $4$ đỉnh của đa giác, do đa giác lồi nên giao điểm 2 đường chéo của tứ giác này nằm trong đa giác và cũng là giao điểm 2 đường chéo của đa giác.

Ngược lại với $1$ giao điểm của $2$ đường chéo bất kỳ trong đa giác thì $2$ cặp đầu mút của $2$ đường chéo này lập thành $1$ tứ giác có $4$ đỉnh là $4$ đỉnh phân biệt của đa giác. Tóm lại ta lập được song ánh giữa số giao điểm và số tứ giác tạo bởi $4$ đỉnh phân biệt của đa giác.

$\Rightarrow$ Số giao điểm là $C^4_n$.

Số miền: Ta xuất phát từ đầu với $1$ miền (chính là $n$-giác) và lần lượt nối các đường chéo. Mỗi đường chéo chia đa giác thêm $1$ phần, và mỗi khi nó giao với đường chéo khác nó lại chia đa gíc thêm $1$ phần nữa.

Dễ tính được số đường chéo là: $C^2_n-n$.

$\Rightarrow$ Số miền là: $1+C^2_n-n+C^4_n$.

 

Bài 3 (Toán trò chơi-Nguồn: Tournament of the Towns). Trên bảng ô vuông $20$x$20$ mỗi ô có $1$ quân cờ. $A$ chọn một số thực $d$ và $B$ phải đưa mỗi quân cờ đi tới ô cách ô ban đầu nó đứng một khoảng cách ít nhất là $d$ (khoảng cách giữa $2$ ô được tính theo khoảng cách tâm của $2$ ô đó) và mỗi ô chỉ có thể có $1$ quân cờ. Hỏi với điều kiện gì của $d$ thì $B$ có thể thao tác thoả mãn điều kiện trên?

Hỏi tương tự với bảng $21$x$21$




#430054 Chứng minh rằng các vị đại sứ có thể ngồi xung quanh một cái bàn, mà trong đó...

Đã gửi bởi whatever2507 on 23-06-2013 - 20:40 trong Tổ hợp và rời rạc

Bài này có thể giải bằng đơn biến nhưng nhân thể đang học đồ thị mình giải kiểu đồ thị :):

Xét đồ thị $G=(V,E)$ với $\left \{ V \right \}=\left \{ A_i| 1 \leq i \leq 2n  \right \}$, mỗi đỉnh $A_i$ đại diện cho đại sứ $X_i \forall 1 \le i \le 2n$, $2$ đỉnh bất kỳ kề nhau khi và chỉ khi $2$ người mà chúng đại diện không phải là kẻ thù của nhau $\Rightarrow$ Mỗi đỉnh có bậc lớn hơn $n+1$ $\Rightarrow$ theo định lý Dirac, đồ thị tồn tại chu trình Hamilton.

WLOG, giả sử chu trình Hamilton đi theo thứ tự $A_1A_2...A_{2n}A_1$. Khi đó ta xếp các vị đại biểu lần lượt từ trái sang phải $X_1 \rightarrow X_2 \rightarrow...\rightarrow X_{2n} \rightarrow X_1$, khi đó đại sứ $X_i$ ngồi cạnh $X_{i-1}$ & $X_{i+1} (X_{2n+1}=X_1)$ mà theo lập luận trên đồ thị ta có $A_i$ kề $A_{i-1}$ & $A_{i+1}$ nên $X_{i-1}$ & $X_{i+1}$ không phải kẻ thù của $X_i$. Vậy ta có đpcm.

 




#424975 ${x_1} = 1;{x_2} = - 1;{x_{n + 2}...

Đã gửi bởi whatever2507 on 08-06-2013 - 01:17 trong Dãy số - Giới hạn

Tính vài giá trị đầu: $x_1=1, x_2=-1, x_3=\frac{3}{4}, x_4=\frac{5}{16}, x_5=\frac{-71}{256}, x_6=\frac{-5199}{65536}.$
Ta CMR: $\forall n \geq 4: |x_n| < \frac{1}{n-1} (*)$, từ đó suy ra $\lim_{n \to +\infty }x_n=0$

  • Ta thấy $(*)$ đúng với $n=4, n=5, n=6$.
  • Giả sử $(*)$ đúng $\forall 4 \leq k \leq n+1$.
  • Xét $k=n+2 (n \geq 5)$. Ta có:

$x_{n+2}=x_{n+1}^2-\frac{1}{2}x_n \Rightarrow |x_{n+2}| < x_{n+1}^2+\frac{1}{2}|x_n| < \frac{1}{n^2}+\frac{1}{2(n-1)}$.

Ta chỉ cần CMR: $\frac{1}{n^2}+\frac{1}{2(n-1)} < \frac{1}{n+1}$, khai triển ta có BĐT tương đương $n^3-5n^2+2 > 0 (1)$ mà do $n \geq 5$ nên BĐT $(1)$ đúng.

Vậy $(*)$ đúng $\forall n \geq 4$.

KL: $\lim_{n \to +\infty }x_n=0$.




#424834 Chứng minh rằng trong mỗi nhóm $9$ người, mà trong đó không tìm đượ...

Đã gửi bởi whatever2507 on 07-06-2013 - 18:03 trong Tổ hợp và rời rạc

Bài này bản chất là định lý Ramsey: $R(3,4)=9$ :))




#424574 CMR: $AD$ là đường thẳng Euler của $\Delta HB'C'...

Đã gửi bởi whatever2507 on 06-06-2013 - 19:10 trong Hình học

Mình post luôn bài toán khiến mình nghĩ ra kết quả trên :):
Cho $\bigtriangleup ABC$, đuờng thẳng qua $A$ song song với đường thẳng Euler của $\bigtriangleup ABC$ cắt $BC$ tại $E$. CMR: Đường thẳng Euler của $\bigtriangleup ACE$ song song với $AB$.




#424201 Chứng minh rằng hội toán học của thành phố đó không thể có ít hơn 60 thành viên.

Đã gửi bởi whatever2507 on 05-06-2013 - 19:05 trong Tổ hợp và rời rạc

Đặt $n$ là số thành viên của hội toán học. Xét đồ thị $G=(V,E)$ với $|V|=n$ đại diện cho $n$ người, $2$ đỉnh kề nhau khi và chỉ khi  $2$ người mà $2$ đỉnh này đại diện có gặp nhau tại một buổi họp.

Ban đầu đồ thị có $0$ cạnh, sau nỗi buổi họp thì đồ thị lại tăng thêm $C^2_{10}=45$ cạnh $\Rightarrow$ sau $40$ buổi họp đồ thị có $40.45=1800$ cạnh $(1)$.

Do không có 2 nhà toán học nào gặp nhau quá một lần nên đồ thị nhận được là đồ thị đơn $\Rightarrow$ Đồ thị nhận được có nhiều cạnh nhất khi nó là đồ thị đầy đủ, và khi đó số cạnh là $C^2_n= \frac{n(n-1)}{2} (2)$.

Từ $(1)$ và $(2)$ ta suy ra $\frac{n(n-1)}{2} \geq 1800$, giải bpt này ta có đpcm.




#424190 CMR: $AD$ là đường thẳng Euler của $\Delta HB'C'...

Đã gửi bởi whatever2507 on 05-06-2013 - 17:58 trong Hình học

Cho $\bigtriangleup ABC$ với 3 đường cao $AD, BE, CF$. $DE \cap AB \equiv C^{'}, DF \cap AC \equiv B^{'}. H$ là trực tâm tam giác $AB^{'}C^{'}$. CMR: $AD$ là đường thẳng Euler của tam giác $HB^{'}C^{'}$.

 

Nguồn: Tự chế, không biết có đụng hàng với ai không  :))




#422965 Chứng minh tồn tại tam giác có đỉnh, điểm và các cạnh đều được tô cùng một màu.

Đã gửi bởi whatever2507 on 01-06-2013 - 22:16 trong Tổ hợp và rời rạc

Ta CM bài toán bằng quy nạp.

  • Với $n=1$ ta có ngay đpcm.
  • Giả sử KL đúng đến $n$.
  • Xét đồ thị $(n+1)a_n+2$ đỉnh được tô bằng $n+1$ màu $x_1 \rightarrow x_{n+1}$
    .

Xét một đỉnh $A$ bất kỳ của đồ thị này, đỉnh $A$ được nối với $(n+1)a_n+1$ đỉnh khác bằng các cạnh được tô bằng $n+1$ màu. Theo nguyên lý Đirichlet tồn tại $a_n+1$ cạnh cùng màu, giả sử là màu $x_1$. Xét $a_n+1$ đỉnh nối với $A$ bằng màu $x_1$, nều tồn tại $2$ điểm $B, C$ trong chúng được nối với nhau bằng màu $x_1$ thì $\bigtriangleup ABC$ thỏa mãn ycbt. Nếu các cạnh nối $a_n+1$ đỉnh này chỉ được tô bằng $n$ màu $x_2 \rightarrow x_{n+1}$ thì theo gtqn ta cũng có $1$ tam giác có các cạnh cùng màu. Tóm lại KL đúng đến $n+1$ và ta có đpcm.




#422854 Bosnia Herzegovina Team Selection Test 2013

Đã gửi bởi whatever2507 on 01-06-2013 - 17:44 trong Thi HSG Quốc gia và Quốc tế

Làm luôn câu 3 cho hết ngày 1 :)

Câu 3. Đề bài chỉ ra khá rõ hướng làm là định lý Ramsey trong đồ thị, ta đưa về CM: Trong đồ thị đầy đủ $G=(V;E), |V|=C^n_{2n}$ được tô màu cạnh bằng 2 màu thì tồn tại đồ thị con đầy đủ $n+1$ cạnh cùng màu, tức là CM: $R(n+1, n+1) \leq C^n_{2n}$.

Trước tiên ta CM 2 bổ đề:

Bổ đề 1: $\forall s, t>2$ thì: $R(s,t) \leq R(s-1, t)+R(s, t-1)$.

CM: Đặt $N=R(s-1, t)+R(s, t-1)$, xét 1 cách tô màu xanh đỏ các cạnh của một đồ thị $K_N$ ($K_N$ ký hiệu đồ thị đầy đủ $N$ đỉnh). Gọi $A$ là một đỉnh bất kỳ. Trong $N-1$ cạnh kề A có không ít hơn $R(s-1, t)$ cạnh màu xanh hoặc $R(s, t-1)$ cạnh màu đỏ. WLOG giả sử có $R(s-1, t)$ cạnh màu xanh kề $A$. Các đầu mút khác $A$ của các cạnh này sẽ tạo thành $1$ đồ thị đầy đủ $R(s-1, t)$ đỉnh. Theo định lý Ramsey đồ thị này chứa một đồ thị con $K_{s-1}$ cạnh màu xanh hoặc $K_t$ cạnh màu đỏ. Trong TH đầu tiên, lấy thêm $A$ ta có đồ thị con $K_s$ với các cạnh màu xanh còn với TH2 ta có ngay đồ thị $K_t$ cạnh đỏ, từ đó ta có đpcm.

Bổ đề 2: $\forall s, t \geq 2, R(s,t) \leq C^{s-1}_{s+t-2}$.

CM: Bổ đề này dễ dàng CM được bằng quy nạp kết hợp bổ đề 1: $$R(s,t) \leq R(s-1,t)+R(s,t-1) \leq C^{s-2}_{s+t-3}+C^{s-1}_{s+t-3}=C^{s-1}_{s+t-2}$$ (đẳng thức Pascal).

Trở lại bài toán, áp dụng bổ đề 2 ta có $R(n+1, n+1) \leq C^{n+1-1}_{n+1+n+1-2}=C^n_{2n}$ (đpcm) :))




#422522 Cho tam giác $ABC$ có $O$ là tâm đường tròn ngoại tiếp và...

Đã gửi bởi whatever2507 on 31-05-2013 - 13:00 trong Hình học

Cả 2 lời giải đều thiếu 1 TH là $\angle BAC=120^o$ vẫn thỏa đề.

Đúng rồi với TH $\bigtriangleup ABC$ tù tại $A$ thì $AH=-acotA$ :))




#422299 Bosnia Herzegovina Team Selection Test 2013

Đã gửi bởi whatever2507 on 30-05-2013 - 18:49 trong Thi HSG Quốc gia và Quốc tế

bài này lập phương trình đặc trưng của dãy rồi tìm được công thức tổng quát thôi mà!

Bạn up lời giải lên đi, coi như 1 cách làm khác :)).

Chém luôn câu số cho nó nóng :)):
Câu 4. Dễ thấy rằng $p, q \neq 2, 3, 5$ và $p \neq q \Rightarrow \exists$ 1 số $\geq 11$ và 1 số $\geq 7$.

Ta có $pq|(30p-1)(30q-1) \Rightarrow pq|30(p+q)-1$. Đặt $30(p+q)-1=kpq (*) (k \in \mathbb{N^*})$

$\Rightarrow 30(\frac{1}{p}+\frac{1}{q})-\frac{1}{pq}=k$

$\Rightarrow k \leq 30(\frac{1}{7}+\frac{1}{11}) $

$\Rightarrow k \leq 7$.

Lại từ $(*)$ ta phân tích thành $(kp-30)(kq-30)=900-k$.

Nhận xét: Nếu $2|k$ thì $4|VT \Rightarrow 4|VP$

$\Rightarrow 4|k$

$\Rightarrow k=4$

$\Rightarrow (2p-15)(2q-15)=224$ nên không tồn tại $p, q$ thoả mãn.

Vậy k lẻ.

  • Nếu $k=3$ thì $9|VT \Rightarrow 9|VP \Rightarrow 9|897$ (vô lý).
  • Nếu $k=5$ thì $25|VT \Rightarrow 25|VP \Rightarrow 25|895$ (vô lý).
  • $k=1$, thay vào giải trực tiếp ta được $(p;q)=(59; 61); (61; 59); (929; 31); (31;929)$
  • $k=7$, giải được $(p;q)=(11;7); (7;11)$.

KL: Có 6 bộ $(p;q)$ thoả mãn là $(59;61); (61;59)$ và $(7; 11); (11;7)$ và $(929; 31); (31;929)$




#422288 Bosnia Herzegovina Team Selection Test 2013

Đã gửi bởi whatever2507 on 30-05-2013 - 18:17 trong Thi HSG Quốc gia và Quốc tế

Chém câu dãy số :)):

Câu 2. Lập dãy phụ $(b_n): b_0=b_1=1; b_{n+1}=4b_n-b_{n-1}$, Ta CMR quy nạp rằng $a_n=(b_n)^2 \forall n (*)$.

$(*)$ đúng với $n=0; n=1$, giả sử $(*)$ đúng $\forall 0 \leq k \leq n$. Ta CMR: $a_{n+1}=(b_{n+1})^2   (1)$.

Trước tiên ta viết lại dãy $(b_n)$ dưới dạng: $b_{n+1}=\frac{b_n^2-2}{b_{n-1}} \Rightarrow b_{n+1}b_{n-1}-b_n^2=2  (2)$.

Theo công thức xác định dãy $(a_n)$ ta có: $a_{n+1}=14b_n^2-b_{n-1}^2-4$.

Do đó $(1) \Leftrightarrow (4b_n-b_{n-1})^2=14b_n^2-b_{n-1}^2-4 \Leftrightarrow b_{n+1}b_{n-1}-b_n^2=2$ (đúng theo $(2)$).

Vậy mệnh đề $(*)$ đúng $\forall n$ và ta có đpcm.

 

 

 

 

 




#422186 Chứng minh rằng:$\varphi (a^n-1)$ chia hết cho $n$ v...

Đã gửi bởi whatever2507 on 30-05-2013 - 10:31 trong Số học

$ord_{a^n-1}(a)$ hiển nhiên bằng $n$, $gcd(a^n-1,a)=1$ nên $a^n-1|a^{\varphi(a^n-1)}-1$ suy ra $n|\varphi(a^n-1)$ :))




#421953 $x^{2}+7= 2^{k}$

Đã gửi bởi whatever2507 on 29-05-2013 - 17:49 trong Số học

Đây là phương trình Ramanujan-Nagell, lời giải của nó khá kinh khủng, có thể xem ở trang 50-51 ở file sau  :lol:

File gửi kèm