ほぼ数学科の大学生の備忘録。

数学/物理の話をしていく…つもりだった……

工業簿記の費用の分類が覚えられないあなたへ

実は最近簿記2級の勉強をしている．
工業簿記の費用は大きく6つに分かれるが，どれがどれだか…という感じになったのでまとめてみる．

まず，原価は，（直接/間接）（材料費/労務費/費用）の6つに分かれる．

このうち，「直接費」とは，特定の製品に対してかかった費用のことを指す（材料，部品費など）．一方で，「間接費」は，製品に対してかかるものではなく工場全体などある程度範囲を持ってかかるものを指す．
直接費は仕掛品勘定で処理する一方で，間接費は製造間接費を経由する．

次に材料費，労務費，費用について見ていく．
材料費はその名の通り，製品を作るのに必要な材料のことを指す．
この場合の「材料」とは，一般的な言葉の「材料」とは少し違い，「製品を製造するために使われる物」という意味になる．
そのため，部品などはもちろん，塗装用のペンキや工具なども材料費として数えられる．
直接・間接の判定については，材料費と買入部品費が直接材料費で，その他（補助材料費，工場消耗費，消耗工具器具部品費）は間接材料費である．
部品の判定については，そのまま取り付けるだけの部品が買入部品費，そうではないものが補助材料費となる．
例えば，自動車製造におけるタイヤは買入部品費であるが，塗装用のペンキなどは補助材料費である．

次に，労務費について見ていく．労務費とは，「工場で」働く人にかかる費用のことである．
工員（製造に直接関わる人）にかかる給料を賃金，その他の人にかかる給料を給料と呼ぶ．
その他の労務費としては，「工場の従業員の」賞与や，退職給付費用，法定福利費などがある．
直接・間接の判定は簡単で，直接工の直接作業分以外はすべて間接労務費である．

最後に，経費について見る．
経費は，上の二つ（材料費・労務費）に入らない原価を言う．
主なところとしては，外注加工賃，特許権使用料，減価償却費，水道光熱費などがある．
前半二つが直接経費，その他が間接経費である．

以上です．

ABC108D

本日はAtCoderのお話．
暇なときに過去問を埋めていて，そのときにかなり詰まった問題があったので自戒を込めて解説してみる．

問題は，こちら：
atcoder.jp

ABCのほかにARCでも使われたっぽいですね．
2年弱前の問題．

L \leq 10^6 \leq 2^{20}であることを考えると， Lの二進展開っぽいことをすればよいというのまでは想像がついたが…

自分が通した解法

最初は二進展開っぽいことを二分木でやってみようとしたが普通に頂点

数が 20を超えた．そりゃそうだ．
他に良い手が思いつかなかったので，解説を眺めることに．
一直線のグラフを作って少しずつ調整するっぽいな，ということだけ認識してそこから自力でやってみることにした．

ここでかなり苦労したのだが，結果的に通せた解法を紹介してみる．

L が 2冪の場合は簡単で，例えば L=3の場合には図のようにすればよい．

2冪でない場合が問題でである．
考察として，各点までで打ち切った場合に，どの長さのパスまで存在するかを書いてみる（半開区間で書いてあることに注意）．

f:id:prfm_mkr:20200606174107p:plain

最終的に，一番右下を [0, L) にできればよいわけだ．
r番目のノードまで，この図の形でグラフを作るとすると， [0, 2^r-1)までは何も手を加えなくても実現できていることが分かる．

そのため，まずは 2^{r-1} \leq L を満たす最大の r を求める．
現状ではこんな感じ．
f:id:prfm_mkr:20200606180213p:plain

[0, 2^{r-1})については良いことにすると，残るは [2^{r-1}, L) である．
どこかに辺を足すことで残りの部分について対応していきたいが，各点までのパスの長さが 0 から始まっていることを考えるとどこかに 2^{r-1}の長さの辺を足すのが妥当そうである．

例えば， r-1のノードからrのノードへと長さ 2^{r-1}の辺を足すことにすると，新たに [2^{r-1}, 2^{r-1} + 2^{r-2}) の長さのパスが増えることになる．
これは， 2^{r-1} + 2^{r-2} \leq L のときは追加してよいが，そうでない場合は過剰にパスが増えてしまう．
従って，この判定を繰り返すことで徐々に残りの区間が減っていき，正しく解答できる．

f:id:prfm_mkr:20200606180035p:plain

イメージとしてはこんな感じです．

【英語】目的語は単数？複数？

最近英語で論文を書いていて困ったことがある．
それは，複数形が主語の時の目的語の単複である．

例えば，
「すべての文章は原著の翻訳を添える必要があります」
という文章を英語で言うときに，
All documents must be accompanied by ...
の後に何を置けばよいのか，という疑問である．

  1. a translation of the original
  2. translations of the originals

どっちもよさそうに見える．

それぞれの文章に一つの原文があるのだから単数形だ，と思えば1.の形になるし，
文章は複数あるのだから原文も複数ある．だから2.だ！とも言えそうである．

Renew of Practical English Usage, Michael Swan によると，答えは
「どっちでもよい」
だそうだ．

上の例文はこの本に載っていたものだが，どちらも良いことになっている．

この本，割と界隈では有名な本のようで，
楽天koboで電子書籍版が600円くらいだったので興味があれば是非買ってみてほしい．

ちなみに楽天koboのリーダーは非常に読みづらい．．．

楕円曲線上のねじれ群の分解

E を，体 K 上の楕円曲線としたときに， 互いに素な整数 a,b について
\begin{equation}
E[ab] \simeq E[a] \oplus E[b]
\end{equation}

となることの証明につまずいたのでメモしておく．

ここで示す必要があるのは，

  • 直和の正当性
  • 同型写像の存在

の2つ．

直和の正当性

直和の正当性をしめすには，

  • 共通部分が自明（無限遠点のみ）
  • 和が一意

の2つを示せばよい．

共通部分が自明

まず，前者について， P \in E[a] \cap E[b] を取ると， P の位数 {\rm ord}\ P は a,b, をともに割り切る．
a,bは互いに素なので， {\rm ord}\ P = 1 となり， P = \infty が示される．

和が一意

後者について，
\begin{equation}
P_1 + Q_1 = P_2 + Q_2\
\left(
\begin{aligned}
P_1,P_2 &\in E[a] \\
Q_1,Q_2&\in E[b]
\end{aligned}
\right)
\end{equation}
であると仮定する．このとき P_1 = P_2,\ Q_1 = Q_2 であることを示せばよいが，
\begin{equation}
P_1 - P_2 = Q_2 - Q_1
\end{equation}
であり，左辺は E[a] の元の引き算なので E[a] の元で，同様に右辺は E[b] の元である．
既に E[a] \cap E[b] = \{\infty\} であることは示しているので，
\begin{equation}
P_1 - P_2 = Q_2 - Q_1 = \infty
\end{equation}
となり， P_1 = P_2,\ Q_1 = Q_2 が従う．

以上より，直和の正当性は示されれた．

同型写像の構成

次に，具体的に写像を与えて，その同型性を示す．
直感的にもそうだが，同型写像は
\begin{equation}
P\in E[ab] \mapsto ([b]P,[a]P) \in E[a] \oplus E[b]
\end{equation}
とする*1．この写像の準同型性はスカラー倍の準同型性に帰着されるので明らか．
従ってここではこの写像が全単射（従って，単射性と全射性）を示せばよいことになる．以下，この写像を \psi と置く．

単射性

P_1, P_1 \in E[ab] について，\psi(P_1)=\psi(P_2) とすると，特に [a]P_1 = [a]P_2 なので，
\begin{align}
[a]P_1 - [a]P_2 &= \infty \\
[a](P_1-P_2) &= \infty \\
P_1 - P_2 &\in E[a]
\end{align}
となる．同様に， P_1 - P_2 \in E[b] も示されるので，
\begin{equation}
P_1 - P_2 \in E[a] \cap E[b] = \{\infty\}
\end{equation}
より， P_1 = P_2 が従う．よって \psi が単射であることが示された．

全射性

P\in E[a], Q \in E[b] を固定する．

ねじれ群は，代数閉包 \bar{K}上で定義されることに注意する． E(K) \to E(K) なる自己準同型写像は全射なので*2， [b] R_1 = P となる R_1 \in E(\bar{K}) が存在する．このとき，
\begin{equation}
[ab] R_1 = [a]([b]R_1) = [a] P = \infty\ (\because P \in E[a])
\end{equation}
より， R_1 \in E[ab] である．

（直感的な話）
この R_1 が， [a]R_1 = Q を満たすとは限らないが， R_1 には E[b] 分の自由度があることに注意する．つまり，任意の B \in E[b] について， [b](R_1 + B) = P が保たれる．以下，これを用いて b 倍したときの値は変えないまま a 倍したときの値が Q になるように調整する．

このR_1に対し，集合
\begin{equation}
\mathcal{A} = \{ [a] (R_1+A)\ |\ A\in E[b] \}
\end{equation}
を考える． \mathcal{A}\subseteq E[b] は明らかで， A_1, A_2 \in E[b] に対して，
\begin{align}
&[a](R_1+A_1) = [a](R_1+A_2)\\
\Rightarrow & [a](A_1 - A_2) = \infty \\
\Rightarrow & A_1-A_2 \in E[a]
\Rightarrow & A_1 - A_2 \in E[a]\cap E[b] = \{\infty\}
\end{align}
となるため， \#\mathcal{A} = \#E[b] であることが分かる． \mathcal{A}\subseteq E[b] と \#\mathcal{A} =\#E[b] から， \mathcal{A} = E[b] であることが示される．

従って， Q\in E[b] に対し，ある A\in E[b] が存在して， [a] (R_1+A) = Q が成立し，この R_1+A \in E[ab] は， \psi(R_1+A) = (P,Q) を満たすため， \psi は全単射となる．

*1:筆者は良く知らないが，ほかにも同型写像の取り方はあるかもしれない．

*2:L. Washington. "Elliptic Curves; Number Theory and Cryptography" 参照．直感的な証明としては，閉体の上では，点 Q\in E(\bar{K}) が与えられた時に方程式 \alpha(P)=Q が解けるため．

行列式とトレース

大学数学 線形代数

お久しぶりです。気づけば1年近く放置しておりました。

今回は2次形式とトレースの関係式

\begin{equation} x^TAx = {\rm tr}(Axx^T) \end{equation}

というものを紹介したいと思います。ただし、 A は正方行列、xは適当な大きさのベクトルです。

証明は簡単で、A=(a_{ij}),x=(x_1,x_2,\cdots,x_n)^T としたときに、

\begin{align} x^TAx &=(x_1,x_2,\cdots,x_n)\left(\begin{array}{c} \displaystyle \sum_{j=1}^n a_{1j}x_j \\ \displaystyle \sum_{j=1}^n a_{2j}x_j\\ \vdots\\ \displaystyle \sum_{j=1}^n a_{nj}x_j \end{array} \right) \\ &=\sum_{i=1}^n\sum_{j=1}^n x_ia_{ij}x_j \end{align}
であり、
\begin{align} (Axx^T) &= \left(\begin{array}{cccc} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{array} \right) \left(\begin{array}{cccc} x_1x_1 & x_1x_2 & \cdots &x_1x_n\\ x_2x_1 & x_2x_2 & \cdots & x_2x_n \\ \vdots & \vdots & \ddots & \vdots \\ x_nx_1 & x_nx_2 & \cdots & x_nx_n \end{array} \right)\\ \\ &=\left(\begin{array}{cccc} \sum_{j=1}^n a_{1j}x_jx_1 & & & {\Large {*}}\\ & \sum_{j=1}^n a_{2j} x_jx_2& & \\ & & \ddots & \\ {\Large {*}}& & & \sum_{j=1}^n a_{nj}x_jx_n \end{array} \right) \end{align}
のtraceをとれば
\begin{align} {\rm tr}(Axx^T) &=\sum_{i=1}^n\sum_{j=1}^n x_ia_{ij}x_j\\ &=x^TAx \end{align}
となることが示せます。

行列やシグマの計算に慣れる意味でも一度自分で証明してみるといいと思います（ \LaTeX でやるのは少々めんどくさいです）。

ベルンシュタインの定理（２）

大学数学

今回は、ベルンシュタインの定理を証明します。

まず、 |A| \leq |B| かつ |B| \leq |A| であるとします。濃度の大小関係の定義からAからBへの単射 f とBからAへの単射 g が存在します。ここで、写像 h:A \to A としてh=g \circ f を考えます。

この元で、Aの部分集合の列 \{A_n\}_{n\in \mathbb{N}} を、以下のように考えます。

A_0=A,A_1=g(B),A_{n+2}=g\circ f(A_n)\ (n=0,1,2\cdots)

こうすると、この列は減少列、つまり A_0 \supset A_1 \supset A_2 \cdots となります。

また、 f,g が単射なのでその合成 h=g \circ f も単射です。そのため、 g \circ f を各 A_n から A_{n+2} への写像としてみると全単射とみなせます。つまり、

\[ |A_1|=|A_3|=|A_5|=\cdots ,\ |A_0|=|A_2|=|A_4|=\cdots\]

であることがわかります。同様にして g は B から A_1 への全単射とみなせるので、 |B|=|A_1| です。

以上より、 |A|=|A_1| を示せば、 |A|=|B| であることが示せます。

これは具体的に全単射を構成することで示します。

まず、\( K=\cup_{i=1}^{\infty}A_i \)とします。このもとで、\( \Phi:A\to A_1\)を

\[ \Phi(x)=\begin{cases}
h(x)\ &(x\in A_{2n+1} \setminus A_{2n})\\
x &(x\ \in \left( A_{2n+2}\setminus A_{2n} \right)\cup K)
\end{cases} \]

とすればこれは全単射となり、ベルンシュタインの定理が証明できたことになります。

最後の写像は、イメージとしては二つずつ内側に押し込めていくイメージです。実際に図を書いてみて確認してみてください。

ベルンシュタインの定理（１）

大学数学

前回が集合論の加算無限非加算無限の話でしたが、今回は集合の濃度に関する定理、ベルンシュタインの定理の紹介とその説明をします。

集合の濃度とは、直感的には集合の要素の個数、もしくは大きさです。但し濃度は有限集合に限らず無限集合に対しても定義されます。

具体的には、k個の要素から成る有限集合AにたいしてはAの濃度 |A|=k とし、無限集合B,Cに対して、BからCへの全単射がある時に |B|=|C| とします。全単射があるということは、その各要素に対して一対一の対応が取れるということなので、全単射があるときの集合の「大きさ」が等しいという定義は合理的に思えます。

また、集合A,Bに対してAからBへの単射が存在するときに、 |A|\leq|B| と定義します。AからBへの単射があるということは、Aの要素に対して対応する要素がBの中にあるということを表しており、BのAの要素に対応しない要素も存在する可能性があることから、Bの要素の数の方がAの要素の数よりも多くなるというのが直感的な説明です。

この元で、ベルンシュタインの定理とは、
|A|\leq|B|かつ|B|\leq|A| ならば |A|=|B| である

というものです。有限集合について考えれば当然の定理ですが、無限集合に対してもこれが適用できます。

少し長くなってきたので証明はまた次回とします。