Đến nội dung

Hình ảnh

Một số vấn đề của tóan tổ hợp rời rạc và ứng dụng


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

#1
ducvipdh12

ducvipdh12

    Sĩ quan

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

CHUYÊN ĐỀ: Một số vấn đề của tóan tổ hợp rời rạc và ứng dụng

$\xi 1$ NGUYÊN LÝ DIRICHLET

Nguyên lý Dirichlet hay còn gọi là nguyên lý "chuồng và thỏ".Đây là nguyên lý thóat nhìn có vẻ đơn giản và hiển nhiên nhưng ứng dụng rất hiệu quả và to lớn trong chứng minh tóan học,đặc biệt là trong việc chứng minh về sự tồn tại của một đối tượng thỏa mãn tính chất nào đó

nguyên lý Dirichlet được phát biểu như sau:

Nếu nhốt $m.n+r$ ( $m,n,r$ là các số nguyên dương ) con thỏ vào $n$ cái chuồng thì phải có ít nhất một chuồng chứa không ít hơn $m+1$ con thỏ

Nhìn thóang qua thì có vẻ đơn giản và dễ hiểu nhưng áp dụng thì không hề dễ dàng.Phải biết linh hoạt trong việc chọn chuồng và thỏ mới thấy được tính "Dirichlet" trong đó 

Một số dạng áp dụng của nguyên lý Dirichlet:

-Phân chia tập hợp để tạo thành n-chuồng ( nội dung của phương pháp là chia đối tượng lớn thành nhiều đối tượng nhỏ )

-Xây dựng các n-chuồng theo đối tượng xuất phát ( nội dung của phương pháp là từ một đối tượng xuất phát mà mình đã chọn,ta lập luận để xây dựng các đối tượng tiếp theo )

-Xây dựng các dãy số ( nội dung của phương pháp là tạo ra các dãy số từ bài tóan. Sau đó áp dụng nguyên lý Dirichlet cho các số hạng của dãy số được chọn )

-Xây dựng bảng ( nội dung của phương pháp là lập các bảng, Sau đó áp dụng nguyên lý Dirichlet cho các hàng ( hoặc cột ) để suy ra tính chất cần thiết )

BÀI TẬP ÁP DỤNG:

1. Chứng minh rằng từ 5 số nguyên bất kỳ,luôn tìm được 3 số có tổng chia hết cho 3

2. Trong hình tròn $(C)$ có diện tích bằng 8 đặt 17 điểm phân biệt bất kì. Chứng minh rằng bao giờ cũng tìm được ít nhất 3 điểm tạo thành 1 tam giác có diện tích bé hơn 1

3. Trên mặt phẳng cho 5 điểm A,B,C,D,E có các tọa độ là các sô nguyên. Chứng minh rằng trong số các tam giác được tạo thành từ 5 điểm đó có ít nhất 3 tam giác có diện tích nguyên

4. Chứng minh rằng từ 52 số tự nhiên bất kì luôn chọn được 2 số sao cho tổng,hoặc hiệu của 2 số đó chia hết cho 100. Kết luận còn đúng không đối với 51 số?

5. Có 200 chiếc kẹo được chia cho 21 học sinh. Chứng minh rằng với mọi cách chia,luôn tồn tại hai học sinh có số kẹo như nhau ( kể cả được 0 chiếc kẹo )

6. Chứng minh rằng không tồn tại một đường thẳng không đi qua đỉnh và cắt các cạnh của một tam giác. Hỏi còn đúng không đối với trường hợp $2n+1$-giác

7. Chứng minh rằng trong 11 số tự nhiên tùy ý,luôn có thể chọn ra hai số có hiệu bình phương chia hết cho 20

8. Chứng minh rằng có thể tìm được số tự nhiên có dạng 201520152015...2015000...0 chia hết cho 1999

9. Viết $n$ số thành 1 hàng ngang. Chứng minh rằng hoặc có một số chia hết cho $n$ hoặc có một số số liên tiếp có tổng chia hết cho $n$ ( $n>1$ )

10. Trong một giải vô địch bóng đá có 10 đội tham gia,hai đội bất kì phải đấu với nhau đúng một trận. Chứng minh rằng tại mọi thời điểm của giải đấu,luôn có 2 đội có số trận đấu bằng nhau

 

$\xi 2$ NGUYÊN LÝ CỰC HẠN

 

nguyên lý cực hạn được phát biểu như sau:

Một tập hợp hữu hạn ( khác rỗng ) các số thực bất kì đều có phần tử lớn nhất hoặc phần tử nhỏ nhất

$(*)$ các trường hợp đặc biệt:

- Đối với một đa giác,các điểm đặc biệt là những điểm thuộc cạnh ( điểm biên ) , các đỉnh ( điểm cực biên ) hoặc các điểm mà tại đó có một đặc trưng nào đó đạt giá trị đặc biệt. Cũng có thể là trọng tâm,tâm tỉ cự,... của 1 hình

- Đối với một tập hợp sắp thứ tự, các điểm đặc biệt là những phần tử nhỏ nhất hoặc lớn nhất của tập hợp

- Một số điểm đặc biệt của trục số $0,1,-1,+\infty,-\infty$

- Đối với một bài tóan có điều kiện,các trường hợp xảy ra khi các biến có mặt bằng nhau hoặc xảy ra dấu đẳng thức trong các đánh giá của điều kiện

- Đối với một hàm số, các điểm đặc biệt là những điểm mà tại đó thì hàm sô không xác định, đạt cực trị,...

 Các trường hợp nói trên được gọi là các điểm cực hạn

 

BÀI TẬP ÁP DỤNG:

1. Chứng minh rằng bốn hình tròn có các đường kính là bốn cạnh của một tứ giác lồi thì phủ kín miền tứ giác đó

2. Chứng minh rằng phương trình $x^2-7y^2=0$ có nghiệm nguyên duy nhất $x=y=0$

3. Bảy người đi câu cá đã câu được 100 con cá. Biết rằng không có hai người nào câu được số cá như nhau. Chứng minh rằng có 3 người trong 7 người câu được câu được tổng số cá không ít hơn 50 con cá

4. Một quốc gia có 100 sân bay. Khoảng cách giữa các sân bay là khác nhau. Mỗi sân bay chỉ có một chuyến bay đến sân bay gần nhất. CMR không có sân bay nào có quá 5 chuyến bay đến

5. Chứng minh rằng trong 15 số nguyên dương thuộc $(2,3,...,1992)$ và đôi một  nguyên tố cùng nhau,có ít nhất 1 số nguyên tố

 

BÀI TẬP TỔNG HỢP VỀ TỔ HỢP RỜI RẠC,CÁC BÀI TÓAN LẬP LUẬN :

1. Có một số 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 trọng lượng của 2 quả cân đó

Hỏi có ít nhất mấy quả cân?

2. Mặt phẳng phân hoạch thành các tam giác đều bằng nhau sao cho 2 tam giác bất kì hoặc chỉ có đỉnh chung,hoặc chỉ có cạnh chung. Chứng minh rằng tồn tại một hình tròn chứa đúng 2005 đỉnh của các tam giác đó

3. Một đống sỏi có 2009 viên. Chia nó thành 2 phần 1 cách tùy ý. Đếm số sỏi trong mỗi phần rồi ghi lại tích của chúng. Lại chia 1 trong 2 đống sỏi nhỏ ( có số sỏi lớn hơn 1 ) thành 2 phần và ghi lại tích của số viên sỏi trong hai đống nhỏ mới thu được. Cứ làm như vậy cho đến khi thu được 2009 đống sỏi nhỏ mà mỗi đống có đúng một viên. Hãy tính tổng của tất cả các số được ghi lại

4. CMR với mọi $a,b\epsilon N*,(36a+b)(36b+a)$ không thể là một lũy thừa của 2


Bài viết đã được chỉnh sửa nội dung bởi ducvipdh12: 08-05-2015 - 20:46

FAN THẦY THÔNG,ANH CẨN,THẦY VINH :icon6: :icon6:

#2
ducvipdh12

ducvipdh12

    Sĩ quan

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

hi vọng mọi người ủng hộ,vẫn còn khá khá bài tập nhưng nhác gõ Latex nên để lần sau post tiếp,làm hết phần bài tập trên đã :))


FAN THẦY THÔNG,ANH CẨN,THẦY VINH :icon6: :icon6:

#3
congdaoduy9a

congdaoduy9a

    Sĩ quan

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

1) Ta có : Các số dư khi chia cho 3 là 0;1;2 .Theo nguyên lí Đirichlet thì có ít nhất hai số có cùng số dư .

Giả sử có ít ba số cùng số dư thì ta có tổng ba số đó chia hết cho 3.

Nếu chỉ có 2 số cùng số dư khi chia cho 3 ,theo nguyên lí Đirichlet sẽ có cả 3 số dư .Khi đó tổng ba số ấy sẽ chi hết cho 3 .(Có chỗ nào cần chỉnh sửa thì nói e,đây chỉ là tự làm nên a thông cảm :)) )

4) Em đã giải ở đây http://diendantoanho...ên/#entry557566

Kết luận không đúng với 51 số vì chúng có thể nằm trong 51 nhóm {0};{1;99};...;{49;51};{50}.Khi đó không có tổng hai số nào chia hết cho 100.


Bài viết đã được chỉnh sửa nội dung bởi congdaoduy9a: 08-05-2015 - 21:31


#4
the man

the man

    Thiếu úy

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

 

2. Trong hình tròn $(C)$ có diện tích bằng 8 đặt 17 điểm phân biệt bất kì. Chứng minh rằng bao giờ cũng tìm được ít nhất 3 điểm tạo thành 1 tam giác có diện tích bé hơn 1

8. Chứng minh rằng có thể tìm được số tự nhiên có dạng 201520152015...2015000...0 chia hết cho 1999

 

2.Chia hình tròn thành 8 phần có diện tích như nhau, mỗi phần có diện tích là 1

 Có 17 điểm được đặt trong 8 phần , 17 chia 8 = 2 dư 1 nên tồn tại ít nhất một phần chứa ít nhất 3 điểm 

 Đương nhiên, 3 điểm nằm trong một phần sẽ có diện tích nhỏ hơn 1 (đpcm)

8. $201520152015...2015000...0 = 201520152015...2015 \times 100...0 $

  Do $100...0$ và $1999$ nguyên tố cùng nhau nên ta cần chứng minh rằng tồn tại một số tự nhiên có dạng

  $201520152015...2015$ chia hết cho $1999$

Xét 2015 số có dạng sau:

    $2015$

    $20152015$

    $201520152015$

    .....

    $201520152015...2015$ (2015 nhóm 2015)

 Có 2015 số mà có 1999 số dư khi chia cho 1999 nên theo Nguyên lí Dirichle thì tồn tại 2 số có cùng số dư khi chia cho 1999. Gọi 2 số đó là 

           $a_m$ và $a_n$  $(1 \leq n<m \leq 2015)$ ($m,n$ là số nhóm 2015)

$\Rightarrow a_m-a_n \vdots 1999$

 $\Leftrightarrow 201520152015...2015000...0 \vdots 1999$ (m-n nhóm 2015, 4n chữ số 0)

 $\Leftrightarrow 201520152015...2015 \vdots 1999$   (m-n nhóm 2015)

 $\Rightarrow $ đpcm


"God made the integers, all else is the work of man."

                                                Leopold Kronecker


#5
congdaoduy9a

congdaoduy9a

    Sĩ quan

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

Bài 10: Các trận có thể các đội đá với nhau là 0;1;2;3;4;5;6;7;8;9 

Gía trị 0 và 9 không cùng xảy ra vì khi có đội chưa thi đá trận nào thì số trận không quá 8 và nếu đã có đội thi đá 9 trận thì không thể có đội chưa đá trận nào 

Vì vậy số trận mà mỗi đội gặp nhau có thể là 0;1;2;3;4;5;6;7;8 hoặc 1;2;3;4;5;6;7;8;9

Theo nguyên lí ddirrichlet thì có ít nhất hai đội bóng có cùng số trận

PS:Thấy mọi người bảo nên lập TOPIC mà chả ai trả lời cho sôi nổi ~~


Bài viết đã được chỉnh sửa nội dung bởi congdaoduy9a: 09-05-2015 - 19:10


#6
ducvipdh12

ducvipdh12

    Sĩ quan

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

Bài 10: Các trận có thể các đội đá với nhau là 0;1;2;3;4;5;6;7;8;9 

Gía trị 0 và 9 không cùng xảy ra vì khi có đội chưa thi đá trận nào thì số trận không quá 8 và nếu đã có đội thi đá 9 trận thì không thể có đội chưa đá trận nào 

Vì vậy số trận mà mỗi đội gặp nhau có thể là 0;1;2;3;4;5;6;7;8 hoặc 1;2;3;4;5;6;7;8;9

Theo nguyên lí ddirrichlet thì có ít nhất hai đội bóng có cùng số trận

PS:Thấy mọi người bảo nên lập TOPIC mà chả ai trả lời cho sôi nổi ~~

anh cũng thấy thế,phải sôi nổi mới có thể cung cấp thêm nhiều bài mới chơ hoang vắng thế này thì ~~


FAN THẦY THÔNG,ANH CẨN,THẦY VINH :icon6: :icon6:

#7
toile432000

toile432000

    Lính mới

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

1. Chứng minh rằng bốn hình tròn có các đường kính là bốn cạnh của một tứ giác lồi thì phủ kín miền tứ giác đó

Xét tứ giác lồi  ABCD và 1 điểm M thuộc miền trong hoặc nằm trên các cạnh của tứ giác đó. Ta có:

góc AMB+ góc BMC+ góc CMD+ góc DMA= 360 độ. Suy ra, tồn tại 1 trong 4 góc AMB, BMC, CMD, DMA có số đo lớn hơn hoặc bằng 90 độ.

Không mất tính tổng quát, giả sử góc CMD $\geq$ 90 độ nên M nằm trong hoặc trên đường tròn đường kính CD.

Suy ra đpcm!



#8
grigoriperelmanlapdi

grigoriperelmanlapdi

    Trung sĩ

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

Mấy bạn giúp mình chứng minh bài số học này bằng Dirichle với:

''Chứng minh rằng tồn tại số tự nhiên $k$ sao cho $1999^k - 1$ chia hết cho $104$.''


Bài viết đã được chỉnh sửa nội dung bởi grigoriperelmanlapdi: 10-05-2015 - 21:58


#9
hoanglong2k

hoanglong2k

    Trung úy

  • Điều hành viên THCS
  • 965 Bài viết

Mấy bạn giúp mình chứng minh bài số học này bằng Dirichle với:

''Chứng minh rằng tồn tại số tự nhiên $k$ sao cho $1999^k - 1$ chia hết cho $104$.''

Sử dụng định lí phi hàm Ơ-le ta có :

  $104=2^3.13\Rightarrow \varphi (104)=48$

Lại có $(1999,104)=1\Rightarrow 1999^{48}\equiv 1(\mod 104)$
           $\Rightarrow 1999^{48}-1$ $\vdots$ $104$
Vậy ...


#10
grigoriperelmanlapdi

grigoriperelmanlapdi

    Trung sĩ

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

bạn giải theo cách lớp 10 được không



#11
congdaoduy9a

congdaoduy9a

    Sĩ quan

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

Bài 5: Giả sử không có hai học sinh nào có số kẹo giống nhau .Chọn số kẹo mỗi học sinh là 0;1;2;...;20

Ta thấy 0+1+2+...+20>200 

Do đó ít nhất có hai học sinh có số kẹo giống nhau 

Chắc a đăng bài giải luôn để làm tài liệu chứ TOPIC nhạt quá  :(



#12
ducvipdh12

ducvipdh12

    Sĩ quan

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

Bài 5: Giả sử không có hai học sinh nào có số kẹo giống nhau .Chọn số kẹo mỗi học sinh là 0;1;2;...;20

Ta thấy 0+1+2+...+20>200 

Do đó ít nhất có hai học sinh có số kẹo giống nhau 

Chắc a đăng bài giải luôn để làm tài liệu chứ TOPIC nhạt quá  :(

chắc do hiện tại các thành viên đang bận rộn ôn luyện nên ít lên diễn đàn :))


FAN THẦY THÔNG,ANH CẨN,THẦY VINH :icon6: :icon6:

#13
dogsteven

dogsteven

    Đại úy

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

Mấy bạn giúp mình chứng minh bài số học này bằng Dirichle với:

''Chứng minh rằng tồn tại số tự nhiên $k$ sao cho $1999^k - 1$ chia hết cho $104$.''

Vì tập hợp số dư của $104$ là hữu hạn nên tồn tại hai số nguyên dương $a,b$ với $a>b$ sao cho $1999^a-1$ và $1999^b-1$ chia hết cho $104$

Khi đó $104\mid 1999^b(1999^{a-b}-1)$

Mà $(1999, 104)=1$ nên $1999^{a-b}-1$ chia hết cho $104$


Quyết tâm off dài dài cày hình, số, tổ, rời rạc.


#14
Namthemaster1234

Namthemaster1234

    Thiếu úy

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

 

4. CMR với mọi $a,b\epsilon N*,(36a+b)(36b+a)$ không thể là một lũy thừa của 2

 

Giả sử $(36a+b)(36b+a)=2^n$ ( n thuộc $N$ )

 

Đặt $(a,b)=d$ thì $a=da_1$ , $b=db_1$

 

$d^2(36a_1+b_1)(36b_1+a_1)=2^n$

 

$d^2 \mid 2^n$ hay $d^2=2^k$ (k thuộc $N$ )

 

$(36a_1+b_1)(36b_1+a_1)= 2^{n-k}$

 

$ (a_1,b_1)=1$ suy ra  $(36a_1+b_1)(36b_1+a_1)$ lẻ

 

hay $n=k$ hay $(36a_1+b_1)(36b_1+a_1)=1$

 

Vô lý vì $(36a_1+b_1)(36b_1+a_1)\geqslant 37^2$


Đừng lo lắng về khó khăn của bạn trong toán học, tôi đảm bảo với bạn rằng những khó khăn toán học của tôi còn gấp bội.
(Albert Einstein)

Visit my facebook: https://www.facebook.com/cao.simon.56

:icon6: :icon6: :icon6: :icon6: :icon6:


#15
VOHUNGTUAN

VOHUNGTUAN

    Hạ sĩ

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

Mấy bạn giúp mình chứng minh bài số học này bằng Dirichle với:

''Chứng minh rằng tồn tại số tự nhiên $k$ sao cho $1999^k - 1$ chia hết cho $104$.''

ĐỂ EM GIẢI CÁCH LỚP 9: Xét 105 số:  1999n;1999n+1;1999n+2;...;1999105+n thì theo nguyên lí điriclê, luôn tồn tại 2 số có cùng số dư khi chia cho 104.

                                                  đặt 2 số đó là 1999m;1999q (q>m)=> 1999q-m$\vdots 104$( đây là dpcm với k=q-m)


TOÁN HỌC LÀ LINH HỒN CỦA CUỘC SỐNG

 

VIỆC HỌC TOÁN SONG SONG VỚI CUỘC ĐỜI

!

 

(~~)  :ukliam2:  >:)  :ukliam2:  (~~)

:ukliam2:  :icon13:  :icon13:  :ukliam2:  :lol:  :mellow:  :D :mellow:   :lol:  :ukliam2:  :icon13:  :icon13:  :ukliam2: 

~O)  ~O)  ~O)
 

 


#16
VOHUNGTUAN

VOHUNGTUAN

    Hạ sĩ

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

Giả sử $(36a+b)(36b+a)=2^n$ ( n thuộc $N$ )

 

Đặt $(a,b)=d$ thì $a=da_1$ , $b=db_1$

 

$d^2(36a_1+b_1)(36b_1+a_1)=2^n$

 

$d^2 \mid 2^n$ hay $d^2=2^k$ (k thuộc $N$ )

 

$(36a_1+b_1)(36b_1+a_1)= 2^{n-k}$

 

$ (a_1,b_1)=1$ suy ra  $(36a_1+b_1)(36b_1+a_1)$ lẻ

 

hay $n=k$ hay $(36a_1+b_1)(36b_1+a_1)=1$

 

Vô lý vì $(36a_1+b_1)(36b_1+a_1)\geqslant 37^2$

THEO MÌNH HÌNH NHƯ ĐOẠN MÀU ĐỎ CÓ VẤN ĐỀ ĐÓ BẠN! NẾU a1 lẻ, b1 chẵn thì sao nhỉ? :ohmy:  :icon13:


TOÁN HỌC LÀ LINH HỒN CỦA CUỘC SỐNG

 

VIỆC HỌC TOÁN SONG SONG VỚI CUỘC ĐỜI

!

 

(~~)  :ukliam2:  >:)  :ukliam2:  (~~)

:ukliam2:  :icon13:  :icon13:  :ukliam2:  :lol:  :mellow:  :D :mellow:   :lol:  :ukliam2:  :icon13:  :icon13:  :ukliam2: 

~O)  ~O)  ~O)
 

 


#17
Pham Thuy 2000

Pham Thuy 2000

    Lính mới

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

1) Ta có : Các số dư khi chia cho 3 là 0;1;2 .Theo nguyên lí Đirichlet thì có ít nhất hai số có cùng số dư .

Giả sử có ít ba số cùng số dư thì ta có tổng ba số đó chia hết cho 3.

Nếu chỉ có 2 số cùng số dư khi chia cho 3 ,theo nguyên lí Đirichlet sẽ có cả 3 số dư .Khi đó tổng ba số ấy sẽ chi hết cho 3 .(Có chỗ nào cần chỉnh sửa thì nói e,đây chỉ là tự làm nên a thông cảm :)) )

4) Em đã giải ở đây http://diendantoanho...ên/#entry557566

Kết luận không đúng với 51 số vì chúng có thể nằm trong 51 nhóm {0};{1;99};...;{49;51};{50}.Khi đó không có tổng hai số nào chia hết cho 100.

Giúp em bài tổng quát này đc ko ạ: Chứng minh với 2n-1 số nguyên bất kì bao giờ cũng có n số có tổng là bội n



#18
Saturina

Saturina

    Hạ sĩ

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

Ai giúp em bài số 3 được không ạ?


$Em$ $đẹp$ $như$ $chiếc$ $cúp$ $Euro$ $2020$ $vậy$
$Vì$ $em$ $là$ $của$ $người$ $Ý$ $chứ$ $không$ $phải$ $Anh$ :(
:( :( 

 

$Thì$ $chả$ $thế$ $à$ $?$

 





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

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