GỌI 6 TH ÀNH PHỐ ĐÃ CHO L À A,B,C,D,E,F+ X ÉT THÀNH PHỐ A .THEO NGU...

2) Gọi 6 th ành phố đã cho l à A,B,C,D,E,F

+ X ét thành phố A .theo nguyên l í Dirichlet ,trong 5 th nh ph à ố còn lại thì có ít nhất

3 th nh ph à ố

liên lạc được với A hoặc có ít nhất 3 th nh ph à ố không liên lạc được với A ( v ì nếu

số th nh ph à ố liên lạc được với A cũng không vượt quá 2 và số thành phố không liên

lạc được với A cũng không vượt quá 2 thì ngoài A , số thành phố còn lại cũng không

vượt quá 4 ) . Do đó chỉ xảy ra các khả năng sau :

 Khả năng 1 :

số thành phố liên lạc được với A không ít hơn 3 , giả sử B,C,D liên lạc được với A .

Theo đề bài trong 3 thành phố B,C,D có 2 thành phố liên lạc được với nhau . Khi đó 2

thành phố này cùng với A tạo thành 3 thành phố đôi một liên lạc được với nhau .

 Khả năng 2 :

số thành phố không liên lạc được với A , không ít hơn ,giả sử 3 thành phố không liên

lạc được với A là D,E,F . Khi đó trong bộ 3 thành phố ( A,D,E) thì D và E liên lạc được

với nhau ( v ì D,E không

liên lạc được với A )

Tương tự trong bộ 3 ( A,E,F) v à ( A,F,D) th ì E,F liên lạc được với nhau , F và D liên

lạc được với nhau và như vậy D,E,F l à 3 thành phố đôi một liên lạc được với nhau .

Vậy ta có ĐPCM

Cho tập A = { 1 ; 2 ; 3 ; ….; 16 } . Hãy tìm số nguyên dương k nhỏ nhất sao cho trong

mỗi tập hợp con gồm k phần tử của A đều tồn tại hai số phân biệt a, b mà a

²

+b

²

là một

số nguyên tố

HD : Nếu a , b chẵn thì a

²

+ b

²

là hợp số . Do đó nếu tập con X của A có 2 phần tử phân

biệt a,b m à a

²

+ b

²

là số nguyên tố thì X không thể chỉ chứa các số chẵn => K

Bây giờ ta đi chứng minh K = 9 là giá trị nhỏ nhất cần tìm của bài toán .

Thật vậy với tập con X gồm 9 phần tử bất kì của A luôn tồn tại 2 phần tử phân biệt

a,b m à a

²

+ b

²

l à số nguyên tố . Thật vậy : ta chia tập hợp A thành các cặp 2 phần tử

phân biệt a , b mà a

²

+ b

²

là số nguyên tố ,ta có tất cả 8 cặp l à : ( 1;4) , ( 2;3) , ( 5;8) ,

( 6;11) , ( 7; 10) , ( 9 ;16 ) , ( 12 ;13) , ( 14 ; 15 ) . Theo nguyên lí Dirichlet thì 9 phần

tử của X có 2 phần tử cùng thuộc một cặp => ĐPCM