岡圭吾(東京大学) 稲葉直貴(タイムインターメディア) 飯野玲(日本評論社)

Slides:



Advertisements
Similar presentations
Voronoi Game on Graph and its Complexity 寺本 幸生 上原 隆平 (JAIST)
Advertisements

2015 年度 有限幾何学 期末試験 次の各問に答えよ.( (1), (2), (3), (4), (5), (7), (8), (10) は答えだけでよい) (1) 有向閉路が存在しない位数 4 のトーナメントを描け. (2) 内点の個数が 10 個の正則 2 分木の葉の個数を求めよ. (3) グラフ.
ACM/ICPC と アルゴリズム 「実践的プログラミング」 稲葉 一浩. 自己紹介 ﻪ 理Ⅰ → 理学部情報科学科 → 情報理工学系研究科コンピュータ科学専攻 ﻩ 博士課程1年 ﻩXML を扱う専用言語の研究など ﻪ 個人的には ﻩ ﻯD.
1 設計基礎コース もう一度学ぶ材料力学の基礎 座屈 ( Buckling ) 長軸に軸方向圧縮力を作用させると、ある荷 重で急に軸が曲がる。 この急に曲がる荷重条件を探る。 X の位置での曲げモーメントは たわみの微分方程式は.
模擬国内予選2013 Problem F テトラ姫のパズル 原案:須藤 解答:大友、須藤 解説:須藤.
3次元nクイーン問題の 解に関する研究 論理工学研究室 伊藤精一
凸関数じゃないですか (最大値/最小値を求める問題) 目的関数を固定する (最大値/最小値を最小/最大化する問題)
豊中高校土曜講座「数学セミナー2003」 プラトン多面体の数学 なぜ正多面体は5種類しかないのか 大阪府立豊中高等学校 深川 久.
6 空間図形 1章 空間図形 §4 空間における平面と直線         (2時間).
折り紙幾何学 ~折り紙で数学を楽しもう~ 2903 木村 麻里.
    有限幾何学        第8回.
中学数学1年 5章 平面図形 §1 図形の基礎と移動 (7時間).
「2次方程式を利用して、いろいろな問題を解決しましょう。」
プログラミング入門 手順を作る マイクロワールドEX講義用資料(ICT活用教育ICT活用教育研究所)
    有限幾何学        第12回.
下のように、つりあいのとれた形の半分をかくしました。見えている半分の形から全体の形を予想しましょう。
 Combinations(2)        古川 勇輔.
4章 平行と合同 2 多角形の外角の和.
A path to combinatorics 第6章前半(最初-Ex6.5)
碁石ゲームに関する考察 4目並べ講座 パターン生成ゲームの楽しみ 徳山 豪 (東北大学) .
情 報 A ー ディジタル化のしくみ ー.
平行四辺形のかきかたを 確認しよう!!.
JAVAでつくるオセロ 伊東飛鳥、宮島雄一 長畑弘樹、ソギ原直人.
3 Seminar ブラッシュアップ! パワポが 好きになる! 練習スライド マイクロソフトMVP 大阪府立学校教員 講 師 稲葉 通太
拡張タングラムとラッキーパズルの凸配置について
学習の流れ 本時のねらい 「2次方程式を利用して、いろいろな問題を解決しましょう。」 ↓ 課題の提示 カレンダー 図形での活用場面4
研究集会「組合せゲーム・パズル」,豊橋技術科学大学
博士たちの愛する幾何 徳山 豪 東北大学 Geometry that professors love
本時のねらい 「相似の意味と性質を理解し、相似な図形の辺の長さや角度を求めることができる。」
SystemKOMACO Jw_cad 基本操作(6) Ver.1
シャノンのスイッチングゲームにおけるペアリング戦略について
徳山 豪 東北大学 Geometry that professors love 博士たちの愛する幾何.
平成15年度情報システム工学序論 Inside of the Black Box バーコード(スキャナ)
独立成分分析 1.問題は何か:例:解法:全体の見通し 2007/10/17 名雪 勲.
三角形や四角形ではない図形の 角の大きさの和を求めよう。.
中学校2年生 数学科 図形の性質.
本時のねらい 「三角形の1辺に平行な直線が他の2辺と交わるとき、それぞれの交点は、その2辺を等しい比に分けることを理解する。」
千葉大学 理学部数学・情報数理学科 松井宏樹
中3数 三平方の定理の導入 中学校 3年数学 三平方の定理 授業導入時に実施する。
「R入門」  5.7 行列に対する諸機能  10月23日 (木) 発表者 大城亜里沙.
立体のいろいろな見方 面や線を動かしてできる立体
面積の単位(㎠/㎡/a/ha/㎢) 1㎡ 1a 1ha 1k㎡ ㎡ 10000㎡ 100㎡ 10000a 100a 100ha
古代の難問と曲線 (3時間目) 筑波大学大学院 教育研究科 1年                 石井寿一.
証 明 本時のねらい 「仮定、結論の意味を理解し、図形の性質に基づいて、なぜそうなるのかを説明できる。」
京都大学大学院情報学研究科 宮川博光 伊藤大雄
5 図形と合同 1章 三角形 §1 二等辺三角形         (4時間).

GRAPESを用いた平面図形の教材研究と授業実践
中学数学1年 5章 平面図形 §2 作図 (3時間).
多角形の外角の和 凹型四角形の角 星形五角形の内角の和
7 Calculating in Two Ways: Fubini’s Principle
母分散の信頼区間 F分布 母分散の比の信頼区間
学 正多角形のどんな性質を使えば,プログラミングで正多角形を描くことができるだろうか。
4. システムの安定性.
中3数 三平方の定理の計算 三平方の定理の逆 中学校 3年数学 三平方の定理 授業第2時に実施する。
決断のための分布合算 京大(医)統計遺伝学分野 山田 亮.
円と正多角形 プログルをつかって学ぼう.
今から2200年ほど前に,古代ギリシアのアルキメデスは,円周率が3と71分の10より大きく,3と7分の1より小さいことを発見しました。・・・
5年 算数 「面積(平行四辺形)」.
本時のねらい 「合同な三角形の作図を通して三角形の合同条件を導き、それを理解する。」
プログラミング入門 はじめてのタートルグラフィックス マイクロワールドEX講義用資料(ICT活用教育ICT活用教育研究所)
1.基本概念 2.母集団比率の区間推定 3.小標本の区間推定 4.標本の大きさの決定
第2章 統計データの記述 データについての理解 度数分布表の作成.
2017年度 有限幾何学 期末試験 注意:ループと多重辺がないグラフのみを扱う. 問1 次の定理と,その証明の概略を読み,各問に答えよ.
博士たちの愛する組合せ論 徳山 豪 東北大学 Combinatorics that professors love
問2 次の問に答えよ. (ただし,握手補題,オイラーの定理,Oreの定理 は授業で紹介したものとする) (1) 握手補題を書け.
下の図のように、直角三角形と正方 形が直線ℓ上に並んでいる。 8cm 8cm ℓ 8cm 8cm.
アルゴリズム ~すべてのプログラムの基礎~.
ペンシルパズルの大道芸ステージショーへの応用
ペンシルパズル「一本線」のヒント数の扱いに関する解析
Presentation transcript:

岡圭吾(東京大学) 稲葉直貴(タイムインターメディア) 飯野玲(日本評論社) ポリオミノの はみ出し可能な被覆問題 岡圭吾(東京大学) 稲葉直貴(タイムインターメディア) 飯野玲(日本評論社)

ポリオミノとは いくつかの単位正方形が辺でつながった図形 ポリオミノでない ポリオミノである  いくつかの単位正方形が辺でつながった図形 点でつながったものや、2つに分かれているものは、ポリオミノではありません ポリオミノでない ポリオミノである

QUIZ 6×6の盤面は 右のポリオミノをいくつか使ってピッタリ覆えるか?(回転、裏返しはよい) Ans. 覆えない。(証明略) ?

はみだしてもいいことにする 覆えた!

はみ出しを許しても、ゼッタイ6×6を覆えないポリオミノは存在するか?

穴開き禁止なら? それでも存在する ここが覆えていない

問題 穴開きでない どんなポリオミノによっても 覆えるポリオミノには どんなものがあるだろう?

穴開きでないどんなポリオミノによっても覆えるポリオミノ モノミノ  ドミノ  は、どんなポリオミノを持ってきても必ず覆える トリオミノ    テトロミノ             も必ず覆える

ペントミノ 必ず覆える 覆えないものがある 必ず覆える → 証明が必要 覆えないポリオミノがある  → そのポリオミノを示せばよい 未解決

2×2は必ず覆えることの証明 2×2を覆えないポリオミノがあったとする 外周にセルが連続する箇所はない

2×2は必ず覆えることの証明 2×2を覆えないポリオミノがあったとする 外周にセルが連続する箇所はない

2×2は必ず覆えることの証明 2×2を覆えないポリオミノがあったとする 外周にセルが連続する箇所はない

2×2は必ず覆えることの証明 2×2を覆えないポリオミノがあったとする 外周にセルが連続する箇所はない

2×2は必ず覆えることの証明 2×2は必ず覆える → P も必ず覆える 2×2を覆えないポリオミノがあったとする 外周にセルが連続する箇所はない 2×2は必ず覆える → P も必ず覆える

ペントミノY  は必ず覆えることの証明 Yを覆えないポリオミノが存在したとする 外周にセルが連続する箇所はない

ペントミノY  は必ず覆えることの証明 Yを覆えないポリオミノが存在したとする 外周にセルが連続する箇所はない

ペントミノY  は必ず覆えることの証明 Yを覆えないポリオミノが存在したとする 外周にセルが連続する箇所はない

ペントミノY  は必ず覆えることの証明 Yを覆えないポリオミノが存在したとする 外周にセルが連続する箇所はない

ペントミノY は必ず覆えることの証明 Yを覆えないポリオミノが存在したとする 外周にセルが連続する箇所はない 外周に一つおきにセルが並ぶ箇所もない

ペントミノY は必ず覆えることの証明 Yを覆えないポリオミノが存在したとする 外周にセルが連続する箇所はない 外周に一つおきにセルが並ぶ箇所もない

ペントミノY は必ず覆えることの証明 Yを覆えないポリオミノが存在したとする 外周にセルが連続する箇所はない 外周に一つおきにセルが並ぶ箇所もない

ペントミノY は必ず覆えることの証明 Yを覆えないポリオミノが存在したとする 外周にセルが連続する箇所はない 外周に一つおきにセルが並ぶ箇所もない

ペントミノY は必ず覆えることの証明 Yを覆えないポリオミノが存在したとする 外周にセルが連続する箇所はない 外周に一つおきにセルが並ぶ箇所もない

ペントミノY は必ず覆えることの証明 Yを覆えないポリオミノが存在したとする 外周にセルが連続する箇所はない 外周に一つおきにセルが並ぶ箇所もない

ペントミノY は必ず覆えることの証明 Yを覆えないポリオミノが存在したとする 外周にセルが連続する箇所はない 外周に一つおきにセルが並ぶ箇所もない

ペントミノY は必ず覆えることの証明 Yを覆えないポリオミノが存在したとする 外周にセルが連続する箇所はない 外周に一つおきにセルが並ぶ箇所もない

Yは必ず覆える ペントミノY は必ず覆えることの証明 Yを覆えないポリオミノが存在したとする 外周にセルが連続する箇所はない 外周に一つおきにセルが並ぶ箇所もない Yは必ず覆える

ペントミノT は必ず覆えることの証明 (概要) → 枝分かれのない一本の道になっている。ただし道から一マスはセルが突き出ていてもよい → 下の図のどちらかが4辺のどこかにある

Xを覆えないポリオミノ 11×11 (57マス)

Iを覆えないポリオミノ 33×33 (423マス)

ヘキソミノ 覆えないものがある 未解決

作業用 斜めに連続しない 未解決

n×n (nは奇数)の中に、ぴったり収まる+,X を考える +はn×nのエリアに高々9個しか入らない ひとつの+とひとつのXは高々8マスでしか重ならない(+の縦線と横線を別々に考えれば自明) → Xは+によって高々8×9=72マスしか覆われない n×nのエリアにXは高々9個しか入らない 面積n以上のポリオミノはn×nのエリアにそれらのうちのnマスが入るように置ける → そのようなポリオミノがXで覆われたとき、  n/9 を覆うXが存在する → n>72*9 のとき、そのポリオミノは+で覆えない