6
1
2017
0

Uyhip2017 May

好久好久没更uyhip辣。这次题目不算难就更一下吧。

题面:对哪些$n$,存在大小为$n$的Abel群$(G,+)$与三个$G\to G$的双射$A,B,C$,使得$\forall x\in G$,$A(x)+B(x)=C(x)$?如果不要求$G$是Abel群,只要求$G$是群呢?

题解在此

照着题解写一遍blog也没意思,所以我打算讲一点心路历程(雾)。

 

首先是我看到这题是某题的变种,那题要求$G$是循环群,然后稍微想一下就会发现很简单。$n$是奇数的情况$A,B$取成单位映射,$C:x\mapsto 2x$是双射;$n$是偶数的情况用一个算两次的思路就可以证明无解,具体地说把$n$个式子“$A(x)+B(x)=C(x)$”的左右加起来,会发现$n$整除$\frac{n(n-1)}{2}$,而$n$是偶数时这一点是做不到的。

那么根据uyhip的尿性,这题的答案当然也是$n$是奇数有解,偶数无解啦。我们用跟前面相同的方法证明$n$是偶数时无解,然后发现需要证明所有阶为$2$的元素的和不等于$0$。$n\equiv 2\pmod 4$是奇数的时候,阶为$2$的元素是唯一的,这个证明就很容易推过去;然而$n\equiv 0\pmod 4$时就遇到麻烦了。

然后我就开始手算$n=4$的例子(不能算循环群,显然要算${\mathbb{Z}}_2\times {\mathbb{Z}}_2$),没想到$n=4$居然有解(见题解)。然后我注意到这玩意是积性的($a$有解,$b$有解,那么$a\times b$有解),奇数有解$4$有解,那么所有$2^st$($s$是偶数)有解。我想如果$8$有解的话,有解的数的集合就是$s\ne 1$了,会显得更优美。于是我xjb玩了一下群${\mathbb{Z}}_2\times{\mathbb{Z}}_2\times{\mathbb{Z}}_2$,发现居然真的有解(见题解)。这样我们就确定了第一问的答案:无解当且仅当$n\equiv 2\pmod 4$。

第二问我想了好几个小时。因为群运算不交换了,上面的论述都狗带了。至于想的什么呢,都是往各种方面xjb想。。。这个确实也靠灵感。。最终还是抓住了$n\equiv 2\pmod 4$的一个性质(存在大小为$n/2$的子群$H\le G$)然后想了出来。我发现阶为$2$的元素$u$是唯一的,而且一个元素乘以$u$会改变它是否在$H$中这个属性。于是就可以把元素的这个属性$\chi(a)=[a\not\in H]$定义出来,然后发现$\chi(xy)\equiv \chi(x)+\chi(y)\pmod 2$,剩下的事情就是一个简单的算两次,最终能推出$\frac{n}{2}=\sum_{a\in G}\chi(a)=$一个偶数,导致矛盾。

关于为什么$H$是存在的,可以见我写的题解或者uyhip官方题解或者官方题解中给出的mathematics.stackexchange的链接

 

其实我挺喜欢这个题的。。(可能解题者都喜欢自己想了很久最终征服了的题吧,虽然这里题目也水解题者也菜)

这题只需要很基础的群论,但是解题过程也不是那么好想。

Category: 未分类 | Tags: UyHiP 抽代 | Read Count: 110

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com