Đến nội dung

Hình ảnh

CMR:Từ n số nguyên bất kì luôn tìm được 1 số hoặc 1 số số có tổng chia hết cho n

- - - - -

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

#1
leanh9adst

leanh9adst

    Thượng sĩ

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

Đây là một số bài toán sử dụng nguyên lí Dirichlet, mong mọi người giúp đỡ:

Bài 1: CMR Từ n số nguyên bất kì ta luôn tìm được 1 số hoặc 1 số số có tổng chia hết cho n.

Bài 2: Cho 9 điểm bất kì nằm trong hình vuông đơn vị,CMR tìm được 3 điểm lập thành 1 tam giác có diện tích nhỏ hơn hoặc bằng 1/8

Bài 3: Trên mặt phẳng cho 5 điểm có tọa độ nguyên,trong đó không có 3 điểm nào thẳng hàng.CMR trong số các tam giác được tạo thành từ 5 điểm trên có ít nhất 3 tam giác có diện tích nguyên

Bài 4: Viết n số thành một hàng ngang.CMR hoặc có 1 số chia hết cho n hoặc có 1 số số liên tiếp có tổng chia hết cho n(n>1)

Bài 5: Trên đường tròn cho 16 điểm được tô bởi 1 trong 3 mày:xanh ,đỏ,vàng.Các dây cung nối 2 điểm trong 16 điểm trên được tô bởi 2 màu: tím,đen.CMR ta luôn có 3 trong 16 điểm trên được tô cùng màu và 3 dây cung nối chúng cũng được tô cùng màu

Bài 6: Trên đường tròn,một số cung được tô màu đen, phần còn lại tô màu đỏ.Biết tổng độ dài các cung màu đen nhỏ hơn nửa chu vi đường tròn.CMR có thể kẻ được 1 đường kính của đường tròn với 2 đầu mút cùng màu đỏ

Bài 7: Trên bàn cờ 10x10,người ta viết các số từ 1 đến 100.Mỗi hàng chọn ra số lớn thứ 3.CMR tồn tại 1 hàng có tỏng các số trong hàng nhỏ hơn tổng các số lớn thứ 3 được chọn

Bài 8: Có 3 trường học,mỗi trường có n học sinh.Mỗi học sinh quen ít nhất n+1 học sinh từ 2 trường khác.CMR người ta có thể chọn ra mỗi trường 1 học sinh sao cho 3 học sinh được chọn đôi một quen nhau

Bài 9: Có 1 bộ các quả cân có tính chất sau:

-Trong bộ có ít nhất 5 quả cân có trọng lượng khác nhau

-Với 2 quả cân bất kì,tìm được 2 quả cân khác có tổng trọng lượng bằng tổng trọng lượng của 2 quả cân dó

Hỏi bộ quả cân này có ít nhất là bao nhiêu quả cân?


Mặt trời mọc rồi lặn,mặt trăng tròn rồi lại khuyết nhưng ánh sáng mà người thầy rọi vào ta sẽ còn mãi trong cuộc đời!


#2
I Love MC

I Love MC

    Đại úy

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

Ta xét các số 
$S_1=a_1$ 
$S_2=a_1+a_2$ 
... 
$S_n=a_1+a_2+...+a_n$ 
TH1 : Nếu tồn tại một số $S_i$ chia hết cho $n$ ta có đpcm $i=1,2,..,n$
TH2 : Ko tồn tại một số $S_i$ chia hết cho $n$ 
Ta chia $S_i$ cho $n$ thì nhận được các số dư là $1,2..,n-1$. Vì có $n$ số dư mà chỉ có $n-1$ giá trị thì theo nguyên tắc Dirichlet 
tồn tại $2$ số có số dư bằng nhau khi đó ta có $S_x-S_y$ chia hết cho $n$ ($1 \le x,y \le n$)



#3
I Love MC

I Love MC

    Đại úy

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

Bài 5: Trên đường tròn cho 16 điểm được tô bởi 1 trong 3 mày:xanh ,đỏ,vàng.Các dây cung nối 2 điểm trong 16 điểm trên được tô bởi 2 màu: tím,đen.CMR ta luôn có 3 trong 16 điểm trên được tô cùng màu và 3 dây cung nối chúng cũng được tô cùng màu
Xét đường tròn $(O)$ gồm $16$ điểm $A_1,A_2,...,A_{16}$ 
Giả sử không có $3$ điểm nào tô cùng màu. 
Vậy thì có $3$ màu vậy thì số điểm sẽ không lớn hơn : $3.2$ (mâu thuẫn) 
Ta chứng minh : 
3 dây cung nối chúng cũng được tô cùng màu 
Gia su 3 diem duoc to cung mau la $A_1,A_2,A_3$  
Xet diem $A_1$  vay con 15 diem . 
$15=2.7+1$ suy ra ton tai $8$ day cung duoc to cung mau .De roi 
Open : Tren mat phang cho $5x+2$,ko co 3 diem nao thang hang. To cac doan thang bang $x$ mau thi luon ton tai tam giac "dep" (cac canh cung mau) 
P/S : **king  unikey



#4
leanh9adst

leanh9adst

    Thượng sĩ

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

Ta xét các số 
$S_1=a_1$ 
$S_2=a_1+a_2$ 
... 
$S_n=a_1+a_2+...+a_n$ 
TH1 : Nếu tồn tại một số $S_i$ chia hết cho $n$ ta có đpcm $i=1,2,..,n$
TH2 : Ko tồn tại một số $S_i$ chia hết cho $n$ 
Ta chia $S_i$ cho $n$ thì nhận được các số dư là $1,2..,n-1$. Vì có $n$ số dư mà chỉ có $n-1$ giá trị thì theo nguyên tắc Dirichlet 
tồn tại $2$ số có số dư bằng nhau khi đó ta có $S_x-S_y$ chia hết cho $n$ ($1 \le x,y \le n$)

Bạn đọc lại đề bài giúp mình.hình như bạn giải sai thì phải!


Mặt trời mọc rồi lặn,mặt trăng tròn rồi lại khuyết nhưng ánh sáng mà người thầy rọi vào ta sẽ còn mãi trong cuộc đời!


#5
I Love MC

I Love MC

    Đại úy

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

Bạn đọc lại đề bài giúp mình.hình như bạn giải sai thì phải!

Đúng bạn ạ còn không bạn lên chuyên đề số học VMF . Cách giải giống mình :)



#6
leanh9adst

leanh9adst

    Thượng sĩ

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

hihi bạn giải giúp mình mấy bài còn lại đi ! :)


Mặt trời mọc rồi lặn,mặt trăng tròn rồi lại khuyết nhưng ánh sáng mà người thầy rọi vào ta sẽ còn mãi trong cuộc đời!


#7
happyfree

happyfree

    Trung sĩ

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

Đây là một số bài toán sử dụng nguyên lí Dirichlet, mong mọi người giúp đỡ:

Bài 1: CMR Từ n số nguyên bất kì ta luôn tìm được 1 số hoặc 1 số số có tổng chia hết cho n.

Bài 2: Cho 9 điểm bất kì nằm trong hình vuông đơn vị,CMR tìm được 3 điểm lập thành 1 tam giác có diện tích nhỏ hơn hoặc bằng 1/8

Bài 3: Trên mặt phẳng cho 5 điểm có tọa độ nguyên,trong đó không có 3 điểm nào thẳng hàng.CMR trong số các tam giác được tạo thành từ 5 điểm trên có ít nhất 3 tam giác có diện tích nguyên

Bài 4: Viết n số thành một hàng ngang.CMR hoặc có 1 số chia hết cho n hoặc có 1 số số liên tiếp có tổng chia hết cho n(n>1)

Bài 5: Trên đường tròn cho 16 điểm được tô bởi 1 trong 3 mày:xanh ,đỏ,vàng.Các dây cung nối 2 điểm trong 16 điểm trên được tô bởi 2 màu: tím,đen.CMR ta luôn có 3 trong 16 điểm trên được tô cùng màu và 3 dây cung nối chúng cũng được tô cùng màu

Bài 6: Trên đường tròn,một số cung được tô màu đen, phần còn lại tô màu đỏ.Biết tổng độ dài các cung màu đen nhỏ hơn nửa chu vi đường tròn.CMR có thể kẻ được 1 đường kính của đường tròn với 2 đầu mút cùng màu đỏ

Bài 7: Trên bàn cờ 10x10,người ta viết các số từ 1 đến 100.Mỗi hàng chọn ra số lớn thứ 3.CMR tồn tại 1 hàng có tỏng các số trong hàng nhỏ hơn tổng các số lớn thứ 3 được chọn

Bài 8: Có 3 trường học,mỗi trường có n học sinh.Mỗi học sinh quen ít nhất n+1 học sinh từ 2 trường khác.CMR người ta có thể chọn ra mỗi trường 1 học sinh sao cho 3 học sinh được chọn đôi một quen nhau

Bài 9: Có 1 bộ các quả cân có tính chất sau:

-Trong bộ có ít nhất 5 quả cân có trọng lượng khác nhau

-Với 2 quả cân bất kì,tìm được 2 quả cân khác có tổng trọng lượng bằng tổng trọng lượng của 2 quả cân dó

Hỏi bộ quả cân này có ít nhất là bao nhiêu quả cân?

Bài 3:

Gọi 5 điểm đó là $A,B,C,D,E$

Vì những tọa độ các điểm đã cho $A,B,C,D,E$ là những số nguyên, sau khi thêm vào các tọa độ này những số chẵn thích hợp thì mỗi tọa độ sẽ chỉ nhận các  giá  trị $0$ và $1$ .Do đó mọi 5 điểm đã cho tạo nên bởi các điểm $(0,0),(0,1),(1,0),(1,1)$.Áp dụng nguyên lí Đi-rich-lê suy ra ít nhất 2 điểm trong các điểm $A,B,C,D,E$  biến đổi thành cùng 1 điểm trong ${(0,0),(0,1),(1,0),(1,1)}$. Giả sử đó là $A,B$.Ta sẽ khẳng định diện tích các tam giác $ABC,ABD$ và $ABE$ là những số nguyên .Thật vậy, các tam giác này bị biến thành các đoạn thẳng (do $A$ và $B$ biến thành cùng 1 điểm) nên diện tích ảnh của chúng bằng $0$. Vậy trước khi biến  đổi, diện tích của chúng phải là số nguyên


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


#8
leanh9adst

leanh9adst

    Thượng sĩ

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

Bài 3:

Gọi 5 điểm đó là $A,B,C,D,E$

Vì những tọa độ các điểm đã cho $A,B,C,D,E$ là những số nguyên, sau khi thêm vào các tọa độ này những số chẵn thích hợp thì mỗi tọa độ sẽ chỉ nhận các  giá  trị $0$ và $1$ .Do đó mọi 5 điểm đã cho tạo nên bởi các điểm $(0,0),(0,1),(1,0),(1,1)$.Áp dụng nguyên lí Đi-rich-lê suy ra ít nhất 2 điểm trong các điểm $A,B,C,D,E$  biến đổi thành cùng 1 điểm trong ${(0,0),(0,1),(1,0),(1,1)}$. Giả sử đó là $A,E$.Ta sẽ khẳng định diện tích các tam giác $ABC,ABD$ và $ABE$ là những số nguyên .Thật vậy, các tam giác này bị biến thành các đoạn thẳng (do $A$ và $B$ biến thành cùng 1 điểm) nên diện tích ảnh của chúng bằng $0$. Vậy trước khi biến  đổi, diện tích của chúng phải là số nguyên

Thanks bạn nhưng mình thấy ở trên là A và E , ở dưới sao lại A và B


Mặt trời mọc rồi lặn,mặt trăng tròn rồi lại khuyết nhưng ánh sáng mà người thầy rọi vào ta sẽ còn mãi trong cuộc đời!


#9
I Love MC

I Love MC

    Đại úy

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

Bài $2$ phải cho số cụ thể hình vuông là mấy chứ ? 
Tớ lấy ví dụ cho hình vuông có $S=100000000000000000000cm^2$  
Như vậy cho $9$ điểm bất kì thì cũng sẽ ko tồn tại $S=1/8$ ? 
 



#10
leanh9adst

leanh9adst

    Thượng sĩ

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

Bài $2$ phải cho số cụ thể hình vuông là mấy chứ ? 
Tớ lấy ví dụ cho hình vuông có $S=100000000000000000000cm^2$  
Như vậy cho $9$ điểm bất kì thì cũng sẽ ko tồn tại $S=1/8$ ? 
 

hihi hình như là 1 đơn vị ý!


Mặt trời mọc rồi lặn,mặt trăng tròn rồi lại khuyết nhưng ánh sáng mà người thầy rọi vào ta sẽ còn mãi trong cuộc đời!


#11
leanh9adst

leanh9adst

    Thượng sĩ

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

Bài 5: Trên đường tròn cho 16 điểm được tô bởi 1 trong 3 mày:xanh ,đỏ,vàng.Các dây cung nối 2 điểm trong 16 điểm trên được tô bởi 2 màu: tím,đen.CMR ta luôn có 3 trong 16 điểm trên được tô cùng màu và 3 dây cung nối chúng cũng được tô cùng màu
Xét đường tròn $(O)$ gồm $16$ điểm $A_1,A_2,...,A_{16}$ 
Giả sử không có $3$ điểm nào tô cùng màu. 
Vậy thì có $3$ màu vậy thì số điểm sẽ không lớn hơn : $3.2$ (mâu thuẫn) 
Ta chứng minh : 
3 dây cung nối chúng cũng được tô cùng màu 
Gia su 3 diem duoc to cung mau la $A_1,A_2,A_3$  
Xet diem $A_1$  vay con 15 diem . 
$15=2.7+1$ suy ra ton tai $8$ day cung duoc to cung mau .De roi 
Open : Tren mat phang cho $5x+2$,ko co 3 diem nao thang hang. To cac doan thang bang $x$ mau thi luon ton tai tam giac "dep" (cac canh cung mau) 
P/S : **king  unikey

mình chưa hiểu lắm,bạn giải thích rõ hơn hộ mình được ko?


Mặt trời mọc rồi lặn,mặt trăng tròn rồi lại khuyết nhưng ánh sáng mà người thầy rọi vào ta sẽ còn mãi trong cuộc đời!


#12
happyfree

happyfree

    Trung sĩ

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

Thanks bạn nhưng mình thấy ở trên là A và E , ở dưới sao lại A và B

mình đánh lộn chữ $B$ thành  chữ $E$



#13
happyfree

happyfree

    Trung sĩ

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

Đây là một số bài toán sử dụng nguyên lí Dirichlet, mong mọi người giúp đỡ:

Bài 1: CMR Từ n số nguyên bất kì ta luôn tìm được 1 số hoặc 1 số số có tổng chia hết cho n.

Bài 2: Cho 9 điểm bất kì nằm trong hình vuông đơn vị,CMR tìm được 3 điểm lập thành 1 tam giác có diện tích nhỏ hơn hoặc bằng 1/8

Bài 3: Trên mặt phẳng cho 5 điểm có tọa độ nguyên,trong đó không có 3 điểm nào thẳng hàng.CMR trong số các tam giác được tạo thành từ 5 điểm trên có ít nhất 3 tam giác có diện tích nguyên

Bài 4: Viết n số thành một hàng ngang.CMR hoặc có 1 số chia hết cho n hoặc có 1 số số liên tiếp có tổng chia hết cho n(n>1)

Bài 5: Trên đường tròn cho 16 điểm được tô bởi 1 trong 3 mày:xanh ,đỏ,vàng.Các dây cung nối 2 điểm trong 16 điểm trên được tô bởi 2 màu: tím,đen.CMR ta luôn có 3 trong 16 điểm trên được tô cùng màu và 3 dây cung nối chúng cũng được tô cùng màu

Bài 6: Trên đường tròn,một số cung được tô màu đen, phần còn lại tô màu đỏ.Biết tổng độ dài các cung màu đen nhỏ hơn nửa chu vi đường tròn.CMR có thể kẻ được 1 đường kính của đường tròn với 2 đầu mút cùng màu đỏ

Bài 7: Trên bàn cờ 10x10,người ta viết các số từ 1 đến 100.Mỗi hàng chọn ra số lớn thứ 3.CMR tồn tại 1 hàng có tỏng các số trong hàng nhỏ hơn tổng các số lớn thứ 3 được chọn

Bài 8: Có 3 trường học,mỗi trường có n học sinh.Mỗi học sinh quen ít nhất n+1 học sinh từ 2 trường khác.CMR người ta có thể chọn ra mỗi trường 1 học sinh sao cho 3 học sinh được chọn đôi một quen nhau

Bài 9: Có 1 bộ các quả cân có tính chất sau:

-Trong bộ có ít nhất 5 quả cân có trọng lượng khác nhau

-Với 2 quả cân bất kì,tìm được 2 quả cân khác có tổng trọng lượng bằng tổng trọng lượng của 2 quả cân dó

Hỏi bộ quả cân này có ít nhất là bao nhiêu quả cân?

Bài 2:

Chia hình vuông ra 4 hình vuông con có cạnh $0,5$. Có 9 điểm và 4 hình vuông nên theo nguyên lí Đi-rich-lê thì có ít nhất 1 hình vuông chứa ít nhất 3 điểm .  Diện tích tam giác tạo bởi 3 điểm ấy nhỏ hơn hoặc bằng $\frac{1}{8}$



#14
dauhoctoanoc

dauhoctoanoc

    Binh nhất

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

Bài 5: Trên đường tròn cho 16 điểm được tô bởi 1 trong 3 mày:xanh ,đỏ,vàng.Các dây cung nối 2 điểm trong 16 điểm trên được tô bởi 2 màu: tím,đen.CMR ta luôn có 3 trong 16 điểm trên được tô cùng màu và 3 dây cung nối chúng cũng được tô cùng màu
Xét đường tròn $(O)$ gồm $16$ điểm $A_1,A_2,...,A_{16}$ 
Giả sử không có $3$ điểm nào tô cùng màu. 
Vậy thì có $3$ màu vậy thì số điểm sẽ không lớn hơn : $3.2$ (mâu thuẫn) 
Ta chứng minh : 
3 dây cung nối chúng cũng được tô cùng màu 
Gia su 3 diem duoc to cung mau la $A_1,A_2,A_3$  
Xet diem $A_1$  vay con 15 diem . 
$15=2.7+1$ suy ra ton tai $8$ day cung duoc to cung mau .De roi 
Open : Tren mat phang cho $5x+2$,ko co 3 diem nao thang hang. To cac doan thang bang $x$ mau thi luon ton tai tam giac "dep" (cac canh cung mau) 
P/S : **king  unikey

Giải thích dùm mình chỗ dây cung cùng màu liên quan tới 3 điểm cùng màu, mình ko hiễu chỗ đó



#15
leanh9adst

leanh9adst

    Thượng sĩ

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

Giải thích dùm mình chỗ dây cung cùng màu liên quan tới 3 điểm cùng màu, mình ko hiễu chỗ đó

Dùng Nguyên lí Dirichlet đó bạn!


Mặt trời mọc rồi lặn,mặt trăng tròn rồi lại khuyết nhưng ánh sáng mà người thầy rọi vào ta sẽ còn mãi trong cuộc đời!


#16
dauhoctoanoc

dauhoctoanoc

    Binh nhất

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

Dùng Nguyên lí Dirichlet đó bạn!

Mình cũng biết là dùng  Dirichlet mà đọc từ hồi chiều tới giờ chưa hiểu.Hix. đầu óc chậm tiêu hóa quá



#17
Trinh Huu An

Trinh Huu An

    Hạ sĩ

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

vào tổ hợp toán rời rạc mà hỏi í


   :ukliam2:  Nothing no can :ukliam2:

                      :wub:  ﻃ☺ﻵe♥HT fѲ₤ﻍѵҽr :wub:

Có những thứ tưởng chừng như trong lòng bàn tay nhưng bạn lại không nắm được nó.

Đừng chọn cuộc sống an nhàn khi mà bạn còn chịu khổ được.





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

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