で $n \times n$ ポイントのグリッド、選択 $2n-1$ ポイント、常に直角三角形があります

2
Yes it's me 2020-06-13 20:47.

$\textbf{Question:}$ 考えてみてください $n×n$ポイントのグリッド。どのように選んでもそれを証明する$2n-1$ これらからのポイント、これらの間に頂点を持つ直角三角形が常にあります $2n-1$ ポイント。

この質問は確かに前に投稿されましたhttps://math.stackexchange.com/questions/668414/choosing-2n-1-points-from-n-times-n-grid-such-that-3-points-always-form-a、しかし私はグラフ理論を使用して別の解決策を探していました。

私はこの質問を次のようなグラフ理論の観点から言い換えました。

与えられた $n$ 沿って $n$ 2部グラフ(頂点が行と列に対応する場合)、および列のある点がある場合 $c_i$ と行 $r_j$、間にエッジを追加します $(c_i,r_j)$。次に、ステートメントはそれをで示すことと同等です$2n-1$ このグラフのエッジには、少なくとも長さのパスが存在する必要があります $3$

ある頂点の次数が隣接する頂点の次数よりも1より大きい場合、次のような明らかな事実に気づきました。 $1$

3 answers

2
Calvin Lin 2020-06-14 02:13.

他の2つの解決策を読むことを強くお勧めします。それらははるかに簡単な証拠を提供します。


注:セットアップでは、底辺がエッジに平行な直角三角形のみが考慮されます(これにより長さ3のパスが得られます)。これは問題を証明するのに十分です。傾斜した直角三角形(長さ3のパスにつながらない)を考慮する必要はありません。

「ある頂点の次数が隣接する頂点の次数よりも1より大きい場合、1になる」という観察結果が主な要点です。

ヒント:焦点を合わせる代わりに$n\times n$ 四角、状態をリラックスして $ n \times m$ 長方形。


誘導によってより一般的なステートメントを証明します。

$ n, m \geq 2$、 のために $ (n, m)$ 少なくとも2部グラフ $ n + m - 1 $ エッジには、長さ3のパスがあります。

基本ケース:それを証明する $ n = 2$ そしてすべて $m\geq 2$
これは読者に任されています(次数の合計を考慮してください$ d(m_1) + d(m_2) = n + 1$。)

帰納法:矛盾による証明。
のために仮定します$n, m \geq 3$、長さ3のパスがないようなグラフがあること $ n, m \geq 2$
頂点があります(WLOG$c_1$)程度の $d \geq 2$
場合$d = m$、明らかに関与していない他のエッジ $c_1$私たちは長さ3のパスを与え
た場合$d = m-1$、この頂点とその隣接頂点の1つを除くすべてを削除します。これにより、 $ (n, 2)$ 2部グラフ $n+m-1-(m-2) \geq n + 2 -1 $エッジ。
それ以外の場合は、この頂点とそのすべての隣接頂点を削除します。これにより、$ (n-1, m - d)$ 2部グラフ $ n+m - 1 - d \geq (n-1) + (m-d) - 1 $ エッジ。


3
bof 2020-06-14 03:47.

これがより簡単な証拠です。考えてみてください$m\times n$ グリッド、 $m,n\ge2$; しましょう$P$ グリッドポイントのセットであり、 $|P|=m+n-1$; 矛盾があると仮定して$P$ 直角三角形の頂点は含まれていません。

しましょう $H$ (それぞれ $V$)すべてのポイントのセットになります $x\in P$ 他のポイントがないように $P$ と同じ水平(それぞれ垂直)線上にあります $x$。明らかに$P=H\cup V$。以来$|P|=m+n-1$、どちらか $|H|\ge m$ または $|V|\ge n$

一般性を失うことなく、私たちは $|H|\ge m$。の2点から$H$ 同じ水平線上に置くことはできません、それぞれ $m$ 水平線には、 $H$ したがって、 $P$、wherece $|P|=m$ そして $n=1$、私たちの仮定と矛盾する $n\ge2$

PSこの証明をグラフ理論に変換すると、次のようになります。2部グラフには2部グラフがあります$(V_1,V_2)$$|V_1|=m\ge2$$|V_2|=n\ge2$、そしてそれは持っています $m+n-1$エッジ。長さのパスがない場合$3$、次に各エッジには次数の端点があります $1$。したがって、少なくとも$m+n-1$ 次数の頂点 $1$、つまり、次数の最大1つの頂点 $\ne1$。したがって、すべての頂点が$V_1$ 学位を持っている $1$、ただあります $m$ エッジ、および $n=1$、またはのすべての頂点 $V_2$ 学位を持っている $1$、ただあります $n$ エッジ、および $m=1$

2
Aqua 2020-06-22 01:31.

このグラフを推測すると $G$ 二部です。

  • サイクルがある場合は、それぞれに長さがあります $2l$ したがって、最小の長さは $4$ これで完了です。
  • サイクルがない場合は、ツリーである必要があります(サイクルがあると言えば簡単に確認できます $k$ コンポーネント、次に各コンポーネント $C_i$ 我々は持っています $\varepsilon _i\geq n_i -1$、しかしこれは力 $k=1$)したがって接続されています。頂点が存在しなければならないので$u$ そして $v$ 接続されていないパーティションのさまざまな部分に、少なくとも明らかに長さが異なるパスがそれらの間に存在します $3$ これで完了です。

Related questions

MORE COOL STUFF

ダイアナ妃は、8歳でウィリアム王子を寄宿学校に送るという決定に「涙を流した」

ダイアナ妃は、8歳でウィリアム王子を寄宿学校に送るという決定に「涙を流した」

ウィリアム王子が 8 歳のときに寄宿学校に通わせたことについて、ダイアナ妃がどのように感じたかを学びましょう。

シャキール・オニールは、レイカーズのスターが彼のチキン帝国を北テキサスに拡大するにつれて、ダラスの外に永住権を購入しました

シャキール・オニールは、レイカーズのスターが彼のチキン帝国を北テキサスに拡大するにつれて、ダラスの外に永住権を購入しました

Shaquille O'Neal は最近、Big Chicken レストラン帝国を拡大するため、ダラス郊外に住居を購入しました。

「90 日間の婚約者」: イヴが逮捕され、浮気スキャンダルの後、モハメドに対する家庭内暴力の容疑に直面している — 何が起こったのか?

「90 日間の婚約者」: イヴが逮捕され、浮気スキャンダルの後、モハメドに対する家庭内暴力の容疑に直面している — 何が起こったのか?

「90日の婚約者」シーズン9のスター、イヴ・アレラーノが逮捕され、モハメド・アブデルハメドへの暴行容疑で家庭内暴力の罪に問われている.

ナターシャ・リオンは、ピーウィー・ハーマンは「ビジネスで最高のGIFを送る」と言います

ナターシャ・リオンは、ピーウィー・ハーマンは「ビジネスで最高のGIFを送る」と言います

ナターシャ・リオンは、ピーウィー・ハーマン自身、ポール・ルーベンスと親密です。彼らの友情について彼女が言ったことを発見してください。

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セント ヘレナ島のジェイコブズ ラダーは 699 段の真っ直ぐ上る階段で、頂上に到達すると証明書が発行されるほどの難易度です。

The Secrets of Airline Travel Quiz

The Secrets of Airline Travel Quiz

Air travel is far more than getting from point A to point B safely. How much do you know about the million little details that go into flying on airplanes?

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

バイオニック読書はあなたをより速く読むことができますか?

バイオニック読書はあなたをより速く読むことができますか?

BionicReadingアプリの人気が爆発的に高まっています。しかし、それは本当にあなたを速読術にすることができますか?

Razer Phoneレビュー:ゲーム用電話を作る正しい方法

Razer Phoneレビュー:ゲーム用電話を作る正しい方法

ゲーム中心のスマートフォンを作成する以前の試みには、スライド式ゲームコントローラーを備えた電話、Sony PlayStationPortableと電話とNokiaN-Gageのクロスが含まれます。Razerは、最初のゲーミングフォンとして、見事なディスプレイと優れたスピーカーを備えた強力な黒い長方形を採用しました。

2018年のビデオゲームの予測

2018年のビデオゲームの予測

キングダムハーツIII私たち全員が核のホロコーストで死ぬわけではないと仮定すると、ビデオゲームは2018年に何をもたらすでしょうか?今週のKotakuSplitscreenで、いくつかの予測の時間です。最初のカークと私は、Gravity Rush 2ファン、警察のスワッティングコールで死にかけている罪のない男、そして以前のローガンポールの激しい論争を含む今週のニュース(13:46)について話します来年の大きな予測を立てます(34:16)。

スイス航空ショーで2機の曲技飛行機が衝突、1人のパイロットが死亡したと報告

スイス航空ショーで2機の曲技飛行機が衝突、1人のパイロットが死亡したと報告

昨日のショアハム航空ショーでの恐ろしい墜落に続いて、ドイツのグラスホッパーズ曲技飛行チームに所属する2機のイカルスC42航空機が、スイスのディッティンゲンでの航空ショーで演奏中に空中で衝突しました。報告によると、1人のパイロットが衝突中に飛行機から投げ出され、地面にパラシュートで降下しました。

Chromebookをたった150ドルで購入できるようになりました(そしてさらに良くなっています)

Chromebookをたった150ドルで購入できるようになりました(そしてさらに良くなっています)

5年前、GoogleのCEOであるEric Sc​​hmidtは、ラップトップは使い捨てになると宣言しました。もうすぐです。

ケイト・ミドルトンとウィリアム王子は、彼らが子供たちと行っているスパイをテーマにした活動を共有しています

ケイト・ミドルトンとウィリアム王子は、彼らが子供たちと行っているスパイをテーマにした活動を共有しています

ケイト・ミドルトンとウィリアム王子は、子供向けのパズルの本の序文を書き、ジョージ王子、シャーロット王女、ルイ王子と一緒にテキストを読むと述べた.

事故で押しつぶされたスイカは、動物を喜ばせ水分補給するために野生生物保護団体に寄付されました

事故で押しつぶされたスイカは、動物を喜ばせ水分補給するために野生生物保護団体に寄付されました

Yak's Produce は、数十個のつぶれたメロンを野生動物のリハビリ専門家であるレスリー グリーンと彼女のルイジアナ州の救助施設で暮らす 42 匹の動物に寄付しました。

デミ・ロヴァートは、新しいミュージシャンのボーイフレンドと「幸せで健康的な関係」にあります: ソース

デミ・ロヴァートは、新しいミュージシャンのボーイフレンドと「幸せで健康的な関係」にあります: ソース

8 枚目のスタジオ アルバムのリリースに向けて準備を進めているデミ ロヴァートは、「スーパー グレート ガイ」と付き合っている、と情報筋は PEOPLE に確認しています。

Plathville の Kim と Olivia Plath が数年ぶりに言葉を交わすことへようこそ

Plathville の Kim と Olivia Plath が数年ぶりに言葉を交わすことへようこそ

イーサン プラスの誕生日のお祝いは、TLC のウェルカム トゥ プラスビルのシーズン 4 のフィナーレで、戦争中の母親のキム プラスと妻のオリビア プラスを結びつけました。

水門の修理

水門の修理

天王星と海王星の間の領域に向かって宇宙を 3/4 g の低温で航行しながら、私たちは数週間燃え続けていました。Dawson Trawler の科学者が Yggdrasil ポータルと呼んだもの。

美しいもの

美しいもの

女性として、私は通常、関係を築くことをためらっています。私はいつも彼らに負けないように苦労しました。私は誰かと共有したいという衝動と戦わなければなりません。

逃走中の女性からの発信

最も家が必要なときに家のように感じる場所はありません。

逃走中の女性からの発信

私は誰よりも移動しました。父が住んでいた土地には、父が 1 歳馬を折るミニチュアの競馬場がありました。

死にゆく男から学んだ最大の人生の教訓

彼は、私たちが持っているのはこの現在の瞬間だけであることを知るのが遅すぎました。

死にゆく男から学んだ最大の人生の教訓

ブラッドは、カーキ色のショート パンツとポロ シャツを着たまま、白いゴルフ グローブを両手で高く引っ張ったまま、ベッドルームに入ってきました。彼は満面の笑みを浮かべながら、「今年は私の人生で最高の年だったと思います!」と言いました。通常は保守的な消費者である私たちは、通常とは異なることをしました。

Language