2021-11-22

等差数列中の素数 /「算数にチャレンジ!!」第1133問

問題概略
等差中項

問題概略

4 つの自然数 $a$ , $b$ , 63, $c$ はこの順に等差数列をなしていて， $a$ が最小です。
また， $a$ , $b$ , $c$ はすべて素数です。 $c$ を求めてください。
http://www.sansu.org/used-html/index1133.html

解説の pdf も作りました。きれいなレイアウトで読みたい方はこちらをどうぞ。

drive.google.com

等差中項

4 つの数を「 $a$ , $b$ , 63」と「 $b$ , 63, $c$ 」にわけて考えます。
これらは等差数列です。

$a+63=2b,\, b+c=2\cdot 63$
$\therefore a=189-2c,\, b=126-c$

$2\leqq a< b< 63< c$ から $64\leqq c\leqq 93$ が言えて，素数 $c$ の候補は 67, 71, 73, 79, 83, 89 の 6 個にしぼられます。

あとはしらみつぶしです。
$(a,\, b,\, c)$ を書き下して $a$ , $b$ が素数かどうか調べます。

$(\underline{55},\, 59, 67),\, (47,\, \underline{55},\, 71),\, (43,\, 53,\, 73),$
$(31,\, 47,\, 79),\, (23,\, 43,\, 83),\, (11,\, 37,\, 89)$

下線を引いた 55 以外は素数なので条件をみたす $c$ は次の 4 個です。

variee.hatenablog.com

2021-11-19

3つのサイコロの目の積の確率 / 2018 一橋大学第3問

大学入試（日本）一橋大学

問題概略
「目の集合→目の出方」の順に数える
- (1)について
- (2)について
  - {x, y, z} 型で 1 通りのとき
  - {x, x, y} 型で 2 通りのとき
おまけ：プログラムを組んで計算

問題概略

3 個のさいころを投げる。
(1)　出た目の積が 6 となる確率を求めよ。

(2)　出た目の積が $k$ となる確率が $\frac{1}{36}$ であるような $k$ をすべて求めよ。

解説の pdf も作りました。きれいなレイアウトで読みたい方はこちらをどうぞ。

drive.google.com

「目の集合→目の出方」の順に数える

すべてのサイコロを区別します。
目の出方は全部で $6^3=216$ 通で，これらは同様に確からしいです。

(1)について

積が 6 になる目の集合は $1,\, 1,\, 6\}$ , $\{1,\, 2,\, 3\}$ の 2 つ。
どのサイコロがどの目を出すかを考えると，目の出方は $3+3!=9$ 通りです。求める確率は

$\frac{9}{216}=\frac{1}{24}$

(2)について

基本的には(1)と同様で，「目の集合→目の出方」の順に数えますが，最初は逆算が必要です。

$\frac{1}{36}=\frac{6}{216}$ より目の出方は 6 通り。

$x$ , $y$ , $z$ を相異なる数とします。目の集合は
$\{x,\, y,\, z\}$ , $\{x,\, x,\, y\}$ , $x,\, x,\, x\}$
の 3 パターンあって，それぞれ $3!=6$ , 3, 1 通りの目の出方を与えます。

6 は $3+1+1+1$ や $\underbrace{1+1+\cdots+1}_{\text{6個}}$ という分割もできますが，ある数が立方数 $x^3$ として 2 通り以上にあらわせることはないので，目の出方が 6 通りになるのは次のどちらかのときです。

$\{x,\, y,\, z\}$ 型で 1 通りにあらわせる
$\{x,\, x,\, y\}$ 型で 2 通りにあらわせる

{x, y, z} 型で 1 通りのとき

$\{x,\, y,\, z\}$ 型は ${}_6\mathrm{C}_3=20$ 通りしかありません。全部書いて $k=xyz$ のダブリをチェックします。

f:id:variee:20211119205101p:plain

f:id:variee:20211119205112p:plain

$k=10,\, 15,\, 40,\, 90,\, 120$ は条件をみたします。

{x, x, y} 型で 2 通りのとき

$\{x,\, x,\, y\}$ 型は $6^2=36$ 通りあります。これも全部書いて $k=x^2y$ のダブリをチェックします。

f:id:variee:20211119205125p:plain

$k=4,\, 16$ は 2 通りにあらわせますが，他はダメです。

以上まとめて
$k=4,\, 10,\, 15,\, 16,\, 40,\, 90,\, 120$

おまけ：プログラムを組んで計算

プログラミングありだったら(2)は楽勝ですね。
$i$ , $j$ , $k$ で 3 重にループさせて $ijk$ の登場回数を調べるだけです。

mathematica は関数型言語でループ処理は苦手なのですが，それでも 0.0006 秒でした。

    In[]:= AbsoluteTiming[
        a = ConstantArray[0, 6^3];
        For[i = 1, i <= 6, i++,
         For[j = 1, j <= 6, j++,
          For[k = 1, k <= 6, k++,
           a[[i*j*k]]++]]];
        ans = Last@Reap@Do[If[a[[i]] == 6, Sow@i], {i, 1, 6^3}]]
       
    Out[]= {0.0006358, {{4, 10, 15, 16, 40, 90, 120}}}

関数型言語らしく書くと 0.0002 秒で答えが出ます。

    In[]:= AbsoluteTiming[
        lst = Tuples[Range@6, 3];
        ans = First /@ Select[Tally[Times @@ # & /@ lst], Last@# == 6 &]]
       
    Out[]= {0.0002293, {4, 10, 15, 16, 40, 90, 120}}

variee.hatenablog.com

2021-11-19

平方数の和の1の位が5になる回数 /「算数にチャレンジ!!」第1127問

算数にチャレンジ!!

問題概略
割ってから足す
足してから割る
おまけ：プログラムで計算

問題概略

次のような動作をする機械があります。
「キーボードから数 $n$ を入力すると $n^2$ を計算し，それまでの合計に加算する」
この機械に 1 から 1000 までの整数を小さい順に入力していき，1 回ごとに表示される数値を確認していきます。
次のように表示されますね。

1 回目は $1\times 1=1$

2 回目は $2\times 2+1=5$

3 回目は $3\times 3+5=14$

表示される数値の 1 の位が 5 になることは 1000 回のうち何回あるでしょうか。

http://www.sansu.org/used-html/index1127.html

解説の pdf も作りました。きれいなレイアウトで読みたい方はこちらをどうぞ。

drive.google.com

割ってから足す

平方数を 10 で割った余りは周期 10 で，その値は 1, 4, 9, 6, 5, 6, 9, 4, 1, 0 です。

これらの和は 45 で，2 倍した 90 は 10 の倍数。
$n$ 回目に表示される数を $S_n$ とおいて， $S(n)$ を 10 で割った余りを $g(n)$ とおくと，これは 20 を周期にもちます。

$g(n)=\bmod (S_n,\, 10)=\bmod\left(\sum_{k=1}^n k^2,\, 10\right)$
$=\bmod\left(\sum_{k=1}^n \bmod(k^2, 10),\, 10\right)$

数式で書くとなにやら仰々しいのですが，「全部足してから 10 で割る」のと「10 で割った余りを足して，最後にもう一回 10 で割る」のは同じです。

$g(n)$ の関係式を求めましょう。 $S_{n+1}=S_n+(n+1)^2$ から

\begin{align*}
g(n+1) &=\bmod (S_{n+1},\, 10)=\bmod (S_n+(n+1)^2,\, 10)\\
&=\bmod\big(\bmod(S_n,\,10)+ \bmod\left((n+1)^2,\, 10\right),\, 10\Big)\\
&=\bmod\Big(g(n)+\bmod\left((n+1)^2,\, 10\right),\, 10\Big)
\end{align*}

$g(1)=\bmod(S_1,\, 10)=1$ からスタートして
「 $2^2=4$ を 10 で割った余り 4 を足して 10 で割る」のような計算を 20 回やることは手計算でも簡単でしょう。

$S_n$ の 1 の位が 5 になるのは $n$ が 2, 5, 9, 10, 14, 17 のときで 6 回あります。
答えはこの $\frac{1000}{20}=50$ 倍なので「300 回」です。

足してから割る

$S_n=\sum_{k=1}^n k^2=\frac{1}{6}n(n+1)(2n+1)$ を利用します。
$f(n)=n(n+1)(2n+1)$ とおきます。

$S_n=\frac{1}{6}f(n)$ の 1 の位が 5 のとき $f(n)=6(10m+5)=60m+30$ とおけて $f(n)$ を 60 で割った余りは 30 です。

法が 60 では手計算で解く気がおきないので， $60=2^2\cdot 3\cdot 5$ を利用して法を小さくします。

法として 3, 4, 5 をとると条件はこうなります。

$f(n)\equiv 30\equiv 0\pmod{3}$
$f(n)\equiv 30\equiv 2\pmod{4}$
$f(n)\equiv 30\equiv 0\pmod{5}$

$S_n=\frac{1}{6}f(n)$ は整数なので $f(n)$ は 6 の倍数で， $f(n)\equiv 0\pmod{3}$ はつねに成立します。
$n$ の条件として考えないといけないのは $f(n)\equiv 2\pmod{4}$ と $f(n)\equiv 0\pmod{5}$ です。

まず $\bmod\, 5$ で考えます。 $f(n)\equiv 0$ の条件は「 $n\equiv 0$ または $n+1\equiv 0$ または $2n+1\equiv 0$ 」です。

$n+1\equiv 0$ のとき $n\equiv 4$ 。 $2n+1\equiv 0$ は次のように変形できます。

$2n\equiv -1\equiv 4\quad \therefore n\equiv 2\quad (\because \text{2と5は互いに素})$

まとめると $n\equiv 0,\, 2,\, 4\pmod{5}\mbox{　……(1)}$ です。

次は $\bmod\, 4$ で考えます。
$f(n)$ は整数係数で $a\equiv b\Rightarrow f(a)\equiv f(b)$ が使えるので
$f(0)$ , $f(\pm 1)$ , $f(2)$ を 4 で割った余りを調べるのが手っ取りばやいです。

$f(0)=0\equiv 0,\, f(1)=6\equiv 2,\, f(-1)=0\equiv 0,\, f(2)=30\equiv 2$

余りが 2 になる条件は $n\equiv 1,\, 2\pmod{4}\mbox{　……(2)}$ です。

1～ $20\ (=4\times 5)$ で考えると(1)(2)をみたす $n$ は 2, 5, 9, 10, 14, 17 の 6 個。
答えはこの $\frac{1000}{20}=50$ 倍なので「300 回」です。

おまけ：プログラムで計算

項が 1000 個しかないので愚直にコードを書いても十分高速です。約 0.003 秒でした。

    In[]:= AbsoluteTiming[
        f[n_] := Mod[n (n + 1) (2 n + 1)/6, 10] == 5;
        ans = Length@Select[Range@1000, f]]
       
    Out[]= {0.0030521, 300}

variee.hatenablog.com