zenaの日記

麻雀と最近放置している不等式と、極希に更新しているスペクトル以外には、ここを見る価値は基本的にありません。また、管理者は気まぐれにしか更新しませんので悪しからず。

ジュース

久しぶりにジュースの問題(mixiの2009/11/23かここの下書きにある.)を考えてみたけど,1/n以上あるかどうかだけの判定だとn=6で反例が出来るようだ.(勘違いしている可能性はある)
今のところ,全ての冪集合を確かめる方でDulmage–Mendelsohn Decompositionとか云うのを使って帰納法にするか,アルゴリズムの方でTutte条件を確かめてperfect matchingを見つければいい気がするが,どちらも難しそう.

と思ったので普通にアルゴリズム詰めてたら,できてるような気がしてきた.が,普通に証明にギャップがあったwwww