娱乐 【题解】数学算法挑战 斯芬克斯之谜

[Nemakori]

题目来源：

https://icpc.global/worldfinals/scoreboard/2023/scoreboards/46/finals46.pdf【ps:该题目在比赛中最终通过率为100%哦】
题解视频：

https://www.youtube.com/watch?v=EdCcwTZxD50（ICPC WF Luxor Solution Video: Problem W|A - Riddle of the Sphinx）【英文讲解，要不咱们还是看下面的吧】
题解：
①:a = ?
②:b = ?
③:c = ?
④:a + b + c = ?
⑤:a + 2b + 3c = ?

证明如下
(1): 带入①,②,③进④式，若④验证通过，则①，②，③，④正确，直接给出答案即可
(2):若经过步骤(1)之后仍然没有正确答案，那么证明①②③④中一定有一个错误，则⑤正确，带入①②③到⑤中，若⑤验证通过，则①②③⑤正确，直接给出正确答案即可
(3):若经过步骤(2)之后仍然没有正确答案，那么①②③中一定有错误，则④⑤正确，通过⑤-④得：b+2c = ?（记作⑥），带入②，③至⑥中，若⑥验证通过，则②③④⑤，解方程得到a的值即可
(4):若经过步骤(3)之后仍然没有正确答案，则证明②③中有错误，则①正确，则联立①④⑤可以解出一组解

其他解答：
(a,0,0)
(0,b,0)
(0,0,c)
(d1,d2,d3)
(e1,e2,e3)
若向量(d1,d2,d3)与(e1,e2,e3)中互相平行，且d1,d2,d3,e1,e2,e3 ≠0，且他们可以消去且仅仅可以消去一项【严谨数学说法，不重要：即④⑤加上①②③中任意一组向量，都可以构成一组三维向量空间的基】

 

以下为表彰名单：

首先是第一个回答出正确答案的 @367ddd【基本和题解一致】

评论链接：

https://sstm.moe/topic/358943-数学算法挑战-构造-斯芬克斯之谜/?do=findComment&comment=17788052

以及第二个给出正确回答的  @danielrosen4【没注意到是自然数-1分，能给出具体解法就更好了哦，但是除此之外没有什么问题】

评论链接：

https://sstm.moe/topic/358943-数学算法挑战-构造-斯芬克斯之谜/?do=findComment&comment=17788529

 

特别表彰：

暂时没发现问题，不过这是唯一一个用到依次询问条件的，感觉思路应该没问题，至少通过数位分离参数的解法是很有意思的

@刁刁茶茶丸

评论链接：

https://sstm.moe/topic/358943-数学算法挑战-构造-斯芬克斯之谜/?do=findComment&comment=17789718

 

下期预告：

解决了斯芬克斯之谜的云雾猫猫成为了勇者，被迫踏上了讨伐恶龙的旅途，不过讨伐恶龙的旅途并不顺畅，勇敢的旅行者啊，为了世界的和平，敬请期待吧【下期之前，我先学一下这个文本编辑器怎么用，我会做出一个更好的挑战哦】

[刁刁茶茶丸]

作答的时候就觉得自己的解法几乎是作弊了，因为可以让斯芬单次回答即包含全部3个谜底的信息

甚至可以有更简单的方法，例如第一问先（1,1,1）确认大致的数量级
第二问直接就可以完美地分离参数获知3个谜底

至于混淆，则可以重复提问一次，如果答案不同则再度重复提问来获得绝对正确的信息（X）

七月 18，由刁刁茶茶丸修改

[Nemakori]

刚刚，刁刁茶茶丸说道:

作答的时候就觉得自己的解法几乎是作弊了，因为可以让斯芬单个即包含全部3个谜底的信息

甚至可以有更简单的方法，例如第一问先（1,1,1）确认大致的数量级
第二问直接就可以完美地分离参数获知3个谜底

甚至可以每次提问都重复一遍保证正确性，就这样还省下一次提问（x）

因为原题有数据范围限制 所以我当时都没往这想过w 思路比较新颖 我也很难断言有没有错 不过至少我认为是没有错的

[IOPU]

原来是acm啊,那没事了,这方面喊小学那会的我来都比现在的我强

[367ddd]

其实我那答案都有点问题来着，看到楼下 @danielrosen4的条件才意识到我给的描述有问题，我以为的条件是a4，a5和a1到a3任意揪一个出来组成线性无关就行了，实际上111,123这个配置是更强一点的任选三组线性无关了。

顺带一提，这位的题解其实更简单，求行列式即可

我们假设询问k11，k21，k31得到的答案是n1，那么我们合并记为向量p1。

若p1，p2，p3，p4均为正确答案，则由于p1，p2，p3的k线性无关易知，通过p1，p2，p3的线性组合，我们可以得到p4，那么p1到p4组成的矩阵行列式为0

这时我们再考虑p1到p4中混入了一个错误答案的情况，由于行的交换不影响绝对值，所以我们不妨再假设错误的是p4，错误答案为n4+m，m≠0，则根据行列式的定义得知，此时p1到p4组成的行列式的绝对值等于0+[ m x（k11k21k31到k13k23k33组成的矩阵的行列式）]的绝对值，由于我们给的询问条件是任取三组线性无关，所以k11k21k31到...的矩阵行列式不等于0，由于m也不等于0，则可得，在混入错误答案的情况时，行列式不等于0。

也就是说，按daniel这位取的五组方程组来构建矩阵，有且仅有全部正确的一组，行列式计算为0，在这一组中任取三个方程，由于线性无关，易知可以求解

53 分钟前，刁刁茶茶丸说道:

作答的时候就觉得自己的解法几乎是作弊了，因为可以让斯芬单次回答即包含全部3个谜底的信息

甚至可以有更简单的方法，例如第一问先（1,1,1）确认大致的数量级
第二问直接就可以完美地分离参数获知3个谜底

至于混淆，则可以重复提问一次，如果答案不同则再度重复提问来获得绝对正确的信息（X）

顺带一提，阁下这个解法有一个问题，如果第一问斯芬克斯就给出了非常离谱的数量级错误呢？例如给出的错误答案是10，实际上每个变量都达到了10^100数量级这种恐怖的差距？至少应该改成先问两次1,1,1来确认最大数量级，在第三问才进行变量分离吧

[Nemakori]

1 小时前，IOPU说道:

原来是acm啊,那没事了,这方面喊小学那会的我来都比现在的我强

不过我早就没接触算竞了啦，这个题是之前看见有意思就去试着想了一下，不过里面有些题目确实挺有意思的，而且不需要太多数学和算法基础，佬可以试试下一场，下一场就不是来源于算竞了，题目来源是某个游戏，但是我感觉可能数学要求要稍高一些QwQ

[Nemakori]

1 小时前，367ddd说道:

其实我那答案都有点问题来着，看到楼下 @danielrosen4的条件才意识到我给的描述有问题，我以为的条件是a4，a5和a1到a3任意揪一个出来组成线性无关就行了，实际上111,123这个配置是更强一点的任选三组线性无关了。

顺带一提，这位的题解其实更简单，求行列式即可

我们假设询问k11，k21，k31得到的答案是n1，那么我们合并记为向量p1。

若p1，p2，p3，p4均为正确答案，则由于p1，p2，p3的k线性无关易知，通过p1，p2，p3的线性组合，我们可以得到p4，那么p1到p4组成的矩阵行列式为0

这时我们再考虑p1到p4中混入了一个错误答案的情况，由于行的交换不影响绝对值，所以我们不妨再假设错误的是p4，错误答案为n4+m，m≠0，则根据行列式的定义得知，此时p1到p4组成的行列式的绝对值等于0+[ m x（k11k21k31到k13k23k33组成的矩阵的行列式）]的绝对值，由于我们给的询问条件是任取三组线性无关，所以k11k21k31到...的矩阵行列式不等于0，由于m也不等于0，则可得，在混入错误答案的情况时，行列式不等于0。

也就是说，按daniel这位取的五组方程组来构建矩阵，有且仅有全部正确的一组，行列式计算为0，在这一组中任取三个方程，由于线性无关，易知可以求解

顺带一提，阁下这个解法有一个问题，如果第一问斯芬克斯就给出了非常离谱的数量级错误呢？例如给出的错误答案是10，实际上每个变量都达到了10^100数量级这种恐怖的差距？至少应该改成先问两次1,1,1来确认最大数量级，在第三问才进行变量分离吧

具体通解的话 可以看我题解的通解范围 虽然可能有遗漏的 但是范围内应该是充分的

[刁刁茶茶丸]

1 小时前，367ddd说道:

其实我那答案都有点问题来着，看到楼下 @danielrosen4的条件才意识到我给的描述有问题，我以为的条件是a4，a5和a1到a3任意揪一个出来组成线性无关就行了，实际上111,123这个配置是更强一点的任选三组线性无关了。

顺带一提，这位的题解其实更简单，求行列式即可

我们假设询问k11，k21，k31得到的答案是n1，那么我们合并记为向量p1。

若p1，p2，p3，p4均为正确答案，则由于p1，p2，p3的k线性无关易知，通过p1，p2，p3的线性组合，我们可以得到p4，那么p1到p4组成的矩阵行列式为0

这时我们再考虑p1到p4中混入了一个错误答案的情况，由于行的交换不影响绝对值，所以我们不妨再假设错误的是p4，错误答案为n4+m，m≠0，则根据行列式的定义得知，此时p1到p4组成的行列式的绝对值等于0+[ m x（k11k21k31到k13k23k33组成的矩阵的行列式）]的绝对值，由于我们给的询问条件是任取三组线性无关，所以k11k21k31到...的矩阵行列式不等于0，由于m也不等于0，则可得，在混入错误答案的情况时，行列式不等于0。

也就是说，按daniel这位取的五组方程组来构建矩阵，有且仅有全部正确的一组，行列式计算为0，在这一组中任取三个方程，由于线性无关，易知可以求解

顺带一提，阁下这个解法有一个问题，如果第一问斯芬克斯就给出了非常离谱的数量级错误呢？例如给出的错误答案是10，实际上每个变量都达到了10^100数量级这种恐怖的差距？至少应该改成先问两次1,1,1来确认最大数量级，在第三问才进行变量分离吧

是这样...所以我上面的留言里给了先验证数量级再获取信息的改良解法

[IOPU]

18 小时前，Nemakori说道:

不过我早就没接触算竞了啦，这个题是之前看见有意思就去试着想了一下，不过里面有些题目确实挺有意思的，而且不需要太多数学和算法基础，佬可以试试下一场，下一场就不是来源于算竞了，题目来源是某个游戏，但是我感觉可能数学要求要稍高一些QwQ

我初中数学都没学好,我就是飞舞,写不了一点

[fakeclouds]

我觉得其实就是找冗余信息的问题吧。如果考虑k1 k2 k3三个向量的话其实是不够的，还要考虑斯芬克斯的答案。所以真正考虑的向量是(k1,k2,k3,b)。我们可以要求五组k1 k2 k3组成的矩阵

k11 k12 k13

k21 k22 k23

k31 k32 k33

k41 k42 k43

k51 k52 k53 

中任选三个都是满秩的。

然后回答错误了一次的情况下，其实四个正确答案对应的(k1,k2,k3,b)是完全可以被互相表示的，也就是共线的。只需要找到四个共线性向量组合就好了。而之所以需要五个方程组是因为有一次错误，然后有三个变量，需要一个冗余来确定。我想到个进阶版的问题。

 

例如斯芬克斯有n个不知道的神秘数字(a1,a2,...,an)，但是你可以提供n个数字(k1,k2,...kn)了，他会告诉你k1*a1+...+kn*an的值。但是它在你提问的时候会给你最多m个错误答案。那这种情况下你最少要提问几次，才能求出正确的神秘数字。

下面是我的猜测

剧透

我个人的猜测是需要m+1+max(m,n)次。而求解的思路也是，找到1+max(m,n)个向量（每个向量的长度是n+1而不是n），使得这些向量组成矩阵的秩是n。这是矩阵的秩的介绍：https://baike.baidu.com/item/矩阵的秩/6285316

 

而之所以有个max(m,n），其实是考虑到n>=m和n<m的两种情况。

1.当n>=m的时候，只需要找到n+1个向量就可以了。

这里面存在且仅存在一组n+1个向量，他们组成矩阵的秩是n，这也就是斯芬克斯给的正确答案。

而自然的，剩下的那些答案是错误的。

 

 

2. 而当n<m的时候，我们则需要找到2m+1个向量。

因为我们考虑个极端的情况，如果我们只要了n+m+1个向量，我们找到的n+1个向量组成矩阵的秩是n。但是这n+1个向量完全可能都是斯芬克斯的谎言。

所以这种情况下，我觉得只能从2m+1个向量里找那m+1个正确答案。方法同样是选出m+1个向量，然后当他们组成矩阵的秩是n时，这些答案都是正确的。

 

 

十月 5，由fakeclouds修改

[l1ll5]

final 题还行... 我（队）在现场的一眼秒的做法是

(1,0,0)
(0,1,0)
(0,0,1)
(1,1,1)

问完这四组后再枚举一个能让矛盾唯一的第五个问题...

充分展示了对线代的不敏感...