[ ホームページ ] [ 携帯用URL ]
DS 数学 BBS・2
小中高の範囲は DS 数学 BBS(携帯電話用)へ。
数学以外の話題は赤猫雑談掲示板で。
注意事項, 記号の書き方例をお読みになった上でご利用ください。

[ EZBBS.NET | 新規作成 | ランキング | サポート ]
名前 一覧
 E-mail 
題名
内容

投稿KEY    タグ有効 改行有効 等幅フォント
URL
添付

 
掲示板のTOP | 過去ログ集 | 投稿練習 | よく質問される問題 | エッセイblog



51827.Re: 字数n個の文字の並びに必要な文字の種類について  
名前:果汁30%    日付:2017年09月27日(水) 23時06分
Original Size: 785 x 781, 53KB

黄桃様

ご回答有難うございました。
私も自分でやってみた結果は3種類でした。ひとまず黄桃様と同じ答えとなりほっとしています。
黄桃様にご回答いただいた証明の内容はまだ理解できていないため、どこかで時間をかけて
整理してみます。
それと、念のため以下私の証明を記載致しますが、御覧のとおりひどい有様です。
多分こういうことを言いたいのだろうというのをわかっていただけると幸いです。
(参考画像も添付致します。)


文字列の各字の場所をWkとする。
文字の各種類をCqとする。(q=1,2,3,・・・p)

(1)基本ルールのみ存在する場合

p=1のとき、n=2とすると
W1=C1, W2=C1 →W1=W2となり基本ルールを満たさない。

p=2のとき、
nが偶数とすると、
W1=C1, W2=C2, ・・・, Wn-1=C1, Wn=C2 →偶数は基本ルールを満たす。
nが奇数とすると、
W1=C1, W2=C2, ・・・, Wn-1=C2, Wn=C1 →Wn=W1となり基本ルールを満たさない。

p=3のとき、
基本ルールを満たすようにW1から順に埋めていくとすると、
W1は3種類の文字から選択できる。
W2〜Wn-1は2種類の文字から選択できる。
WnはWn-1=W1であれば2種類、Wn-1≠W1であれば1種類の文字から選択できる。
そのためW1〜Wnの全ての場所でルールを満たす。

よって、3種類の文字(p=3)が必要である。


(2)追加ルール(同じ文字にする)を設定する場合

同じ文字にする追加ルールの範囲内に他の追加ルールを含まないケース(ルールX)を考える。
ルールXが設定された文字の場所をそれぞれWa,Wbとする。
ルールXの範囲内の文字列をS,文字列Sの字数をmとし、各字の場所をS1,S2,S3,・・・Smとする。
このとき、ルールXの範囲上と範囲内をあわせた文字列は、
Wa,S1,S2,・・・Sm,Wb で表すことができる。
さらに、Wa=Wbとなることから、文字列は
Wa,S1,S2,・・・Sm,Wb(=Wa)
→Wa,S1,S2,・・・Sm という基本ルールのみ存在する文字列と同じ構成となる。
よって、ルールX内(範囲上を含む)の文字列は3種類の文字が必要である。

次に、ルールXの範囲外からWa,S1,S2,・・・Sm,Wbの取り扱いを考える。
このときの文字列は
・・・,Wa-2,Wa-1,Wa,S1,S2,・・・Sm,Wb,Wb+1,Wb+2,・・・ となる。
ルールXにより、Wa=Wbとなることから、このとき範囲外に適用されている基本ルールは
Wa-1≠Wa →Wa-1≠Wb
Wb≠Wb+1 →Wa≠Wb+1 と考えることができる。
さらにルールX内(範囲上を含む)を1つの場所としてまとめたものをWxとすると、
・・・,Wa-2,Wa-1,Wx,Wb+1,Wb+2,・・・ となり、基本ルールのみ存在する文字列と
同じ構成となる。
そのため、ルールX内(範囲上を含む)の文字列を範囲外の文字列から考慮するときは
1つの文字の場所として扱えばよい。


(3)追加ルール(異なる文字にする)を設定する場合

異なる文字にする追加ルールの範囲内に他の追加ルールを含まないケース(ルールY)を考える。
ルールYが設定された範囲上の文字の場所をそれぞれWc,Wdとする。
ルールYの範囲内の文字列をS,文字列Sの字数をmとし、各字の場所をS1,S2,S3,・・・Smとする。
このとき、ルールY内(範囲上を含む)の文字列は、
Wc,S1,S2,・・・Sm,Wd で表すことができる。
さらに、Wc≠Wdとなることから、基本ルールのみ存在する文字列と同じ構成となる。
よって、ルールY内(範囲上を含む)の文字列は3種類の文字が必要である。

次に、ルールYの範囲外からWc,S1,S2,・・・Sm,Wdの取り扱いを考える。
このときの文字列は
・・・,Wc-2,Wc-1,Wc,S1,S2,・・・Sm,Wd,Wd+1,Wd+2,・・・ となる。
さらに、Wc≠Wdとなることから、範囲外と範囲上の文字列を対象に各字の場所のルールを考えると
Wc-2≠Wc-1,Wc-1≠Wc,Wc≠Wd,Wd≠Wd+1,Wd+1≠Wd+2,・・・となり、文字列Sが無い状態で
基本ルールに従った構成となる。
そのため、ルールYの範囲内の文字列を範囲外の文字列から考慮するときは存在しない
ものとして扱えばよい。


(4)ルールXやルールYが他の追加ルール(ルールZ)に含まれる場合

追加ルール使用条件により、ある追加ルール(A)が他の追加ルール(B)に含まれる場合には、
Aが設定された2つの場所は、どちらもBの範囲上または範囲内に存在しなければならない。
(2つの場所のうち1つがルールBの範囲外を指定すると、使用条件に反する。)
そのため、Aは必ずBに内包される。
(2)(3)よりルールXを1つの文字として扱い、ルールYの範囲内の文字列を存在しないもの
として扱うと、ルールZ内のルールX,ルールYを外して基本ルールのみ存在する文字列に変換する
ことができる。


上記(2)〜(4)により、条件を満たす追加条件がどのように設定されても
基本ルールのみ存在する文字列として考えることが出来る。
また、基本ルールのみ存在する文字列は(1)よりp=3であり、(2)(3)で
変換・存在しないとされた部分もp=3となることから、必要数は3種類である。


それとお気付きかもしれませんが、やりたいこととしては四色定理を自分なりに考えて
みたいと思います。
書きたいことをまとめたら別質問として記載致しますので、もしよろしければそちらも
御覧ください。
(社会人)
h219-110-44-182.catv02.itscom.jp (219.110.44.182)
Mozilla/5.0 (Windows NT 6.3; WOW64; Trident/7.0; rv:11.0) like Gecko


51822.Re: 字数n個の文字の並びに必要な文字の種類について  
名前:黄桃    日付:2017年09月27日(水) 07時57分
もしかしたら、どこか穴があるかもしれませんが、以下のような感じで、3種類、ということがいえそうです。
n=2の場合も許すことにします(2点に異なる文字を配置ということになります)。
長くなるので概略だけ記述します。
問題の条件のうち、【追加ルール使用条件】以外は、以下のように記述できます。
(1)正n角形(頂点をA1,A2,...,Anとする)を用意する。
(2)辺(AiA[i+1], i=1,2,...,n-1, AnA1)は赤く塗る
(3)対角線を交わらないように好きなだけ(0本でもいい)選んで赤か青で塗る。
その上で、
(0)赤い線の両端は異なる文字、青い線の両端は同じ文字になるように文字を配置する
ということを考えることになります。

上記(1),(2),(3)を満たすような図形に対して、次のような操作を行います。
(A)辺以外の赤い線で切ってバラバラにする。これにより内部には青い線しか含まない多角形ができます。
  例: n=4, 四角形ABCDで、対角線ACが赤い時、ABC とCDAの2つの3角形に分割します。
  このようにして得られた2つの多角形は(1)-(3)をやっぱり満たしています。

  これを繰り返してどの多角形にも赤い線が内部にないようにします。
  対角線は交わらないので、赤い線も交わりませんから、どのような順序でも赤い線の数だけ
  この操作(どれかの多角形を選んで赤い線を切る)を繰り返すことができ、その間全体の青い線の数も変わりません。
  すべての赤い対角線を切ってしまうと、各多角形は(1)-(3)の他に、さらに
(3)'対角線を交わらないように好きなだけ(0本でもいい)選んで青で塗る。
も満たしています。
そして、各々の多角形を条件を満たすように文字を配置できれば、全体としてもできます。
  (ばらしたのと逆の順序で順々に文字を配置していけばいい;どの段階でも2つの多角形の共通部分は1つの辺だけなので、
  その2か所が同じになるように合わせる方の多角形の文字の配置を置き換えればよい)
(B)ばらした各多角形について、青い線で結ばれている頂点をすべて1か所にまとめてしまう。
  例1: n=6 六角形ABCDEFで、AC,CE,EAが青い線で結ばれている場合、A=C=Eを1つの点Xにして、
  4点X,B,D,F において、X-B, X-D, X-F という3つの「2角形」が結ばれている状態にする。
例2: n=6 六角形ABCDEFで AC, DF が青い線で結ばれている場合、A=C=X, D=F=Yとして
4点B,X,Y,E が3つの「2角形」B-X, X-Y, Y-E で結ばれている状態にする。
例3: n=6 六角形ABCDEFで ADが青い線で結ばれている場合、A=D=Xとして
5点X,B,C,E,Fが2つの3角形XBCとXEFとが点Xでくっついている状態にする。
その上で、その点を切り離して複数の多角形に分割する。
例1 であれば、XB,XD,XFの3つに、例2であれば、BX,XY,YEの3つに、例3であればXBCとXEFの2つに分ける。

連結している一連の青い線に対応する頂点を1つにまとめると、
対角線は交わらない、外側の隣接点は赤い線で結ばれている
ので、この操作により、他の青い線に影響することなく1点だけを共有するいくつかの独立した多角形(2角形を含みます)に分かれます。

この操作をこの後いくら繰り返しても独立した多角形に共有点はでてこないので各多角形に文字を配置し、
最後に共通する点の部分の文字を調整すれば全体としての配置ができます。

なお、(B)の操作を行う際に、同一視する点の間に「矛盾」(例えば、A=C=Eでなければならないのに、AとEが隣接している)する
可能性がありますが、これは【追加ルール使用条件】により、起こらないことが保証されています。

以上の操作により、元の正n角形は、内部に赤の線も青の線もない、((1),(2)のみを満たす)いくつかの多角形に分割できます。
そして分割された多角形に文字を配置していけば全体として配置が可能です。

内部に線のない、正n角形の各頂点が隣接点が異なるように文字を配置するには、nが奇数なら3, nが偶数なら2種類の文字が必要です。
以上から、最大3種類の文字があれば、このルールをみたすように文字を配置することができます。
(なお、2種類でできる場合もあり、それは、(A),(B)により分割した多角形がすべて偶数角形の場合に限ります)。

#数学的に正しく証明するなら、nに関する帰納法。
fp276e1bf1.chbd224.ap.nuro.jp (39.110.27.241)
Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:55.0) Gecko/20100101 Firefox/55.0

51817.字数n個の文字の並びに必要な文字の種類について  
名前:果汁30%    日付:2017年09月26日(火) 02時47分
初投稿です。
説明がわかりづらく且つ長くて恐縮ですが、どなたかご解答いただける方いましたら
お願い致します。


字数n個の文字の並びを作ります。
基本ルールは以下のとおりです。

【基本ルール】

・使用する文字の種類はなんでもよい(日本語、英語、数字など)。
・同じ文字を何回でも使用してよい。
・k番目(k=1,2,3,・・・,n)とk+1番目(ただしk=nのときは1番目)は異なる文字を使用する。

例)n=5のとき、
・abcdc OK
・5n8hi OK
・abccd ←3番目と4番目が同じなのでNG
・5n8h5 ←5番目と1番目が同じなのでNG


上記の基本ルールに、さらに以下の追加ルールを任意で好きな数だけ設定できます。
ただし、その後に記載の追加ルール使用条件を守る必要があります。

【追加ルール】
1)a番目の文字とb番目の文字を同じ文字にする。(a+1<b)
2)c番目の文字とd番目の文字を異なる文字にする。(c+1<d)


【追加ルール使用条件】
・ある追加ルールが設定されたとき、そのルールが設定された位置の範囲内の1つと範囲外の
 1つをセットとして他の追加ルールを設定することはできない。
例)3番目と8番目を同じ文字にする
  ・4〜7番目は「範囲内」
  ・1,2,9〜番目は「範囲外」
  ・3番目と8番目は「範囲上」
   →4〜7番目のいずれか1つと、1,2,9〜番目のいずれか1つを指定した追加ルールは
    設定できない
    ・4番目(範囲内)と6番目(範囲内)を異なる文字にする OK
    ・5番目(範囲内)と8番目(範囲上)を同じ文字にする OK
    ・1番目(範囲外)と4番目(範囲内)を同じ文字にする NG
    ・2番目(範囲外)と9番目(範囲外)を異なる文字にする OK
    ・7番目(範囲外)と10番目(範囲外)を同じ文字にする NG

・ルールの矛盾が生じるような追加ルールは設定できない。
例)1番目と3番目を同じ文字にする
  さらに、1番目と4番目を同じ文字にする
  →1,3,4番目が同じ文字となるが、3番目と4番目は基本ルールで異なる文字にする必要が
   あるためNG
例)1番目と3番目を同じ文字にする
  さらに、3番目と5番目を同じ文字にする
  さらに、1番目と5番目を異なる文字にする
  →1,3,5番目は同じ文字であり、1番目と5番目を異なる文字に出来ないためNG


【問題】
nが3以上で追加ルールの設定数がいくつであっても文字の並びを作りたい場合、最低何種類の
文字が必要でしょうか。また、その証明はどのようになりますでしょうか。
(社会人/質問者)
h219-110-44-182.catv02.itscom.jp (219.110.44.182)
Mozilla/5.0 (Windows NT 6.3; WOW64; Trident/7.0; rv:11.0) like Gecko


「51817.字数n個の文字の並びに必要な文字の種類について」への返信


特定の個人への誹謗中傷は無予告削除対象です。

   投稿KEY
   パスワード

EZBBS.NET produced by InsideWeb