Đến nội dung

Hình ảnh

TRƯỜNG HÈ TOÁN HỌC MIỀN BẮC 2016

inex tohop truonghe 2016

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

#1
ineX

ineX

    Sĩ quan

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

TRƯỜNG HÈ TOÁN HỌC MIỀN BẮC 2016

Nguồn: Thầy Trần Mạnh Sang- THPT Chuyên Lê Hồng Phong

 

Bài 1: 

Cho 2016 tập hợp, mỗi tập có 45 phần tử, hai tập bất kì có đúng một phần tử chung. Chứng minh rằng tồn tại 1 phần tử thuộc tất cả các tập.

 

Bài 2:

Cho tập $X$ hữu hạn phần tử. Các tập $A_{1},A_{2},...A_{50}$ là các tập con của $X$, mỗi tập có nhiều hơn một nửa số phần tử của $X$

Chứng minh: 

a, Tồn tại phần tử $a$ thuộc ít nhất 26 tập con đã cho.

b, Tồn tại $A\subset X$ thỏa mãn $\left | A \right |\leq 5$ mà $A\cap A_{i}\neq \oslash (i=\overline{1,50})$

 

Bài 3: Có bao nhiêu số nguyên dương không vượt quá 2016 thỏa mãn số đó chia hết cho 3 hoặc 4 nhưng không chia hết cho 5.

 

Bài 4: Cho S= \left \{ 1,2,...,2014 \right \} 

Cần phải bỏ đi ít nhất bao nhiêu phần tử của $S$ để tập còn lại thỏa mãn không phần tử nào bằng tích hai phần tử khác.

 

Bài 5: Tìm tất cả các tập hữu hạn $A\subset \mathbb{N}$  và $B\subset \mathbb{N}$ thỏa mãn $A\subset \mathbb{B}$ và $\sum x_{b}=\sum x_{a}^{2}$

 

Bài 6: Cho tập $S$ thỏa mãn 

+> Mỗi phần tử của $S$ là một dãy có 15 kí tự, chỉ sử dụng $a,b$

+> Hai phần tử trong $S$ được gọi là khác nhau nếu chúng khác nhau ở ít nhất ba phần tử 

CMR: $\left |S  \right |\leq 2^{11}$

 

Bài 7: Cho tập $S$ có 2008 phần tử và $S_{1},S_{2},...S_{50}$ là tập con của $S$ thỏa mãn

+> $\left | S_{1} \right |=100 (i=\overline{1,50})$

+> $S_{1}\cup S_{2}\cup ....\cup S_{i}=S$

CMR: tập $S_{i}, S_{j}$ $i$ khác $j$ thỏa $\left | S_{1}\cap S_{j} \right |\leq 3$

 

Bài 8: Cho $n,k\in N$ và $S=\left \{ 1,2,...,n \right \}$ 

$A_{1},A_{2},.....A_{k}$ là các tập con của $S$ thỏa:

+> $\left | A_{i} \right |\geq \frac{n}{2}\left ( i=\overline{1,k} \right )$

+> $\left | A_{i}\cap A_{j} \right |\leq \frac{n}{4}(i\neq j)$

CMR: $\left | A_{1}\cup A_{2}....\cup A_{k} \right |\geq \frac{k}{k+1}$

 

Bài 9: Cho số tự nhiên dương $n$ nhỏ hơn $2014$ 

Tập $A=\left \{ a_{1},a_{2},...,a_{n} \right \}$ là tập con của $S= \left \{ 1,2,3,...,2014 \right \}$ thỏa nếu $a_{i}\neq a_{j}\leq 2014(i\leq i\leq j\leq n)$ thì $a_{i}+a_{j}\in A$

Chứng minh: $\frac{a_{1}+a_{2}+.....+a^{n}}{n}\geq \frac{2015}{2}$

 

Bài 10: Cho $S$ có 2016 phần tử. Tìm số bộ sắp thứ tự $(S_{1},S_{2},....,S_{n})$ với $S_{i}$ là tập con của $S$ thỏa $S_{1}\cap S_{2}\cap S_{3}\cap ....S_{2015}\neq \oslash $

 

Bài 11: Cho $S$ là tập các số nguyên dương nhỏ hơn $15$ thỏa không có hai tập con rời nhau của $S$ có tổng các phần tử bằng nhau. 

a, Chứng minh: số phần tử của $S$ không quá 5

b, Tìm tổng lớn nhất của số các phần tử của $S$

 

Bài 12: Cho $S\subset A= \left \{ 1,2,3,...n \right \}$n với $n$ nguyên dương. Tạo ra tập mới theo các luật sau: 

+> Nếu $1\notin S$ thì thêm $1$ vào $S$

+> Nếu $n\in S$ thì bỏ $n$

+> Với $1\leq t< n,t\in S,t+1\notin S$ thì bỏ $t$ thêm $t+1$

Ta bắt đầu từ tập rỗng.

Chứng minh $n= 2^{m}=1$ với m nguyên dương.

 

Bài 13: Cho các số nguyên dương $m,n$ không nhỏ hơn 2 thảo $S$ là tập có $n$ phần tử. $A_{1},A_{2},...,A_{m}$ là các tập con của $S$ mà mỗi tập có ít nhất 2 phần tử và thỏa mãn nếu $A_{i}\cap A_{j}\neq \oslash$, $A_{i}\cap A_{k}\neq \oslash$, $A_{j}\cap A_{k}\neq \oslash$ thì $A_{i}\cap A_{j}\cap A_{k}\neq \oslash$

Chứng minh: $m\leq 2^{n-1}-1$

 

Bài 14: Có tồn tại hay không một tập có 2010 số nguyên dương thỏa mãn nếu bỏ bất kỳ một phần tử nào của tập này thì tập còn lại có thể chia thành hai tập mà tổng các phần tử trong mỗi tập này bằng nhau?

 

P/s: Chuyên đề này được thầy hoàn thành trong 6 giờ làm việc, và đây là những bài đã giải quyết xong trên lớp, mình gõ lên để cho các bạn không có điều kiện tham gia trường hè giải thử. Các bài tập ở đây về độ khó khá đa dạng, từ khá dễ đến khó, được thầy sưu tầm lại, minh đã xin phép thầy để đăng lên đây.

Mong các bạn ở trường hè các miền khác có thể chia sẻ các bài tập của các bạn để có thể trao đổi!

Mong các bạn tham gia giải quyết hết các bài tập trên.


Bài viết đã được chỉnh sửa nội dung bởi ineX: 19-07-2016 - 18:28

"Tôi sinh ra là để thay đổi thế giới chứ không phải để thế giới thay đổi tôi" - Juliel

 

3cf67218ea144a6eb6caf571068071ff.1.gif


#2
Zaraki

Zaraki

    PQT

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

Bài 8: Cho $n,k\in N$ và $S=\left \{ 1,2,...,n \right \}$ 

$A_{1},A_{2},.....A_{k}$ là các tập con của $S$ thỏa:

+> $\left | A_{i} \right |\geq \frac{n}{2}\left ( i=\overline{1,k} \right )$

+> $\left | A_{i}\cap A_{j} \right |\leq \frac{n}{4}(i\neq j)$

CMR: $\left | A_{1}\cup A_{2}....\cup A_{k} \right |\geq \frac{k}{k+1}$

Hình như bài này mình nghĩ nên là $\ge \frac{kn}{k+1}$.


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”). 


#3
Zaraki

Zaraki

    PQT

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

Bài 2:

Cho tập $X$ hữu hạn phần tử. Các tập $A_{1},A_{2},...A_{50}$ là các tập con của $X$, mỗi tập có nhiều hơn một nửa số phần tử của $X$

Chứng minh: 

a, Tồn tại phần tử $a$ thuộc ít nhất 26 tập con đã cho.

b, Tồn tại $A\subset X$ thỏa mãn $\left | A \right |\leq 5$ mà $A\cap A_{i}\neq \oslash (i=\overline{1,50})$

Xin mở màn trước. :D

 

Lời giải. a) Giả sử tập $X$ có $k$ phần tử $a_1,a_2, \cdots, a_k$, và kí hiệu $s(a_i)$ là số các tập con $A_i \; (1 \le i \le 50)$ mà $a_i \in A_i$. Khi đó ta sẽ có $$\sum_{i=1}^ks(a_i)= \sum_{j=1}^{50} \left | A_i \right |.$$

Để ý rằng $\left| A_i \right| > \frac{k}{2}$ nên $$k \cdot  \text{max}  \{ s(a_1),s(a_2), \cdots , s(a_k) \}=ks(a_l)> \sum_{i=1}^{k}s(a_i) = \sum_{j=1}^{50} \left | A_i \right | > 25k,$$ suy ra $s(a_l) \ge 26$.

 

b) Do tồn tại $a_l$ như a nên ta chỉ cần xét $24$ tập còn lại, giả sử là $A_1,A_2, \cdots , A_{24}$. Lập luận tương tự ta tìm được tồn tại $a_i \ne a_l$ sao cho $a_i$ thuộc ít nhất $13$ tập trong $24$ tập trên. Xét $11$ tập còn lại. Khi đó tồn tại $a_j$ thuộc ít nhất $6$ trong $11$ tập. Xét $5$ tập còn lại thì tồn tại $a_h$ thuộc ít nhất $3$ trong $5$ tập. Xét hai tập còn lại thì luôn tồn tại $a_m$ thuộc cả hai tập này.

Khi đó ta chọn $A= \{ a_l,a_i,a_j,a_h,a_m \}$.


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

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”). 


#4
Tran Quoc Khang

Tran Quoc Khang

    Binh nhất

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

Bài 1:

Xét tập A trong số 2016 tập đã cho, tập A giao với 2015 tập còn lại nên tồn tại $a\in A$ là phần tử chung của không ít hơn $\left [ \frac{2015}{45} \right ]+1=45$ tập còn lại.

Vậy a thuộc các tập $A,A_{1},A_{2},...,A_{45}$ và trong 46 tập này không có hai tập nào có phần tử chung khác a.

Bây giờ ta chứng minh a thuộc tập B bất kì trong 2016 tập đã cho.

Thật vậy, nếu $a\notin B$ thì B có với mỗi tập  $A,A_{1},A_{2},...,A_{45}$ một phần tử chung khác a, suy ra B có không ít hơn 46 phần tử. Mâu thuẫn. Như vậy ta có điều phải chứng minh.



#5
JUV

JUV

    Trung sĩ

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

Bài 14: 

Dễ chứng minh rằng không có $2$ số nào khác tính chẵn lẻ (Nếu không thì sẽ bỏ được $1$ số sao cho tổng $2009$ số còn lại lẻ). Đương nhiên tất cả các số không thể đều lẻ nên tất cả các số đều chẵn. Chia mỗi số cho $2$ ta được $2010$ số mới thỏa mãn đề bài. Đến đây dùng nguyên lí cực hạn dễ thấy điều vô lí



#6
Zaraki

Zaraki

    PQT

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

Bài 4: Cho S= $\left \{ 1,2,...,2014 \right \}$. 

Cần phải bỏ đi ít nhất bao nhiêu phần tử của $S$ để tập còn lại thỏa mãn không phần tử nào bằng tích hai phần tử khác.

Tổng quát hơn với tập $S= \{ 1,2, \cdots , n \}$, cần phải bỏ đi ít nhất $a-1$ phần tử với $a$ là số nguyên dương thoả mãn $a(a+1) \le n<(a+1)(a+2)$ và $n \ge 2$. Tập các số bỏ đi sẽ là $\{ 2,3, \cdots , a \}$.

 

Lời giải. Kí hiệu $s(n)$ là số các phần tử cần phải bỏ đi ít nhất. Luôn tồn tại $a$ thoả $a(a+1) \le n<(a+1)(a+2)$.

 

Trong khoảng $[a(a+1),(a+1)(a+2))$ thì $a-1$ số $2(2a-1),3(2a-2), \cdots , a(a+1)$ nằm trong khoảng này. Dễ thấy rằng các số này phân biệt và là tích của hai số phân biệt. Do đó với mỗi số $i(2a-i+1)$ với $2 \le i \le a$ thì ta có được một bộ ba $\{ i,2a-i+1,i(2a-i+1) \}$. Cho nên, ta cần loại ít nhất một phần tử trong mỗi bộ để tập còn lại thoả mãn đề bài. Ta suy ra $s(n) \ge a-1$.

 

Ta hoàn toàn có thể đạt được $s(n)=a-1$ nếu ta loại đi $2,3, \cdots , a$.

 

Vậy, bài toán được chứng minh.  $\square$

 

Với $44 \cdot 45<n=2014<45 \cdot 46$ nên $s(2014)=43$.

 

EDIT: Lời giải trước của mình chưa chặt chẽ nên mình viết lại. 


Bài viết đã được chỉnh sửa nội dung bởi Zaraki: 20-07-2016 - 16:27

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”). 


#7
Boruto

Boruto

    Binh nhất

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

Bạn Zaraki giải thích rõ hơn bài 2 dc k bạn , mình k hiêu cho lắm



#8
Zaraki

Zaraki

    PQT

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

Bạn Zaraki giải thích rõ hơn bài 2 dc k bạn , mình k hiêu cho lắm

Bạn cần giải thích chỗ nào vậy?


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”). 


#9
bangbang1412

bangbang1412

    Độc cô cầu bại

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

Bài 9 : Phải sửa thành với mọi $i,j$ thì $a_{i}+a_{j}....$ nhé bạn nếu không không được trong trường hợp $n$ lẻ . 

Ta ghép tất cả các cặp $a_{k}+a_{n+1-k}$ lại và chứng minh mỗi tổng này $\geq 2015$ . Giả sử ngược lại rằng tồn tại $k$ mà $a_{k}+a_{n+1-k}\leq 2014$ . Sắp xếp lại bộ này $a_{1}\leq a_{2} \leq .... a_{k} \leq .... a_{n}$ như vậy tất cả các số $a_{i}+a_{n+1-k}$ với $1\leq i \leq k$ . Như vậy có tổng cộng $k$ số lớn hơn $a_{n+1-k}$ cùng thuộc tập này . Nhưng theo cách giả có nhiều nhất $n-(n+1-k)=k-1$ số . Vô lý vậy ghép $\frac{n}{2}$ lại có đpcm . 

Bài 10 : Gọi tổng các phần tử của một tập là $sum(A)$ . Dễ thấy nếu một tập con của một tập " tốt " thỏa mãn đề bài thì nó cũng phải " tốt " . Giờ ta sẽ giả sử có một tập " tốt " gồm  $6$ phần tử . Số các $sum(A)$ mà $|A| \leq 4$ là $C_{6}^{1}+C_{6}^{2}+C_{6}^{3}+C_{6}^{0}+C_{6}^{4}=6+15+20+1+15=56$ , nhưng mỗi tập con này tổng không vượt quá $15+14+13+12=54$ nên tồn tại hai $sum$ bằng nhau , bỏ phần tử chung của hai tập này ta có đpcm . Một tập con có $5$ phần tử thỏa mãn là $15,14,13,11,8$ . Ta sẽ chứng minh rằng max của các tập con năm phần tử là $61$ . Xét tập con  " tốt " gồm năm phần tử $a<b<c<d<e$ . Rõ ràng $d+e \leq 14+15=29$ còn $e \leq 13$ . Ta sẽ đánh giá max của $a+b$ . Rõ ràng tập gồm hai phần tử thì có max là $d+e$ còn min phải là $a+b$ ( hai phần tử bé nhất và lớn nhất ) nên chúng cách nhau ít nhất $9$ đơn vị . Hay $a+b\leq 20$ do đó $a+b+c+d+e \leq 62$ . Dấu bằng không xảy ra nên max chỉ là $61$ .

Bài 12 : Ta thấy sau mỗi bước dùng thuật toán $1$ và $3$ thì tổng các phần tử tăng lên $1$ còn dùng $2$ thì tổng phần tử giảm đi $n$ . Gọi $a$ là số bước sử dụng cả $3$ thuật toán , gọi $b$ là số bước sử dụng thuật toán $2$ . Do tổng tất cả các phần tử các tập con luôn không đổi nên $a - b - bn = 0$ hay $a=b(n+1)$ , lại thấy mỗi tập con được tác động $1$ lần nên $a=2^{n}$ chia hết cho $n+1$ nên $n=2^{m}-1$ ở đây $m \leq n$ . 


Bài viết đã được chỉnh sửa nội dung bởi bangbang1412: 23-07-2016 - 11:08

$$[\Psi_f(\mathbb{1}_{X_{\eta}}) ] = \sum_{\varnothing \neq J} (-1)^{\left|J \right|-1} [\mathrm{M}_{X_{\sigma},c}^{\vee}(\widetilde{D}_J^{\circ} \times_k \mathbf{G}_{m,k}^{\left|J \right|-1})] \in K_0(\mathbf{SH}_{\mathfrak{M},ct}(X_{\sigma})).$$


#10
Ego

Ego

    Thượng sĩ

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

Bài 1. Cho 2016 tập hợp, mỗi tập có 45 phần tử, hai tập bất kì có đúng một phần tử chung. Chứng minh rằng tồn tại 1 phần tử thuộc tất cả các tập.



#11
bangbang1412

bangbang1412

    Độc cô cầu bại

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

Bài 15 : (Bạn này ghi thiếu một bài mình bổ sung ) Tập số tự nhiên được phân hoạch thành hai tập $A,B$ . Chứng minh rằng với mọi số tự nhiên $n$ tồn tại $a,b>n$ mà $a,b,a+b$ cùng thuộc một tập . 

Ghi chú : Đây là trường hợp bé nhất của định lý Folkman , một trường hợp tiếp theo của nó là : Giả sử tập số tự nhiên được phân hoạch thành ba tập $A,B,C$ . Chứng minh rằng tồn tại $a,b,c$ tự nhiên mà $a,b,c,a+b,a+c,b+c,a+b+c$ cùng thuộc một tập ( là bài toán trong đề thi đội tuyển Anh theo bộ phim A brilliant young mind ) . 

Định lý tổng quát : đây


$$[\Psi_f(\mathbb{1}_{X_{\eta}}) ] = \sum_{\varnothing \neq J} (-1)^{\left|J \right|-1} [\mathrm{M}_{X_{\sigma},c}^{\vee}(\widetilde{D}_J^{\circ} \times_k \mathbf{G}_{m,k}^{\left|J \right|-1})] \in K_0(\mathbf{SH}_{\mathfrak{M},ct}(X_{\sigma})).$$


#12
JUV

JUV

    Trung sĩ

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

Bài 15 : (Bạn này ghi thiếu một bài mình bổ sung ) Tập số tự nhiên được phân hoạch thành hai tập $A,B$ . Chứng minh rằng với mọi số tự nhiên $n$ tồn tại $a,b>n$ mà $a,b,a+b$ cùng thuộc một tập . 

Ghi chú : Đây là trường hợp bé nhất của định lý Folkman , một trường hợp tiếp theo của nó là : Giả sử tập số tự nhiên được phân hoạch thành ba tập $A,B,C$ . Chứng minh rằng tồn tại $a,b,c$ tự nhiên mà $a,b,c,a+b,a+c,b+c,a+b+c$ cùng thuộc một tập ( là bài toán trong đề thi đội tuyển Anh theo bộ phim A brilliant young mind ) . 

Định lý tổng quát : đây

Với trường hợp $n=0$ thì xét các số từ $1$ đến $6$ sẽ có điều phải chứng minh. Còn với các trường hợp $n$ lớn hơn $0$, có thể đưa về trường hợp $n=0$ bằng cách chỉ xét các số chia hết cho $n+1$ nằm trong $2$ tập hợp. Chia mỗi số đó cho $n+1$ rồi chứng minh tương tự trường hợp $n=0$ 


Bài viết đã được chỉnh sửa nội dung bởi JUV: 24-07-2016 - 21:47


#13
khavh

khavh

    Lính mới

  • Thành viên mới
  • 1 Bài viết
Mọi người giúp em bài này ạ!!!
Cho n là số tự nhiên lớn hơn 1 và xét tập X={1,2,...,2n-1}. Xét tập A là con của X thỏa:
(i) A có ít nhất n-1 phần tử
(ii) nếu a, b thuộc A( không nhất thiết phân biệt) thì (a+b) thuộc A miễn là (a+b) thuộc X
Chứng minh tổng tất cả các phần tử của X không nằm trong A là không vượt quá n^2

Bài viết đã được chỉnh sửa nội dung bởi khavh: 18-09-2018 - 15:39






Được gắn nhãn với một hoặc nhiều trong số những từ khóa sau: inex, tohop, truonghe, 2016

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

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