第四版杀拉五题串烧

22568

5.附加题.
显然(ceil(log[3](40*2-1))=)4是一个下界.
下面构造一个4的可行解..

	1	3	9	27
0
1	+
2	-	+
3		+
4	+	+
5	-	-	+
6		-	+
7	+	-	+
8	-		+
9			+
10	+		+
11	-	+	+
12		+	+
13	+	+	+
14	-	-	-	+
15		-	-	+
16	+	-	-	+
-17	+		+	-
-18			+	-
-19	-		+	-
20	-	+	-	+
-21		-	+	-
22	+	+	-	+
23	-	-		+
24		-		+
25	+	-		+
26	-			+
27				+
28	+			+
29	-	+		+
30		+		+
-31	-	-		-
-32	+	+	-	-
-33		+	-	-
-34	-	+	-	-
-35	+		-	-
-36			-	-
-37	-		-	-
-38	+	-	-	-
-39		-	-	-

上表为40个整数的"每个位均属于{-1,0,1}的四位三进制表达".
(换句话说,某行为n,a,b,c,d,则有n=a+3b+9c+27d.)
可以看出每列中+和-数量相同.
将40行分别对应40个苹果,四次称量分别看四列:将标了-的放在左边,将标了+的放在右边.
对每次称量,若左边轻则记为1,若左边重则记为-1,若一样重则记为0.
记四次称量的结果为a,b,c,d,记s=a+3b+9c+27d∈{-40,-39,...,39,40}.
所求坏苹果为编号±s那行对应的苹果.
至于s=±40?不存在的.

ps.其实我第一眼喵到这题就想到40=(1111)3了难道我会说

21457

引用

天马行空 发表于 2017-11-6 23:16
5.附加题.
显然(ceil(log[3](40*2-1))=)4是一个下界.
下面构造一个4的可行解..上表为40个整数的"每个位均 ...

基本把我想说的都给说了
连表格也是一样
构造一个4*40的矩阵，分别以+1,-1，0代表放在左盘右盘和不放，乘以一个元素为40的列向量，得到一个结果为4个元素的列向量。
其中要求该矩阵，使得每两个行向量不相等且不互为负向量，且不全为0。每一个列向量都有四个1、四个-1和四个0。
40元素列向量只有一个元素是1或者-1，其余为0.（1代表重，-1代表轻，当然也可以反过来表示）
4元素列向量只可能结果为-1,1,0（1代表左重，0代表平衡，-1代表右边重）
这样就可以保证一个结果向量（4个元素的列向量），一定能对应一个原向量（40个元素的向量），而该向量就是解。

21457

22L可能没说清楚，这里再细说一遍



对于称量结束后才知道称量结果的情况，可以用一个线性代数的模型解决
构造一个矩阵乘法AX=Y
其中A代表着称量方法，X代表苹果，Y代表称量结果
其中X=[x1;x2;x3;x4;x5;x6...x40]，x1到x40之间只有一个非0的数，且为1或者-1，而记1为重，-1为轻，这四十个数分别代表四十个苹果
Y=[y1;y2;y3;y4]，y1到y4之间均可能为1,0，-1，代表着称重的结果，其中1为左重，0为平衡，-1为右重。
于是我们的题目就变成，找到一个A(4行，40列的矩阵)满足AX=Y的运算，且对于每一种可能的X均有一个唯一的Y。

对于A而言，需要遵守下面四个规定：

1.每一个列向量不可以全0：不可以不把任何一个苹果一直不放到称上
2.每两个列向量不能互为线性关系，即任意两个列向量不能相等或者相反：不能有两个苹果被执行相同的称量操作，或完全相反的操作(例如：1苹果分别在四次称量中充当：“没被称，放右边，放右边，放左边”的角色，那么不能有苹果2，被执行“没被称，放左边，放左边，放右边”的操作，否则出来的结果无法分辨出是1苹果重，还是2苹果轻)
3.每个行向量中的1和-1的个数相等：必须保证天平左右两边的苹果个数相同，否则称量没有意义

对于矩阵A而言，40个列向量，每个向量4个元素。
每个向量4个元素，那么，总共有3^4=81种可能。
不能有全0的向量，那么，还有1-1=80种可能。
不能有相同和相反的向量，那么，还有80/2=40种可能。
正好足够题目中的40个向量。
故该矩阵A存在，因为各个向量之间等价，故A有多种解

22568

引用

shalamixi 发表于 2017-11-7 15:43
22L可能没说清楚，这里再细说一遍

我是来各种纠错的.

22LL中L可能没说清楚，这里再完整说一遍

引用

我们的题目就变成，找到一个A(4行，40列的矩阵)满足AX=Y的运算，且对于每一种可能的X均有一个唯一的Y。

错.事实上我们的问题是

引用

如何称4次，将“坏”苹果找出？

并没有要求指出坏苹果是重还是轻.所以是允许有双解的,只要俩解和为0.

引用

1.每一个列向量不可以全0：不可以不把任何一个苹果一直不放到称上

错.然而lz没有给出这么说的理由所以无法反驳.至少,我的答案就与此矛盾.(再次声明,题目不要求指出坏苹果是重还是轻.)

引用

对于矩阵A而言，40个列向量，每个向量4个元素。
每个向量4个元素，那么，总共有3^4=81种可能。
不能有全0的向量，那么，还有1-1=80种可能。
不能有相同和相反的向量，那么，还有80/2=40种可能。
正好足够题目中的40个向量。
故该矩阵A存在，因为各个向量之间等价，故A有多种解

这些并没有成为"A存在"的理由.事实上这是显然无解的:
lz提到的80个向量组成和为0的40对,lz从中取出40个且两两和不为0,故每对恰好取出一个.
仅考虑它们的第一个分量,显然有27个+1和27个-1和26个0,即27对(-1,+1)和13对(0,0).
lz取出的40个显然会有13个0和27个±1,显然不可能满足

引用

行向量中的1和-1的个数相等

ps.这也是我在我的解中留了一个0的苹果无法分辨轻重的理由.

综上,lz的卷子拿不了多少分.

21457

a=[1,1,1,1,1,1,1,1,1,-1,-1,-1,1,1,1,-1,1,-1,0,0,0,0,0,0,0,0,0,-1,-1,-1,-1,-1,-1,-1,-1,0,0,0,0;
   -1,0,1,-1,0,1,-1,0,1,-1,0,1,1,0,-1,-1,0,1,-1,0,1,-1,0,1,-1,0,-1,1,0,-1,1,0,-1,1,0,1,-1,0,1;
   -1,-1,-1,0,0,0,1,1,1,-1,-1,-1,0,0,0,1,-1,1,-1,-1,-1,0,0,0,1,1,-1,1,1,1,0,0,0,-1,-1,0,1,1,1;
   0,0,0,0,0,0,0,0,0,1,1,1,-1,-1,-1,1,-1,1,1,1,1,1,1,1,1,1,-1,-1,-1,-1,-1,-1,-1,-1,-1,0,0,0,0];
x=[0;0;0;0;
   0;0;0;0;
   0;0;0;0;
   0;0;0;0;
   0;0;0;0;
   0;0;0;0;
   0;0;0;0;
   0;0;0;0;
   0;0;0;0;
   0;0;0;];
y=a*x;
error=0;
for i=1:39
    x=[0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;];
    x(i,1)=1;
    z(:,i)=a*x;
end

for i=1:39
    x=[0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;];
    x(i,1)=-1;
    z(:,39+i)=a*x;
end

for i=1:78
    for j=i+1:78
        if z(:,i)==z(:,j)
            error = 1;
            e1=i;
            e2=j;
        end
    end
end

MATLAB还用的不熟，很多都是刚刚百度到的语法
以上的矩阵a是：
39个物品，可以分清轻重的称量方法
代码可以直接在MATLAB上跑，error为0
如果随意更改a中的一个数，error结果为1,
其他的还没有测试，不过a应该没有问题

56203

你们怎么这么聪明

54530

第一题，平均分成2份，然后立起来所有硬币。两边都是0个正面。

59146

把所有的硬币分成两堆并且都立起来 正面朝上的为零  可以吧