Đến nội dung

Hình ảnh

[TOPIC] ÔN THI TỔ HỢP VÀ RỜI RẠC $\boxed{\text{THPT CHUYÊN}}$ lớp $10$ năm $2018-2019$


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

#41
MoMo123

MoMo123

    Sĩ quan

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

Bài 29: Cho một bảng kích thước $2n \times 2n$ ô vuông. Người ta đánh dấu vào 3n ô bất kì của bảng. CMR có thể chọn ra n hàng và n cột sao cho các ô được đánh dấu đầu nằm trên các hàng, các cột này

 

Ta chọn ra n hàng chứa số ô được đánh dấu nhiều nhất. Ta sẽ chứng minh trong n hàng còn lại, số ô được đánh dấu không quá n 

Giả sử ngược lại, tức là ở n hàng còn lại, có nhiều hơn n ô được đánh dấu.$\Rightarrow \exists$  có ít nhất 1 hàng trong n hàng không được chọn ra này có chứa nhiều hơn 2 ô được đánh dấu.$(1)$

Mặt khác, vì tổng số ô được đánh dấu trong các hàng được chọn ra $>n$ nên tổng số ô được đánh dấu $<2n$

$$\Rightarrow \exists$ 1 hàng trong các hàng được chọn ra chứa ít hơn 2 ô được đánh dấu. (2)

Từ $(1)(2)$ suy ra mâu thuẫn.

$\Rightarrow $ số ô được đánh dấu trong n hàng còn lại không vượt quá n ô.Nên, ta có thể chọn ra n cột chưa n ô này.

n cột và n hàng được chọn ra là cái ta cần tìm.

P/s: Bài 30 phức tạp kinh


Bài viết đã được chỉnh sửa nội dung bởi MoMo123: 27-05-2018 - 23:32


#42
MoMo123

MoMo123

    Sĩ quan

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

Tiếp tục nào

$\boxed{\text{Bài 31}}$ Số nguyên a được gọi là số ''đẹp'' nếu với mọi cách sắp xếp theo thứ tự tùy ý của 100 số 1,2,3,..,100 luôn tồn tại 10 số hạng liên tiếp có tổng lớn hơn hoặc bằng a. Tìm số đẹp lớn nhất.

$\boxed{\text{Bài 32}}$ Trên mặt phẳng cho 10 tam giác, trong đó bất kỳ 2 tam giác nào cũng có điểm chung. Chứng minh rằng tồn tại 1 đường thẳng giao với toàn bộ đa giác.

$\boxed{\text{Bài 33}}$ Cho bảng ô vuông 10x10 gồm 100 ô vuông kích thước 1x1. Điền vào mỗi ô vuông một số nguyên dương không vượt quá 10 sao cho 2 số được điền ở 2 ô vuông chung cạnh hoặc chung đỉnh nguyên tố cùng nhau. Chứng minh trong bảng ô vuông đã cho có một số xuất hiện ít nhất 17 lần


Bài viết đã được chỉnh sửa nội dung bởi MoMo123: 27-05-2018 - 23:04


#43
Korkot

Korkot

    Thượng sĩ

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

Tiếp tục nào

$\boxed{\text{Bài 31}}$ Số nguyên a được gọi là số ''đẹp'' nếu với mọi cách sắp xếp theo thứ tự tùy ý của 100 số 1,2,3,..,100 luôn tồn tại 10 số hạng liên tiếp có tổng lớn hơn hoặc bằng a. Tìm số đẹp lớn nhất.

$\boxed{\text{Bài 32}}$ Trên mặt phẳng cho 10 tam giác, trong đó bất kỳ 2 tam giác nào cũng có điểm chung. Chứng minh rằng tồn tại 1 đường thẳng giao với toàn bộ đa giác.

$\boxed{\text{Bài 33}}$ Cho bảng ô vuông 10x10 gồm 100 ô vuông kích thước 1x1. Điền vào mỗi ô vuông một số nguyên dương không vượt quá 10 sao cho 2 số được điền ở 2 ô vuông chung cạnh hoặc chung đỉnh nguyên tố cùng nhau. Chứng minh trong bảng ô vuông đã cho có một số xuất hiện ít nhất 17 lần

Xí bài dễ nhất: Bài 33:

Xét 1 hình vuông $2 \times 2$ thì theo gt, trong hình vuông này tồn tại nhiều nhất 1 số chẵn và ít nhất 2 số lẻ không chia hết cho 3.

Thật vậy, trong hình vuông $2 \times 2$ có một số chẵn thì tất cả các số còn lại lẻ, và nếu có một sớ chia hết cho 3 thì tất cả các số còn lại chia không hết cho 3 nên từ đó ta thấy mỗi ồ vuông $2 \times 2$ có 2 số lẻ chia không hết cho 3

Một hình vuông $10 \times 10$ có 25 ô $2 \times 2$ nên có 50 số lẻ ko chia hết cho 3.

Mà các số lẻ ko chia hết cho 3 là 1,5,7 nên theo nguyên lí Dirichlet, tồn tại 17 số giống nhau nên ta có đpcm


Bài viết đã được chỉnh sửa nội dung bởi Korkot: 30-05-2018 - 12:28

  Nếu bạn cứ tiếp tục ca thán về cùng một nỗi buồn, cùng một việc nhỏ nhặt, bạn sẽ mãi mãi chìm đắm trong thất bại và sống một  cuộc đời nhỏ bé. Hãy luôn nhớ rằng, ngay cả một ngày tồi tệ nhất cũng chỉ có 24 tiếng đồng hồ mà thôi.

                   :like  :like  :like  :like  :like  :like  :like  :like  :like  :like  :like  :like  :like  :like  :like  :like  :like  :like  :like  :like 


#44
Leuleudoraemon

Leuleudoraemon

    Trung sĩ

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

$\boxed{\text{Bài 32}}$ Trên mặt phẳng cho 10 tam giác, trong đó bất kỳ 2 tam giác nào cũng có điểm chung. Chứng minh rằng tồn tại 1 đường thẳng giao với toàn bộ đa giác.

Mình cũng xí bài dễ

vẽ $\widehat{xOy}=90^o$ sao cho tất cả 10 tam giác đều thuộc miền trong của góc. Mỗi tam giác ta chọn một đỉnh gần với Oy nhất. Từ đỉnh đó kẻ đường vuông góc với Ox. Trong 10 đường này chọn một đường cách xa Oy nhất . Giả sử đó là PQ đi qua tam giác PQR, PQ chia miền trong của góc xOy làm hai miền là I và II. Không có tam giác nào hoàn toàn thuộc 1 miền (do nếu 1 tam giác chỉ thuộc miền I thì không có điểm chung với tam giác PQR, còn nếu 1 tam giác thuộc miền II thì không được)

Vậy PQ là đường cần tìm



#45
BurakkuYokuro11

BurakkuYokuro11

    Thượng sĩ

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

Tiếp tục nào

$\boxed{\text{Bài 31}}$ Số nguyên a được gọi là số ''đẹp'' nếu với mọi cách sắp xếp theo thứ tự tùy ý của 100 số 1,2,3,..,100 luôn tồn tại 10 số hạng liên tiếp có tổng lớn hơn hoặc bằng a. Tìm số đẹp lớn nhất.

 

Mình xí bài cuối cùng :D

Tuyển sinh THPT chuyên KHTN , 2016 vòng 1  :ukliam2:

 

Giả sử x1 , x2, .... , x100 là một nhóm hoán vị tuỳ ý của các số 1,2,....,99,100.Ta chia thành 10 nhóm, mỗi nhóm gồm tổng 10 số hạng liên tiếp

S1=x1+x2+...+x10  ;.........................  ; S10 = x91 + ....+ x100 .

Ta có S1+S2+S3+...+S10 = 1+2+ ...+ 100 = 5050 nên có ít nhất 1 chỉ số $i$$i$ $\epsilon$ N , $1 \leq i \leq 10$ ) sao cho S$i$ $\geq 505$

Vậy a= 505 là 1 số đẹp. 
Ta xét 1 hoán vị đặc biệt 100, 1, 99, 2,., 51,50.
Khi đó tổng của 10 số hạng liên tiếp hoặc bằng 505 (Nếu số đầu tiên là lớn nhất) hoặc 500 (nếu số đầu tiên là nhỏ nhất).Suy ra, nếu a$> 505$ thì a không là số đẹp . Vậy max a = 505  :lol:


Bài viết đã được chỉnh sửa nội dung bởi BurakkuYokuro11: 28-05-2018 - 18:51

WangtaX

 


#46
BurakkuYokuro11

BurakkuYokuro11

    Thượng sĩ

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

Xin gửi TOPIC 1 số bài toán về  Tính Bất Biến trong Tổ Hợp và Rời Rạc  :D

 $\boxed{\text{Bài 34}}$ Người ta viết trên bảng dãy các STN liên tiếp từ 1 đến 100 .Thực hiện trò chơi : Tiến hành xoá a,b bất kì trong dãy , viết lại 1 số là $a^{3} + b^3$ .Thực hiện trò chơi đến khi trên bảng còn lại 1 số . Hỏi số đó có thể là 9876543212019 không ? 

 $\boxed{\text{Bài 35}}$ Trên bảng ghi 2018 số $\frac{1}{1}; \frac{1}{2} ; .... ; \frac{1}{2018}.$ Mỗi lần xoá đi 2 số bất kì , ta thay bằng số $z = \frac{xy}{x+y+1}$ và giữ nguyên các số còn lại .Sau 2017 lần thực hiện thì trên bảng còn lại một số.Tìm số còn lại đó.

$\boxed{\text{Bài 36}}$ Có bao nhiêu tập hợp con A của Tập hợp $\left \{ 1,2,3,.., 2018 \right \}$ thoả mãn ĐK A có ít nhất 2 phần tử và nếu x , y thuộc A (x>y) thì $\frac{y^2}{x-y}$ thuộc A.( Đã sửa ^^)

$\boxed{\text{Bài 37}}$  n là 1 số lẻ . Đầu tiên ta viết các số từ 1 đến 2n trên bảng.Sau đó chọn ra 2 số bất kì a,b và xoá chúng, thay bằng $\left | a-b \right |$ .CMR : Số cuối cùng là số lẻ .


Bài viết đã được chỉnh sửa nội dung bởi BurakkuYokuro11: 01-06-2018 - 21:41

WangtaX

 


#47
Korkot

Korkot

    Thượng sĩ

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

$\boxed{\text{Bài 37}}$  n là 1 số lẻ . Đầu tiên ta viết các số từ 1 đến 2n trên bảng.Sau đó chọn ra 2 số bất kì a,b và xoá chúng, thay bằng $\left | a-b \right |$ .CMR : Số cuối cùng là số lẻ .

Lời giải: 

Tổng của các số là: n(2n+1) là số lẻ. Như vậy, tổng của các số thay đổi hoặc $a-b-a-b=-2b$ hay $b-a-a-b=-2a$ tức tính chẵn lẻ của tổng ko đổi

Vậy sau mỗi bước tổng các số đều lẻ nên số cuối cùng lẻ

Bài 36 thiếu đk kìa

 

 


Bài viết đã được chỉnh sửa nội dung bởi Korkot: 29-05-2018 - 05:56

  Nếu bạn cứ tiếp tục ca thán về cùng một nỗi buồn, cùng một việc nhỏ nhặt, bạn sẽ mãi mãi chìm đắm trong thất bại và sống một  cuộc đời nhỏ bé. Hãy luôn nhớ rằng, ngay cả một ngày tồi tệ nhất cũng chỉ có 24 tiếng đồng hồ mà thôi.

                   :like  :like  :like  :like  :like  :like  :like  :like  :like  :like  :like  :like  :like  :like  :like  :like  :like  :like  :like  :like 


#48
MoMo123

MoMo123

    Sĩ quan

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

 

 $\boxed{\text{Bài 34}}$ Người ta viết trên bảng dãy các STN liên tiếp từ 1 đến 100 .Thực hiện trò chơi : Tiến hành xoá a,b bất kì trong dãy , viết lại 1 số là $a^{3} + b^3$ .Thực hiện trò chơi đến khi trên bảng còn lại 1 số . Hỏi số đó có thể là 9876543212019 không ? 

 $\boxed{\text{Bài 35}}$ Trên bảng ghi 2018 số $\frac{1}{1}; \frac{1}{2} ; .... ; \frac{1}{2018}.$ Mỗi lần xoá đi 2 số bất kì , ta thay bằng số $z = \frac{xy}{x+y+1}$ và giữ nguyên các số còn lại .Sau 2017 lần thực hiện thì trên bảng còn lại một số.Tìm số còn lại đó.

 

Xí bài dễ  :D

$\boxed{\text{Bài 34}}$ 

Ta có $$a^3 \equiv a(mod 3)$$

         $$b^3 \equiv b(mod3)$$

nên $$a^3+b^3\equiv a+b(mod 3)$$

Vì thế sau xóa và viết lại các số, số nhận được luôn có cùng số dư với tổng 2 số ban đầu. Vì tổng các số ban đầu không chia hết 3 nên số còn lại không thể chia hết 3. Mà $9876543212019 $(số gì đã dài :D)  chia hết 3. Nên số còn lại không thể là số $9876543212019.$

$\boxed{\text{Bài 36}}$ 

Nhận thấy $$z=\frac{1}{(\frac{1}{x}+1)(\frac{1}{y}+1)-1}$$ 

Nên số cuối cùng còn lại chính là $$A= \frac{1}{(\frac{1}{1}+1)(\frac{1}{2}+1)...(\frac{1}{2018}+1)} = \frac{1}{2019}$$


Bài viết đã được chỉnh sửa nội dung bởi MoMo123: 29-05-2018 - 11:23


#49
MoMo123

MoMo123

    Sĩ quan

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

$\boxed{\text{Bài 38}}$ Cho $A=\left \{ 1;2;3;...;100 \right \}$

Chứng minh rằng với mỗi tập con gồm $48$ phần tử từ tập A luôn tồn tại 2 phần tử thuộc tập con đó có tổng chia hết 11

$\boxed{\text{Bài 39}}$Cho A là tập hợp gồm các số tự nhiên có phần tử nhỏ nhất là 1 và phần tử lớn nhất là 100. Tìm số phần tử nhỏ nhất của A sao cho với mọi $x\in A, x\neq 1$ luôn tồn tại 2 số $a,b$ sao cho $x=a+b$

$\boxed{\text{Bài 40}}$ Một bát giác lồi có các góc bằng nhau, độ dài các cạnh là số nguyên. Chứng minh các cạnh đối của bát giác bằng nhau


Bài viết đã được chỉnh sửa nội dung bởi MoMo123: 30-05-2018 - 11:01


#50
Le Hoang Anh Tuan

Le Hoang Anh Tuan

    Binh nhất

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

 

$\boxed{\text{Bài 39}}$Cho A là tập hợp gồm các số tự nhiên có phần tử nhỏ nhất là 1 và phần tử lớn nhất là 100. Tìm số phần tử nhỏ nhất của A sao cho với mọi $x\in A, x\neq 1$ luôn tồn tại 2 số $a,b$ sao cho $x=a+b$

 

Giả sử A là một tập con cả tập các số tự nhiên N. Tập A có phần tử nhỏ nhất là 1, phần tử lớn nhất là 100 và mỗi x thuộc A (x khác 1) luôn tồn tại hai số a; b cũng thuộc A sao cho x=a+b (a có thể bằng b). Hãy tìm 1 tập A có số phần tử nhỏ nhất. 
Bài giải:
Xét tập gồm 1, A2,...,An-1, 100
+)Nhận xét:
-A2 chắc chắn sẽ bằng 2 vì A2 chỉ có thể được tính bởi những số nhỏ hơn A2, mà trong tập chỉ có A1 nên A2 =2
-Tương tự A3 sẽ bằng 3 hoặc 4
-Để A có số phần tử ít nhất thì ta cần chọn ra các số có thứ tự tăng với vị trí ở mức cao nên ta sẽ chọn An-1=2An-2, nếu mà An-1<2An-2 thì ta sẽ chọn được nhiều phần tử hơn hoặc bằng so với dự kiến nên ta sẽ chọn An-1=2An-2
-Tiếp tục như vậy cho đến khi 2An-1>100 ta sẽ nhận được A7=64, giờ nhiệm vụ của ta là tìm 1 số trung gian giữa 64 và 100 sao cho biểu diễn được dưới dạng A100=64+Ap+Aq nên Ap+Aq=36=32+4=A6+A3
Do đó ta tìm được A gồm ít nhất là 9 tập con 1;2;4;8;16;32;36;64;100
Giả sử có số tập con nhỏ hơn 9 (NHỎ hơn not bằng)
Thì A3<=4, A4<=8, A5<=16, A6<=32, A7<=64. Mà A6+A7 là giá trị lớn nhất, A6+A7<=96<100 nên đó là điều không thể



#51
Le Hoang Anh Tuan

Le Hoang Anh Tuan

    Binh nhất

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

$\boxed{\text{Bài 38}}$ Cho $A=\left \{ 1;2;3;...;100 \right \}$

Chứng minh rằng với mỗi tập con gồm $48$ phần tử từ tập A luôn tồn tại 2 phần tử thuộc tập con đó có tổng chia hết 11

 

Nhận xét:

Từ 1 đến 100 có:

9 số chia 11 dư 0

10 số chia 11 dư 1

9 số chia 11 dư 2

9 số chia 11 dư 3

9 số chia 11 dư 4

9 số chia 11 dư 5

9 số chia 11 dư 6

9 số chia 11 dư 7

9 số chia 11 dư 8

9 số chia 11 dư 9

9 số chia 11 dư 10

Do đó theo nguyên lý di rich lê tồn tại ít nhất 6 loại số dư khi chia cho 11 được chọn từ 48 số (Do 48>10+9+9+9+9)

Chia 0,1,2,3,...10 thành các tập (0;0),(1;10);(2;9);(3;8);(4;7);(5;6), do có 6 loại số dư nên

TH1: Có 1 số chia 11 dư 0, thì còn 47 số mà 47>10+9+9+9+9 nên vẫn còn 6 loại số dư, xét 5 tập còn lại dễ dàng nhận được 1 nhóm

TH2: không có số nào chia hết cho 11: Tương tự



#52
Korkot

Korkot

    Thượng sĩ

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

$\boxed{\text{Bài 40}}$ Một bát giác lồi có các góc bằng nhau, độ dài các cạnh là số nguyên. Chứng minh các cạnh đối của bát giác bằng nhau

Bạn nhớ sửa đề nhé.

Gọi bát giác đã cho là ABCDEFGH. Vì tám góc của tứ giác bằng nhau nên  số đo mỗi góc là :$\frac{(8-2)180}{8}=135$

AB cắt CD tại I, BC cắt DE tại J, DE cắt GF tại K, AH cắt GF tại L,AH cắt BC tại M,EF cắt CD tại N, HG cắt AB tại P, HG cắt EF tại O

Tam giác IBC có $\angle{IBC}=\angle{ICB}=45$ nên tam giác IBC vuông cân có góc I vuông.

Cmtt có các góc N,O,P vuông nên tg INOP là HCN IN=PO và ON=PI.

Tương tự ta có JK=ML và MJ=LK.

Có: $MJ= \frac{AB}{\sqrt{2}}+\frac{CD}{\sqrt{2}}+CB$

Tương tự có $KL=\frac{EF}{\sqrt{2}}+\frac{HG}{\sqrt{2}} +GF$

Mà KL=MJ nên $\frac{AB}{\sqrt{2}}+\frac{CD}{\sqrt{2}}+CB-\frac{EF}{\sqrt{2}}-\frac{HG}{\sqrt{2}} -GF=0$ 

nên $BC-GF=\frac{EF+HG-AB-CD}{\sqrt{2}}$

Vì BC,CF,EF,HG,AB,CD nguyên mà $\sqrt{2}$ vô tỉ nên điều trên xảy ra khi và chỉ khi BC=GF

Cmtt rồi suy ra các cạnh đối của bát giác bằng nhau

@MoMo123: nhầm :))

Hình gửi kèm

  • geogebra-export.png

Bài viết đã được chỉnh sửa nội dung bởi Korkot: 01-06-2018 - 22:18

  Nếu bạn cứ tiếp tục ca thán về cùng một nỗi buồn, cùng một việc nhỏ nhặt, bạn sẽ mãi mãi chìm đắm trong thất bại và sống một  cuộc đời nhỏ bé. Hãy luôn nhớ rằng, ngay cả một ngày tồi tệ nhất cũng chỉ có 24 tiếng đồng hồ mà thôi.

                   :like  :like  :like  :like  :like  :like  :like  :like  :like  :like  :like  :like  :like  :like  :like  :like  :like  :like  :like  :like 


#53
Le Hoang Anh Tuan

Le Hoang Anh Tuan

    Binh nhất

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

Bài 30: Một dãy các con số 0 và 1 có độ dài 32 được gọi là một xâu.Giá trị của 1 xâu là số các số 1 trong xâu ấy.Ta kí hiệu các xâu A,B,C như sau: 

$A=(a_{1};...;a_{32}); B=(b_{1};...;b_{32}); C=(c_{1};...;c_{32})$

Một máy tính có thể thực hiện hai phép biến đổi sau:

Phép dịch chuyển các phần tử của A đi k vị trí: $(a_{1};...;a_{32}) \Rightarrow (a_{k};...;a_{32};a_{1};...;a_{k-1})$

Phép so sánh hai xâu A và B để được xâu mới C theo quy tắc A&B $\Rightarrow$ C với $c_{i}=1$ nếu $a_{1}=b_{i}$ và $c_{i}=0$ nếu $a_{i} \neq b_{i}$ 

Cho xâu A là một xâu có giá trị bằng 16 và xâu B là một xâu tùy ý. CMR: bằng cách dịch chuyển A đi k vị trí (thích hợp) và so sánh kết quả với B, ta được xâu C có giá trị không nhỏ hơn 16.

* Nhận xét:

Giả sử tồn tại 1 cách sắp xếp sao cho giá trị của C nhỏ hơn 16, thì dễ thấy sau khi di chuyển A thêm 16 đơn vị (Tức là Ak->Ak+1) thì ta sẽ dễ dàng có được C lớn hơn 16


Bài viết đã được chỉnh sửa nội dung bởi Le Hoang Anh Tuan: 05-06-2018 - 16:22


#54
Le Hoang Anh Tuan

Le Hoang Anh Tuan

    Binh nhất

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

Bài 41: Chứng minh rằng 1 đa giác có diện tích bằng 24 thì bao giờ cũng vẽ được trong đa giác 1 tam giác có diện tích không nhỏ hơn 9



#55
MoMo123

MoMo123

    Sĩ quan

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

Hey everybody, I'm back :D . Như chúng ta đã biết, các kì thi chuyên đã hoàn thành xong gần hết và hệ thống ôn chuyên đã đóng lại. Thật là vui khi có thể cùng nhau thảo luận về các bài Toán hay cũng như tranh luận chúng. Mặc dù rất tiếc nhưng để ngăn chặn tình trạng spam, mình vẫn phải thông báo rằng mình sẽ khóa topic tại thời điểm này. Chúc các bạn một mùa hè bổ ích, chúng ta sẽ gặp lại nhau trong topic ôn hè sắp tới :D (gần lộ rồi :D ).

                                             $$-MoMo123-$$






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

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