📄 apsimon 的造币厂问题.htm
字号:
yes"> </span>上界<o:p></o:p></span></p><p class=MsoPlainText><b style='mso-bidi-font-weight:normal'><spanstyle='font-size:12.0pt;mso-bidi-font-size:10.0pt'>分类号 </span></b><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>520.1040<bstyle='mso-bidi-font-weight:normal'><o:p></o:p></b></span></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><![if !supportEmptyParas]> <![endif]><o:p></o:p></span></p><p class=MsoPlainText><b style='mso-bidi-font-weight:normal'><span lang=EN-USstyle='font-size:12.0pt;mso-bidi-font-size:10.0pt'>1<span style="mso-spacerun:yes"> </span>问题简介及主要结果<o:p></o:p></span></b></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><![if !supportEmptyParas]> <![endif]><o:p></o:p></span></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><span style="mso-spacerun: yes"> </span>艾波西蒙(ApSimon)于1984年在他所写的一本书<sup>[1]</sup>中,介绍了下面的造币厂问题:<o:p></o:p></span></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><span style="mso-spacerun: yes"> </span>n 个造币厂生产同一种硬币,但其中某些厂由于材料问题造出了非标准的硬币.设标准的硬币重c克(已知),非标准的硬币只有一种重量,重c(1+e)克,其中e是个不为0的未知数,可以取正数或负数.为了查出哪些厂生产的硬币是非标准的,从各厂中抽出一些样品(个数不限)放在一起进行称重,只能称2次.设a<sub>i</sub>,b<sub>i</sub>(i=1,...,n)分别为第一次,第二次称重从第i个厂中取得的样品个数.每个厂提供的样品或者都是标准的,或者都是非标准的.设p<sub>n</sub>=∑max(a<sub>i</sub>,b<sub>i</sub>)为某一称重方案的样品总数,求一种使p<sub>n</sub>最小的称重方案(参看<sup>[3]</sup>).<o:p></o:p></span></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><span style="mso-spacerun: yes"> </span>其中∑表示对于i从1到n求和,即∑<sub>i=1,</sub></span><sub><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt;font-family:"Courier New";mso-ascii-font-family:宋体;mso-bidi-font-family:"Times New Roman"'>…</span></sub><sub><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>,n</span></sub><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>(以下同).<o:p></o:p></span></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><span style="mso-spacerun: yes"> </span>艾波西蒙给出了以下结果:<o:p></o:p></span></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><span style="mso-spacerun: yes"> </span>(1) 若取 b<sub>i</sub>=1,a<sub>i</sub>=i!,(i=1,...,n),则问题必有解.<o:p></o:p></span></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><span style="mso-spacerun: yes"> </span>(2) 对于n=3,4,5,有:<o:p></o:p></span></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><span style="mso-spacerun: yes"> </span>min(p<sub>3</sub>)=4,a<sub>i</sub>取为(0,1,2), b<sub>i</sub>取为(1,1,0).<o:p></o:p></span></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><span style="mso-spacerun: yes"> </span>min(p<sub>4</sub>)=8,a<sub>i</sub>取为(0,1,1,4),b<sub>i</sub>取为(2,0,1,1).<o:p></o:p></span></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><span style="mso-spacerun: yes"> </span>min(p<sub>5</sub>)=15,a<sub>i</sub>取为(1,0,1,4,5),b<sub>i</sub>取为(1,2,2,5,0).<o:p></o:p></span></p><p class=MsoPlainText><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>根据上述结果<spanlang=EN-US>,艾波西蒙提出了2个问题:<o:p></o:p></span></span></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><span style="mso-spacerun: yes"> </span>A.1<spanstyle="mso-spacerun: yes"> </span>是否对每一个n,均有min(p<sub>n</sub>)≤2<sup>n-1 </sup>?<o:p></o:p></span></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><span style="mso-spacerun: yes"> </span>A.2<spanstyle="mso-spacerun: yes"> </span>min(p<sub>n</sub>)=?<o:p></o:p></span></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><span style="mso-spacerun: yes"> </span>由于只经过2次称重,便可在n个厂中找出所有生产非标准硬币的工厂,故这一问题在理论上和实际应用中(例如测试技术)都具有较大的意义.但该问题迄今仍未解决.1994年,在著名的《TheAmerican Mathematical Monthly》的"Unsolved Problems"栏目,R.Guy<sup>[2]</sup>给出了用计算机得到的以下结果:<o:p></o:p></span></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><span style="mso-spacerun: yes"> </span>min(p<sub>6</sub>)≤38,a<sub>i</sub>取为(1,1,2,3,5,8),b<sub>i</sub>取为(11,6,5,3,1,1);<o:p></o:p></span></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><span style="mso-spacerun: yes"> </span>min(p<sub>7</sub>)≤74,a<sub>i</sub>取为(0,1,3,6,10,15,21),b<sub>i</sub>取为(1,5,8,14,10,8,0).<o:p></o:p></span></p><p class=MsoPlainText><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>但这里的<spanlang=EN-US> 38,74 只是个上界,不是上确界, 由此不能否定问题 A.1.<o:p></o:p></span></span></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><span style="mso-spacerun: yes"> </span>本文介绍了作者在艾波西蒙问题上的研究进展:<o:p></o:p></span></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><span style="mso-spacerun: yes"> </span>L.1<spanstyle="mso-spacerun: yes"> </span>给出了n=6,7 时的更好的上界: min(P<sub>6</sub>)≤32,min(p<sub>7</sub>)≤64,当n=6时,a<sub>i</sub>,b<sub>i</sub>依次取为(8,6,6,0,4,1),(0,3,6,5,5,2),当n=7时,a<sub>i</sub>,b<sub>i</sub>依次取为(11,11,10,3,8,8,0),(0,2,2,9,9,8,6).这就关于n=6,7对问题A.1给予了肯定的回答.<o:p></o:p></span></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><span style="mso-spacerun: yes"> </span>L.2<spanstyle="mso-spacerun: yes"> </span>给出了一种解决问题A.2的计算机搜索算法,对于给定的n,按此算法可找出较好的p<sub>n</sub>,进而可找出min(p<sub>n</sub>).<o:p></o:p></span></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><span style="mso-spacerun: yes"> </span>这是目前在国内外文献上所见到的最好的结果.<o:p></o:p></span></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><![if !supportEmptyParas]> <![endif]><o:p></o:p></span></p><p class=MsoPlainText><b style='mso-bidi-font-weight:normal'><span lang=EN-USstyle='font-size:12.0pt;mso-bidi-font-size:10.0pt'>2 有关的分析<o:p></o:p></span></b></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><![if !supportEmptyParas]> <![endif]><o:p></o:p></span></p><p class=MsoPlainText style='text-indent:24.0pt'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>令<span lang=EN-US>d<sub>i</sub>(i=1,...,n)为对第i个厂检测的结果,若d<sub>i</sub>=0,表示第i个厂生产的硬币是标准的,d<sub>i</sub>=1,表示第i个厂生产的硬币是非标准的.U1,U2为两次称重的结果,则有:<spanstyle="mso-spacerun: yes"> </span>U1=∑c(1+d<sub>i</sub>e)a<sub>i</sub>,U2=∑c(1+d<sub>i</sub>e)b<sub>i</sub>, 由于 U1,U2,c为已知,令W1=U1/c,W2=U2/c,则有 W1=∑(1+d<sub>i</sub>e)a<sub>i</sub>,W2=∑(1+d<sub>i</sub>e)b<sub>i</sub>, ∑d<sub>i</sub>a<sub>i</sub>=(W1-∑a<sub>i</sub>)/e,∑d<sub>i</sub>b<sub>i</sub>=(W2-∑b<sub>i</sub>)/e,<span style="mso-spacerun:yes"> </span>令<span style="mso-spacerun: yes"> </span>R=<o:p></o:p></span></span></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>e∑d<sub>i</sub>a<sub>i</sub>=W1-∑a<sub>i</sub>, 令S=e∑d<sub>i</sub>b<sub>i</sub>=W2-∑b<sub>i</sub>.<o:p></o:p></span></p><p class=MsoPlainText style='text-indent:24.0pt'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>对于<span lang=EN-US>n个造币厂,每个d<sub>i</sub>均有2种可能(取0或1),故(d<sub>1</sub>,d<sub>2</sub>,...,d<sub>n</sub>)共有2<sup>n</sup>种不同的组合,如果R/S=(∑d<sub>i</sub>a<sub>i</sub>)/(∑d<sub>i</sub>b<sub>i</sub>)恰好有2<sup>n</sup>个不同的比值,便可和(d<sub>1</sub>,d<sub>2</sub>,...,d<sub>n</sub>)建立一一对应的关系,从而由R/S的值便可断定哪些厂生产的硬币是非标准的.于是问题转化为求(a<sub>1</sub>,a<sub>2</sub>,...,a<sub>n</sub>),(b<sub>1</sub>,b<sub>2</sub>,...,b<sub>n</sub>),使得对于(d<sub>1</sub>,d<sub>2</sub>,...,d<sub>n</sub>)的任何两组不同的值,均可得到R/S的两个不同的值.<o:p></o:p></span></span></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><![if !supportEmptyParas]> <![endif]><o:p></o:p></span></p><p class=MsoPlainText><b style='mso-bidi-font-weight:normal'><span lang=EN-USstyle='font-size:12.0pt;mso-bidi-font-size:10.0pt'>3<span style="mso-spacerun:yes"> </span>算法简介<o:p></o:p></span></b></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><![if !supportEmptyParas]> <![endif]><o:p></o:p></span></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><span style="mso-spacerun: yes"> </span>变量简介:<spanstyle="mso-spacerun: yes"> </span><o:p></o:p></span></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><span style="mso-spacerun: yes"> </span>samp:钱币样本总数(作为已知数据输入),<o:p></o:p></span></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><span style="mso-spacerun: yes"> </span>n:工厂数(已知),<o:p></o:p></span></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><span style="mso-spacerun: yes"> </span>a[i],b[i]:i=1,...,n,分别为第一次,第二次称重从第i个厂中取得的样品个数(作为结果输出).<o:p></o:p></span></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><span style="mso-spacerun: yes"> </span>m=[n/2],当i≤m时,a[i]≥b[i],当i>m时,a[i]≤b[i],并且,a[1]≥a[2]≥...≥a[m]≥b[m+1]≥...≥b[n],显然,应有:samp=a[1]+a[2]+...+a[m]+b[m+1]+...+b[n].<o:p></o:p></span></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><span style="mso-spacerun: yes"> </span>ss:记录已使用的样品总数.<o:p></o:p></span></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><span style="mso-spacerun: yes"> </span>算法 A.对于给定的a[i],b[i],及(d[1],d[2],...,d[n])的所有可能的取值,判断是否能得到2<sup>n</sup>个不同的R/S=(∑d[i]*a[i])/(∑d[i]*b[i])的值.<o:p></o:p></span></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><span style="mso-spacerun: yes"> </span>A-1 for i:=1to n do d[i]:=0;<o:p></o:p></span></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><span style="mso-spacerun:yes"> </span>t:=1;<spanstyle="mso-spacerun: yes"> </span>d[1]:=1;<span style="mso-spacerun:yes"> </span>计算rs1=R/S;<span style="mso-spacerun: yes"> </span>rj:=1;<spanstyle="mso-spacerun: yes"> </span>e[1]:=rs1;<o:p></o:p></span></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><span style="mso-spacerun: yes"> </span>A-2 whilet<2^n do<o:p></o:p></span></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><span style="mso-spacerun: yes"> </span>【 t:=t+1; t1:=t;<o:p></o:p></span></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><span style="mso-spacerun:yes"> </span>for i:=1 tomint do<o:p></o:p></span></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><span style="mso-spacerun:yes"> </span>【d[i]:=t1 mod 2;<span style="mso-spacerun: yes"> </span>t1:=t1 div 2 】;<o:p></o:p></span></p><p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><span style="mso-spacerun:yes"> </span>计算rs1;<o:p></o:p></span></p>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -