首页 > 其他分享 >皮克定理及其证明

皮克定理及其证明

时间:2024-05-13 18:19:34浏览次数:12  
标签:皮克 多边形 PT dfrac 定理 证明

太美丽的梦。

如果说有一个公式让我日日夜夜都想着证明之,那么也就只有皮克定理了。

参考:百度百科

考虑数学归纳法。

记号

记皮克定理为 \(S_P=P_n+\dfrac{P_m}{2}-1.\)

其中 \(P_n\) 表示所求多边形的内部的格点数,\(P_m\) 表示所求多边形的边上的格点数。

\(S_P\) 表示多边形的面积。

定义 \(PP'\) 为两个不重叠的多边形 \(P,P'\) 的并集。

数学归纳法 · 递推部分证明

考虑到每个多边形都可以表示作若干个不重叠的三角形的并集。所以当证明

在 \(P\) 满足定理,与之有一条重边的三角形 \(T\) 满足定理时 \(PT\) 满足定理,一般三角形 \(T\) 满足定理

定理成立。

先证前半部分。

\[S_P=P_n+\dfrac{P_m}{2}-1 \]

\[S_T=T_n+\dfrac{T_m}{2}-1 \]

设两个多边形的重边上的格点数为 \(c.\) 则

\[S_{PT}=S_P+S_T=P_n+\dfrac{P_m}{2}-1+T_n+\dfrac{T_m}{2}-1=(P_n+T_n+c-2)+\dfrac{P_m+-c+T_m-c+2}{2}-1=PT_{n}+PT_m-1 \]

标签:皮克,多边形,PT,dfrac,定理,证明
From: https://www.cnblogs.com/QxBlogs/p/18189749/Pick_Thoerem

相关文章

  • 日本联合研究团队发布 Fugaku-LLM——证明大型纯 CPU 超算也可用于大模型训练
    相关:https://mbd.baidu.com/newspage/data/landingsuper?context={"nid"%3A"news_10139665591063236146"}研究团队表示其充分挖掘了富岳超算的性能,将矩阵乘法的计算速度提高了6倍,通信速度也提升了3倍,证明大型纯CPU超算也可用于大模型训练。Fugaku-LLM模型参数规模......
  • #dp,Dilworth定理#洛谷 4934 礼物
    题目传送门分析首先,可以放在一起当且仅当\(\max\{a_i,a_j\}\&\min\{a_i,a_j\}\neq\min\{a_i,a_j\}\)根据Dilworth定理可知最小链划分中链的数目等于最长反链的长度所以设\(dp[i]\)表示以\(i\)为结尾的反链的最大长度,则\(dp[i]=\max_{j|i}\{dp[j]\}+[a_k==i]\)......
  • 零知识证明: Tornado Cash 项目学习
    前言最近在了解零知识证明方面的内容,这方面的内容确实不好入门也不好掌握,在了解了一些基础的概念以后,决定选择一个应用了零知识证明的项目来进行进一步的学习。最终选择了TornadoCash这个项目,因为它著名且精致,适合入门的同学进行学习。学习TornadoCash项目,涉及以下方面:......
  • 如何写好Simulation证明(二): 半诚实模型下MPC的定义
    3.SecureComputation–SimulationforSemi-honestAdversaries我们在这里考虑的模型是staticsemi-honest敌手下的两方安全计算.这样的敌手能够在协议开始之前决定控制某一方,并且需要按照协议的描述执行.需要注意的是,这是一个非常弱的假设.如果敌手没有按照协议流......
  • 如何写好Simulation证明(三): 半诚实敌手模型下的OT
    4.ObliviousTransferforSemi-HonestAdversaries在本文中,我们将给出一个证明:基于enhancedOWP,构造一个半诚实敌手模型下的OT.首先我们先介绍enhancedOWP概念.4.1EnhancedOWP.对这个特殊的OWP我们先不做过多的解释,我们先关注参数.一般正式的定义中,一个OWP具......
  • 如何写好Simulation证明(一): 语义安全
    密码学中很多证明需要用到Simulation,尤其是ZK,MPC等等.对于初学者来说,涉及Simulation的证明往往不容易理解,更别说自己独立证明,所以有必要学习一下如何写这样的证明.文章主要参考YehudaLindell的讲义:Howtosimulateit.1.Introduction什么是Simulation?中文翻译......
  • §3. 收敛定理的证明
    不做要求。有能力的同学掌握贝塞尔不等式、黎曼-勒贝格定理和收敛定理的证明。  贝塞尔(Bessel,FriedrichWilhelm,1784~1846)德国天文学家,数学家,天体测量学的奠基人之一。1784年7月22日生于明登,1846年3月17日卒于柯尼斯堡。15岁辍学到不来梅一家出口公司当学徒,在学习航海术......
  • 逆向学习-证明自己吧
     PeiD查看一下,无壳IDA打开静态分析,提示key就是输入的值 F5反汇编看下伪代码,发现sub_401060函数是逻辑判断的关键  可以看到想要正确返回有2个条件,但第一个条件只是把v5变成空值,但并不能得到什么内容跟输入的值有关,还是要看第二个条件看下整个函数注意运输逻辑1.首先......
  • 最高院---发包人对质量问题单方委托第三方单位的,第三方单位所作意见不足以单独对抗竣
    (2020)最高法民申3438号  银川双兴昇工贸有限公司、长枫建设集团有限公司建设工程施工合同纠纷再审审查与审判监督申请人主张:双兴昇公司申请再审称,1.一、二审判决认定事实错误。长枫公司、长枫宁夏分公司在合同履行过程中存在偷工减料、未按图施工的违约行为,案涉钢结构厂房不符......
  • [学习笔记] 质数与唯一分解定理 - 数论
    素性测试素性测试就是判断某个数是否为质数。费马小定理内容:若\(p\)为质数,\(a\)为任意整数,有\(a^{p-1}\equiv1(mod\p)\)那么可以多次随机取一个基数\(a\in(1,p)\)若\(p\)满足上式,那么它为质数的可能性就越大。MillarRabin素性测试inlinellqpow(lla,lln,ll......