[F] Phi Puzzle

問題文

$30$ の正の約数を並べ替えた数列 $A$ としてありうるもの全てに対する，以下の操作方法の個数の総和を解答してください．

• 「連続する $2$ 数 $A_i,A_{i+1}$ であって $A_i \mid A_{i+1}$ を満たすものを $1$ つ選び，それらをともに $A$ から削除する」という操作を $4$ 回行い，$A$ を空にする．

問題文

上から $i$ 段目 $(1 \leq i \leq 2026)$ に $i$ 個の正整数を並べて三角形を作る方法であって，どの段も総和が $2026$ となるようなものの個数を素数 $2029$ で割ったあまりを解答してください．

問題文

$S=\lbrace 0,1, \ldots , 30 \rbrace$ とします．関数 $f:S \rightarrow S$ であって，以下を満たすようなものの個数を $N$ とします．

• 任意の $x,y \in S$ について，$x^{12}-y^{12}$ が $31$ の倍数ならば，$f(x)^{25}-f(y)^{25}$ も $31$ の倍数．

$N = a \cdot b^c$ であるような正整数 $a,b,c$ について，$a+b+c$ の最小値を解答してください．

問題文

$60$ 以下の正整数 $n$ に対して，それを $2,3,4,5$ で割ったあまりをそれぞれ $a,b,c,d$ とします．$xy$ 平面上に $P(a,b)$ と $Q(c,d)$ をとったとき $PQ= 1$ となるような $n$ の個数を解答してください．

問題文

$\dfrac{51-n}{n-1}$ が平方数となるような整数 $n$ の総和を解答してください．

(13:17追記　 $0$ も平方数に含むとします)

問題文

正整数に対して定義され非負整数値をとる関数 $f$ が以下を満たしています．

• 任意の正整数 $x,y$ について $f(xy)=f(x) \oplus f(y)$

• $x$ と $y$ が互いに素ならば $f(xy)=f(x)+f(y)$

このような関数 $f$ について，以下を満たす正整数の組 $(x,y)$ の個数を $c(f)$ とします．$c(f)$ がとりうる値は有限個なので，その総和を解答してください．

• $x,y$ はともに $30^{10}$ の約数である．

• $f(xy)=f(x)+f(y)$

追記: $\oplus$ はビットごとの排他的論理和です

問題文

$$AC = AD，2\angle CBD = \angle CAD$$ をみたす凸四角形 $ABCD$ について，対角線の交点を $E$ とする． また，$ABD$ の外接円と直線 $AC$ の交点を $F$ とする．
$$AE = DE = 6，AB:BF = 3:4$$ が成立するとき，$CD^2$ は正整数 $a, b$ と平方因子を持たない正整数 $c$ を用いて $a - b\sqrt c$ と表されるため，$a + b + c$ を求めよ．
ただし，$XY$ で線分 $XY$ の長さを表すものとする．

解答形式

非負整数値で解答してください．

問題文

$(a_1,a_2,...,a_{900})$ を各項が $1$ 以上 $900$ 以下であるような整数の組とする．
$i = 1, 2, ..., 900$ について
$$P_i = \displaystyle\prod_{k = 1}^{i} a_k$$
とし，$P_i$ を $900$ で割った余りの取りうる値の個数を $C$ とする．このとき，$C$ の取りうる値のうち最大のものを求めよ．

解答形式

非負整数値で解答してください．

問題文

任意の正の整数 $m, n(m\leq n)$ について $\displaystyle |\sum_{i=m}^{n} a_i| \leq 2$
が成り立つような整数列 $a_i (i\geq 1)$ について，$(a_1, a_2, …, a_{100})$ としてありうる組は $N$ 個存在する．$N$ を素数 $97$ で割った余りを求めよ．

訂正: 「非負整数列」と誤りがありましたが，正しくは整数列です．申し訳ありません．

問題文

長さ $60$ の文字列 $S$ を
$S=\underbrace{ABC \cdots \cdots ABC}_{ABC\text{ が }20 \text{ 個}}$
とする．
$S$ から順番を保ったまま $5$ 文字選ぶ方法であって，選んだ $5$ 文字がこの順に「$ABCBA$」 となるような選び方は何通りあるか．

解答形式

非負整数値で解答してください．

問題文

鋭角三角形 $ABC$ について、外接円の劣孤 $BC$ の中点を $M$ とする。$ABC$ の外接円の$A$ における接線と直線 $BC$ の交点を $P$ とするとき、
$$AB=8，　BC=12，　\angle PAB=\angle BAM$$ が成立した。このとき $AP$ は互いに素な正整数 $a, b$ を用いて $\dfrac a b $ と表せるため，$a +b$ を求めよ．
ただし，$XY$ で線分 $XY$ の長さを表すものとする．

解答形式

非負整数値で解答してください．

問題文

横一列に並んだ $14$ 個のオセロの石があります．そして，以下の操作を何度か行い，黒面を向いた石の個数をできるだけ少なくします．

• 連続して並んだ $4$ 個の石を選んで，左から $1,2,4$ 個目の石を全て裏返す．

全ての操作の終了後に黒面を向く石の個数を スコア とします．最初の石の配色は $2^{14}$ 通りありますが，これら全ての場合においてスコアの総和を求めてください．
　但し，オセロの石は，片方が黒面で，もう片方が白面であるとする．

解答形式

正整数で答えてください．