幻方的构造方法

幻方的构造方法

首先:不存在2阶幻方,证明十分简单,假设四个数a、b、c、d,根据幻方的定义,应当有a+b = a+c,但是\(b \neq c\),二者矛盾,所以不存在2阶幻方。

奇数阶幻方和4M+2阶幻方可以阅读:

https://zh.wikipedia.org/wiki/%E5%B9%BB%E6%96%B9

4M阶幻方的构造上文不全面,对于4M阶幻方,应当将从左上角开始将矩阵分成多个4*4的小方阵,将小方阵内的正反对角线上所有元素变换为整个大方阵上的中心对称位置上的元素。

相关问题:https://vjudge.net/problem/UVA-10087

关于对a^b % 2^n = b^a % 2^n,当a为奇数时,在范围[1, 2^n]有且仅有一个b使等式成立的证明

关于对\(a^b \% 2^n = b^a \% 2^n\),当a为奇数时,在范围[1, 2^n]有且仅有一个b使等式成立的证明

首先,如果a是奇数,则它不含有因子2,所以b个a相乘必然没有因数2,即\(a^b\)是个奇数,因此它对一个偶数(这里的\(2^n\))取模得到的一定是一个奇数,所以等式右边也必要是一个奇数,所以b也是个奇数。总结一下:通过上边这个过程,我们得知如果a是个奇数,则b也是个奇数。

我们发现如下规律:

Part 1. 当\(n = 1\)时,由于a是一个奇数,则\(a \% 2 = 1\),我们有:

\(a^b \% 2 = (a \% 2)(a \% 2) … (a \% 2) = a \% 2 = 1\).

同理:

\(b^a \% 2 = (b \% 2)(b \% 2) … (b \% 2) = b \% 2 = 1\).

如果题设等式成立,则:

\(a \% 2  = b \% 2\).                <1>

因为\(b \in [1, 2^n]\),所以对于每一个确定的a,只存在一个b使等式成立。

Part 2. 当\(n = 2\)时,因为奇数的平方模4余1【证明比较比模8的时候要简单,可以去阅读奇数平方模8的证明:关于奇数的平方对8取余(取模)得1的证明】,对于b个(奇数个)a取模,我们运用取模的分配率得到:

\(a ^ b \% 4 = (a ^ 2 \% 4)(a ^ 2 \% 4)…(a \% 4) = a \% 4\).

同理:

\(b ^ a \% 4 = (b ^ 2 \% 4)(b ^ 2 \% 4)…(b \% 4) = b \% 4\).

如果题设等式成立,则:

\(a \% 4  = b \% 4\).                <2>

显然,对于确定的a,\(b \in [1, 4]\)只存在唯一的b。

Part 3. 当\(n = 3\)时,因为奇数的平方模8余1【关于这点的证明请看:关于奇数的平方对8取余(取模)得1的证明】,对于b个(奇数个)a取模,有:

\(a ^ b \% 8 = (a ^ 2 \% 8)(a ^ 2 \% 8)…(a \% 8) = a \% 8\).

同理:

\(b ^ a \% 8 = (b ^ 2 \% 8)(b ^ 2 \% 8)…(b \% 8) = b \% 8\).

如果题设等式成立,则:

\(a \% 8  = b \% 8\).                <3>

显然,对于确定的a,\(b \in [1, 8]\)只存在唯一的b。

Part 4. 当\(n = 4\)时,因为奇数的4次方模16余1【证明部分请阅读:关于奇数的四次方对16取余(取模)得1的证明】,对于b个(奇数个)a取模,有:

\(a ^ b \% 16 = (a ^ 4 \% 16)(a ^ 4 \% 16)…(a^{b \% 4} \% 16) = a^{b \% 4} \% 16\).

同理:

\(b ^ a \% 16 = (b ^ 4 \% 16)(b ^ 4 \% 16)…(b^{a \% 4} \% 16) = b^{a \% 4} \% 16\).

如果题设等式成立,则:

\(a^{b \% 4} \% 16  = b^{a \% 4} \% 16\).

由于前面已经证明过的<2>式\(a \% 4 = b \% 4\),我们可以由上式等价得到:

\(a \% 16  = b \% 16\).                <4>

显然,对于确定的a,\(b \in [1, 16]\)只存在唯一的b。

要证明题设命题,显然不能手动继续逐个n值接着往后推【那样做始终是优先数量的,无法保证结论的普适性】。

所以计划使用数学归纳法:

证明:

Part 1. 对于n = 1以及n = 2的证明,可以直接看上边,这里略过。

Part 2. 假设从n = 1到n = k都有\(a \% 2^n = b \% 2^n\)成立,现在要证明对于\(n = k + 1\)仍然能使上式成立。

我们用到一个结论,就是:对于\(t \in \mathbb{N}\)且\(t \neq 0\),奇数的\(2^t\)次幂被\(2^{t + 1}\)取余后得1【证明请阅读:关于奇数的2^t幂被2^(t + 1)取余得1的证明】。

因此,我们有:

\(\begin{aligned} & a^b \% 2^{k + 1} \\ = & (a^{2^k} \% 2^{k + 1})(a^{2^k} \% 2^{k + 1})…(a^{2^k} \% 2^{k + 1})a^{b \% 2^{k}} \% 2^{k + 1} \\ = & a^{b \% 2^{k}} \% 2^{k + 1} \end{aligned}\)                <5>

\(\begin{aligned} & b^a \% 2^{k + 1} \\ = & (b^{2^k} \% 2^{k + 1})(b^{2^k} \% 2^{k + 1})…(b^{2^k} \% 2^{k + 1})b^{a \% 2^{k}} \% 2^{k + 1} \\ = & b^{a \% 2^{k}} \% 2^{k + 1} \end{aligned}\)                <6>

根据\(a \% 2^k = b \% 2^k\),\(a^b \% 2^n = b^a \% 2^n\),以及<5><6>式,我们便推出\(a \% 2^{k + 1} = b \% 2^{k + 1}\)。

至此,满足数学归纳法的两个条件,因此我们证明了当a是奇数的时候,总能够由\(a^b \% 2^n = b^a \% 2^n\)推出\(a \% 2^n = b \% 2^n\),因为b的取值范围是\([1, 2^n]\),所以对于每一个确定的a,显然在取值范围内只存在1个b使上式成立。

证毕。

 

用到了这个结论的ACM赛题:【HDU-6189】Law of Commutation

关于奇数的2^t幂被2^(t + 1)取余得1的证明

关于奇数的\(2^t\)幂被\(2^(t + 1)\)取余得1的证明

证明:

奇数可以表示为(2k + 1)的形式,因此对于\((2k + 1)^{2^t}\),我们根据二项式定理有:

\(\begin{aligned} & (2k + 1)^{2^t} \\ = & (^{2^t}_{2^t})2^{2t}k^{2t} + (^{2^t}_{2^{t – 1}})2^{2t – 1}k^{2t – 1} + … + (^{2^t}_1)2k + 1 \\ = & 2^{2t}k^{2t} + 2^t \cdot 2^{2t – 1} \cdot k^{2t – 1} + … + 2^t \cdot 2k + 1 \\ = & 2^{t + 1}k(2^{t – 1}k^{2t – 1} + 2^{t – 2}k^{2t – 2} + … + 1) + 1 \end{aligned}\).

由于结果除去括号最外层值为1的项,其具有因数\(2^{t + 1}\),即证明了它能被\(2^{t + 1}\)整除,考虑回来那个值为1的项后,得到结论,奇数的\(2^t\)次幂被\(2^{t + 1}\)取余得到1.

证毕。

 

注:补充,虽然上面已经证明了命题,但是需要补充的一点是,它被\(2^(t + 2)取余得1,原因是,[latex]k\)与

\(2^{t – 1}k^{2t – 1} + 2^{t – 2}k^{2t – 2} + … + 1\),

二者之间必然有一个是偶数,所以它能够被2整除,于是奇数的\(2^t\)次幂能被\(2^{t + 2}\)取余得到1。

 

相关问题:

关于奇数的平方对8取余(取模)得1的证明

关于奇数的四次方对16取余(取模)得1的证明

关于对a^b % 2^n = b^a % 2^n,当a为奇数时,在范围[1, 2^n]有且仅有一个b使等式成立的证明

关于奇数的四次方对16取余(取模)得1的证明

关于奇数的四次方对16取余(取模)得1的证明

证明:

对于一个奇数,它显然可以表示为\(2k + 1\),则根据二项式定理我们有:

\(\begin{aligned} (2k + 1)^4 & = (^4_4) 2^4 k^4 + (^4_3) 2^3 k^3 + (^4_2) 2^2 k^2 + (^4_1) 2k + 1 \\ & = 16k^4 + 32k^3 + 24k^2 + 8k + 1 \\ & = 8k(2k^3 + 4k^2 + 3k + 1) + 1 \end{aligned}\)

可以证明,\(k\)与\(2k^3 + 4k^2 + 3k + 1\)二者中必然有一个是偶数,所以\(8k(2k^3 + 4k^2 + 3k + 1)\)可以被16整除,因此\(8k(2k^3 + 4k^2 + 3k + 1) + 1\)对16取余得1,即奇数的4次方对16取余得1.

证毕。

 

相关问题:

关于奇数的平方对8取余(取模)得1的证明

关于奇数的2^t幂被2^(t + 1)取余得1的证明

关于对a^b % 2^n = b^a % 2^n,当a为奇数时,在范围[1, 2^n]有且仅有一个b使等式成立的证明

关于奇数的平方对8取余(取模)得1的证明

关于奇数的平方对8取余(取模)得1的证明

证明:

【注:%表示取余(也叫取模)】

对于\(\forall n \in \mathbb{R}\)满足\(n \% 2 = 1\),总\(\exists k \in \mathbb{R}\)使得\(n = 2k + 1\)。

所以有:

\(n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 4k(k + 1) + 1\).

其中,\(k(k + 1)\)中k与k + 1二者必然存在一个偶数,因此\(k(k+1)\)能被2整除,即\(k(k + 1) \% 2 = 0\)。所以有,\(4k(k+1) \% 8 = 0\),因此\((4k(k+1) + 1) \% 8 = 1\),也就是一个奇数的平方对8取余得1。

证毕。

 

相关问题:

关于奇数的四次方对16取余(取模)得1的证明

关于奇数的2^t幂被2^(t + 1)取余得1的证明

关于对a^b % 2^n = b^a % 2^n,当a为奇数时,在范围[1, 2^n]有且仅有一个b使等式成立的证明

证明区间[0, 1]上的所有实值连续函数构成的实向量空间是无限维的。

Question:

Show that the real vector space consisting of all real-valued continuous function on the interval \([0, 1]\) is infinite-dimensional.

证明区间\([0, 1]\)上的所有实值连续函数构成的实向量空间是无限维的。

Solution:

Since we know the subspace of finite-dimensional vector space is a finite-dimensional vector space, if a space’s subspace is infinite-dimensional, this space will be infinite-dimensional.

Now think about \(P(\mathbb{F})\) on the interval [0, 1]. Take a list of polynomials of the \(P(\mathbb{F})\). Let m be the maximum power of this list of polynomials. Then the highest power of polynomials in the span of this polynomial list is \(m\). Therefor the polynomials whose highest power is \(m + 1\) are not belong to this span. Thus there not exist any list can span \(P(\mathbb{F})\). Hence \(P(\mathbb{F})\) is infinite-dimensional.

Since \(p(\mathbb{F})\) is a subspace of the vector space V (which is consists of all real-valued continuous functions on the interval \([0, 1]\)), V is infinite-dimensional.

证明F^∞是无限维的

Question:

Prove \(\mathbb{F}^\infty\) is infinite-dimensional.

证明\(\mathbb{F}^\infty\)是无限维的。

Solution:

设\(e_1 = (1, 0, 0, …)\),\(e_2 = (0, 1, 0, …)\)…\(e_m = (0, 0, …【1前面共计m – 1个0】, 1, 0, …)\),对于向量组\(e_1, e_2, …, e_m\)张成的空间\(span(e_1, e_2, …, e_m)\),总存在向量\(e_{m + 1} = (0, 0, …【1前面共计m个0】, 1, 0, …) \notin span(e_1, e_2, …, e_m)\),由此可证明\(\mathbb{F}^\infty\)是无限维的。

证毕。

设v1, v2, v3, v4张成V,证明v1 – v2, v2 – v3, v3 – v4, v4也张成V.

Question:

Suppose \(v_1, v_2, v_3, v_4\) spans \(V\).

Prove that \(v_1 – v_2\), \(v_2 – v_3\), \(v_3 – v_4\), \(v_4\) also spans \(V\).

Solution:

Let \(v \in V\). Since \((v_1, v_2, v_3, v_4)\) spans \(V\), we know that there exist scalars \(a_1, a_2, a_3, a_4 \in \mathbb{F}\) such that:

\(a_1 v_1 + a_2 v_2 + a_3 v_3 + a_4 v_4 = v\).

We seek coefficient \(b_1, b_2, b_3, b_4 \in \mathbb{F}\) such that:

\(b_1 (v_1 – v_2) + b_2 (v_2 – v_3) + b_3 (v_3 – v_4) + b_4 v_4 = v = a_1 v_1 + a_2 v_2 + a_3 v_3 + a_4 v_4\).

Using distributive property, we get:

\(b_1 v_1 + (b_2 – b_1)v_2 + (b_3 – b_2)v_3 + (b_4 – b_3)v_4 = a_1 v_1 + a_2 v_2 + a_3 v_3 + a_4 v_4\).

So we get:

\(b_1 = a_1, b_i – b_{i – 1}= a_i\).    \((i \in [2, 4])\)

Now we claim that for each \(b_i\), there exist \(b_i = \sum_{k = 1}^i a_k\). Clearly this is correct for \(b_1\), since \(b_1 = a_1\). Now we assume \(j \in [2, 3]\) and \(b_j = \sum_{k = 1}^j a_k\). Since \(b_i – b_{i – 1}= a_i\), we can deduce:

\(b_{j + 1} = b_j + a_{j+1} = \sum_{k = 1}^j a_k+ a_{j + 1} = \sum_{k = 1}^{j + 1} a_k\).

So the formula is proved by induction.

This proved that:

\(a_1(v_1 – v_2) + (a_1 + a_2)(v_2 – v_3) + (a_1 + a_2 + a_3)(v_4 – v_3) + (a_1+a_2+a_3+a_4)v_4 = v\).

Since for each \(v \in span(v_1, v_2, v_3, v_4)\) there exist this formula, the list \(v_1 – v_2, v_2 – v_3, v_3 – v_4, v_4\) spans \(V\).

设Ue是R上的偶函数集合,Uo是R的奇函数集合,证明R^R = Ue与Uo的直和

Foreword:

We use the operator “\(\oplus\)” to express “direct sum”.

Question:

函数\(f: R \rightarrow R\)称为偶函数,如果对所有\(x \in R\)均有\(f(-x) = f(x)\)。函数\(f: R \rightarrow R\)称为奇函数,如果对所有\(x \in R\)均有\(f(-x) = -f(x)\)。用\(U_e\)表示\(R\)上的实值偶函数的集合,用\(U_o\)表示\(R\)上实值奇函数的集合,证明\(R^R = u_e \oplus U_o\).

Solution:

Let

\(U_e = \{f: \mathbb{R} \rightarrow \mathbb{R}\) : such that f is even\(\}\),

\(U_o = \{f: \mathbb{R} \rightarrow \mathbb{R}\) : such that f is odd\(\}\).

For each function \(f(x) \in \mathbb{R}^\mathbb{R}\), we can divide it into:

\(f_e(x) = \frac{f(x) + f(-x)}{2}\),

\(f_o(x) = \frac{f(x) – f(-x)}{2}\).

Clearly \(f(x) = f_o(x) + f_e(x)\).

Therefor \(\mathbb{R}^\mathbb{R} = U_e + U_o\).

Since \(U_e \cap U_o = f_0(x) = 0\), \(\mathbb{R}^\mathbb{R} = U_e \oplus U_o\).