百度作业网证明题一道 （构造与论证）
来源：学生作业帮 编辑：百度作业网作业帮 分类：数学作业 时间：2024/05/16 09:00:33
证明题一道 （构造与论证）
用数字0和1组成的88个数围成一圈,使得其中任意连续的32个数中最多有9个1.求证:这88个数中至多有24个1.
用数字0和1组成的88个数围成一圈,使得其中任意连续的32个数中最多有9个1.求证:这88个数中至多有24个1.
用反证法,
设:满足条件:"用数字0和1组成的88个数围成一圈,使得其中任意连续的32个数中最多有9个1"的数字圈中,1的个数多于24,不妨设有25个1.
从任意一个数开始,顺序取:第1---32个数为A组,33---64为B组,65--88这24个数为C组.
由于A,B组中1的个数都不超过9,故C组中1的个数必不小于7.由此推出:任意连续的24个数中1的个数必不小于7.
再次从任意位置开始,顺序取:1--24,25----48,49---72,73---88,分为4 组,由于前三组中1的个数都不小于7,即前三组中1的总数不少于21,故最后一组:73----88这18个数中,1的个数不得多于4个.由此,知任意连续的18个数中1的个数不得不得多于4.
再次从任意位置开始,顺序取:1--18,19---36,37---54,55---72,73--88.分为5 组,由于其中1的个数都不多于4,故88个数中1的个数的总数不多于20.这与假设有25个1 相矛盾.即满足条件: 时,其中1的个数至多有24个.
即证明命题成立.
设:满足条件:"用数字0和1组成的88个数围成一圈,使得其中任意连续的32个数中最多有9个1"的数字圈中,1的个数多于24,不妨设有25个1.
从任意一个数开始,顺序取:第1---32个数为A组,33---64为B组,65--88这24个数为C组.
由于A,B组中1的个数都不超过9,故C组中1的个数必不小于7.由此推出:任意连续的24个数中1的个数必不小于7.
再次从任意位置开始,顺序取:1--24,25----48,49---72,73---88,分为4 组,由于前三组中1的个数都不小于7,即前三组中1的总数不少于21,故最后一组:73----88这18个数中,1的个数不得多于4个.由此,知任意连续的18个数中1的个数不得不得多于4.
再次从任意位置开始,顺序取:1--18,19---36,37---54,55---72,73--88.分为5 组,由于其中1的个数都不多于4,故88个数中1的个数的总数不多于20.这与假设有25个1 相矛盾.即满足条件: 时,其中1的个数至多有24个.
即证明命题成立.