2020年9月国际数学奥林匹克竞赛试题-离散数学-树与图

证明题（数学·2020年9月·国际数学奥林匹克）

给定整数n > 1 ．在一座山上有n²个高度互不相同的缆车车站．有两家缆车公司 A 和B，各运营 k 辆缆车；每辆从一个车站运行到某个更高的车站（中间不停留其他车站） . A 公司的 k 辆缆车的k个起点互不相同， k 个终点也互不相同，并且起点较高的缆车，它的终点也较高． B 公司的缆车也满足相同的条件．我们称两个车站被某家公司连接，如果可以从其中较低的车站通过该公司的一辆或多辆缆车到达较高的车站（中间不允许在车站之间有其他移动）.

确定最小的正整数 k ，使得一定有两个车站被两家公司同时连接．

(印度供题）

解答提示

答案是n2 - n + 1.首先我们说明对 k ≤n2 - n ，存在一种缆车的运行路线，使得不存在两个车站同时被两家公司连接．显然只需对 k = n2 - n，举例，对更小的 k ，从中删去一些缆车即可．设 S1 , S2, … Sn ，是高度依次递增的n2个车站.考虑 A 公司的n2 - n辆缆车，从Si到Si+1，其中 1 ≤ i ≤ n2，且 n|i ； B 公司的n2 - n辆缆车，从Si到Si+1，其中 1 ≤ i ≤ n2 ．从而 Si , Sj 被 A 公司连接当且仅当 [i/n] = [j/n] ，被B公司连接当且仅当 i ≡ j (modn)，显然这两个条件不能同时成立，故没有两个车站同时被 A 公司和B公司连接．下面证明当 k = n2 - n + 1 时，一定有两个车站被两家公司同时连接．定义有向图 GA , 顶点集为n2个车站｛S1,S2, … Sn...

查看完整答案，请下载word版

竞赛

若 z = 1 +i，则|z2 −2z| =【】

埃及胡夫金字塔是古代世界建筑奇迹之一, 它的形状可视为一个正四棱锥, 以该四棱锥的高为边长的正方形面积等于该四棱锥一个侧面三角形的面积, 则其侧面三角形底边上的高与底面正方形的边长的比值为【】

已知 A 为抛物线 C : y2 = 2px(p > 0) 上一点, 点 A 到 C 的焦点的距离为 12, 到 y 轴的距离为 9, 则 p=【】。

某校一个课外学习小组为研究某作物种子的发芽率 y 和温度 x (单位: °C) 的关系, 在 20 个不同的温度条件下进行种子发芽实验, 由实验数据 (xi, yi) (i = 1, 2, · · · , 20) 得到下面的散点图:由此散点图, 在 10°C 至 40°C 之间, 下面四个回归方程类型中最适宜作为发芽率 y 和温度 x 的回归方程类型的是【】。

函数 f(x) = x4 − 2x3 的图像在点 (1, f(1)) 处的切线方程为【】。

设函数 f(x) = cos (ωx + π/6 ) 在 [−π, π] 的图像大致如下图, 则 f(x) 的最小正周期为【】。

已知 α ∈ (0, π), 且 3cos2α − 8cosα = 5, 则 sinα =【】

已知 A, B, C 为球 O 的球面上的三个点， ⊙O1 为 △ABC 的外接圆. 若 ⊙O1 的面积为 4π， AB = BC =AC = OO1，则球 O 的表面积为【】

已知 ⊙M : x2 + y2 − 2x − 2y − 2 = 0，直线 l : 2x + y + 2 = 0, P 为 l 上的动点. 过点 P 作 ⊙M 的切线PA, PB, 切点为 A, B, 当 |PM| · |AB| 最小时, 直线 AB 的方程为【】

若 2a + log2a = 4b + 2log4b, 则【】

离散数学

设集合 A ={x | x2 −4 ⩽ 0},B ={x | 2x + a ⩽ 0}, 且 A∩B ={x |−2 ⩽ x ⩽ 1}, 则 a =【】

的展开式中 x3y3 的系数为【】

已知集合 A = {x | x2 −3x−4 < 0},B = {−4,1,3,5}, 则 A∩B=【】

执行如图的程序框图，则输出的 n =【】

已知集合 U = {−2, −1, 0, 1, 2, 3}, A = {−1, 0, 1}, B = {1, 2}, 则 CU (A ∪ B) =【】

4 名同学到 3 个小区参加垃圾分类宣传活动, 每名同学只去 1 个小区, 每个小区至少安排 1 名学生, 则不同的安排方法有种

设有下列四个命题:p1 : 两两相交且不过同一点的三条直线必在同一平面内.p2 : 过空间中任意三点有且仅有一个平面.p3 : 若空间两条直线不相交, 则这两条直线平行.p4 : 若直线 l ⊂ 平面 α, 直线 m ⊥ 平面 α, 则 m ⊥ l.则下列命题中所有真命题的序号是.① p1 ∧ p4 ② p1 ∧ p2 ③ ¬p2 ∨ p3 ④ ¬p3 ∨ ¬p4

已知集合 A = {x| |x| < 3, x ∈ Z}, B = {x| |x| > 1, x ∈ Z}, 则 A ∩ B =【】

执行如图的程序框图, 若输入 k = 0, a = 0, 则输出的 k 为【】

已知集合 A = {1, 2, 3, 5, 7, 11}, B = {x | 3 < x < 15}, 则 A ∩ B 中元素的个数为【】

树与图

There are 4n pebbles of weights 1,2,3,…,4n. Each pebble is coloured in one of n colours and there are four pebbles of each colour. Show that we can arrange the pebbles into two piles so that the following two conditions are both satisfied:● The total weights of both piles are the same.● Each pile contains two pebbles of each colour.有 4n 枚石子，重量分别为 1 , 2 , 3 , … ， 4n ．每一枚小石子都染了n种颜色之一，使得每种颜色的小石子恰有四枚．证明：可以把这些小石子分成两堆，且满足以下两个条件：● 两堆小石子的总重量相同；● 每堆中每种颜色的小石子各有两枚．(匈牙利供题)

给定整数n > 1 ．在一座山上有n2个高度互不相同的缆车车站．有两家缆车公司 A 和B，各运营 k 辆缆车；每辆从一个车站运行到某个更高的车站（中间不停留其他车站） . A 公司的 k 辆缆车的k个起点互不相同， k 个终点也互不相同，并且起点较高的缆车，它的终点也较高． B 公司的缆车也满足相同的条件．我们称两个车站被某家公司连接，如果可以从其中较低的车站通过该公司的一辆或多辆缆车到达较高的车站（中间不允许在车站之间有其他移动）. 确定最小的正整数 k ，使得一定有两个车站被两家公司同时连接．(印度供题）

如图,小圆圈表示网络的结点,结点之间的连线表示它们有网线相连.连线标注的数字表示该段网线单位时间内可以通过的最大信息量.现从结点A向结点B传递信息,信息可以分开沿不同的路线同时传递,则单位时间内传递的最大信息量为【】

Let n be a positive integer. A“Northern European Square Matrix (NESM) is an n×n square containing all the integers from 1 to n²,so that there is exactly one number in each grid.The two different grids are neighbours if they share a common edge.A grid is called a "valley”if the integer in it in smaller than the integers in all the neighbours of the grid. An "uphill path”is a sequence containing one or more grids satisfying:(i)the frist grid of the sequence is a valley,(ii) each subsequent grid in the sequence is the neighbour of its previous grid,(iii) the integers in the girds of the sequence is incremented.Figure out the minimum possible value of the number of uphill paths in a NESM which should be represented by a function of n.译文：令n为一个正整数，一个“北欧方阵”是一个包含1至n²所有整数的n×n的方格表，使得每个方格中恰有一个数字。两个相异方格如果有公共边，称它们是相邻的。如果一个方格内的数字比所有相邻方格内的数字都小，称其为“山谷”。一条“上坡路径”是一个包含一或多个方格的序列，满足：(1)序列的第一个方格是山谷；(2)序列中随后的每个方格都和前一个方格相邻；(3)序列中方格所写的数字递增。试求一个北欧方阵中山坡路径的最小可能值，以n的函数表示之。

某城街路为棋盘式，走向南北者有 a 条，而走向东西者有 6 条，一行人欲由西北隅向最短之路走到东南隅，问计共有若干方法？

设n是一个正整数.日式三角是将1+2+…+n个圆排成正三角形的形状,使得对 i= 1,2，…,n,从上到下的第i行恰有个圆，且其中恰有一个被染为红色.在日式三角内，忍者路径是指一串由n个圆组成的序列，从最上面一行的圆开始，每次从当前圆连接到它下方相邻的两个圆之一，直至到达最下面一行的某个圆为止.下图为一个n=6的日式三角,其中画有一条包含两个红色圆的忍者路径.求最大的整数k(用n表示),使得在每个日式三角中都存在一条忍者路径,它包含至少k个红色圆.

在n×n的方格表中，若两个方格有公共边，则称它们是相邻的.若l个互异方格A1,A2,⋯,Al满足Ai和Ai+1相邻（1≤i≤l-1），则称它们为一条长度为l的“龙”.求最大正整数k，使得可以给每个方格填上0或者1，并且对任意一个方格A，和以A中数字为首项的0,1序列m1,m2,⋯,mk，都存在从A开始的长度为k的龙，方格中的数字依次是m1,m2,⋯,mk.

一个国家共有n座城市，其中整数n≥100.某些城市之间有双向直飞航班.对于两座城市 A,B，我们定义:(ⅰ)从A到B的路径为一列互不重复的城市序列A=C0,C1,⋯,Ck,Ck+1=B(k≥0)，其中对任意0≤i≤k，城市与之间有直飞航班；(ⅱ)从A到B的长路径是指一条路径，使得不存在其他从A到B的路径包含更多城市；(ⅲ)从A到B的短路径是指一条路径，使得不存在其他从A到B的路径包含更少城市.已知对于任意两座城市A和B，均存在一条长路径和一条短路径，且这两条路径除A和B外没有其他共同城市.设F为该国家中通过直飞航班连接的城市对的总数，求F的所有可能值.