2010-07-19 10:31:30 +0800 #1
、
、
、
2010-07-19 10:31:30 +0800 #2
第1题觉得是n=40×2+9，这样拆(41+8)有40个，另一个是（41+1+1+1+1+1+1+1+1）
理由两次分拆，每组和分别是41，49，即49至少拆成49=41+8,因为去掉41个8是偶数，这些而和构成8个41是奇数，至少再出现8个奇数，即至少7次分拆，就把8=1+1+1+1+1+1+1+1
第2题，还没想出，
理由两次分拆，每组和分别是41，49，即49至少拆成49=41+8,因为去掉41个8是偶数，这些而和构成8个41是奇数，至少再出现8个奇数，即至少7次分拆，就把8=1+1+1+1+1+1+1+1
第2题，还没想出，
2010-07-19 10:31:30 +0800 #3
n=89还有一种构造方式：40个41、40个8、5个9、4个1
41*49=40*（41+8）+（5*9+1+1+1+1）
49*41=40*41+5*（4*8+9）+4*（5*8+1）
感觉没有更少的了。
41*49=40*（41+8）+（5*9+1+1+1+1）
49*41=40*41+5*（4*8+9）+4*（5*8+1）
感觉没有更少的了。
2010-07-19 10:31:30 +0800 #4
3楼也对，不过不是感觉，是证明
2010-07-19 10:31:30 +0800 #5
我觉得2楼的证明并不严谨。
事实上n=89的实例我找到十好几个，下面是比较特殊的两个：
第一个：34个41、34个8、7个25、6个24、6个1、2个9
41*49=34*（41+8）+6*（25+24）+（25+2*9+6*1）
49*41=34*41+7*（2*8+25）+6*（2*8+24+1）+2（4*8+9）
这个实例里边41的个数只有34个。
第二个：39个41、39个8、9个9、1个13、1个4
41*49=39*（41+8）+（5*9+4）+（4*9+13）
49*41=39*41+9*（4*8+9）+（3*8+13+4）
这个实例里边没有出现1。
事实上n=89的实例我找到十好几个，下面是比较特殊的两个：
第一个：34个41、34个8、7个25、6个24、6个1、2个9
41*49=34*（41+8）+6*（25+24）+（25+2*9+6*1）
49*41=34*41+7*（2*8+25）+6*（2*8+24+1）+2（4*8+9）
这个实例里边41的个数只有34个。
第二个：39个41、39个8、9个9、1个13、1个4
41*49=39*（41+8）+（5*9+4）+（4*9+13）
49*41=39*41+9*（4*8+9）+（3*8+13+4）
这个实例里边没有出现1。
2010-07-19 10:31:30 +0800 #6
用配对的想法找到n=89的一个非常平均分布的实例：
其中41是9个，剩下的8、33、16、25、24、17、32、9、40、1全都是8个。
41*49=8*（41+8）+8*（33+16）+8*（25+24）+8*（17+32）+8*（40+9）+（41+8*1）
49*41=9*41+8*（8+33）+8*（16+25）+8*（24+17）+8*（32+9）+8*（40+1）
其中41是9个，剩下的8、33、16、25、24、17、32、9、40、1全都是8个。
41*49=8*（41+8）+8*（33+16）+8*（25+24）+8*（17+32）+8*（40+9）+（41+8*1）
49*41=9*41+8*（8+33）+8*（16+25）+8*（24+17）+8*（32+9）+8*（40+1）
2010-07-19 10:31:30 +0800 #7
1，是89，可是怎么证明啊，我这里有参考答案，是用连通图的性质证明的篇幅较长，也不明白
2，第二题答案也是很长，我也是看不懂
拜托高手帮帮忙
2，第二题答案也是很长，我也是看不懂
拜托高手帮帮忙
2010-07-19 10:31:30 +0800 #8
我对图论一窍不通，不过可以传上来大家帮忙看看。
这个题是哪里的竞赛题么？
这个题是哪里的竞赛题么？
2010-07-19 10:31:30 +0800 #9
哦，等等，我明天发上来
2010-07-19 10:31:30 +0800 #10
没不严谨啊，n最小，并有一个（你是找到了多个）实例.
第二题，还是没完全解决，选定一点A，到点A距离从最小1，√2，√3，...√[3（n-1）^2],（共3（n-1）^2项）
也就是说集合S元素个数k个，则k个元素两两间的距离有C(k,2)种，有C(k,2)《3（n-1）^2
解得k≤0.5+√[0.25+6（n-1）^2<√6n,(n≥1)]
k≤0.5+√[0.25+6（n-1）^2〈（n+2）√(n/3),(几何画板试验是n>11成立)
第二题，还是没完全解决，选定一点A，到点A距离从最小1，√2，√3，...√[3（n-1）^2],（共3（n-1）^2项）
也就是说集合S元素个数k个，则k个元素两两间的距离有C(k,2)种，有C(k,2)《3（n-1）^2
解得k≤0.5+√[0.25+6（n-1）^2<√6n,(n≥1)]
k≤0.5+√[0.25+6（n-1）^2〈（n+2）√(n/3),(几何画板试验是n>11成立)
2010-07-19 10:31:30 +0800 #11
如何证明n最小啊
2010-07-19 10:31:30 +0800 #12
等等，我一会儿贴答案
2010-07-19 10:31:30 +0800 #13
先发第一题
2010-07-19 10:31:30 +0800 #14
第二题的答案
2010-07-19 10:31:30 +0800 #15
2010-07-19 10:31:30 +0800 #16
2010-07-19 10:31:30 +0800 #17
2010-07-19 10:31:30 +0800 #18
打到我都眼冒金星了，没有功劳也有苦劳啊，望高手想一想了，我就是连答案都看不懂，我只是负责把答案贴上来
若看懂了的就麻烦帮我解释一下吧。
若看懂了的就麻烦帮我解释一下吧。
2010-07-19 10:31:30 +0800 #19
想不到第一个问题居然可以转化成图论问题。
为了弄懂这个题的解答，我正特地翻看一本图论书。
感觉用的图论概念也不是很多，就二部图、连通图。
二部图是说可以对一个图的顶点集作这样一个二划分：每一类顶点集的内部中的点之间没有边相连，图中的边都只在这两类顶点之间相连。据此判断解答中所构造的图确实是二部图。
第一题还有什么不明白的？
为了弄懂这个题的解答，我正特地翻看一本图论书。
感觉用的图论概念也不是很多，就二部图、连通图。
二部图是说可以对一个图的顶点集作这样一个二划分：每一类顶点集的内部中的点之间没有边相连，图中的边都只在这两类顶点之间相连。据此判断解答中所构造的图确实是二部图。
第一题还有什么不明白的？
2010-07-19 10:31:30 +0800 #20
这道题2009年吉林省预赛都用了，原为罗马尼亚大师赛的题目。
仔细看看，想看懂没太大难度。
仔细看看，想看懂没太大难度。
2010-07-19 10:31:41 +0800 #21
第一题：为什么至少有90-1=89条边
第二题：为什么C(t,2)要小于等于3（n-1）^2
第二题：为什么C(t,2)要小于等于3（n-1）^2
2010-07-19 10:31:41 +0800 #22
在连通图里边边最少的时候一定不会含圈，也就是说树是连通图里边最少的。
而具有p个顶点的树的边有p-1条。这一点在直观上是比较容易验证的。
而具有p个顶点的树的边有p-1条。这一点在直观上是比较容易验证的。
2010-07-19 10:31:41 +0800 #23
我还是不明白
1，例如一个图中四个点A1,A2,B1,B2分成两组A,B。A1连B1,A2连B2，如楼上所述，图中的边都只在A,B两组顶点之间相连，应该满足要求，但是只有两条边。
是不是我想错呢？
2，什么是树？树状图？两个组之间的树状图怎么画？
1，例如一个图中四个点A1,A2,B1,B2分成两组A,B。A1连B1,A2连B2，如楼上所述，图中的边都只在A,B两组顶点之间相连，应该满足要求，但是只有两条边。
是不是我想错呢？
2，什么是树？树状图？两个组之间的树状图怎么画？
2010-07-19 10:31:41 +0800 #24
第一，题目已经用反证法证明了那是一个连通图。你举的例子并不连通，比如：A1就不能“走到”B2，也不能“走到”A2。如果把A1B2连起来，就是连通的了。这时正好是4-1=3条边。
第二，树就是不含圈的连通图。任何一棵树都可以画成我平时所见的“树”的形象：有一个根，然后上面有一些树叉。
两个组之间（我想你指的是二部图）：虽然同组的两个点不能相连，但可以都与另一组的某个点相邻接，从而实现连通。比如上面你说的那个例子：如果再把A1B2连起来就成一棵树了。B1可以走到A1，A1可以走到B2，B2又可以走到A2，那么这四个点（不管是否同组）就连起来了。但不能再连A2B1，否则里面就形成一个圈，有了圈就不是树了。
因为不含圈，所以树是连通图里面边最少的。
第二，树就是不含圈的连通图。任何一棵树都可以画成我平时所见的“树”的形象：有一个根，然后上面有一些树叉。
两个组之间（我想你指的是二部图）：虽然同组的两个点不能相连，但可以都与另一组的某个点相邻接，从而实现连通。比如上面你说的那个例子：如果再把A1B2连起来就成一棵树了。B1可以走到A1，A1可以走到B2，B2又可以走到A2，那么这四个点（不管是否同组）就连起来了。但不能再连A2B1，否则里面就形成一个圈，有了圈就不是树了。
因为不含圈，所以树是连通图里面边最少的。
2010-07-19 10:31:41 +0800 #25
哦，我知道了
那第二大题呢，看懂了没？
那第二大题呢，看懂了没？
2010-07-19 10:31:41 +0800 #26
第二个，realone在10楼已经解释过了
