Bài tập toán rời rạc 4

Tham khảo tài liệu bài tập toán rời rạc 4, khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Bài tập toán rời rạc 4Bài5:Chứngminhrằngtrongsố10ngườibấtkỳbaogiờcũngtìmđượchoặclà2ngườicócùngtổng sốtuổichiahếtcho16,hoặclàhaingườimàhiệuchiahếtcho16.Giải:Gọia0……a15làsốdưkhichiatuổicủa10ngườicho16=>ai€{0,1….15}vớii=0…15; TH1:Tachia16thành16=15+1=14+2=…………=8+8=0+0;=>Cótấtcảlà9cặptrongkhiđócó10người.TheonguyênlýDirichlet=>tồntại2tổngsố cácaithuộccùng1tổng>Luôntìmđược2ngườicótổngsốtuổichiahếtcho16. TH2:Docó10ngườimàlạicó15sốdư>Tồntại2ngườicócùng1sốdưkhichiatuổicủahọcho16Suyraluôntồntạiai=aj>Tìmđược2ngườimàhiệusốtuổicủahọchiahếtcho16. Bài6: Cầncóítnhấtbaongiêubộcóthứtựgồm2sốnguyên(a,b)saochochắcchắntìmđược trongsốhaibộ(c,d)&(e,f)spchoce&dflàcácsốcótậncùngbằng0.Giải:Taxétcặp(a,b)bấtkỳ.Chiacáccặpnàythành10nhómcósốdưcủaakhichiacho 10là0,……9;Vậy2cặp(a1,a2)&(a3,a4)trongcùng1nhómthìa1&a3cùngsốdưkhichiacho10.Dođóchỉcầntìmcặp(a,b)saochoítnhất1trong10nhómtrên>ítnhấtlà11cặp.Trongnhómvừanêntrênsẽcó2cặp(c,d)&(e,f)saocho(ce)tậncùngbằng0và(df) tầncùng=0.Màcó10nhómnênđểtồntạiítnhất1nhómcóítnhất11cặpthìsốcặp(a,b)cầnchọn là:11*10+1=101.Bài7:17nhàbáchọcđôi1viếtthưtraođổichonhauvè3chủđề,mỗicặpchỉtraođổi vớinhauvề1chủđề.Chứngminhrằngluôntìmđược3nhàbáchọcđôimộtviết thưtraođổivớinhauvềcùng1chủđề.Giảsửlấy1nhàbáchọcbấtkìlàa1viếtthưcho16báchọccònlại>docó3vấnđềcầntraođổinêntồntạiítnhất6nhàbáchọca1vấnđề1nào đó.Trong6nhàbáchọctrênlấyra1nhàbáchọcbấtkìlàa2.5ngườicònlạinếucó1nhàbáchọcviếtthưtraođổivớia2vềvấnđề1thìbài toánđãgiảiquyết.TaxétTH:a2viếtthưtraođổivới5ngườivề2vấnđềcònlại.Theonguyênlýdicrichlettồntai3ngườitraođổivớia2vềvấnđềnàođógọi làvấnđề2.Trong3ngườitraođổivềvấnđề2nếucó1ngườitraođổivấnđề2thìbài toánđượcgiải.Ngượclạinếukhôngcóaitrong3ngườiđótraođổivềvấnđề2thìchắcchắn họsẽtraođổivềvấnđề3.=>Bàotoánđãđượcgiải. Bài8:Trongkhônggiancho9điểmcótoạđộnguyên.Chứngminhrằngtrongsố9 điểmluôntìmđược2diểmsaochođoạnthẳngnốichúngđiquađiểmcótạođộ nguyên.Giải: Xét1diểmbấtkìtrongkhônggian(x,y,z).Do1giátrịxhoặcyhoặczchỉnhận1trong2giátrịchẵn,lẽ.>cótấtcảlà2*2*2=8bộmà(x,y,z)cóthểnhận.Vídụnhư(chẵn,chẵn,chẵn),(chẵn,chẵn,lẽ)…….Màtheobàirathìcótấtcảlà9điểm.TheonguyênlýDirichlethìtồntại2điểm cócùngtọađộchẵn,lẽ.=>trungđiểmcủađoạnthẳngnối2điểmđólàsốnguyên>dpcm