[组合] 求鸟最多的圆上最少几只鸟

地上$10$只鸟，任意$5$只中至少$4$只共圆，求鸟最多的圆上最少几只鸟

分享到: QQ空间 腾讯微博 腾讯朋友

abababa

2^#

发表于 2019-3-3 19:43 | 只看该作者

回复 1# abababa

顶一下这帖

TOP

业余的业余

3^#

发表于 2019-3-4 01:19 | 只看该作者

回复 2# abababa

这个问题蛮绕，程序搜都不知道怎么写。先试着换个形式表述下。把 $\{A,B,C,D,E,F,G,H,I,J\}$ 分成任意必要个数的小组，小组长度无限制，使得:

1. 从其中任取 $5$ 个的所有组合中，每个组合中都至少有一种方式使得其中的 $4$ 个同时出现在上面的小组之一；
2. 任意两个小组的共同元素不多于 $2$ 个.

则所有这些合法的分组方式中单组长度最大值的最小值，即为所求答案。

TOP

realnumber

4^#

发表于 2019-3-4 14:33 | 只看该作者

地上6只鸟，任意5只中至少4只共圆，求鸟最多的圆上最少4只鸟.
就三个等圆，两两相交，6个交点位置6只鸟.
变成8只鸟就开始晕了，特殊到一般也不容易啊.

TOP

hbghlyj

5^#

发表于 2020-1-14 12:31 | 只看该作者

本帖最后由 hbghlyj 于 2020-1-14 13:37 编辑

平面上有10个互异的点,任意5点中至少有4点共圆,问点最多的圆周上最少有几个点?
首先证明有5点共圆.如若不然,则5点组共有$C_{10}^5=252$个,每个5点组中有4点共圆.这4点属于6个5点组,于是圆的个数≥$\frac{252}{6}$=42个.这42个不同的圆上总共应有42x4=168点,但实际只有10点.因而,至少有一点A属于$\lceil\dfrac{168-1}{10}\rceil$=17个圆周.这17个圆周上另有17×3=51个点,余下9点,至少还有一点B属于$\lceil\dfrac{51-1}{9}\rceil$=6个圆周.这有两个公共点的6个圆周上另有6×2=12个点,余下8点,至少还有一点B属于$\lceil\dfrac{12-1}{8}\rceil$=2个圆周.这两个圆周有三个公共点,矛盾.
其次证明前面所得出的至少有5点所在的这个圆周上至少有9点.记五点A,B,C,D,E共圆周c.如果结论不真,则记不在C上的两点为H,K.因{A,B,C,H,K}中有4点共圆，而H,K均不在c上, 因而可设A,B,H,K共圆d，C,D,E均不在d上.因{C,D,E,H,K}中有4点共圆,而H,K均不在c上，故可设C,D,H,K共圆e上,而E不在e上. 于是,考查{A,C,E,H,K}中任何4点共圆上均导致矛盾.故在e之外，至多有1只鸟.即有鸟最多的一个圆周上至少有9只鸟.

TOP

hbghlyj

6^#

发表于 2020-1-14 13:17 | 只看该作者

本帖最后由 hbghlyj 于 2020-1-15 12:45 编辑

设点最多的圆上至少有l个点，当九点共圆,第十点在圆外时l=9，则4≤l≤9.
首先证明，l≠4. 由l≤9，必有4点不共圆，过其中每3点作一个圆，共得4个圆，其余6点与上述4点组成6个5点组，因而必在(上述4个圆中)某一个圆上，6点中必有2个在同一圆上，因此这五点共圆.
其次，如果5≤l≤8，设圆c上有l个点，则c外至少有两点A,B. 对圆c上任三点，其中必有两点与A,B共圆，不妨设ABCD,ABEF共圆，c上第5个点G及C,E,A,B五点中无四点共圆矛盾.所以l=9.

1 评分人数