nは自然数、x、yは、0≦x＜1、0≦y＜1を満たす実数とする。
(2^n-1)x+(3^n-2^n)yと(3^n-1)yがともに整数となるような、(x,y)の個数を求めなさい。
何度計算しても、(2^n-1)(3^n-1)となり、解答と合いません。正しい解き方を御教授願います。
|
No.83659 - 2022/10/21(Fri) 14:05:22
| ☆ Re: 整数 / らすかる | | | (2^n-1)x+(3^n-2^n)y と (3^n-1)y がともに整数
⇔
(2^n-1)x+(3^n-2^n)y-(3^n-1)y と (3^n-1)y がともに整数
⇔
(2^n-1)(x-y) と (3^n-1)y がともに整数
(3^n-1)yが整数になるためには y=s/(3^n-1) （ただし0≦s＜3^n-1）
(2^n-1)(x-y)が整数になるためには x-y=t/(2^n-1) （ただし0≦t＜2^n-1）
となっている必要があります。
※※※ t＜0を考え落としていますので、その分の追加検討が必要です。
※※※ 以下はt≧0の分のみです。
また0≦x＜1なので
0≦s/(3^n-1)+t/(2^n-1)＜1も必要です。
もし0≦s/(3^n-1)+t/(2^n-1)＜2ならば(2^n-1)(3^n-1)個ですが
このうち約半数が1≦s/(3^n-1)+t/(2^n-1)＜2となりますので
それを考慮しなければなりません。
s＞0,t＞0ならば
0＜s/(3^n-1)+t/(2^n-1)＜1 となるものと
1＜s/(3^n-1)+t/(2^n-1)＜2 となるものは同数ですから、
s/(3^n-1)+t/(2^n-1)=1となる個数をaとすると
0≦s/(3^n-1)+t/(2^n-1)＜1となる個数は
{(2^n-2)(3^n-2)-a}/2+(2^n-1)+(3^n-1)-1
=(6^n-a)/2-1個です。
aは、2^n-1と3^n-1が互いに素であればa=0ですが、
そうでないときa＞0になります。
例えばn=4のときgcd(2^4-1,3^4-1)=5であり
3/(2^4-1)+64/(3^4-1)
6/(2^4-1)+48/(3^4-1)
9/(2^4-1)+32/(3^4-1)
12/(2^4-1)+16/(3^4-1)
の4つが1になります。
つまりa=gcd(2^n-1,3^n-1)-1ということです。
従って求める(x,y)の個数は
{6^n-gcd(2^n-1,3^n-1)+1}/2-1
={6^n-gcd(2^n-1,3^n-1)-1}/2
になると思います。
（変な答えなので若干自信なし）
|
No.83660 - 2022/10/21(Fri) 15:05:33 |
| ☆ Re: 整数 / IT | | | > (2^n-1)(x-y)が整数になるためには x-y=t/(2^n-1) （ただし0≦t＜2^n-1）
x-y が負でも良いのでは？
|
No.83661 - 2022/10/21(Fri) 19:26:03 |
| ☆ Re: 整数 / らすかる | | | 御指摘ありがとうございます。確かにそうですね。
そうすると…
t＜0の場合はちょっと面倒そうですね。
|
No.83662 - 2022/10/21(Fri) 20:45:37 |
| ☆ Re: 整数 / IT | | | 例えば n=4 の場合、2^n-1＝15,3^n-1=80 で
y = s/80 を[0,1) に取り
1/15刻みの目盛りの定規を考え、
y に目盛りの一つを合わせたとき[0,1)内にいくつの目盛り（ここがx)が入るかを考えると、その個数はyの位置に関わらず常に15個。
|
No.83664 - 2022/10/21(Fri) 21:24:23 |
| ☆ Re: 整数 / IT | | | 求める(x,y)の個数は(2^n-1)(3^n-1) であっているような気がしますが､書いてある解答はいくらですか？
|
No.83665 - 2022/10/21(Fri) 21:34:43 |
| ☆ Re: 整数 / らすかる | | | 上の回答は間違いでしたのでやり直しです。
(2^n-1)x+(3^n-2^n)y と (3^n-1)y がともに整数
⇔
(2^n-1)x+(3^n-2^n)y-(3^n-1)y と (3^n-1)y がともに整数
⇔
(2^n-1)(x-y) と (3^n-1)y がともに整数
(3^n-1)yが整数になるためには y=s/(3^n-1) （ただし0≦s＜3^n-1）
(2^n-1)(x-y)が整数になるためには x-y=t/(2^n-1) （ただし-2^n+1＜t＜2^n-1）
となっている必要があります。
sは0〜3^n-2の3^n-1通りなのでyは3^n-1通り
x=y+t/(2^n-1)について
t=0のときx=yなのですべて条件を満たす
t=1のときとt=-2^n+2のときを合わせて考えると
1/(2^n-1)-(-2^n+2)/(2^n-1)=1なので
0≦s/(3^n-1)+(-2^n+2)/(2^n-1)ならば
0≦s/(3^n-1)+(-2^n+2)/(2^n-1)＜1 なので
1≦s/(3^n-1)+1/(2^n-1)＜2 となり
t=1,-2^n+2のうちt=-2^n+2の方だけ条件を満たす
s/(3^n-1)+(-2^n+2)/(2^n-1)＜0ならば
-1＜s/(3^n-1)+(-2^n+2)/(2^n-1)＜0 なので
0＜s/(3^n-1)+1/(2^n-1)＜1 となり
t=1,-2^n+2のうちt=1の方だけ条件を満たす
従ってyの各値に対してt=1またはt=-2^n+2のどちらか一つだけが成り立つので
t=1とt=-2^n+2を合わせて3^n-1通りになる
同様に
t=2のときとt=-2^n+3のときを合わせて3^n-1通り
t=3のときとt=-2^n+4のときを合わせて3^n-1通り
・・・
t=2^n-2のときとt=-1のときを合わせて3^n-1通り
のようになり、結局全部で
(2^n-1)(3^n-1)通りになる。
というわけで、(2^n-1)(3^n-1)通りで合っていると思います。
|
No.83666 - 2022/10/21(Fri) 22:24:21 |
| ☆ Re: 整数 / Mari | | | 先生方、御答ありがとうございます。
ですが、解答は、2^n・3^n・(3^n-2^n)となっております…
先生の解答は私も納得できますし、似たように解いたのですが…
|
No.83673 - 2022/10/22(Sat) 23:33:38 |
| ☆ Re: 整数 / IT | | | n=1 のときを考えると
2^n・3^n・(3^n-2^n)＝6は誤りであることがわかりますね
|
No.83675 - 2022/10/23(Sun) 01:18:47 |
|
