Đến nội dung

Hình ảnh

ĐỀ TUYỂN SINH LỚP 10 CHUYÊN TOÁN TIN PTNK 1993-1994


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

#1
I Love MC

I Love MC

    Đại úy

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

Câu 1 : Chia tập hợp những số tự nhiên $\{1,2,...,2n\}$ thành hai tập con rời nhau $A$ và $B$,mỗi tập có $n$ phần tử. 
Kí hiệu các phần tử của hai tập theo thứ tự tăng : 
$A=\{a_1<a_2<...<a_{n-1}<a_n\}$ và $B=\{b_n<b_{n-1}<...<b_2<b_1\}$ 
Hãy chứng minh rằng $|a_1-b_1|+|a_2-b_2|+..+|a-n-b_n|=n^2$ 
Câu 2 : Cho một bảng kích thước $2n x 2n$ ô vuông. Người ta đánh dấu vào $3n$ ô vuông bất kì của bảng. Chứng minh có thể chọn ra $n$ hàng vaf $n$ cột của bảng sao cho các ô được đánh dấu đều nằm trên $n$ hàng hoặc $n$ cột này 
Câu 3 : Cho hình thang vuông $ABCD$ có $AB$ là cạnh đáy nhỏ ,$CD$ là cạnh đáy lớn. $M$ là giao của $AC$ và $BD$. Biết rằng hình thang $ABCD$ ngoại tiếp đường tròn bán kính $R$. Tính $S_{ADM}$ 
Câu 4 : Một hộp đựng $52$ viên bi ,trong đó có $13$ viên xanh,$13$ đỏ,$13$ vàng,$13$ trắng. Cần phải lấy ra ít nhất bao nhiêu viên bi (mà không nhìn trước) để chắc chắn trong số đó có không ít hơn $7$ viên bi cùng màu. Hãy phát biểu và chứng minh bài toán tổng quát hơn 
Câu 5 : Một dãy các con số $0$ và $1$ có độ dài $32$ được gọi là một xâu. Ta kí hiệu các xâu $A,B,C$ như sau : 
$A=(a_1,a_2,..,a_{32})$ 
$B=(b_1,b_2,..,b_{32})$ 
$C=(c_1,c_2,..,c_{32})$ 
Với $a_i,b_i,c_i=0$ hay $1$ và $i=1,2,..,32$ 
Giá trị của một xâu là số các con số $1$ có trong xâu ấy. 
Một máy tính có thể xử lí các xâu bằng 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í , $1 \le k \le 32$ theo quy tắc : 
$(a_1,a_2,..,a_{32}) \Rightarrow (a_k,a_{k+1},...,a_{31},a_{32},a_1,a_2...,a_{k-1})$ 
- Phép so sánh hai xâu $A$ và $B$ để được một xâu mới $C$ theo qui tắc 
$A & B$  $\Rightarrow C$ với : 
$C_i=1$ nếu $(a_i=b_i=0)$ hay $(a_i=b_i=1)$ 
$C_i=0$ nếu $(a_i=1,b_i=0)$ hay $(a_i=0,b_i=1)$ 
Cho xâu $A$ có giá trị là $16$ và $B$ là một xâu tùy ý bất kì. Chứng minh rằng ,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 sẽ được xâu $C$ có giá trị không nhỏ hơn $16$ 


Bài viết đã được chỉnh sửa nội dung bởi I Love MC: 17-04-2016 - 21:00


#2
Mystic

Mystic

    Thượng sĩ

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

Câu 1 : Chia tập hợp những số tự nhiên $\{1,2,...,2n\}$ thành hai tập con rời nhau $A$ và $B$,mỗi tập có $n$ phần tử. 
Kí hiệu các phần tử của hai tập theo thứ tự tăng : 
$A=\{a_1<a_2<...<a_{n-1}<a_n\}$ và $B=\{b_n<b_{n-1}<...<b_2<b_1\}$ 
Hãy chứng minh rằng $|a_1-b_1|+|a_2-b_2|+..+|a-n-b_n|=n^2$ 
Câu 2 : Cho một bảng kích thước $2n x 2n$ ô vuông. Người ta đánh dấu vào $3n$ ô vuông bất kì của bảng. Chứng minh có thể chọn ra $n$ hàng vaf $n$ cột của bảng sao cho các ô được đánh dấu đều nằm trên $n$ hàng hoặc $n$ cột này 
Câu 3 : Cho hình thang vuông $ABCD$ có $AB$ là cạnh đáy nhỏ ,$CD$ là cạnh đáy lớn. $M$ là giao của $AC$ và $BD$. Biết rằng hình thang $ABCD$ ngoại tiếp đường tròn bán kính $R$. Tính $S_{ADM}$ 
Câu 4 : Một hộp đựng $52$ viên bi ,trong đó có $13$ viên xanh,$13$ đỏ,$13$ vàng,$13$ trắng. Cần phải lấy ra ít nhất bao nhiêu viên bi (mà không nhìn trước) để chắc chắn trong số đó có không ít hơn $7$ viên bi cùng màu. Hãy phát biểu và chứng minh bài toán tổng quát hơn 
Câu 5 : Một dãy các con số $0$ và $1$ có độ dài $32$ được gọi là một xâu. Ta kí hiệu các xâu $A,B,C$ như sau : 
$A=(a_1,a_2,..,a_{32})$ 
$B=(b_1,b_2,..,b_{32})$ 
$C=(c_1,c_2,..,c_{32})$ 
Với $a_i,b_i,c_i=0$ hay $1$ và $i=1,2,..,32$ 
Giá trị của một xâu là số các con số $1$ có trong xâu ấy. 
Một máy tính có thể xử lí các xâu bằng 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í , $1 \le k \le 32$ theo quy tắc : 
$(a_1,a_2,..,a_{32}) \Rightarrow (a_k,a_{k+1},...,a_{31},a_{32},a_1,a_2...,a_{k-1})$ 
- Phép so sánh hai xâu $A$ và $B$ để được một xâu mới $C$ theo qui tắc 
$A & B$  $\Rightarrow C$ với : 
$C_i=1$ nếu $(a_i=b_i=0)$ hay $(a_i=b_i=1)$ 
$C_i=0$ nếu $(a_i=1,b_i=0)$ hay $(a_i=0,b_i=1)$ 
Cho xâu $A$ có giá trị là $16$ và $B$ là một xâu tùy ý bất kì. Chứng minh rằng ,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 sẽ được xâu $C$ có giá trị không nhỏ hơn $16$ 

Cái này là làm trên máy tính hay trên giấy vậy bạn ?


>>> Nếu bạn luôn buồn phiền hãy dùng hy vọng để chữa trị <<<

Và ...

>>>  Không bao giờ nói bạn đã thất bại

Cho đến khi đó là nỗi lực cuối cùng của bạn

           Và không bao giờ nói rằng:

        Đó là nỗi lực cuối cùng của bạn

         Cho tới khi bạn đã thành công  >>>

 

~ Mystic Lâm


#3
I Love MC

I Love MC

    Đại úy

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

Cái này là làm trên máy tính hay trên giấy vậy bạn ?

Viết bạn ạ



#4
nntien

nntien

    Sĩ quan

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

Câu 1:

Cho trước $A=\{a_1,a_2,...,a_n\}$, $B=\{b_1,b_2,...,b_n\}$, thỏa mãn yêu cầu bài toán.

Đặt $M=|a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|$, gọi là tổng trị tuyệt đối của hai tập $A, B$

Ta dễ thấy $1 \in A$ hoặc $1 \in B$. Không mất tính tổng quát ta giả sử $1 \in A$

=> $a_1=1$. Nếu $b_1=2n$. Thì ta xét tiếp các phần tử $2$ và $2n-1$.

Giả sử $a_n=2n$. Khi đó $M=b_1-1+|a_2-b_2|+...+2n-b_n=2n-1+|a_2-b_2|+...+b_1-b_n$. 

Tổng sau cùng được xem như là tổng trị tuyệt đối của hai tập $A'=\{1,a_2,...,b_1\}$ và $B'=\{2n,b_2,...,b_1\}$. Nghĩa là ta thực hiện hoán đổi hai phần từ $a_n, b_1$ ở hai tập $A, B$ để trở thành $A', B'$.

$B'$ đã có thứ tự như yêu cầu đề bài nhưng $A'$ có thể chưa sắp thứ tự như yêu cầu đề bài.

Ta thực hiện sắp lại như sau: tồn tại $k$ sao cho $a_{k-1}<b_1<a_{k}$ => $a_i>b_i$ với $i=k,k+1,..,n$.

$A''=\{1, a_2,...,a_{k-1},b_1,a_k,a_{k+1},...,a_{n-1}\}$ là tập sắp thứ tự.

Khi đó tổng trị tuyệt đối của hai tập $A'', B'$ là:

$2n-1+|a_2-b_2|+|a_{k-1}-b_{k-1}|+b_1-b_k+a_k-b_{k+1}+a_{n-1}-b_n=2n-1+|a_2-b_2|+|a_{k-1}-b_{k-1}|+a_k-b_k+...+b_1-b_n=M$

=> Ta thực hiện hoán đối hai phần tử  $a_n, b_1$ ở hai tập $A, B$ để trở thành $A'', B'$ mà tổng trị tuyệt đối vẫn không đổi.

=> Ta xét tiếp phần tử $2$ và $2n-1$ ... cuối cùng ta được hai tập $X=\{1,2,...,n\}, Y=\{2n,2n-1,...,n+1\}$ có tổng trị tuyệt đối là:

$M=n+n+...+n=n^2$ (đpcm).


Bài viết đã được chỉnh sửa nội dung bởi nntien: 25-04-2016 - 22:21

$Maths$$Smart Home$ and $Penjing$

123 Phạm Thị Ngư


#5
nntien

nntien

    Sĩ quan

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

Bài 2:

Xét $3n$ điểm trên các hàng. Ta có $2n$ hàng, theo nguyên lý Dirchlet ta suy ra có $n$ hàng mà mỗi hàng chứa ít nhất 2 điểm => $n$ hàng này chứa ít nhất $2n$ điểm. Suy ra nhiều nhất $n$ điểm còn lại có $n$ cột chứa nó. Suy ra đpcm.


$Maths$$Smart Home$ and $Penjing$

123 Phạm Thị Ngư


#6
nntien

nntien

    Sĩ quan

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

Câu 3:

Gọi O là tâm đường tròn nội tiếp hinh thang ABCD. E, F, K là các tiếp điểm => tam giác OBC vuông tại O => $OK^2=BK.KC=EB.FC=R^2=AE^2$

=>$\frac{AE}{FC}=\frac{EB}{AE}=\frac{DF}{FC}$ => $E,M,F$ thẳng hàng =>

=> $S_{ADM}=\frac{S_{AEFD}}{2}$ => $S_{ADM}=R^2$

 

Hình gửi kèm

  • PTNK.jpg

$Maths$$Smart Home$ and $Penjing$

123 Phạm Thị Ngư


#7
nntien

nntien

    Sĩ quan

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

Câu 4: Theo nguyên lý Dirichlet ta cần lấy ra ít nhất $4 \times (7-1)+1=25$ viên bi để có không ít hơn 7 viên bi cùng màu.

 


$Maths$$Smart Home$ and $Penjing$

123 Phạm Thị Ngư


#8
nntien

nntien

    Sĩ quan

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

Câu 5:

Từ phép so sánh như định nghĩa ta thấy số 1 sinh ra do hai trường hợp 0&0 và 1&1

Gọi x là giá trị của C. m là số vị trị mà phần tử 1 ở C trùng với phần tử 1 của B, n là số vị trí mà phần tử 0 ở C trùng với phần tử 0 của B. 

Suy ra giá trị của $C\&B$ là $m+n$.

Gọi A' là chuỗi anh em của A sau khi dịch k phần tử. Suy ra từ A ta có 31 chuỗi anh em tương ứng với dịch 1, 2, .., 31 đều có giá trị 16.

Ta có các giá trị $m_1, n_1$, $m_2, n_2$, .., $m_{32}, n_{32}$.

Ta dễ thấy rằng $m_1+m_2+...+m_{32}=16x$, $n_1+n_2+...+n_{32}=16(32-x)$ => $m_1+n_1+m_2+n_2+...+m_{32}+n_{32}=16.32$

Trong số 32 cặp giá trị trên sẽ tồn tai ít nhất một cặp sao cho $m_i+n_i$ là lớn nhất.

Ta chỉ cần chứng minh $m_i+n_i \geq 16$.

Giả sử tất cả $m_i+n_j < 16$ => cộng các cặp giá trị ta có $m_1+n_1+m_2+n_2+...+m_{32}+n_{32}<16.32$ => vô lý => đpcm


$Maths$$Smart Home$ and $Penjing$

123 Phạm Thị Ngư





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

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