Nguyên Lý Dirichlet - CaolacVC

Có thể bạn quan tâm

Home
Contact
Edit

HomeBài toán hayNguyên lý Dirichlet Nguyên lý Dirichlet March 30, 2017 Dirichlet là nhà toán học người Đức (13/2/1805 - 5/5/1859) Nguyên lý Dirichlet về số con thỏ và chuồng thỏ là một trong những nguyên lý cơ bản, cực kỳ dễ hiểu và rất dễ hình dung bằng hình ảnh. Tuy đơn giản nhưng dựa vào nguyên lý này hàng loạt các vấn đề toán học được giải quyết. Đối với nguyên lý này người ta chỉ chứng minh được sự tồn tại chứ không chỉ ra được phương pháp tìm vật cụ thể. Tuy nhiên có một số vấn đề trong toán học chỉ cần chỉ ra sự tồn tại cũng là quá đủ rồi. Nội dung nguyên lý. Dạng 1: Có $n$ phần tử cho vào $k$ tập thì tồn tại ít nhất một tập có nhiều hơn$\left[\dfrac{n}{k}\right]+1$ phần tử. Trong đó $\left[\dfrac{n}{k} \right]$ là phần nguyên của $\dfrac{n}{k}$. Dạng 2: (Phát biểu theo kiểu ánh xạ) Cho hai tập $A,B$, trong đó tập $A$ có $n+1$ phần tử, tập $B$ có $n$ phần tử. Xét một ánh xạ đi từ $A\to B$. Khi đó tồn tại hai phần tử của $A$ có chung ảnh thuộc $B$ (tức là $\exists x_1,x_2 \in A : f(x_1)=f(x_2)$). "Để làm dạng toán này đầu tiên ta cần phải làm quen một số bài toán dễ cơ bản để làm nền và có cảm nhận, sau đó khi đọc bài toán ta phải tìm cách xây dựng được một mô hình mà ở đó có thể vận dụng được nguyên lý Dirichlet. Việc xây dựng được mô hình hợp lý logic để giải quyết bài toán phụ thuộc vào tư duy và lối logic của mỗi người, nó không tuân theo một quy tắc nào cả."

Một số bài toán ứng dụng của nguyên lý Dirichlet.

1. Một số bài toán ứng dụng trong thực tế.

Bài 1: Trong một hội trường có 400 đại biểu. Chứng minh rằng có ít nhất $2$ đại biểu có cùng ngày và tháng sinh. Tutorial. Một năm bất kỳ có nhiều nhất $366$ ngày (năm nhuận). Có $400$ đại biểu trong hội trường. Theo nguyên lý Dirichlet tồn tại ít nhất một ngày có nhiều hơn hai đại biểu được sinh. Tức là luôn có hai đại biểu sinh cùng ngày. Bài 2: Các nghiên cứu về sinh học chỉ ra rằng số tóc trên đầu của một người không vượt quá $200,000$ sợi. Chứng minh rằng trong số hơn $1,500,000$ người dân ở Bình Định luôn có ít nhất $8$ người có cùng số sợi tóc. Tutorial. "Một đề bài quá ảo diệu, nếu như tưởng tượng thì chắc khó mà tin, làm sao biết có $8$ người cùng số tóc? Gần như không thể kiểm chứng, nhưng bằng nguyên lý Dirichlet ta chỉ ra được là trên thực tế nó lại đúng @@." Bài 1: Chứng minh rằng một đường thẳng bất kỳ không đi qua đỉnh của một tam giác luôn cắt tối đa $2$ điểm nằm trên các cạnh của một tam giác. Ý tưởng: "Một bài toán đọc mang tính hiển nhiên quá cao, nhưng sử dụng nguyên lý Dirichlet ta lại dễ dàng chứng minh được" Một đường thẳng luôn chia mặt phẳng thành hai phần. Có $3$ đỉnh. Theo nguyên lý Dirichlet thì tồn tại một phần của mặt phẳng chứa nhiều hơn $2$ đỉnh. TH1: Chứa cả 3 đỉnh. Khi đó thì $(d)$ không cắt tam giác. TH2: Chứa $2$ đỉnh. Khi đó $(d)$ cắt tam giác tại hai điểm. Suy ra điều phải chứng minh. Bài 2: Giả sử trong mặt phẳng mỗi điểm tô một trong hai màu trắng hoặc đen. Chứng minh rằng tồn tại một hình chữ nhật có 4 đỉnh cùng màu. Ý tưởng: "Đây là đề thi Olympic dành cho sinh viên. Nếu như chưa tiếp cận thì việc đọc xong đề bài toán gần như ta không có một chút hình dung nào về nó cả, tóm lại là hại não. Vì bài toán không có bất kỳ một dữ kiện gì." Vì mỗi điểm trong mặt phẳng đều được đánh một trong hai màu trắng hoặc đen. Ta xét hình chữ nhật có kích thước $3\times 9$ o--o--o--o--o--o--o--o--o o--o--o--o--o--o--o--o--o o--o--o--o--o--o--o--o--o Xét trên cột thứ nhất. Có $3$ vị trí, mà mỗi vị trí chỉ được đánh một trong hai màu trắng hoặc đen. Theo nguyên lý Dirichlet thì tồn tại ít nhất một màu có nhiều hơn hai vị trí. (Nói dễ hình dung hơn là sẽ tồn tại hai điểm cùng màu.) Có tổng cộng $8$ cách tô màu cho $3$ vị trí. (Một vị trí là $2$, ba vị trí là $2^3=8$) Có $9$ cột. Có $8$ cách tô. Theo nguyên lý Dirichlet có ít nhất một cách tô có nhiều hơn hai cột. (Nói dễ hiểu là tồn tại $2$ cột được tô y chang nhau.) Vậy có $2$ cột được tô giống nhau, mà trên mỗi cột có $2$ điểm cùng màu. Suy ra có một hình chữ nhật có $4$ đỉnh cùng màu. (đpcm) Bài 3: Cho $6$ điểm không có $3$ điểm nào thẳng hàng. Mỗi đoạn thẳng nối $2$ điểm được tô một trong hai màu đỏ hoặc đen. Chứng minh rằng tồn tại một tam giác có các đỉnh cùng màu. Ý tưởng: Vì $6$ điểm không thẳng hàng nên $3$ điểm bất kỳ luôn tạo thành một tam giác. Giả sử $6$ điểm là $A,B,C,D,E,F$. Không mất tính tổng quát ta chọn $A$ làm gốc. Nối các đoạn $AB,AC,AD,AE,AF$. Có tổng cộng $5$ đoạn, mỗi đoạn có $2$ cách tô màu đỏ hoặc đen. Theo nguyên lý Dirichlet thì tồn tại ít nhất một màu tô nhiều hơn $3$ đoạn. Không mất tính tổng quát ta giả sử $3$ đoạn $AB,AC,AD$ được tô màu đỏ. Khi đó $3$ đoạn $BC,CD,DB$, với $2$ cách tô màu thì theo nguyên lý Dirichlet cũng tồn tại một màu được tô nhiều hơn $2$ đoạn. TH1: Nếu $BC,CD,DB$ được tô cùng màu đen. Tức tam giác $BCD$ thỏa yêu cầu bài toán. Ta có đpcm. TH2: Tồn tại ít nhất một cạnh màu đỏ. Không mất tính tổng quát giả sử là $BC$. Khi đó tam giác $ABC$ thỏa yêu cầu bài toán. Ta cũng có đpcm. Bài 4: Cho một tam giác đều cạnh là $1$. Chấm $5$ điểm phân biệt bất kỳ trong tam giác. Chứng minh rằng tồn tại ít nhất $2$ điểm có khoảng cách nhỏ hơn $0,5$. Ý tưởng: "Đây là một trong những bài nền tảng, nên nhớ làm nền để từ đó có thể vận dụng cho các bài tập phức tạp hơn" Chia tam giác đều thành $4$ phần bằng nhau. (Cách chia là lấy trung điểm của cạnh khi đó số tam giác đều được chia là $2^2=4$, mở rộng thì số tam giác đều được chia bằng nhau là một số chính phương. Tức là nếu ta chia cạnh thành $3$ phần bằng nhau ta sẽ được $9$ tam giác đều, tương tự cho $16,25,36\ldots$) Có $5$ điểm đặt vào $4$ tam giác đều. Theo nguyên lý Dirichlet thì tồn tại một tam giác đều chứ nhiều hơn hai điểm.(Nói dễ hình dung là tồn tại tam giác đều chứa $2$ điểm) Mà mỗi tam giác đều có cạnh lớn nhất là $0,5$. Ta suy ra đpcm. Một số bài tương tự. Bài 4.1 Trong một hình vuông cạnh $1$. Chấm $51$ điểm phân biệt. Chứng minh có $3$ điểm nằm trong đường tròn có bán kính $\dfrac{1}{7}$. Tags: 1000 Bài toán hay

admin

0 Comments

Vui lòng đăng nhập google để bình luậnĐể gõ công thức toán, hãy đặt [biểu thức toán] trong dấu $$Ví dụ: $[biểu thức toán]$

ĐỀ THPTQG MÔN TOÁN FILE WORD CÓ LỜI GIẢI

GÕ THUÊ $\LaTeX$

PHIẾU BTTN

FULL CÔNG THỨC

Tìm kiếm trong Blog

Tổng lượt truy cập

FULL KÍ TỰ LATEX

November 04, 2018 $WATERMARK TRONG LATEX$

WATERMARK TRONG LATEX

November 02, 2018

MỘT SỐ BÀI TOÁN HÌNH THÚ VỊ

December 17, 2018

CÁCH VẼ VÀ TỊNH TIẾN ĐỒ THỊ ĐẶC BIỆT

May 02, 2020 $DẤU NGOẶC TRONG LATEX$

DẤU NGOẶC TRONG LATEX

June 23, 2017

CaolacVC

Khi làm bất cứ việc gì, đừng bao giờ mâu thuẫn nội tại

05/10/2022: Đạt 500.000 lượt truy cập

11/11/2022: Lần đầu tiên trong 1 ngày đạt 2000 lượt truy cập

30/11/2022: Lần đầu tiên trong 1 ngày đạt 3400 lượt truy cập

Menu Footer Widget

Home
About
Contact Us

Created By | Distributed By Blogger Themes

Từ khóa » Nguyên Lý Dirichlet Và Bài Toán Tô Màu

Nguyên Lý Dirichlet - CaolacVC

Một số bài toán ứng dụng của nguyên lý Dirichlet.

1. Một số bài toán ứng dụng trong thực tế.

admin

You may like these posts

Post a Comment

0 Comments

Tìm kiếm trong Blog

Tổng lượt truy cập

Tags

Tags

FULL KÍ TỰ LATEX

WATERMARK TRONG LATEX

MỘT SỐ BÀI TOÁN HÌNH THÚ VỊ

CÁCH VẼ VÀ TỊNH TIẾN ĐỒ THỊ ĐẶC BIỆT

DẤU NGOẶC TRONG LATEX

CaolacVC

Menu Footer Widget

Ứng Dụng Nguyên Lí Dirichlet Vào Giải Bài Toán Tô Màu Hình - 123doc

Bài 06. Nguyên Lý Dirichlet Trong Các Bài Toán Về Tô Màu - Hocmai

Ứng Dụng Nguyên Lí Dirichlet để Giải Toán Tổ Hợp Hình Học Trong đề ...

[PDF] áp Dụng Nguyên Lý Dirichlet Vào Việc Giải Một Sôn Bài Toán Tôn Màu

Nguyên Lý Đirichlet Và áp Dụng - Toán Việt

Ứng Dụng Nguyên Lí Dirichlet Vào Giải Bài Toán Tô Màu Hình

[PDF] Nguyên Lí Dirichlet Và ứng Dụng Giải Toán Sơ Cấp

Các Bài Toán Về Nguyên Lý Dirichlet Trong Số Học

Ứng Dụng Nguyên Lý Dirichlet Trong Giải Toán Tổ Hợp THCS ôn Thi ...

[PDF] Nguyên Lí Dirichlet Và ứng Dụng Trong Các Dạng Toán Cơ Bản

Cơ Bản Về Nguyên Lý Đi-rích-lê - Toán Rời Rạc

Ứng Dụng Của Nguyên Lí Dirichlet Trong Các Dạng Bài Tổ Hợp , Trong ...

Ứng Dụng Nguyên Lí Dirichlet Vào Giải Bài Toán Tô Màu Hình

Liên Hệ