Nguyên lý Đi-rich-lê là gì? Cho ví dụ?P/s: Nhanh mình tick

K

Khách

Hãy nhập câu hỏi của bạn vào đây, nếu là tài khoản VIP, bạn sẽ được ưu tiên trả lời.

Chọn lớp

Chọn môn

Mua vip

DN

Đan Nghi

20 tháng 7 2018 - olm

Nguyên lý Đi-rich-lê là gì? Cho ví dụ?

P/s: Nhanh mình tick

7

KC

khanh cuong

20 tháng 7 2018

- Nguyên lý Dirichlet do nhà toán học người Đức nổi tiếng là Dirichlet đề xuất từ thế kỷ XX đã được áp dụng để chứng minh sự tồn tại nghiệm trong nhiều bài toán tổ hợp. Nguyên lý này được phát triển từ một mệnh đề rất đơn giản gọi là nguyên lý “nguyên lý quả cam” hay là nguyên lý “chuồng chim bồ câu”: Giả sử có một đàn chim bồ câu bay vào chuồng. Nếu số chim nhiều hơn số ngăn chuồng thì chắc chắn có ít nhất một ngăn có nhiều hơn một con chim.

- Một cách tổng quát, nguyên lý Dirichlet được phát biểu như sau:

Nếu xếp nhiều hơn n+1 đối tượng vào n cái hộp thì tồn tại ít nhất một hộp chứa không ít hơn hai đối tượng.

- Việc chứng minh nguyên lý này có thể tiến hành bằng lập luận phản chứng rất đơn giản: Giả sử không hộp nào chứa nhiều hơn một đối tượng thì chỉ có nhiều nhất là n đối tượng được xếp trong các hộp, trái với giả thiết là số đối tượng lớn hơn n.

vVí dụ 1:

Một năm có nhiều nhất là 365 ngày. Do vậy trong số 366 người bất kỳ bao giờ cũng có ít nhất 2 người có cùng ngày sinh nhật ( không xét năm nhuận ).

vVí dụ 2:

Thang điểm bài kiểm tra là từ 0 đến 10, tức là có 11 thang điểm khác nhau. Do vậy trong số 12 sinh viên bất kỳ của một lớp sẽ có ít nhất 2 người có kết quả bài kiểm tra giống nhau.

vVí dụ 3:

Cấp bậc quân hàm của sĩ quan có 8 cấp bậc từ thiếu úy đến đại tá. Do vậy trong một đơn vị có 9 sĩ quan thì sẽ có ít nhất 2 người cùng cấp bậc.

· Nguyên lý Dirichlet cơ bản:

Nếu nhốt n+1 con thỏ vào n cái chuồng thì bao giờ cũng có một chuồng chứa ít nhất 2 con thỏ.

· Nguyên lý Dirichlet mở rộng:

Nếu nhốt n con thỏ vào cái chuồng thì tồn tại một chuồng có ít nhất con thỏ .

Ở đây kí hiệu để chỉ phần nguyên của .

Ta có thể chứng minh nguyên lý Dirichlet mở rộng như sau: Giả sử mọi chuồng thỏ không có đến ==(con)

thì số thỏ trong mỗi chuồng đều nhỏ hơn hoặc bằng con. Từ đó suy ra tổng số con thỏ không vượt quá con. Điều này vô lý vì có n con thỏ. Vậy giả thiết phản chứng là sai. Nguyên lý Dirichlet mở rộng được chứng minh.

N

Nguyệt

20 tháng 7 2018

Nếu đem m thỏ vào n lồng với m>n thì ít nhất cũng có một lồng nhốt không ít hơn 2 thỏ. Tương tự, nếu đem m đồ vật vào n ô ngăn kéo, với m>n, thì ít nhất cũng phải có 1 ô ngăn kéo chứa không ít hơn 2 đồ vật
Phần chứng minh bài toán, các bạn chắc gần như ai cũng biết, mình chỉ xin nêu một vài bài toán vận dụng cơ bản.

Ví dụ 1:
Trong một lớp chuyên toán có 40 học sinh. Trong một kỳ kiểm tra chất lượng môn toán chỉ có một em đạt điểm tối đa là 10, và một em đạt điểm 4, các em khác đạt từ điểm 5 trở lên. Chứng minh rằng trong lớp ít nhất cũng có 8 em có điểm số như nhau, biết rằng điểm số các em đều là các số nguyên.

Lời giải:
Theo giả thiết của bài toán thì chỉ có một em đạt điểm 10 và một em đạt điểm 4, do đó sẽ có 40−2=3840−2=38 em đạt điểm 5 đến điểm 9. Coi mỗi học sinh là một "thỏ", mỗi loại điểm là 1 "lồng", như vậy ta sẽ có các lồng sau:
"Lồng 5": nhốt những ai đạt điểm 5
"Lồng 6": nhốt những ai đạt điểm 6
"Lồng 7": nhốt những ai đạt điểm 7
"Lồng 8": nhốt những ai đạt điểm 8
"Lồng 9": nhốt những ai đạt điểm 9
Với 5 lồng nhốt 38 thỏ, vậy có ít nhất một lồng nhốt không ít hơn 8 thỏ, bài toán được chứng minh.
Ví dụ 2:
Cho 10 số tự nhiên bất kỳ: a1,a2,a3...,a9,a10a1,a2,a3...,a9,a10
Chứng minh rằng thế nào cũng có một số hoặc tổng một số số liên tiếp nhau trong dãy 10 số đã cho chia hết cho 10.
Lời giải:

Để làm xuất hiện khái niệm "thỏ", "lồng", ta thành lập dãy số mới sau đây:
Đặt B1=a1B1=a1
B2=a1+a2B2=a1+a2
B3=a1+a2+a3B3=a1+a2+a3
B4=a1+a2+a3+a4B4=a1+a2+a3+a4
...
B10=a1+...+a10B10=a1+...+a10
Ta thấy rằng:
- Nếu tồn tài một BiBi nào đó (i=1,2,3,...,10) chia hết cho 10 thì bài toán đã được chứng minh.
- Nếu không tồn tại một B1B1 nào đó chia hết cho 10 thì ta chỉ việc đem tất cả BiBi chia cho 10, lúc đó được 10 số dư từ 1-9, trong khi đó các số tự nhiên từ 1-9 chỉ có 9 số (như vậy tương đương với việc nhốt 10 chủ thỏ vào 9 lồng), theo nguyên tắc Đi-rích-lê, tồn tại 1 lồng nhốt không ít hơn 2 chú thỏ, tương đương với việc tồn tại hai số có cùng số dư, như vậy có hiệu chia hết cho 10, bài toán được chứng minh

Những câu hỏi liên quan

ML

mai love N

14 tháng 11 2018 - olm

đồng dư là gì (cho ví dụ)

nguyên lý đi rích lê là gì (cho ví dụ)

2

LH

Lê Hữu Phúc

14 tháng 11 2018

Trong toán học, đặc biệt là trong đại số và lý thuyết số, quan hệ đồng dư (gọi đơn giản là đồng dư) là một quan hệ tương đương trên tập hợp số nguyên.

Định nghĩa[sửa | sửa mã nguồn]

Cho số nguyên dương n, hai số nguyên a,b được gọi là đồng dư theo mô-đun n nếu chúng có cùng số dư khi chia cho n. Điều này tương đương với hiệu a-b chia hết cho n.

Ký hiệu:

{\displaystyle a\equiv b{\pmod {n}}\,} $a\equiv b{\pmod {n}}\,$

Ví dụ:

{\displaystyle 11\equiv 5{\pmod {3}}\,} $11\equiv 5{\pmod {3}}\,$

Vì 11 và 5 khi chia cho 3 đều cho số dư là 2:

11: 3 = 3 (dư 2)

5: 3 = 1 (dư 2)

Tính chất[sửa | sửa mã nguồn]

Ngoài các tính chất của một quan hệ tương đương (phản xạ, đối xứng, bắc cầu), phép đồng dư còn có thêm các tính chất sau: Có thể cộng, trừ, nhân và nâng lên lũy thừa các đồng dư thức có cùng một mô-đun, cụ thể. Nếu ta có:

{\displaystyle a_{1}\equiv a_{2}{\pmod {n}}\,} $a_{1}\equiv a_{2}{\pmod {n}}\,$

{\displaystyle b_{1}\equiv b_{2}{\pmod {n}}\,} $b_{1}\equiv b_{2}{\pmod {n}}\,$

Thì ta có:

{\displaystyle (a_{1}+b_{1})\equiv (a_{2}+b_{2}){\pmod {n}}\,} $(a_{1}+b_{1})\equiv (a_{2}+b_{2}){\pmod {n}}\,$
{\displaystyle (a_{1}-b_{1})\equiv (a_{2}-b_{2}){\pmod {n}}\,} $(a_{1}-b_{1})\equiv (a_{2}-b_{2}){\pmod {n}}\,$
{\displaystyle (a_{1}b_{1})\equiv (a_{2}b_{2}){\pmod {n}}.\,} $(a_{1}b_{1})\equiv (a_{2}b_{2}){\pmod {n}}.\,$
{\displaystyle a_{1}^{k}\equiv a_{2}^{k}{\pmod {n}}\,} $a_{1}^{k}\equiv a_{2}^{k}{\pmod {n}}\,$ , với k nguyên dương.
Luật giản ước[sửa | sửa mã nguồn]
Nếu {\displaystyle (a_{1}*b)\equiv (a_{2}*b){\pmod {n}}\,} $(a_{1}*b)\equiv (a_{2}*b){\pmod {n}}\,$ và (b,n)=1 (b,n nguyên tố cùng nhau) thì {\displaystyle a_{1}\equiv a_{2}{\pmod {n}}\,} $a_{1}\equiv a_{2}{\pmod {n}}\,$
Nghịch đảo mô-đun[sửa | sửa mã nguồn]
Nếu số nguyên dương n và số nguyên a nguyên tố cùng nhau thì tồn tại duy nhất một số {\displaystyle x\in \{0,1,2,\cdots ,n-1\}} $x\in \{0,1,2,\cdots ,n-1\}$ sao cho: {\displaystyle ax\equiv 1{\pmod {n}}\,} $ax\equiv 1{\pmod {n}}\,$ , số x này được gọi là nghịch đảo của a theo mô-đun n.
Hệ thặng dư đầy đủ[sửa | sửa mã nguồn]
Tập hợp {\displaystyle \{a_{1},a_{2},\cdots ,a_{n}\}} $\{a_{1},a_{2},\cdots ,a_{n}\}$ được gọi là một hệ thặng dư đầy đủ mô-đun n nếu với mọi số nguyên i, {\displaystyle 0\leq i\leq n-1} $0\leq i\leq n-1$ , tồn tại duy nhất chỉ số j sao cho {\displaystyle a_{j}\equiv i{\pmod {n}}\,} $a_{j}\equiv i{\pmod {n}}\,$ .
Tính chất[sửa
Nếu {\displaystyle \{a_{1},a_{2},\cdots ,a_{n}\}} $\{a_{1},a_{2},\cdots ,a_{n}\}$ là một hệ thặng dư đầy đủ mô-đun n thì {\displaystyle \{a_{1}+a,a_{2}+a,\cdots ,a_{n}+a\}} $\{a_{1}+a,a_{2}+a,\cdots ,a_{n}+a\}$ là một hệ thặng dư đầy đủ mô-đun n với mọi số nguyên a.
Nếu {\displaystyle \{a_{1},a_{2},\cdots ,a_{n}\}} $\{a_{1},a_{2},\cdots ,a_{n}\}$ là một hệ thặng dư đầy đủ mô-đun n thì {\displaystyle \{aa_{1},aa_{2},\cdots ,aa_{n}\}} $\{aa_{1},aa_{2},\cdots ,aa_{n}\}$ là một hệ thặng dư đầy đủ mô-đun n với mọi số nguyên a nguyên tố cùng nhau với n.

NC

❖︵Ňɠυүễη Çɦâυ Ƭυấη Ƙїệт♔

14 tháng 11 2018

Trong toán học, đặc biệt là trong đại số và lý thuyết số, quan hệ đồng dư (gọi đơn giản là đồng dư) là một quan hệ tương đương trên tập hợp số nguyên.

VD :

$(a_{1}+b_{1})\equiv (a_{2}+b_{2}){\pmod {n}}\,$
$(a_{1}-b_{1})\equiv (a_{2}-b_{2}){\pmod {n}}\,$
$(a_{1}b_{1})\equiv (a_{2}b_{2}){\pmod {n}}.\,$
$a_{1}^{k}\equiv a_{2}^{k}{\pmod {n}}\,$ , với k nguyên dương.

Nếu đem m thỏ vào n lồng với m>n thì ít nhất cũng có một lồng nhốt không ít hơn 2 thỏ. Tương tự, nếu đem m đồ vật vào n ô ngăn kéo, với m>n, thì ít nhất cũng phải có 1 ô ngăn kéo chứa không ít hơn 2 đồ vật
Phần chứng minh bài toán, các bạn chắc gần như ai cũng biết, mình chỉ xin nêu một vài bài toán vận dụng cơ bản.

PQ

Phạm Quỳnh Anh

3 tháng 12 2019 - olm

Vật lý

Viết 3 ví dụ về đòn bẩy
Viết 3 ví dụ về mặt phẳng nghiêng
Viết 3 ví dụ về ròng rọc

Ai nhanh mình tick cho

#Ngữ văn lớp 6

1

P

Phương_Ly

3 tháng 12 2019

-Lấy búa nhổ đinh ra khỏi tường.

- Dắt xe lên một bề mặt dốc: Dắt xe len dốc, lên nhà,..

- Kéo nước từ giếng lên

K mk nha!!

T

tructoab2016

12 tháng 12 2017 - olm

Từ là gì ? Từ Tiếng Việt chia làm mấy loại lớn ? Cho ví dụ.

AI NHANH NHẤT MÌNH TICK

#Ngữ văn lớp 6

4

LT

lê trần minh quân

12 tháng 12 2017

Từ là đơn vị nhr nhất để tạo nên câu

từ được chia làm 2 loại: từ đơn và từ phức

VD: từ đơn: đèn, học,bàn

từ phức: học hành, bàn ghế

V

viet

12 tháng 12 2017

từ là đơn vị ngôn ngữ nhỏ nhất dùng để tạo nên câu

VD: học

LT

Lê Thanh Nga

15 tháng 8 2018 - olm

a) Oxit là gì? Phân loại và cách đọc tên. Cho ví dụ

b) Axit là gì? Cách gọi tên. Cho ví dụ

c) Bazơ là gì? Cách gọi tên. Cho ví dụ

Ai nhanh mk tick. Nhớ kết bạn nha.

3

LM

Linh Mun Mun

15 tháng 8 2018

1) Đặc điểm oxit: 2 nguyên tố (M_xO_y)
2) Oxit gồm 2 loại:
+ Oxit axit: chứa phi kim (hoặc một số kim loại có hóa trị cao ví dụ: Mn (VII), Cr (VII)…) và tương ứng với 1 axit.
VD: SO₃ có axit tương ứng là H₂SO₄.
+ Oxit bazơ: chứa kim loại và tương ứng với 1 bazơ.
VD: K₂O có bazơ tương ứng là KOH.
3) Tên gọi:
Cách gọi chung: Tên nguyên tố + oxit
+ Với kim loại nhiều hóa trị:
          Tên oxit bazơ: Tên kim loại (kèm hóa trị) + oxit
+ Với phi kim nhiều hóa trị:
          Tên oxit axit: Tên phi kim                  +                 oxit
          (kèm tiền tố chỉ số nguyên tử phi kim) (kèm tiền tố chỉ số nguyên tử oxi)
Các tiền tố: 2 – đi; 3 – tri; 4 – têtra; 5 – penta.
Ví dụ
Phân loại các oxit sau và gọi tên các oxit đó.
SO₂, K₂O, MgO, P₂O₅, N₂O₅, Al₂O₃, Fe₂O₃, CO₂.

LM

Linh Mun Mun

15 tháng 8 2018

Axit

1. Khái niệm

- VD: HCl, H₂S, H₂SO₄ , HNO₃, H₂CO₃, H₃PO₄.

- TPPT: Có 1 hay nhiều nguyên tử hiđro liên kết với gốc axit (- Cl, =S, =SO₄, -NO₃...)

- Phân tử axit gồm có một hay nhiều nguyên tử hiđro liên kết với gốc axit, các nguyên tử hiđro này có thể thay thế bằng các nguyên tử kim loại.

2. Công thức hoá học

- Gồm một hay nhiều nguyên tử hiđro và gốc axit.

Công thức chung: H_nA.

Trong đó: - H: là nguyên tử hiđro.

- A: là gốc axit.

3. Phân loại

- 2 loại:

+ Axit không có oxi: HCl, H₂S, HBr, HI, HF...

+ Axit có oxi: H₂SO₄, HNO₃, H₃PO₄, H₂CO₃...

4. Tên gọi

a. Axit không có oxi

Tên axit : Axit + tên phi kim + hiđric.

VD : - HCl : Axit clohiđric.

- H₂S : Axit sunfuhiđric.

HT

Hà Trâm Anh

18 tháng 11 2018 - olm

Thế nào là số nguyên số và hợp số ?cho ví dụ

ai nhanh mình tick nha cố lên

4

DY

Đặng Yến Ngọc

18 tháng 11 2018

số nguyên tố là các số tự nhiên >1,chỉ có 2 ước là 1 và chính nó

hợp số là các số tự nhiên >1,có nhiều hơn 2 ước

K

KAl(SO4)2·12H2O

18 tháng 11 2018

Số nguyên tố là số tự nhiên khác 0 chỉ có hai ước số dương phân biệt 1 và chính nó

VD: 13 chia hết cho 1 và 13

Các số có nhiều hơn 2 ước số dương được gọi là hợp số

VD: 16 chia hết cho 1, 2, 4, 8, 16

A

Aki

29 tháng 12 2017 - olm

giúp mình nữa nek

1.Phát biểu các dấu hiệu chia hết cho 2,cho 3,cho 5,cho 9.

2.Thế nào là số nguyên tố,hợp số?Cho ví dụ?

3.Thế nào là hai số nguyên tố cùng nhau?Cho ví dụ?

4.ƯCLN của hai hay nhiều số là gì?Nêu cách tìm.

5.BCNN của hai hay nhiều số là gì?Nêu cách tìm.

Nhan mình tick

1

NT

NGÁO Tai

29 tháng 12 2017

1/ Dấu hiệu chia hết cho 2 : Các số có chữ số tận cùng là số chẵn thì chia hết cho 2 và chỉ những số đó mới chia hết cho 2

Dấu hiệu chia hết cho 3 : Các số có tổng các chữ số chia hết cho 3 thì chia hết cho 3 và chỉ những số đó mới chia hết cho 3

Dấu hiệu chia hết cho 5 : Các số có chữ số tận cùng là 0 hoặc 5 thì chia hết cho 5 và chỉ những số đó mới chia hết cho 5

Dấu hiệu chia hết cho 9 : Các số có tổng các chữ số chia hết cho 9 thì chia hết cho 9 và chỉ những số đó mới chia hết cho 9

2/

Số nguyên tố : là số tự nhiên lớn hơn 1 , chỉ có hai ước là 1 và chính nó

VD : 2; 3 ;4 ..

Hơp số : là số tự nhiên lớn hơn 1 , có nhiều hơn hai ước

VD : 4 ; 6 ;9..

3/

Hai số nguyên tố cùng nhau là : Các số nguyên a và b được gọi là số nguyên tố cùng nhau nếu chúng có UwCLN là 1

VD : 2 và 13 ; 4 và 19 ..

4/

UWCLN của hai hay nhiều số là : số lớn nhất trong tập hợp các ƯC của các số đó

Cách tìm :

B1 : Phân tích mỗi số ra thừa số nguyên tố

B2 : Chọn ra các thừa số nguyên tố chung

B3 : Lấy lũy thừa nhỏ nhất của các thừa số nguyên tố rồi tính tích

5/

BCNN của hai hay nhiều số là : số nhỏ nhất khác 0 trong tập hợp các bội chung của các số đó

Cách tìm :

B1 : Phân tích các số ra thừa số nguyên tố

B2 : Chọn ra các thừa số nguyên tố chung và riêng

B3 : Lấy số mũ lớn nhất rồi tính tích của các thừa số nguyên tố đó

k mình nha ^^

TK

Tạ Khánh Linh

21 tháng 10 2016

thông tin là gì ? em hãy nêu một số ví dụ về thông tin và cách thức mà con người thu thập thông tin đó .

giúp mình đi ngày mai mình kiểm tra 45 phút rồi . ai trả lời nhanh nhất mình hứa sẽ tick cho người đó ngay !

#Tin học lớp 6

3

LH

Lưu Hạ Vy

21 tháng 10 2016

Thông tin là tất cả những gì đem lại sự hiểu biết về thế giới xung quanh (sự vật, sự kiện...) và về chính con người.ví dụ về thông tin:
+Tấm biển chỉ đường hướng dẫn em cách đi đến một nơi cự thể nào đó(tiếp nhận bằng thị giác)
+ Tín hiệu xanh đỏ của đèn tín hiệu giao thông trên đường phố cho em biết khi nào có thể qua đường(tiếp nhận bằng thị giác)
+ Tiếng trống trường báo cho em biết đến giờ ra chơi hay vào lớp(tiếp nhận bằng thính giác)
Ngoài ra,còn có thể tiếp nhận thông tin bằng các giác quan khác như mũi ngửi để phân biệt mùi hương,lưỡi nếm để nhận biết vị....

TT

Tin Tin

27 tháng 10 2016

thông tin là tất cả những gì đem lại sự hiểu biết về thế giới xung quanh và về chính con người

NN

Ngô Nhất Khánh

8 tháng 11 2015 - olm

tài nguyên của máy tính là gì?

cho ví dụ?

nhanh nhất và kể tên nhiều tài nguyên của máy tính nhất mình sẽ like

1

NN

Ngô Nhất Khánh

8 tháng 11 2015

ko có chuột và bàn phím đâu bạn

SN

Sunny Ngọc Diệp

13 tháng 11 2021 - olm

hoán dụ là gì ? lấy ví dụ cụ thể .

ai nhanh và đúng mik sẽ tick cho nha !

#Ngữ văn lớp 6

9

QC

Quang cường

13 tháng 11 2021

sao thg trả lời nhanh nhất ko đc k

là sao z bạn

lỡ bn fake của t thì sao

?

DN

Doãn Như Quỳnh

13 tháng 11 2021

Hoán dụ là gọi tên một sự vật , một hiện tượng hoặc một khái niệm bằng tên của một sự vật , một hiện tượng hoặc một khái niệm khác. Chúng có nhiều nét gần gũi với nhau để nhằm mục đích làm cho sự diễn đạt tốt hơn .

VD : Đội tuyển sở hữu một bàn tay vàng với khả năng bắt bóng cức giỏi.

\(\Rightarrow\)Biện pháp hoán dụ dùng thứ cụ thể để nói về thứ trừu tượng.