9月学术版征答

Newton1983

<>A题:</P>
<>农夫过河问题 </P>
<>有一个农夫带一条狼、一只羊和一棵白菜过河。如果没有农夫看管，则狼要吃羊，羊要吃白菜。但是船很小，只够农夫带一样东西过河。问农夫该如何解此难题,试用程序实现之!</P>
<P>B题:</P>
<P>投掷100次硬币，出现连续7次以上（含7次）同面（同正面或同反面）的概率是多大？</P>

<P>C题txy提供)</P>
<P>同余式 MM'= 1 (mod p) -------- (1) 其中p为奇素数,它的解的情形与性质,显然是使用中国剩余定理的一个重要问题.
设 M=np+r,M'=n'p+r',其中0&lt;r&lt;p,0&lt;r'&lt;p,则有
MM'=rr'(mod p),因此解同余式MM'=1 (mod p),只需考虑M与M'介于0与p之间的解.例如,p=13时,对应的解有
(M,M')=(1,1),(2,7),(3,9),(4,10),(5,8),(6,11),(7,2),(8,5),(9,3),(10,4),(11,6),(12,12).
其中(1,1)是显而易见的,无论p为何值,(1,1)都是(1)式的解,称为平凡解.人们更关心非平凡解的性质.美国著名数学家莱默(D.H.Lehmer,1905- )希望人们关注M与M'的奇偶性相反的解,将其解的个数记为Np.例如,N13=6,即(2,7),(5,8),(6,11),(7,2),(8,5),(11,6).
现在已经求出N3=0,N5=2,N7=0,N11=4,N13=6,N17=10,N19=4,N23=12,N29=18,N31=4.
由此可以归纳出:
当p=4n-1时,Np能被4整除,即Np=0 (mod 4);
当p=4n+1时,Np被4除余2,即Np=2 (mod 4).
这一猜想是否正确,尚未得知.</P>

txy

<>上边的C题好象有一些遗漏，本人再次补充。</P><>      有没有这样的k个同余式
                     n=a<SUB>1</SUB>(mod n<SUB>1</SUB>)
                     n=a<SUB>2</SUB>(mod n<SUB>2</SUB>)
                     ......
                     n=a<SUB>k</SUB>(mod n<SUB>k</SUB>)
    使得任一整数n至少满足其中之一?这是可以办到的.例如,任一整数n至少满足下列6个同余式之一:
    (1) n=1 (mod 2)      (2) n=1 (mod 3)       (3) n=2 (mod 4)
    (4) n=4 (mod 8)      (5) n=0 (mod 12)      (6) n=8 (mod 24)
    可以检验如下:
        如果n为奇数,则适合(1).
        如果 n为偶数,则n必为下列形式之一:
    n=24m,24m+2,24m+4,24m+6,24m+8,24m+10,24m+12,24m+14,24m+16,24m+18,24m+20,24m+22.其中m为任意整数.
        当 24m+4,24m+16,24m+22 时,适合(2)
        当 24m+2,24m+6,24m+10,24m+14,24m+18, 时,适合(3)
        当 24m+20 时,适合(4)
        当 24m,24m+12 时,适合(5)
        当 24m+8, 时,适合(6)
    这样的一祖同余式,称为覆盖同余式系.覆盖同余式系在数论中有很重要的应用.例如,我们可以用它证明:存在一个正整数k,使得
N=k2<SUP>n</SUP>+1对于每一个正整数n都是合数.
    首先,对于正整数n按照上面的覆盖同余式系进行分类.
        当n适合(1)时,n=2m+1,m为整数,于是N=k2<SUP>n</SUP>+1=2k4<SUP>m</SUP>+1,但是 4<SUP>m</SUP>=1(mod 3),从而 N=2k+1 (mod 3)
    只要适当选择k满足2k+1=0 (mod 3),就可以使 N 能被3整除,因而 N 为合数.解同余式 2k+1=0 (mod 3)得到 k=1 (mod 3).
    当n 适合(2)时,n=3m+1,m为整数.N=k2<SUP>n</SUP>+1=2k8<SUP>m</SUP>+1,但是 8<SUP>m</SUP>=1 (mod 7),从而 N=2k+1 (mod 7).
    只要适当选择k满足2k+1=0 (mod 7),就可以使 N 能被7整除,因而 N 为合数.解同余式 2k+1=0 (mod 7)得到 k=3 (mod 7).
同理,对于n 满足其余四个式子之一时,分别得出 k 应满足
    k=1 (mod 5),k=1 (mod 17),k=-1 (mod 13),k=16(mod 241)
    综上所述,只要k 满足下列同余式组
    k=1 (mod 3)
    k=1 (mod 5)
    k=3 (mod 7)
    k=-1 (mod 13)
    k=1 (mod 17)
    k=16 (mod 241)
就能对于任意正整数 n ,使得 N 能被3,5,7,13,17,241之一整除,即 N 为合数.
利用中国剩余定理可以解出上述同余式组的解为 k = 1207426 (mod 5592405 ) 即 k=5592405t+1207426 .其中 t 为任意整数.
取t=0,k=1207426,则有 N=1207426*2<SUP>n</SUP>+1,对于任何正整数 n 都是合数.
    覆盖同余式系不是唯一的.例如,下面的12个同余式也组成覆盖同余式系:
    n=1 (mod 3), n=2 (mod 4), n=5 (mod 6)
    n=4 (mod 8), n=0 (mod 9), n=0 (mod 12)
    n=0 (mod 16), n=3 (mod 18), n=3 (mod 24)
    n=33 (mod 36), n=8 (mod 48), n=15 (mod 72).
    一般地,如果覆盖同余式系
    n=a<SUB>1</SUB>(mod n<SUB>1</SUB>)
    n=a<SUB>2</SUB>(mod n<SUB>2</SUB>)
    ......
    n=a<SUB>k</SUB>(mod n<SUB>k</SUB>)
中,c=n<SUB>1</SUB>&lt;n<SUB>2</SUB>&lt;...&lt;n<SUB>k</SUB>,则 c 越大,找到覆盖同余式系的难度越大.已经找到了 c=3,6,8,10,14,18,20 所对应的覆盖同余式系.数学家厄特希猜想:对于任意大的正整数 c 都有覆盖同余式系存在.并悬赏500美元征求这个猜想的解决-------证明它或推翻它!
    厄特希还认为:当模 n1,n2,...nk都是大于1的各不相同的奇数时,这样的覆盖同余式系是不存在的.但是数学家赛尔弗里奇(J.L.Selfridge)则宁愿悬赏500美元征求这种覆盖同余式系存在的例子.究竟如何,尚待解决.</P><>           我希望大家踊跃参加答题，这是我们的挑战，苹果在前面！！！[em02]</P>

txy

<>我们数学爱好者永远支持 学术杂谈！！！！！！！！！！！！！！</P>

Newton1983

<>农夫过河问题 </P><>有一个农夫带一条狼、一只羊和一棵白菜过河。如果没有农夫看管，则狼要吃羊，羊要吃白菜。但是船很小，只够农夫带一样东西过河。问农夫该如何解此难题？ </P><>分析：以向量（人，狼，羊，菜）表示状态，其中每个变元可取0或1，取0表示在左岸（出发点），取1表示在右岸，则我们有八个规则：
（0，*，*，*）---&gt;（1，*，*，*） （1）
（0，0，*，*）---&gt;（1，1，*，*） （2）
（0，*，0，*）---&gt;（1，*，1，*） （3）
（0，*，*，0）---&gt;（1，*，*，1） （4）
（1，*，*，*）---&gt;（0，*，*，*） （5）
（1，1，*，*）---&gt;（0，0，*，*） （6）
（1，*，1，*）---&gt;（0，*，0，*） （7）
（1，*，*，1）---&gt;（0，*，*，0） （8）
注：每个*号可以是任意的0或1，但是在每条规则内部，左边和右边的对应*号应取相同值。
将这八个规则存储在一个二维数组rule(8,4)中，易知该数组的内容是：
（1， 0， 0， 0）
（1， 1， 0， 0）
（1， 0， 1， 0）
（1， 0， 0， 1）
（1， 0， 0， 0）
（-1， 0， 0， 0）
（-1，-1， 0， 0）
（-1， 0，-1， 0）
（-1， 0， 0，-1）
初态是：（0，0，0，0），终态是：（1，1，1，1），
非法中间状态有：（0，0，1，1），（0，1，1，0），（0，1，1，1），
（1，1，0，0），（1，0，0，1），（1，0，0，0）。
相应的广度优先搜索算法的PASCAL程序如下：
program farmer(output);
{programmer: Cheng Zhengxian Date: 1995.1}
const rule:array[1..8,1..4] of -1..1=((1,0,0,0),(1,1,0,0),(1,0,1,0),(1,0,0,1),
(-1,0,0,0),(-1,-1,0,0),(-1,0,-1,0),(-1,0,0,-1));
type stype=string[4];
var s:array[1..100] of record
infstype;
rn:0..8;
father:integer;
end;
ob,mr:stype;
j,closed,open:integer;
procedure op;
var pre1,pre2,k,c:integer;
begin
writeln;writeln;c:=0;
k:=open;pre1:=s[k].father;s[k].father:=0;
repeat
pre2:=s[pre1].father;s[pre1].father:=k;
k:=pre1;pre1:=pre2;
until pre1=0;
k:=1;
repeat
writeln('Step ',c,':',s[k].inf20,s[k].rn:10);
k:=s[k].father;inc?;
until k=0;
readln;halt;
end;
function extend(var mr:stype):boolean;
var f:boolean;
k,x:integer;
ss:stype;
begin
ss:=s[closed].info;mr:='';f:=true;
for k:=1 to 4 do
begin
x:=ord(ss[k])-ord('0')+rule[j,k];
if (x&lt;0) or (x&gt;1) then f:=false;
mr:=mr+chr(x+ord('0'));
end;
extend:=f;
end;
function passchk:boolean;
var f:boolean;
k:integer;
begin
f:=true;
for k:=1 to 4 do
if ((mr[2]=mr[3])and(mr[2]&lt;&gt;mr[1])) or ((mr[4]=mr[3])and(mr[3]&lt;&gt;mr[1]))
then f:=false;
if f then
for k:=1 to open-1 do
if mr=s[k].info then f:=false;
passchk:=f;
end;
Begin {=========================main program=============================}
ob:='1111';
closed:=0;open:=1;
s[1].inf='0000';s[1].rn:=0;s[1].father:=0;
repeat
j:=0;closed:=closed+1;
repeat
j:=j+1;mr:='';
if extend(mr) and passchk then
begin
open:=open+1;
s[open].inf=mr;s[open].rn:=j;s[open].father:=closed;
if mr=ob then op;
end;
until j=8;
until closed=open;
writeln('No solution!');
End.
</P>

Newton1983

<>投掷100次硬币，出现连续7次以上（含7次）同面（同正面或同反面）的概率是多大？
大家好！我觉得你们还是把问题简单化了：
①、你们忽略了还有连续8次、9次、10次、……
②、其中有很多交叉的情形，如前7次连续的各种情况中，有很多在后面也出现连续7次以上。
③、可以用很少次的验证一下你们的方法，如抛5次，连续3次的概率是1/2，连续2次的概率是29/32，连续4次的概率是5/32，与你们的结论不符。</P><>这道题不是简单的题目
1.的确有7次以上连续出现的可能
2.连续出现可以是连续正面或者连续反面，同时要考虑“第一次出现连续出现的位置”也很难（因为我们只要观察到第一次连续出现就可以了）
3.个人认为，只有用模拟方法，用频率代替概率来做，永动机做的次数太少，不能用频率来代替，个人认为至少1000次以上吧……</P><>我用matlab编个模拟试一下看。 </P><P>matlb的m文件：toss_coin_simulation.m</P><P>n=input('please enter the experiment''s time:'); %输入试验次数%
a=0; %出现事件的试验次数%
for i=1:n
k=0; %连续出现同一面的次数%
for j=1:100
if k==7
a=a+1;
break;
end
y1=rand;
if y1&lt;=0.5
y1=0;
else
y1=1;
end
if j==1
y=y1;
end
if y1==y
y=y1; %若此次的面同上一次一样，则连续次数+1%
k=k+1;
else
y=y1; %若与上次的面不一样，连续次数清零%
k=0;
end
end
end
disp(a/n); %显示频率% </P><P>
关于程序的说明：
1.只要第一次有达到7次连续就记数，因为已经达到要求，事实上，超过7次连续或者有两段以上连续的都包含在里面了。
2.rand产生[0,1]上的均匀分布的随机数。[0.0.5]取反面(0)，(0.5,1]取正面(1)，0.5一个点根据连续型随机变量来说可以忽略，所以产生的0,1序列依旧是各0.5的概率出现。</P><P>程序运行结果
&gt;&gt; clear
&gt;&gt; toss_coin_simulation
please enter the experiment's time:100
0.3300</P><P>&gt;&gt; toss_coin_simulation
please enter the experiment's time:500
0.3140</P><P>&gt;&gt; toss_coin_simulation
please enter the experiment's time:1000
0.3170</P><P>&gt;&gt; toss_coin_simulation
please enter the experiment's time:2000
0.3210</P><P>&gt;&gt; toss_coin_simulation
please enter the experiment's time:5000
0.3142</P><P>&gt;&gt; toss_coin_simulation
please enter the experiment's time:10000
0.3105</P><P>&gt;&gt; toss_coin_simulation
please enter the experiment's time:100000
0.3169</P><P>求加权平均
(0.3300*100+0.3140*500+0.3170*1000+0.3210*2000+0.3142*5000+0.3105*10000+0.3169*100000)/(100+500+1000+2000+5000+10000+100000)</P><P>ans =</P><P>0.3163
可见事件概率在0.3163左右
(子青提供)</P>