福田の数学〜互除法の操作回数を最大にするには〜慶應義塾大学2023年環境情報学部第1問(1)〜ユークリッドの互除法 - 質問解決D.B.(データベース)

福田の数学〜互除法の操作回数を最大にするには〜慶應義塾大学2023年環境情報学部第1問(1)〜ユークリッドの互除法

問題文全文(内容文):
${\large\boxed{ 1 }}$(1)正の整数$\textit{m}$と$\textit{n}$の最大公約数を効率よく求めるには、$\textit{m}$を$\textit{n}$で割った時の余りを$\textit{r}$としたとき、$\textit{m}$と$\textit{n}$の最大公約数と$\textit{n}$と$\textit{r}$の最大公約数が等しいことを用いるとよい。たとえば、455と208の場合、次のように余りを求める計算を3回行うことで最大公約数13を求めることができる。

455÷208=2・・・39
208÷39=5・・・13
39÷13=3・・・0

このように余りを求める計算をして最大公約数を求める方法をユークリッドの互除法という。20711と15151の最大公約数は${\boxed{ア}}$である。
100以下の正の整数$m$と$n$(ただし$m \gt n$とする)の最大公約数を
ユークリッドの互除法を用いて求めるとき、
余りを求める計算の回数が最も多く必要になるのは
$m={\boxed{イ}},n={\boxed{ウ}}$のときである。

2023慶應義塾大学環境情報学部過去問
単元: #数A#大学入試過去問(数学)#整数の性質#ユークリッド互除法と不定方程式・N進法#学校別大学入試過去問解説(数学)#慶應義塾大学#数学(高校生)
指導講師: 福田次郎
問題文全文(内容文):
${\large\boxed{ 1 }}$(1)正の整数$\textit{m}$と$\textit{n}$の最大公約数を効率よく求めるには、$\textit{m}$を$\textit{n}$で割った時の余りを$\textit{r}$としたとき、$\textit{m}$と$\textit{n}$の最大公約数と$\textit{n}$と$\textit{r}$の最大公約数が等しいことを用いるとよい。たとえば、455と208の場合、次のように余りを求める計算を3回行うことで最大公約数13を求めることができる。

455÷208=2・・・39
208÷39=5・・・13
39÷13=3・・・0

このように余りを求める計算をして最大公約数を求める方法をユークリッドの互除法という。20711と15151の最大公約数は${\boxed{ア}}$である。
100以下の正の整数$m$と$n$(ただし$m \gt n$とする)の最大公約数を
ユークリッドの互除法を用いて求めるとき、
余りを求める計算の回数が最も多く必要になるのは
$m={\boxed{イ}},n={\boxed{ウ}}$のときである。

2023慶應義塾大学環境情報学部過去問
投稿日:2023.12.08

<関連動画>

福田の数学〜ポリアの壺は証明を覚えよう〜杏林大学2023年医学部第1問前編〜ポリアの壺

アイキャッチ画像
単元: #数A#大学入試過去問(数学)#場合の数と確率#確率#数列#漸化式#関数と極限#数列の極限#学校別大学入試過去問解説(数学)#数学(高校生)#杏林大学#数B#数Ⅲ
指導講師: 福田次郎
問題文全文(内容文):
複数の玉が人った袋から玉を 1 個取り出して袋に戻す事象を考える。どの玉も同じ確率で取り出されるものとし、nを自然数として、以下の間いに答えよ。
(1) 袋の中に赤玉 1 個と黒玉 2 個が入っている。この袋の中から玉を 1 個取り出し、取り出した玉と同じ色の玉をひとつ加え、合計 2 個の玉を袋に戻すという試行を繰り返す。n回目の試行において赤玉が取り出される確率を$p_{ n }$とすると、$p_{ 2 }=\dfrac{\fbox{ア}}{\fbox{イ}}, p_{ 3 }=\dfrac{\fbox{ウ}}{\fbox{エ}}$
( 2 )袋の中に赤玉 3 個と黒玉 2 個が人っている。この袋の中から玉を 1 個取り出し、赤玉と黒玉を 1 個ずつ、合計 2 個の球を袋に戻す試行を繰り返す。n回目の試行において赤玉が取り出される確率を$p_{ n }$とすると、次式が成り立つ。
$p_{ 2 }=\dfrac{\fbox{オカ}}{\fbox{キク}}, p_{ 3 }=\dfrac{\fbox{ケコ}}{\fbox{サシ}}$
n回目の試行開始時点で袋に人っている玉の個数$M_{ n } はM_{ n }=n+\fbox{ス}$であり、この時点で袋に入っていると期待される赤玉の個数$R_{ n }はR_{ n }=M_{ n }×P_{ n }$と表される。n回目の試行において、黒玉が取り出された場合にのみ、試行後の赤玉の個数が施行前と比べて$\fbox{セ}$個増えるため、n+ 1 回目の試行開始時点で袋に入っていると期待される赤玉の個数は$R_{ n+1 }=R_{ n }+(1-P_{ n })×\fbox{セ}$となる。したがって、
$P_{ n+1 }=\dfrac{n+\fbox{ソ}}{n+\fbox{タ}}×P_{ n }+\dfrac{1}{n+\fbox{チ}}$
が成り立つ。このことから、$(n+3)×(n+\fbox{ツ})×(P_{n}-\dfrac{\fbox{テ}}{\fbox{ト}})$がnに依らず一定となる事が分かり、$\displaystyle \lim_{ n \to \infty } P_n =\dfrac{\fbox{ナ}}{\fbox{ニ}}$と求められる。

2023杏林大学医過去問
この動画を見る 

慶應義塾大 場合の数 整数 Mathematics Japanese university entrance exam

アイキャッチ画像
単元: #数A#大学入試過去問(数学)#場合の数と確率#整数の性質#場合の数#ユークリッド互除法と不定方程式・N進法#学校別大学入試過去問解説(数学)#慶應義塾大学#数学(高校生)
指導講師: 鈴木貫太郎
問題文全文(内容文):
$x,y,z$は0以上の整数
それぞれ$(x,y,z)$は何組あるか

(1)
$x+y+z=24$

(2)
$x+y+z=24$
$x \leqq y \leqq z$

(3)
$x+2y+3z=24$

出典:2009年慶應義塾 過去問
この動画を見る 

福田のわかった数学〜高校1年生074〜場合の数(13)整数解の個数

アイキャッチ画像
単元: #数A#場合の数と確率#場合の数#数学(高校生)
指導講師: 福田次郎
問題文全文(内容文):
\begin{eqnarray}
数学\textrm{I} 場合の数(13) 整数解の個数\hspace{100pt}\\
次の条件を満たす整数の組(x,y,z,u)は何個あるか。\\
(1)x+y+z+u=10, x \geqq 0, y \geqq 0, z \geqq 0, u \geqq 0\\
(2)x+y+z+u=10, x \geqq 1, y \geqq 1, z \geqq 1, u \geqq 1\\
(3)x+y+z+u \leqq 10, x \geqq 0, y \geqq 0, z \geqq 0, u \geqq 0
\end{eqnarray}
この動画を見る 

福田の数学〜90%の人が間違う平均の計算〜慶應義塾大学2023年総合政策学部第3問〜確率漸化式と平均の計算

アイキャッチ画像
単元: #数A#大学入試過去問(数学)#場合の数と確率#確率#学校別大学入試過去問解説(数学)#慶應義塾大学#数学(高校生)
指導講師: 福田次郎
問題文全文(内容文):
※図は動画内
あるすごろくのゲ ー ムでは、 1 枚のコインを投げてその表裏でコマを前に進め、10 マス目のゴ ー ルを目指すものとする。
コマは、最初、 1 マス目のスタ ー トの位置にあり、コインを投げて表であれば 2マスだけコマを前に進め、裏であれば 1 マスだけコマを前に進める。ただし、 9マス目で表が出たために 10 マス目を超えて前に進めなくてはならなくなった場合には、ゴ ー ルできずにそこでゲ ー ムは終了するものとする。また、コインの表と裏は等しい確率で出るものとする。このとき、ある 1 回のゲ ー ムの中でnマス目(n= 1 , 2 ,・・・,10)にコマが止まる確率を$p_n$とすると,
$p_1=1,p_2=\frac{1}{2},p_3=\dfrac{\fbox{ア}}{\fbox{イ}},p_4=\dfrac{\fbox{ウ}}{\fbox{エ}}$
である。
$p_n=\dfrac{\fbox{オ}}{\fbox{カ}}\dfrac{\fbox{キ}}{\fbox{ク}}(\dfrac{\fbox{ケ}}{\fbox{コ}})^n$
である。またコマがコールしたとき、スタートからゴールするまでにコインを投げた回数は平均$\dfrac{\fbox{サ}}{\fbox{シ}}$回である

2023慶應義塾大学総合政策学部過去問
この動画を見る 

福田のおもしろ数学056〜折り返し問題〜半円を折り返す

アイキャッチ画像
単元: #数A#数Ⅱ#図形の性質#方べきの定理と2つの円の関係#図形と方程式#円と方程式#数学(高校生)
指導講師: 福田次郎
問題文全文(内容文):
図は半円 O を点 C で接するように折り返したもので EF はその折り目である。EF と AB の交点を D とする。 $AC = 6 , BC = 2$ のとき、 AD の長さを求めよ。
※図は動画内参照
この動画を見る 
PAGE TOP