Đến nội dung

Hình ảnh

[Trường Xuân toán học miền nam 2016] Vietnam TST 2016 MOCK Test 2

tst mock tst 2016 trường xuân toán học

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

#1
Zaraki

Zaraki

    PQT

  • Phó Quản lý Toán Cao cấp
  • 4273 Bài viết

Tiểu trường Xuân Toán học miền Nam 2016

 

Vietnam TST 2016 MOCK Test 2

Ngày thi:26/02/2016

Thời gian làm bài: 240 phút

 

Bài 4. a) Cho bảng hình chữ nhật $m \times n$ ô với $m,n$ là các số nguyên dương cho trước. Trên mỗi ô của bảng ta viết $1$ trong các số $0,1,2$ sao cho tổng các số trên mỗi hàng, mỗi cột chia hết cho $3$. Hỏi có thể có nhiều nhất bao nhiêu số $1$?

b) Cho hình hộp chữ nhật $2015 \times 2016 \times 2017$ được tạo thành từ các hình lập phương đơn vị. Trong mỗi hình lập phương đơn vị, ta viết một trong các số $0,1,2$ sao cho tổng các số trong mỗi dài $1 \times 1 \times 1 \times 2017, 1 \times 2016 \times 1$ và $2015 \times 1 \times 1$ chia hết cho $3$. Hỏi có thể có nhiều nhất bao nhiêu số $1$?

 

Bài 5. Cho tam giác $ABC$ nội tiếp đường tròn $(O)$ bán kính $R$, ngoại tiếp đường tròn $(I)$ bán kính $r$ và có các đường trung tuyến là $AA_1,BB_1,CC_1$. Tiếp tuyến tại $B,C$ của đường tròn $(O)$ cắt nhau tại $S$ và giả sử $AS$ cắt $BC$ tại $A_2$. Các điểm $B_2,C_2$ được xác định tương tự. Chứng minh rằng $$\frac{AA_2}{AA_1}+ \frac{BB_2}{BB_1}+ \frac{CC_2}{CC_1} \ge 1+ \frac{4r}{R}.$$

 

Bài 6. Cho số nguyên dương $n$. Gọi $B^{n+1}$ là tập tất cả các xâu nhị phân độ dài $n$, tức là $$B^{n+1}= \left \{ a_na_{n-1} \cdots a_0 \mid a_i \in \{ 0,1 \} \forall i=0,1, \cdots , n \right \}.$$

Với mỗi xâu $a=a_na_{n-1} \cdots a_0$ thuộc $B^{n+1}$ ta gọi $s(a)=a_n+a_{n-1}+ \cdots +a_0 \pmod 2$ là bit kiểm tra của xâu $a$ và $v(a)=a_n2^n+a_{n-1}2^{n-1}+ \cdots + a_1 \cdot 2+a_0$ là giá trị của xâu $a$.

Gọi $B_0^{n+1}, B_1^{n+1}$ tương ứng là tập hợp tất cả các xâu nhị phân có độ dài $n+1$ có bit kiểm tra tương ứng là $0$ và $1$. Chứng minh rằng với mọi số nguyên dương $k,n$, ta có đẳng thức: $$\sum_{a \in B_0^{n+1}}(v(a))^k= \sum_{a \in B_1^{n+1}}(v(a))^k.$$

 

Nguồn: FB của thầy Trần Nam Dũng.


Bài viết đã được chỉnh sửa nội dung bởi Zaraki: 26-02-2016 - 14:47
Typo

Discovery is a child’s privilege. I mean the small child, the child who is not afraid to be wrong, to look silly, to not be serious, and to act differently from everyone else. He is also not afraid that the things he is interested in are in bad taste or turn out to be different from his expectations, from what they should be, or rather he is not afraid of what they actually are. He ignores the silent and flawless consensus that is part of the air we breathe – the consensus of all the people who are, or are reputed to be, reasonable.

 

Grothendieck, Récoltes et Semailles (“Crops and Seeds”). 


#2
hoanglong2k

hoanglong2k

    Trung úy

  • Điều hành viên THCS
  • 965 Bài viết

 Bài 5. 

 Gọi $A_3$ là giao điểm $AA_1$ với $(O)$

 Khi đó $AA_2$ là đường đối trung của tam giác $ABC$ nên $\Delta ABA_2\sim \Delta AA_3C\Rightarrow AA_2.AA_3=AB.AC$

 Mặt khác sử dụng đẳng thức Ptolemy ta có $A_1A.A_1A_3=A_1B.A_1C\Leftrightarrow AA_1(AA_3-AA_1)=\dfrac{BC^2}{4}\Rightarrow AA_1.AA_3=\dfrac{AB^2+AC^2}{2}$

 Từ đó suy ra $\dfrac{AA_2}{AA_1}=\dfrac{2AB.AC}{AB^2+AC^2}$

 Đặt $AB=c;BC=a;CA=b$ thì ta có $\dfrac{AA_2}{AA_1}=\dfrac{2bc}{b^2+c^2}$, tương tư cho các phân thức kia

 Mà theo công thức tính diện tích tam giác ta lại có $S=\dfrac{abc}{4R}=pr$

$\Rightarrow S^2=\dfrac{abcpr}{4R}\Rightarrow \dfrac{4r}{R}=\dfrac{16S^2}{abcp}=\dfrac{16p(p-a)(p-b)(p-c)}{abcp}=\dfrac{2(a+b-c)(b+c-a)(c+a-b)}{abc}$

 Vì thế nên ta chỉ cần chứng minh $\dfrac{2bc}{b^2+c^2}+\dfrac{2ca}{c^2+a^2}+\dfrac{2ab}{a^2+b^2}\geq 1+\dfrac{2(a+b-c)(b+c-a)(c+a-b)}{abc}$

 Bất đẳng thức tương đương với :

$\sum (b-c)^2\left ( \dfrac{b+c-a}{abc}-\dfrac{1}{b^2+c^2} \right )\geq 0\Leftrightarrow S_a(b-c)^2+S_b(c-a)^2+S_c(a-b)^2\geq 0$ trong đó $S_a=\dfrac{b+c-a}{abc}-\dfrac{1}{b^2+c^2}$, ...

 Giả sử $a\geq b\geq c$, khi đó dễ dàng chứng minh được $S_b\geq 0$ và $S_b+S_c\geq 0$

 Mặt khác, do $a,b,c$ là 3 cạnh của một tam giác nên ta cũng chứng minh $S_a+S_b\geq 0$

 Khi đó theo tiêu chuẩn SOS ta có điều cần chứng minh

 Dấu "=" xảy ra khi và chỉ khi $a=b=c$ hay $\Delta ABC$ là tam giác đều :)


Bài viết đã được chỉnh sửa nội dung bởi hoanglong2k: 27-02-2016 - 13:30


#3
canhhoang30011999

canhhoang30011999

    Thiếu úy

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

 

 Bài 5. 

 Gọi $A_3$ là giao điểm $AA_1$ với $(O)$

 Khi đó $AA_2$ là đường đối trung của tam giác $ABC$ nên $\Delta ABA_2\sim \Delta AA_3C\Rightarrow AA_2.AA_3=AB.AC$

 Mặt khác sử dụng đẳng thức Ptolemy ta có $A_1A.A_1A_3=A_1B.A_1C\Leftrightarrow AA_1(AA_3-AA_1)=\dfrac{BC^2}{4}\Rightarrow AA_1.AA_3=\dfrac{AB^2+AC^2}{2}$

 Từ đó suy ra $\dfrac{AA_2}{AA_1}=\dfrac{2AB.AC}{AB^2+AC^2}$

 Đặt $AB=c;BC=a;CA=b$ thì ta có $\dfrac{AA_2}{AA_1}=\dfrac{2bc}{b^2+c^2}$, tương tư cho các phân thức kia

 Mà theo công thức tính diện tích tam giác ta lại có $S=\dfrac{abc}{4R}=pr$

$\Rightarrow S^2=\dfrac{abcpr}{4R}\Rightarrow \dfrac{4r}{R}=\dfrac{16S^2}{abcp}=\dfrac{16p(p-a)(p-b)(p-c)}{abcp}=\dfrac{2(a+b-c)(b+c-a)(c+a-b)}{abc}$

 Vì thế nên ta chỉ cần chứng minh $\dfrac{2bc}{b^2+c^2}+\dfrac{2ca}{c^2+a^2}+\dfrac{2ab}{a^2+b^2}\geq 1+\dfrac{2(a+b-c)(b+c-a)(c+a-b)}{abc}$

 Đến đây sử dụng S.O.S hoặc $pqr$ là được

 Có gì tối em gõ nốt, giờ phải đi học cái đã :P

 

em giải nốt luôn đi chứ anh thấy sos thì ko ra còn pqr thì trâu quá



#4
Nguyen Dinh Hoang

Nguyen Dinh Hoang

    Hạ sĩ

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


Bài 5.

Gọi $A_3$ là giao điểm $AA_1$ với $(O)$

Khi đó $AA_2$ là đường đối trung của tam giác $ABC$ nên $\Delta ABA_2\sim \Delta AA_3C\Rightarrow AA_2.AA_3=AB.AC$

Mặt khác sử dụng đẳng thức Ptolemy ta có $A_1A.A_1A_3=A_1B.A_1C\Leftrightarrow AA_1(AA_3-AA_1)=\dfrac{BC^2}{4}\Rightarrow AA_1.AA_3=\dfrac{AB^2+AC^2}{2}$

Từ đó suy ra $\dfrac{AA_2}{AA_1}=\dfrac{2AB.AC}{AB^2+AC^2}$

Đặt $AB=c;BC=a;CA=b$ thì ta có $\dfrac{AA_2}{AA_1}=\dfrac{2bc}{b^2+c^2}$, tương tư cho các phân thức kia

Mà theo công thức tính diện tích tam giác ta lại có $S=\dfrac{abc}{4R}=pr$

$\Rightarrow S^2=\dfrac{abcpr}{4R}\Rightarrow \dfrac{4r}{R}=\dfrac{16S^2}{abcp}=\dfrac{16p(p-a)(p-b)(p-c)}{abcp}=\dfrac{2(a+b-c)(b+c-a)(c+a-b)}{abc}$

Vì thế nên ta chỉ cần chứng minh $\dfrac{2bc}{b^2+c^2}+\dfrac{2ca}{c^2+a^2}+\dfrac{2ab}{a^2+b^2}\geq 1+\dfrac{2(a+b-c)(b+c-a)(c+a-b)}{abc}$

Đến đây sử dụng S.O.S hoặc $pqr$ là được

Có gì tối em gõ nốt, giờ phải đi học cái đã :P

làm tiếp vẫn còn phức tạp lắm bạn giải đến cùng đi

#5
longatk08

longatk08

    Sĩ quan

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

Một dạng "chế phẩm" từ bài toán của Long đây, tư tưởng S.O.S rõ ràng dù vẫn hơi động tay, động chân tí:

 

https://artofproblem...4035_inequality


Bài viết đã được chỉnh sửa nội dung bởi longatk08: 26-02-2016 - 22:51


#6
Nguyenhuyen_AG

Nguyenhuyen_AG

    Trung úy

  • Thành viên nổi bật 2016
  • 945 Bài viết
Bài 5. Cho tam giác $ABC$ nội tiếp đường tròn $(O)$ bán kính $R$, ngoại tiếp đường tròn $(I)$ bán kính $r$ và có các đường trung tuyến là $AA_1,BB_1,CC_1$. Tiếp tuyến tại $B,C$ của đường tròn $(O)$ cắt nhau tại $S$ và giả sử $AS$ cắt $BC$ tại $A_2$. Các điểm $B_2,C_2$ được xác định tương tự. Chứng minh rằng $$\frac{AA_2}{AA_1}+ \frac{BB_2}{BB_1}+ \frac{CC_2}{CC_1} \ge 1+ \frac{4r}{R}.$$

 

Ta chỉ cần chứng minh

\[\dfrac{2bc}{b^2+c^2}+\dfrac{2ca}{c^2+a^2}+\dfrac{2ab}{a^2+b^2}\geq 1+\dfrac{2(a+b-c)(b+c-a)(c+a-b)}{abc},\]

hay là

\[\frac{(a+b)^2}{a^2+b^2}+\frac{(b+c)^2}{b^2+c^2}+\frac{(c+a)^2}{c^2+a^2} \geqslant 4+\frac{2(a+b-c)(b+c-a)(c+a-b)}{abc}.\]Áp dụng bất đẳng thức Cauchy-Schwarz, ta có\[\frac{(a+b)^2}{a^2+b^2}+\frac{(b+c)^2}{b^2+c^2}+\frac{(c+a)^2}{c^2+a^2} \geqslant  \frac{2(a+b+c)^2}{a^2+b^2+c^2}.\]Ta cần chỉ ra\[\frac{(a+b+c)^2}{a^2+b^2+c^2} \geqslant 2 + \frac{(a+b-c)(b+c-a)(c+a-b)}{abc},\]tương đương với\[(a+b+c)^2\geqslant \frac{(a^2+b^2+c^2)[2abc+(a+b-c)(b+c-a)(c+a-b)]}{abc}. \quad (1)\]Giả sử $b$ là số nằm giữa $a$ và $c.$ Theo bất đẳng thức AM-GM, ta thấy vế phải của $(1)$ sẽ không vượt quá\[\frac{1}{4}\left [ \frac{a^2+b^2+c^2}{b}+ \frac{2abc+(a+b-c)(b+c-a)(c+a-b)}{ca}\right ]^2.\]Như vậy ta cần chứng minh\[2(a+b+c) \geqslant \frac{a^2+b^2+c^2}{b}+ \frac{2abc+(a+b-c)(b+c-a)(c+a-b)}{ca},\]bất đẳng thức này có thể thu gọn thành\[\frac{(a-b)(b-c)(a^2-b^2+c^2)}{abc} \geqslant 0.\]Hiển nhiên đúng theo giả thiết của $b$ nên ta có điều phải chứng minh.

 

P/s. Câu này là anh ra đề. :)


Bài viết đã được chỉnh sửa nội dung bởi Nguyenhuyen_AG: 27-02-2016 - 14:50

Nguyen Van Huyen
Ho Chi Minh City University Of Transport

#7
canhhoang30011999

canhhoang30011999

    Thiếu úy

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

Ta chỉ cần chứng minh

\[\dfrac{2bc}{b^2+c^2}+\dfrac{2ca}{c^2+a^2}+\dfrac{2ab}{a^2+b^2}\geq 1+\dfrac{2(a+b-c)(b+c-a)(c+a-b)}{abc},\]

hay là

\[\frac{(a+b)^2}{a^2+b^2}+\frac{(b+c)^2}{b^2+c^2}+\frac{(c+a)^2}{c^2+a^2} \geqslant 4+\frac{2(a+b-c)(b+c-a)(c+a-b)}{abc}.\]Áp dụng bất đẳng thức Cauchy-Schwarz, ta có\[\frac{(a+b)^2}{a^2+b^2}+\frac{(b+c)^2}{b^2+c^2}+\frac{(c+a)^2}{c^2+a^2} \geqslant  \frac{2(a+b+c)^2}{a^2+b^2+c^2}.\]Ta cần chỉ ra\[\frac{(a+b+c)^2}{a^2+b^2+c^2} \geqslant 2 + \frac{(a+b-c)(b+c-a)(c+a-b)}{abc},\]tương đương với\[(a+b+c)^2\geqslant \frac{(a^2+b^2+c^2)[2abc+(a+b-c)(b+c-a)(c+a-b)]}{abc}. \quad (1)\]Giả sử $b$ là số nằm giữa $a$ và $c.$ Theo bất đẳng thức AM-GM, ta thấy vế phải của $(1)$ sẽ không vượt quá\[\frac{1}{4}\left [ \frac{a^2+b^2+c^2}{b}+ \frac{2abc+(a+b-c)(b+c-a)(c+a-b)}{ca}\right ]^2.\]Như vậy ta cần chứng minh\[2(a+b+c) \geqslant \frac{a^2+b^2+c^2}{b}+ \frac{2abc+(a+b-c)(b+c-a)(c+a-b)}{ca},\]bất đẳng thức này có thể thu gọn thành\[\frac{(a-b)(b-c)(a^2-b^2+c^2)}{abc} \geqslant 0.\]Hiển nhiên đúng theo giả thiết của $b$ nên ta có điều phải chứng minh.

 

P/s. Câu này là anh ra đề. :)

cho em xin hỏi kỹ thuật đánh giá ở trên có chuyên đề nào về nó không ạ



#8
Nguyenhuyen_AG

Nguyenhuyen_AG

    Trung úy

  • Thành viên nổi bật 2016
  • 945 Bài viết

cho em xin hỏi kỹ thuật đánh giá ở trên có chuyên đề nào về nó không ạ

 

Anh có viết một chuyên đề về kỹ thuật này nhưng chưa hoàn thiện. :)


Nguyen Van Huyen
Ho Chi Minh City University Of Transport

#9
Namichan

Namichan

    Binh nhì

  • Thành viên mới
  • 12 Bài viết

Anh có viết một chuyên đề về kỹ thuật này nhưng chưa hoàn thiện. :)

viết xong anh có thể share lên được không ạ  :icon6:  :icon6:  :wub:



#10
baopbc

baopbc

    Himura Kenshin

  • Thành viên nổi bật 2016
  • 410 Bài viết

Hình như câu 5 đã có trong một số tài liệu rồi thì phải! Trên diễn đàn cũng có một topic về bài này rồi nhưng chưa ai giải cả!

Em xin gửi lại link: http://diendantoanho...-geq-1dfrac4rr/

Ở trong ấy anh Bui Ba Anh gõ sai đề, là 1 chứ không phải 1/2



#11
nuoccam

nuoccam

    Thượng sĩ

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

Sao ko ai làm bài 4 vậy, post lên cho em xem với 



#12
Nguyenhuyen_AG

Nguyenhuyen_AG

    Trung úy

  • Thành viên nổi bật 2016
  • 945 Bài viết

Hình như câu 5 đã có trong một số tài liệu rồi thì phải! Trên diễn đàn cũng có một topic về bài này rồi nhưng chưa ai giải cả!

Em xin gửi lại link: http://diendantoanho...-geq-1dfrac4rr/

Ở trong ấy anh Bui Ba Anh gõ sai đề, là 1 chứ không phải 1/2

 

Câu này anh đố Bá Anh nhưng bạn ấy không giải ra nên thử đăng lên diễn đàn để mọi người thảo luận nhưng không nhận được phản hồi nào.


Nguyen Van Huyen
Ho Chi Minh City University Of Transport

#13
Karl Heinrich Marx

Karl Heinrich Marx

    Sĩ quan

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

Bài 4:

câu a.

Nếu cả $m$ và $n$ đều chia hết cho $3$ thì hiển nhiên là ta có nhiều nhất $mn$ số 1.

Giả sử có $m$ hàng và $n$ cột.

Ta có một vài nhận xét sau:

1) Nếu một trong 2 số chia hết cho 3 giả sử là $m$ thì bảng cần ít nhất là $n$ số khác 1 để thỏa mãn

Trường hợp này có thể dễ dàng đưa ra cấu hình thỏa mãn gồm 1 bảng toàn số 1 và 1 cột $m$ số khác 1 (số này là 0 hoặc 2 phụ thuộc vào số dư $n$ chia cho $3$)

2) Nếu 2 số cùng chia cho 3 có chung số dư khác 0. Giả sử $n \ge m$ thì rõ ràng với mỗi cột gồm $m$ ô mà $m$ không chia hết cho $3$ nên phải có ít nhất 1 ô khác 1. Vậy có ít nhất $n$ ô khác 1.

Đưa ra cấu hình thỏa mãn bằng cách chia hình chữ nhật này thành một hình $m$x$m$ và $(n-m)$x$m$. Ta điền cả bảng bằng số 1 ngoại trừ hàng cuối cùng và đường chéo của hình $m$x$m$. Như vậy sẽ có $n$ ô trống, dựa vào số dư của $m,n$ cho $3$ có thể điền vào các ô này thỏa mãn đề bài.

Vậy có trường hợp này có nhiều nhất $(m-1)n$ với $n \ge m$

Thực ra thì khi xây dựng cấu hình thỏa mãn bài toán, một cách tự nhiên ta sẽ nghĩ đến là điền tất cả các số đều là 1 trừ hàng cuối cùng và cột cuối cùng, sau đó tìm số thích hợp điền vào các ô này cho thỏa mãn. Ở trường hợp 1 thì dễ dàng tìm được kết quả, trường hợp 2 để tối ưu ta phải xây dựng một hình vuông $m$x$m$ để đưa về trường hợp 1. Tuy nhiên ta làm đc như vậy vì khi $m$ và $n$ cùng chia $3$ có chung số dư thì các số cần điền ở cuối hàng và cuối cột là như nhau, ta có thể dùng chung bằng cách ghép thành đường chéo hình vuông.

3) Trường hợp $m$ và $n$ chia cho $3$ khác số dư. 

Như mình nói ở trên thì sự "cần" để thỏa mãn đề bài giữa hàng và cột là khác nhau nên cần có đến $n+m-1$ ô để thỏa mãn. Tạm thời chưa biết giải thích thế nào cho hợp lí.

Đưa ra cấu hình thỏa mãn thì giả sử $m$ chia $3$ dư $2$ thì cho một cột gồm $m$ số $0$ đưa về bài toán với $n-1$ và $m$ lại đưa về trường hợp trên. Làm ngược lại nếu $n$ chia $3$ dư $2$.

 

Vế b có lẽ là áp dụng vế a, hoặc cũng có thể dùng thủ thuật chia thành khối lập phương như mình đã dùng chia hình vuông ở trên.

Bài 6:

Trước tiên là quy nạp theo $n$ để chứng minh với $k=1$.

Chú ý là tất cả các phần tử của $B_0^{n+1}$ thu được bằng cách lấy một phần tử của $B_{0}^n$ nhân 2 hoặc lấy một phần tử của $B_{1}^n$ nhân 2 cộng 1. Ngược lại một phần tử của $B_1^{n+1}$ thi được bằng cách lấy phần tử của $B_1^n$ nhân 2 hoặc lấy một phần tử của $B_0^n$ nhân 2 cộng 1. Điều này chứng tỏ tổng các phần tử của $B_0^{n+1}$ và $B_1^{n+1}$ là bằng nhau.

Như vậy với $k=1$ thì bài toán đúng với mọi $n$. Giờ lại chứng minh quy nạp theo $k$.

Đầu tiên đặt $A_0^n$ và $A_1^n$ là tập các chuỗi tận cùng bằng $0$ và $1$ trong $B_0^n$ còn $C_0^n$ và $C_1^n$  là tập các chuỗi tận cùng bằng $0$ và $1$ trong $B_1^n$.

Giả sử bài toán đúng đến $n$ với mọi và với mọi số $k$ bé hơn $t$.

Ta có

$$ \sum_{a \in B_0^{n+1}} (v(a))^t = \sum_{a \in A_0^{n+1}} (v(a))^t+\sum_{a \in A_1^{n+1}} (v(a))^t = \sum_{a \in B_0^n}2^t(v(a))^t+\sum_{a \in B_1^n} (2v(a)+1)^t$$

Tương tự thì:

$$ \sum_{a \in B_1^{n+1}} (v(a))^t = \sum_{a \in C_0^{n+1}} (v(a))^t+\sum_{a \in C_1^{n+1}} (v(a))^t = \sum_{a \in B_1^n}2^t(v(a))^t+\sum_{a \in B_0^n} (2v(a)+1)^t$$

Ta xét đa thức $P(x)= (2x+1)^t-2^t.x^t$ thì $P(x)$ là một đa thức bậc $t-1$.

Dễ thấy là ta đpcm tương đương với:

$$  \sum_{a \in B_0^{n}} P(v(a)) =  \sum_{a \in B_1^{n}} P(v(a))$$

Theo giả thiết quy nạp thì $ \sum_{a \in B_0^{n}} (v(a))^i =  \sum_{a \in B_1^{n}} (v(a))^i$ với mọi $i \le t-1$ nên đẳng thức trên là hiển nhiên với $degP \le t-1$.

 

 



#14
JUV

JUV

    Trung sĩ

  • Điều hành viên OLYMPIC
  • 138 Bài viết

Đào mộ !

Bài 4:

Nếu $m,n$ cùng chia hết cho $3$ thì đáp số là $mn$

Nếu $m$ chia hết cho $3$ còn $n$ thì không, đáp số là $m(n-1)$(Nếu có $m(n-1)+1$ số $1$ thì trong $m$ hàng sẽ có $1$ hàng chứa $n$ số $1$, tổng $n$ số đó không chia hết cho $3$)

Nếu $m \equiv n\not\equiv 0 \pmod{3}$ thì đáp số là $mn-max\left \{ m;n \right \}$, lập luận tương tự trường hợp trên.

Nếu $m \equiv n+1\equiv 2 \pmod{3}$, ta chứng minh sẽ có ít nhất $\frac{2}{3}(m+n)$ ô không chứa số $1$. Gọi các ô không chứa số $1$ là ô lạ, dễ thấy rằng không có ô lạ nào đứng một mình, tức là không có ô lạ nào khác đứng cùng hàng hoặc cột với nó (Nếu không thì tổng trên cột và hàng chứa ô lạ đó sẽ hơn kém nhau $1$ nên không thể cùng chia hết cho $3$). Ta sẽ tô màu các ô của bảng theo cách sau: Đầu tiên chọn $1$ ô lạ, tô màu tất cả các ô chưa được tô màu nằm cùng hàng và cột với ô đó, sau đó chọn $1$ ô lạ khác chưa được chọn và tiếp tục. Dễ thấy mỗi hàng và cột phải có ít nhất $1$ ô lạ nên rút cuộc tất cả các ô trên bảng đều được tô, hay $m+n$ hàng và cột sẽ được tô(một hàng hoặc cột được tô khi tất cả các ô trên nó được tô). Khi chọn $1$ ô lạ bất kì thì tô được thêm nhiều nhất $2$ đường ($1$ đường tức là $1$ hàng hoặc cột). Nếu sau khi chọn $1$ ô lạ ta tộ được $2$ đường chứa nó thì sẽ có $1$ ô lạ khác nằm cùng hàng hoặc cột với nó chưa được chọn (Nếu được chọn trước rồi thì sau khi chọn ô lạ kia, ta chỉ có thể tô thêm được $1$ đường qua nó). Vậy có cách chọn để cứ chọn $2$ ô lạ liên tiếp, ta tô thêm được nhiều nhất $3$ đường $\Rightarrow$ Số ô lạ ít nhất là $\frac{2}{3}(m+n)$. Vậy số ô có chứa số $1$ ít nhất là $mn-\frac{2}{3}(m+n)$. Lưu ý rằng nếu $max\left \{ m;n \right \}>2min\left \{ m;n \right \}$ thì $max\left \{ m;n \right \}>\frac{2}{3}(m+n)$, lập luận tương tự các tường hợp trên thì số số $1$ nhiều nhất là $mn-max\left \{ m;n;\frac{2}{3}(m+n) \right \}$. Dấu "=" xảy ra khi:

Với $max\left \{ m;n \right \}\leq 2min\left \{ m;n \right \}$(giả sử $n>m$), chọn $\frac{2n-m}{3}$ hàng, mỗi hàng điền $2$ số $0$ sao cho không có $2$ số $0$ nào cùng cột. Trong $\frac{2m-n}{3}$ cột không có số $0$, điền vào mỗi cột $2$ số $1$ sao cho không có $2$ số $1$ hoặc $2$ số $0$ và$1$ cùng hàng.

Nếu $n>2m$, từ $1$ bảng $m\times 2m$ được điền, ta chọn thêm $n-2m$ cột và điền vào mỗi cột đó số $0$ vào ô ở dưới cùng và số $1$ vào các ô còn lại


Bài viết đã được chỉnh sửa nội dung bởi JUV: 15-02-2017 - 20:18


#15
toanhoc2017

toanhoc2017

    Thiếu úy

  • Banned
  • 628 Bài viết

cho em xin hỏi kỹ thuật đánh giá ở trên có chuyên đề nào về nó không ạ

Kỹ thuật hay





Được gắn nhãn với một hoặc nhiều trong số những từ khóa sau: tst, mock tst, 2016, trường xuân toán học

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

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