当前位置: 首页 > news >正文

IMO2025 Problem 1

image

考虑 \(n = 3\) 时的下三角,显然有三个容易构造的解,\(k = \{0, \, 1, \, 3\}\),构造如下:

image

image

image

那么 \(n > 3\) 呢?由于下三角的点数恰好为 \(1 + 2 + \cdots + n\) 个点,对于第一条直线,有且仅有 \(3\) 中方式覆盖 \(n\) 个点,也就是非 sunny 的直线,这条直线画完之后将会把下三角递归到第 \(n - 1\) 层,因此同解。

考虑证明不存在其他解,如果考虑不进行递归,那么三角形的三个顶点分别对应三条直线,而边上共有 \(3\)故下三角的斜边上 \(n\) 个点每一个点对应一条 sunny 直线,如果需要覆盖掉直角边上的 \(3n - 3\) 个点,至少需要 \(\left\lceil\frac{3n - 3}{2}\right\rceil \ge n\),当且仅当 \(n = 3\) 时等号成立,故不存在其他方案。

因此符合题目条件的所有的 \(k \in \{0, \, 1, \, 3\}\)

http://www.jsqmd.com/news/25035/

相关文章:

  • Day6综合案例2-注册信息
  • 2014吉林省赛题解 | CCUT应用OJ——Sign in
  • 访答知识库-可以本地使用的知识库
  • 代码大全2 第三四章
  • https代理服务器(六)再次java动态签发【成功】
  • node
  • [AGC032D] Rotation Sort 题解
  • [AGC024E] Sequence Growing Hard 题解
  • 实验2 现代C++编程初体验
  • P7154 [USACO20DEC] Sleeping Cows P 题解
  • Java流程控制——switch多选择结构
  • P3607 [USACO17JAN] Subsequence Reversal P 题解
  • 概率论测试(上)
  • 示性函数2
  • 随笔/杂记
  • k3s 基础 —— 将 traefik 替换为 ingress-nginx
  • 使用 Swift 解析验证码(结合 Tesseract OCR)
  • 常见排序算法Java实现
  • 题解:qoj1875 Nein
  • 【uni-app】申请高德地图key,封装map.js,实现H5、iOS、Android通过getlocation获取地图定位信息(摘)
  • .NET开发上手Microsoft Agent Framework(一)从开发一个AI美女聊天群组开始
  • java作业4
  • 10/28
  • 大学四年的学费/生活费自足攻略
  • 175天 隧道技术篇防火墙组策略FRPNPSChiselSocks代理端口映射C2上线
  • 10.28每日总结
  • 每日反思(2025_10_28)
  • 102302126李坤铭作业1
  • 10月28日日记
  • 【大模型应用开发】之本地部署大模型