构造相似三角形求最值(组合构造第1章容易求值5)
构造相似三角形求最值(组合构造第1章容易求值5)
2024-11-25 12:40:32  作者:猥琐大哥  网址:https://m.xinb2b.cn/know/jtf248576.html




【附】为便于有需要者编辑修改,特提供纯文本文档如下:

3、极端状态

所谓极端状态,是指组成对象的各个元素处于一种极端分布。比如,大多数元素都聚集在某处,各元素都处于某区域的边界,一部分元素的取值相对很大而另一部分元素的取值又相对很小等等。极端状态,通常能使某种操作易于进行或某种状态易于实现。

例8、在n×n棋盘中(n≥3),将某r个方格染红色,其余方格染白色。规定:如果某个白格至少两个红格相邻(具有公共边),则将此格染红色。如果还有这样的白格则染色继续进行。若不论怎样选取最初哪r个格染红色,都不能通过上述操作使棋盘中所有格都染红色,求r的最大值。

分析与解:取有公共边界的两个方格染红色,若不借助其他的红格,还不能按其规则使某个白格染红色。而若取其对角上有公共点的两个方格染红色,则不借助其他的红格,还可按其规则使2个白格染红色。由此可见,如果红色的格是对角分布,则易于使棋盘中的白格按其规则染红色。这样便得到构造,取位于棋盘对角线上的n个格染红色,则按其规则,可使棋盘中所有格染红色,于是r≤n-1。

当r=n-1时,我们证明:不论怎样选取最初哪r个格染红色,都不能按规则使棋盘中所有格都染红色。我们给出两个证法。

证法1:考察红色区域的边界,最初的n–1个红色方格形成的红色区域边界的总长不大于4n–4。每新染一个红色格,此格在染色前至少有两条红色边,这两条边为红色区域的边界。此格染红后,最多增加两条红色边,但原来两条红色边不再在红色区域的边界上,所以红色区域边界上红色边的总长度不增。注意到所有格都染红色后红色区域边界的总长度为4n,故目标状态不能实现。

证法2:若方格A受红色方格B的影响而被染红,则将A,B的中心连线段。这样的线段连接的是两个相邻格,每一行(列)的格至多连n–1条线段,所以线段的条数至多为2n(n–1)。而某格染红至少占用2条线段,所以至多·2n(n–1)=n(n–1)个格受影响而被染红。要使棋盘全染红,最初至少染红n2–n(n–1)=n>n-1个方格。

综上所述,r的最大值是n–1。

例9、用S(A)表示集合A中所有元素之和,设X={a1,a2,… ,a11},其中a1<a2<…<a11为自然数。若对任何自然数n≤1500,存在X的子集A,使S(A)=n。求满足上述要求的a10的最小值。

分析与解:为了求a10的最小值,由a10=S10-S9,需要找到常数a、b,使S10≥a,S9≤b。于是考察:Sk=a1 a2 … ak (k=1,2,… ,11),由于存在S(A)=1500,所以S(X)≥S(A)=1500,即S11≥1500。又S1<S2<…<S11,所以必存在m,使 Sm-1<1500≤Sm。

对k=2,3,… ,m,考察数Sk-1 1,由上面讨论可知,它不大于1500,于是必存在集合A,使S(A)=Sk-1 1。但S({a1,a2,… ,ak-1})=Sk-1,所以ak≤Sk-1 1(k=2,… ,m)……(1)

否则,S({ak})>Sk-1 1,S({a1,a2,… ,ak-1})<Sk-1 1。注意到{a1,a2,… ,ak-1}与{ak}之间不存在子集,对于集合P,若P不含ak,ak 1,… ,a11中的任何一个数,则S(P)≥S({ak})>Sk-1 1,所以不存在A,使S(A)=Sk-1 1,矛盾。

由(1),有 Sk=Sk-1 ak≤2Sk-1 1……(2)

注意到存在S(A)=1,所以a1=1,由(2)迭代,得

Sk 1≤2(Sk-1 1)≤22(Sk-2 1)≤…≤2k-1(S1 1)=2k ……(3)

特别地,有Sm≤2m-1,所以,2m-1≥Sm≥1500,m≥11。

但|X|=11,有m≤11,所以,m=11。由此可知,(2),(3)对k=2,3,… ,11都成立。

由(2),有Sk 1≤2Sk 1,所以(Sk 1-1)≤Sk。又Sk为自然数,所以Sk≥[Sk 1]。特别地,有S10≥[S11]≥[]=7500。

所以a10=S10-S9≥750-511=239(S9≤29-1=511)。

此估计太粗糙,无法使a10=239。利用起点后移,进行修正,有

a9 a10=S10-S8≥750-(28-1)=495。所以495≤a9 a10<2a10,a 10>247,a10≥248。

最后,构造合乎条件的集合X={a1,a2,… ,a11},使a10=248。注意到一个数n能用X中的若干项的和表示,与二进制的特征相近,于是可取1,2,4,8,16,32,64,128,256,…,但此时不包含248,应去掉256,补上248(这里采用了局部调整构造法,见第8章),此时248排列在第9项,还要在128与248之间补充一个数。

由二进制数的性质可知,用1,2,4,8,16,32,64,128可表出1~255中的所有数,于是,可补充一个小于255的尽可能大的数(一种极端情形),则表出的数将尽可能多,于是补充247。

注意到1~255中的所有数与247相加后得到248~502中的所有数,于是,1,2,4,8,16,32,64,128,247可表出1~502中的所有数。类似可知,1,2,4,8,16,32,64,128,247,248可表出1~750中的所有数,最后补充一个数750,则1,2,4,8,16,32,64,128,247,248,750可表出1~1500中的所有数。

综上所述,集合X合乎条件。故a10的最大值为248。

  • 蒸大米饭好吃的技巧(总结4个蒸米饭的小技巧)
  • 2024-11-25总结4个蒸米饭的小技巧淘米:淘米一般淘一两遍就可以了,因为米粒表面有很多营养泡米:淘好的大米将水分淋干,淋干后的大米和水以1:1.5的比例倒入盆中,浸泡半个小时左右加水:米和水的比例,最好为1:1.2增香:(1)在蒸米饭的。
  • 抗美援朝胜利留给我们的精神力量(致敬那场伟大的胜利)
  • 2024-11-25致敬那场伟大的胜利来源:中国新闻网微信公众号青山埋忠骨,山河念英魂2021年10月25日是抗美援朝出国作战71周年纪念日资料图:沈阳抗美援朝烈士陵园大门口,前来祭奠的市民孙昊声摄71年前的今天中国人民志愿军打响入朝后的。
  • 西兰花怎样做好吃(西兰花的做法)
  • 2024-11-25西兰花的做法食材:西兰花一棵,彩椒少许,盐,鸡精,香油,蚝油;西兰花用手掰成小朵,清洗干净;蚝油中加入水(水和蚝油1:1)、芝麻、淀粉、白糖,拌匀;切好香葱、大蒜、辣椒;西兰花放入开水中焯下捞出备用;锅中入油,烧。
  • 什么牌子的汽车蜡好(汽车蜡什么牌子好)
  • 2024-11-25汽车蜡什么牌子好随着人们经济实力的提高,很多人的家中就已经有了私家车,但汽车是已经需要保养的,而给汽车打蜡就是其中很关键的一步了那么汽车蜡什么牌子好呢?下面就跟着小编一起来看看2019汽车蜡十大排行榜吧10.标榜汽车。
  • 人类的科技会发展到极限吗(人类的科技水平会无限发展吗)
  • 2024-11-25人类的科技水平会无限发展吗人类的科技发展,可能是存在一个上限的这个上限有可能无法被打破,也有可能,是可以通过某些手段(虽然很难)来打破的一、形成上限的几种可能1、低效的信息传递方式人类的信息传递方式是比较低效的,这导致人类的技。
  • 关于exo的详细了解(韩网pann热议EXO)
  • 2024-11-25韩网pann热议EXO【pann】#EXO#预告的级别哇还以为是什么电影预告呢节奏像疯了一样12月13号以后续专辑LOVESHOT回归只看预告来猜测的话预想loveshot应该是历代级的有种杀.手电影的氛围实时三个热搜评论。
  • 大疆最新发布消息 更宁静更长续航
  • 2024-11-25大疆最新发布消息 更宁静更长续航2017-09-0110:28:48作者:高君义在今年的IFA展会上,大疆发布了Marvic系列的最新型号MarvicPro铂金版(MavicProPlatinum)新一代机型主要改善了其四轴驱动系统。
  • 发泡剂种类和原理介绍(发泡剂种类大全)
  • 2024-11-25发泡剂种类大全一、物理发泡剂物理发泡剂种类较多,如脂肪烃、氯代烃、氟氯烃和二氧化碳气体等,自20世纪50年代,一氟三氯甲烷(CFC-11)作为聚氨酯首选的发泡剂被广泛应用,因其对大气臭氧层有破坏作用,为了保护地球生。
  • 智慧校园电子班牌系统(打造智慧校园第一步)
  • 2024-11-25打造智慧校园第一步智慧校园是未来校园的蓝图,关乎师生校园生活的方方面面,涉及安全、健康和教育等领域其中,电子班牌作为展现学校日常工作、班级师生风采、家校共育的平台,是智慧校园实现的运用载体,也是智慧教育的一种体现全品A。
  • 盘点女神王祖贤的六部电影(女神王祖贤演的圣女的欲望)
  • 2024-11-25女神王祖贤演的圣女的欲望女神王祖贤,演绎过很多电影,其中尤为大家深刻记忆的,莫过于《倩女幽魂》但是今天我讲述的不是这一部,而是《阿婴》,也叫《圣女的欲望》这部电影里面,王祖贤饰演的是一个县官的女儿,叫阿婴小时候,阿婴的母亲,。
  • 让人忍不住一口气看完的美剧(今年第一部让我献上膝盖的美剧)
  • 2024-11-25今年第一部让我献上膝盖的美剧每分美剧原创,禁止转载!《心灵猎人》后,又一部从“变态连环杀手”着手的悬疑犯罪剧来了该剧在美国播出后,反响热烈,收视直破纪录,首播的平均收视人数为310万今天小编给大家推荐的就是它了——沉默的天使★★。