博士家园

查看: 683|回复: 6

[高等代数] 一道东京大学题目的推广证明

[复制链接]
发表于 2020-12-13 21:18:37 | 显示全部楼层 |阅读模式
10金币
这是东京大学某一年招生压轴的推广情况,原题是考察的数学归纳法,十分有意思。其中最后一问可以转换为矩阵问题,然后转化后的题目难度较大,我没有好的思路,希望能得到解答。
2点说明:
1、东京大学60年的理科招生题目已经上传,有需要可以自行下载
2、本人为某工科研究生,非数学专业,至少这道题在考研范围内超纲。
附件: 您需要 登录 才可以下载或查看,没有帐号?邀请

最佳答案

查看完整内容

洗牌操作相当于集合\{1,2,\cdots,N\}上的一个置换\sigma\in S_N,N=2^n(这里的N没有取原题目中的数值)。可以计算 \sigma=\begin{pmatrix} 1 & 2 & \cdots k & \cdots & 2^n\\ 2^{n-1}+1 & 1 & \cdots \sigma(k) & \cdots & 2^{n-1} \end{pmatrix} 其中 \sigma(k)=\begin{cases} \frac k 2, & k \mod 2 = 0\\ 2^{n-1}+\frac{k+1}{2}, & k \mod 2 = 1 \end{cases} 问题的突破点在于考 ...
发表于 2020-12-13 21:18:38 | 显示全部楼层

洗牌操作相当于集合$\{1,2,\cdots,N\}$上的一个置换$\sigma\in S_N$,$N=2^n$(这里的$N$没有取原题目中的数值)。可以计算

$$\sigma=\begin{pmatrix} 1 & 2 & \cdots k & \cdots & 2^n\\
                  2^{n-1}+1 & 1 & \cdots \sigma(k) & \cdots & 2^{n-1} \end{pmatrix}$$
其中
$$\sigma(k)=\begin{cases}
\frac k 2,  & k \mod 2 = 0\\
2^{n-1}+\frac{k+1}{2},     & k \mod 2 = 1
\end{cases}$$

问题的突破点在于考察$\sigma$的逆,
$$\sigma_0=\sigma^{-1}=
\begin{pmatrix} 1 & 2 & \cdots 2^{n-1} & 2^{n-1}+1 & 2^{n-1}+2 &\cdots & 2^n\\
                2 & 4 & \cdots 2^n     & 1         & 3         &\cdots & 2^n-1
                \end{pmatrix}$$

$\sigma_0$有着简单直观的含义,$\sigma_0$每在集合上作用一次,会将奇偶位置上的元素前后分开。比如,
第1次,数据被分割为两部分,
2 4 6 8 … $2^n$ 1 3 5 7 … $2^n-1$
第2次,数据被分割为4部分
4 8 12… $2^n$ 3 7 11 … $2^n-1$ 2 6 10 … $2^n-2$ 1 5 9 … $2^n-3$
……
由于奇偶位置的交错,每次被分割成的部分数是上一次的2倍,第k次作用会被分割成$2^k$部分,一直到第$n$次结束,

$$\sigma_0^n=
\begin{pmatrix} 1 & 2 & \cdots & 2^n-2 & 2^n-1 & 2^n\\
                2^n & 2^n-1 & \cdots & 3 & 2 & 1
                \end{pmatrix}$$
显然,$\sigma_0^{2n}=\sigma_0^n\sigma_0^n =1$。

这样,$\sigma^{2n}=(\sigma_0^{-1})^{2n} = (\sigma_0^{2n})^{-1} = 1$。
发表于 2021-1-11 00:45:56 | 显示全部楼层
n=4,$\sigma_0$的连续4次作用过程

     2     4     6     8    10    12    14    16     1     3     5     7     9    11    13    15
     4     8    12    16     3     7    11    15     2     6    10    14     1     5     9    13
     8    16     7    15     6    14     5    13     4    12     3    11     2    10     1     9
    16    15    14    13    12    11    10     9     8     7     6     5     4     3     2     1
 楼主| 发表于 2021-1-19 23:54:02 | 显示全部楼层
谢了,这个求逆我没想到,事实上关于这道题我也想了其他的思路,置换是思路1已经被圆满解决了,还有2个思路我不清楚能不能做下去

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?邀请

x
 楼主| 发表于 2021-1-20 00:17:42 | 显示全部楼层
hwiechern 发表于 2020-12-13 21:18
洗牌操作相当于集合\{1,2,\cdots,N\}上的一个置换\sigma\in S_N,N=2^n(这里的N没有取原题目中的 ...

置换关键利用逆进行证明,利用Jordan型以及幂幺矩阵可以证明吗

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?邀请

x
发表于 2021-1-22 14:44:40 | 显示全部楼层
Aros 发表于 2021-1-20 00:17
置换关键利用逆进行证明,利用Jordan型以及幂幺矩阵可以证明吗

如果从这个角度考虑,思路可简化一些,置换矩阵是正交矩阵,肯定可以对角化,至于特征根一定是$2^n$次单位根,未必轻松……
 楼主| 发表于 2021-2-1 22:49:23 | 显示全部楼层
hwiechern 发表于 2021-1-22 14:44
如果从这个角度考虑,思路可简化一些,置换矩阵是正交矩阵,肯定可以对角化,至于特征根一定是2^n次单 ...

再提供一种解法,运用二进制证明,十分有趣

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?邀请

x

关于我们|手机版|博士家园 ( 沪ICP备15045866号-1 )(沪公网安备沪公网安备 31011702001868号) 

GMT+8, 2021-4-17 23:21 , Processed in 1.218750 second(s), 18 queries , Gzip On.

Powered by Discuz! X3.2

© 2004-2021 Comsenz Inc.

快速回复 返回顶部 返回列表