分类： 赛事动态

A small chip is composed of a grid of contacts (marked as dots). Some are already connected (marked as line segments). Connectors are always only between adjacent contacts, horizontally or vertically. We want to connect S and R with a continuous sequence of connectors, which do not touch any already connected contacts.

一个小芯片由一个触点网格（标记为点）组成。其中一些触点已经连接（标记为线段）。连接器总是仅在相邻触点之间水平或垂直连接。我们希望用一连串的连接器将 S 和 R 连接起来，且这些连接器不能接触任何已连接的触点。

Question: 问题:

How many different ways are there to connect S and R with the least possible number of connectors?

用最少的连接器将 S 和 R 连接起来，有多少种不同的连接方式？

A. 5

B. 13 

C. 15

D. 16

 

 

 

 

 

 

Explanation 解释

The correct answer is: 15

正确答案是：15

It is not difficult to find some shortest path (sequence of connectors). You can imagine a wave spreading over the board, one contact at a time, starting at S and moving toward R. When the wave reaches a contact, it certainly took the least possible number of connectors (“steps” of the wave).

要找到一些最短路径（连接器序列）并不难。你可以想象一个波浪在电路板上逐个接触点地扩散开来，从 S 点开始向 R 点移动。当波浪到达某个接触点时，它肯定已经经过了最少数量的连接器（波浪的“步数”）。

The table shows the wave midway through filling in. The numbers show the order in which the wave reached them, and the blacked out cells indicate the connectors we cannot connect to. They are also the length of the shortest path to the respective contact. The highest numbers are the current edge of the wave.

该表展示了波形在填充过程中的中间状态。数字表示波形到达各单元格的顺序，黑色单元格表示无法连接的连接器，它们也是到达相应触点的最短路径长度。最大的数字表示当前波形的前沿。

But if you try to find all the shortest paths, you can easily get lost. Luckily, you do not really need to, you are just interested in the number of paths. So how to break this task down to some smaller pieces?

但如果你试图找出所有最短路径，很容易迷失方向。幸运的是，你其实并不需要这么做，你只是对路径的数量感兴趣。那么如何将这个任务分解成一些更小的部分呢？

Realize this: A shortest path to any given contact must go through one of the adjacent contacts, which is exactly one connector closer to the start. If there are more such contacts, any of them can be used. So if you want to know the number of possibilities, you need to sum the possibilities to get to these adjacent contacts. The number of shortest paths to a certain contact is the sum of the numbers of the shortest paths to the adjacent contacts which are one connector closer to the start.

要明白这一点：到达任何给定接触点的最短路径必须经过其中一个相邻接触点，而该相邻接触点恰好比起始点更近一个连接器。如果有多个这样的接触点，那么其中任何一个都可以使用。所以，如果您想知道可能性的数量，就需要将到达这些相邻接触点的可能性相加。到达某个接触点的最短路径数量，就是到达比起始点更近一个连接器的相邻接触点的最短路径数量之和。

This allows you to follow a procedure, which will reliably give you the final number of shortest paths. You can proceed similarly as with finding the shortest path, filling in the table like a wave. Start at S. The contacts next to it can be reached in only one way. Then add the next contacts along the wave edge and always sum up the neighbour numbers from the previous step.

这使您能够遵循一个程序，该程序能可靠地得出最短路径的最终数量。您可以像寻找最短路径那样进行操作，像波浪一样逐步填满表格。从 S 开始。与它相邻的节点只能通过一种方式到达。然后沿着波浪边缘添加下一个节点，并始终将前一步中相邻节点的数量相加。

The resulting table looks like this, where we have also shown the order in which the cells are filled in by way of the table on the right, which is the completely filled in “shortest path” table discussed above:

最终得到的表格如下所示，我们还在右侧的表格中展示了单元格的填充顺序，该表格即为上文所讨论的已完全填好的“最短路径”表：

Bebras新赛季备赛已开启，扫码领取Bebras真题资料⇓

欢迎咨询【Bebras专业辅导课程】

（Bebras每日一练部分展示）

A mobile is a piece of art that hangs from a ceiling. You may remember one hanging from the ceiling in your bedroom.

风铃是一种悬挂在天花板上的艺术品。您或许还记得自己卧室天花板上挂着的一个。

A mobile consists of sticks and figures. Each stick has a few points to which figures or other sticks may be attached.

一个活动挂图由木棍和图形组成。每根木棍上有几个点，图形或别的木棍可以连接在这些点上。

Also, each stick has a hanging point, from which it is attached to a stick further above (or to the ceiling).

此外，每根棍子都有一个悬挂点，通过这个点它被连接到上方更高处的棍子（或者天花板）。

The following example mobile can be described using these numbers and brackets:

以下这个示例手机可以用这些数字和括号来描述：

(-3 (-1 1) (1 1)) (2 3)

Question: 问题:

Which of the following mobiles is described by the following instructions:

以下哪款手机符合以下描述：

(-3 (-1 4) (2 (-1 1) (1 1))) (2 (-1 6) (2 3))

A.

B.

C.

D.

 

 

 

 

 

  Explanation 解释

正确的答案是A.

Bebras新赛季备赛已开启，扫码领取Bebras真题资料⇓

欢迎咨询【Bebras专业辅导课程】

（Bebras每日一练部分展示）

Every Friday, six spies exchange all the information they have gathered during the week. A spy can never be seen with more than one other spy at the same time. So, they have to have several rounds of meetings where they meet up in pairs and share all the information they have at that point.

每周五，六名间谍都会交换他们一周内所收集到的所有情报。一名间谍绝不能在同一时间与超过一名间谍碰面。因此，他们得分多轮进行会面，每次两人一组，分享当时各自所掌握的所有情报。

The group of 6 spies needs only three rounds to distribute all secrets:

这 6 名间谍组成的小组仅需三轮就能分发完所有机密：

Before the meetings each spy holds a single piece of information. (spy 1 knows 'a', spy 2 knows 'b, etc.). In the first round spies 1 and 2 meet and exchange information so now both know 'ab'. The diagrams show which spies meet in each round with a line. It also shows which pieces of information they all have. After three rounds all information has been distributed.

在会议开始前，每个间谍都掌握着一条单独的信息。（间谍 1 知道“a”，间谍 2 知道“b”，以此类推）。在第一轮中，间谍 1 和间谍 2 相遇并交换信息，这样他们俩现在都知道“ab”。图表显示了每一轮中哪些间谍会面，用一条线表示。它还展示了他们所有人所拥有的信息。经过三轮，所有信息都已分发完毕。

Question: 问题:

After an international incident one spy has stopped attending the meetings. What is the minimum number of rounds needed for the five remaining spies to exchange all information?

在一次国际事件之后，一名间谍不再参加会议。那么剩下的五名间谍要交换所有信息，最少需要几轮？

 

 

 

 

 

 

Explanation 解释

Correct answer is 4 rounds.

正确答案是 4 轮。

This is unexpected: the obvious answer is three (or less?) since we have one spy less. This is even stranger if we consider that four spies would quite obviously exchange the information in two rounds.

这出乎意料：显而易见的答案是三轮（或者更少？），因为我们少了一个间谍。如果考虑到四个间谍显然只需两轮就能交换完信息，那就更奇怪了。

However, unsuccessful attempts at solving the task soon show us the root of the problem: since the number of spies is odd, one of them is “inactive” in every round. Say that spy number 5 does not participate in the first round, but he participates in the second. Thus in the second round, only two spies will know his piece information (e). In the third round, these two spies will meet two other spies, so after three rounds (only) four spies will know e. The fourth round is needed to spread this information to the fifth.

然而，几次尝试解决该任务均未成功，很快我们就发现了问题的根源：由于间谍的数量是奇数，所以在每一轮中都会有一个间谍处于“不活跃”状态。比如，间谍 5 在第一轮不参与，但在第二轮参与。因此，在第二轮中，只有两个间谍会知晓他的情报（e）。到了第三轮，这两个间谍会分别与另外两个间谍碰面，所以经过三轮（仅）之后，只有四个间谍知晓 e。需要第四轮才能将此信息传递给第五个间谍。

Therefore, we proved that at least four rounds are needed. To show that they also suffice, we construct a schema with four rounds.

因此，我们证明了至少需要四轮。为了表明四轮也足够，我们构建了一个四轮的模式。

Bebras新赛季备赛已开启，扫码领取Bebras真题资料⇓

欢迎咨询【Bebras专业辅导课程】

（Bebras每日一练部分展示）

There are 10 plates in a row. There is one apple on each plate.

一排有 10 个盘子。每个盘子上都有一个苹果。

Thomas, the kangaroo, loves to jump. First he jumps onto the leftmost plate with the letter A.

袋鼠托马斯喜欢跳跃。首先，它跳到了最左边标有字母 A 的盘子上。

On each single jump after this, he either jumps forward two plates, or backwards three plates.

在此之后的每一次跳跃，他要么向前跳两块板，要么向后跳三块板。

(An example of the two possible jumps from one plate is shown with arrows in the picture.)（从一块板上可能做出的两种跳跃方式在图中用箭头标出。）

Thomas only jumps onto plates with an apple. If he jumps onto a plate, he collects the apple from it.

托马斯只跳到有苹果的盘子上。如果他跳到盘子上，就会从盘子里把苹果拿走。

Question:问题:

If Thomas collects all 10 apples, which apple does he collect last?

如果托马斯把 10 个苹果都收集起来，他最后收集的是第几个苹果？

 

 

 

 

 

 

Explanation 解释

The correct answer is: I (the second apple fromt he right)

正确答案是：I（从右数第二个苹果）

We number the plates from left to right from A to J. Then Thomas can collect all ten apples in the order A, B, C, D, E, F, G, H, I, J.

我们从左到右将盘子依次编号为 A 到 J。这样托马斯就可以按照 A、B、C、D、E、F、G、H、I、J 的顺序收集所有十个苹果。

This is the only sequence of jumps that allows Thomas to collect all the apples. Why? To begin, Thomas must jump on plates A, C and then E because otherwise he jumps to the left of the first plate. Next, he must jump to plate B because he can only get to plate B from plate E and he will not return to plate E later. The same kind of reasoning can be used to see that all the remaining jumps are also determined uniquely.

这是托马斯能收集到所有苹果的唯一跳跃顺序。为什么？首先，托马斯必须跳到 A、C 然后是 E 板上，否则他会跳到第一块板子的左边。接下来，他必须跳到 B 板上，因为他只能从 E 板跳到 B 板，而且之后不会再回到 E 板。同样的推理可以得出，所有剩余的跳跃也都唯一确定了。

Bebras新赛季备赛已开启，扫码领取Bebras真题资料⇓

欢迎咨询【Bebras专业辅导课程】

（Bebras每日一练部分展示）

Beaver the Alchemist can convert objects into new objects. He can convert:

炼金术士海狸能够将物品转换成新的物品。他可以转换：

• Two clovers into a coin两片三叶草变成一枚硬币
• A coin and two clovers into a ruby一枚硬币和两片三叶草变成了一颗红宝石
• A ruby and a clover into a crown将一颗红宝石和一株三叶草制成一顶王冠
• A coin, a ruby, and a crown into a kitten.一枚硬币、一颗红宝石和一顶王冠变成了一只小猫。

After an object has been converted into another object, it disappears immediately.一个物体在被转换成另一个物体之后，会立刻消失。

Question: 问题:

How many clovers does Beaver the Alchemist need to create one kitten?炼金术士海狸要创造一只小猫需要多少株三叶草？

A. 5

B. 10

C. 11

D. 12

 

 

 

 

 

Explanation 解释

The answer is 11. We can see the conversion as follows:

答案是 11。我们可以看到转换过程如下：

coin       =   2 clovers

ruby      =   2 clovers + 1 coin = 4 clovers

crown    =   1 ruby + 1 clover = 4 clovers + 1 clovers = 5 clovers

kitten    =   1 coin + 1 ruby + 1 crown = 2 clovers + 4 clovers + 5 clovers = 11 clovers

The answer 5 is for those who did not read the graph properly to realize that we need 2 clovers to create a coin or ruby, or for those who did not realize that you need a coin to create a ruby or a ruby to create a crown.

答案 5 是给那些没有正确读图从而没有意识到需要 2 片三叶草才能合成一枚硬币或一颗红宝石的人，或者是那些没有意识到需要一枚硬币才能合成一颗红宝石，或者需要一颗红宝石才能合成一顶王冠的人。

The answer 10 is for those who think that the number of clovers is the same as the number of edges.

答案 10 是给那些认为三叶草的数量与边的数量相同的那些人的。

The answer 12 is for those who miscounted.

答案 12 是给那些数错的人的。

Bebras新赛季备赛已开启，扫码领取Bebras真题资料⇓

欢迎咨询【Bebras专业辅导课程】

（Bebras每日一练部分展示）

The teacher at the beaver school wants to give some material to his students.

海狸学校的老师想给他的学生们一些材料。

He found a portal with a scanned book that explains in its front page that it should be distributed according to a “Creative Commons License” (CC-BY-ND). This allows everyone to share, copy and redistribute the material for free  in any medium or format for any purpose, even commercially, provided that appropriate credit is given.

他发现了一个带有扫描书籍的入口，该书的首页说明应根据“知识共享许可协议”（CC-BY-ND）进行分发。这允许任何人免费在任何媒介或格式中分享、复制和重新分发该材料，用于任何目的，甚至商业用途，但需给予适当的署名。

The license also specifies that if one remixes, translates, or builds upon the book, the modified book may not be distributed.

该许可证还规定，如果有人对这本书进行改编、翻译或在其基础上进行创作，改编后的作品不得进行分发。

Question: 问题:

Which of these actions is not permitted under the terms of this license?

根据本许可条款，以下这些行为中哪一项是不被允许的？

A. Selling book copies to the students.

B. Translating the book, keeping the translated copy for himself.

C. Giving the students his translation of one chapter of the book.

D. Putting a copy of the scanned book on the school website.

 

 

 

 

 

Explanation 解释

C is the correct answer.C 是正确答案。

2015年Bebras挑战练习题

Junior (14-16岁) 集合

名称	类型
Irrigation System（灌溉系统）	A
Fair share （公平的分享）	A
Super Power Family （超能力家族）	A
E-mail Scam （电子邮件诈骗）	A
Beaver Logs （海狸日志）	A
Theatre （剧院）	B
Beaver Lunch （海狸的午餐）	B
Stack Computer （堆栈的电脑）	B
Throw the dice （掷骰子）	B
Drawing Stars （画星星）	B
Popularity （流行）	C
Bowl Factory （碗的工厂）	C
Word Chains （文字链）	C
Hard Fireworks （艰难的烟花）	C
Pirate Hunters （海盗猎人）	C

Bebras新赛季备赛已开启，扫码领取Bebras真题资料⇓

欢迎咨询【Bebras专业辅导课程】

（Bebras每日一练部分展示）

In the game of Pirate Hunters players take turns moving a Pirate or a Policeman.在“海盗猎人”游戏中，玩家轮流移动海盗或警察。

When it is the police's turn, the player moves a policeman over to a neighbouring field.轮到警察时，玩家将一名警察移至相邻的区域。

The pirate is faster than a policeman, and skips a field on its turn, moving two fields.海盗比警察快，在其回合时能跳过一格，移动两格。

A policeman cannot move to a field that is occupied -- either by his colleague policeman, or the pirate.一名警察不能移动到已被占据的区域——无论是被他的同事警察占据，还是被海盗占据。

The game ends when the pirate is forced to move to a field occupied by one of the policemen.当海盗被迫移动到一名警察所在的场地时，游戏结束。

The policeman goes first.警察走在前面。

Question: 问题:

If the pirate plays the best way possible and makes no mistakes, how many moves will it take the police to capture him?如果海盗以最佳方式行动且不犯任何错误，警察需要多少步才能将其抓获？

A. The police can win in 2 turns.

B. The police can win in 3 turns.

C. The police can win in 5 turns.

D. The police has no chance of winning.

 

 

 

 

 

Explanation 解释

The answer is: The police cannot win the game if the pirate plays perfectly.

答案是：如果海盗玩得完美无缺，警察就赢不了这场游戏（选项D）。

Let us assume that the police actually forced the pirate into the above situation and it is the pirate's turn (so he loses). What did the board look like before the police's last move? The police moved one or the other policeman up or down. Since the board is symmetric, we shall assume that it was the right policeman that moved; the situation for the left one is the same. Thus the previous situation was one of these.

我们假设是警方迫使海盗陷入上述局面，且轮到海盗走（所以海盗输了）。警方的上一步棋之前棋盘是什么样子的？警方移动了其中一名警察向上或向下。由于棋盘是对称的，我们假设移动的是右边的警察；左边警察的情况是一样的。因此，之前的局面是这样的。Let us go one more move back. The pirate must had come from the right. Hence the situation before that was one of these two:

让我们再回溯一步。海盗必定是从右边来的。所以之前的情况必然是这两种之一：The above situation, in which the pirate is captured, can therefore arise only from these two positions (and their mirrored versions). However, if the pirate is indeed a good player and found himself in one of these two positions, he would surely move the pirate to the left and not up.

上述海盗被擒获的情况因此只能从这两个位置（及其镜像位置）产生。然而，如果海盗确实是个高手，发现自己处于这两个位置中的任何一个，他肯定会把海盗向左移动而不是向上移动。

Two beavers live in lodges separated by a large forest.

两只海狸分别住在被大片森林隔开的窝里。

They decide to send messages to each other by shooting fireworks into the sky above the trees.

他们决定通过向树梢上方的天空发射烟花来互相传递信息。

Each message is a sequence of words, though the beavers only know five different words.

每条信息都是一串单词，不过海狸们只认识五个不同的单词。

The beavers can shoot two types of fireworks, one after the other, and know the following codes:

海狸们能够依次发射两种烟花，并且知晓以下代码：

For example, to send the (rather strange) message "food, log, food", a beaver would shoot:

例如，要发送（相当奇怪的）信息“食物，原木，食物”，一只海狸会这样射击：

Question: 问题:

How many different meanings can the following sequence of fireworks have?

下面这一系列烟花能有多少种不同的含义？

 

 

 

 

 

 

Explanation 解释

The correct answer is 4. The message could mean any of the following:

正确答案是 4。该消息可能表示以下任何一种意思：

• log, rock, food, river 日志，岩石，食物，河流
• log, log, log, river 木头，木头，木头，河流
• rock, tree, river 岩石、树木、河流
• rock,food, log, river 岩石、食物、原木、河流

To convince yourself that there are no more possibilities, you can systematically count them:

要让自己确信没有其他可能性，你可以系统地进行计数：

- Start with the first firework. It is not a message, so you can assign a zero to it.

从第一个烟花开始。它不是信息，所以你可以给它赋值为零。

- The first two fireworks can only mean log. Assign number one to the second firework.

前两束烟花只能表示“木”。给第二束烟花标上数字 1。

- We are now at the third firework. It can have a meaning of any shorter sub-sequence plus one new word. Yet we see that there is no way to prolong the previously examined sequences (of length 1 and 2), so we only have one possible meaning (rock) and assign 1 to the third firework.

现在我们来到了第三个烟花。它可以表示任何更短的子序列加上一个新词的意思。然而我们发现无法延长之前考察过的序列（长度为 1 和 2 的），所以我们只有一个可能的意思（“岩石”），于是给第三个烟花赋值 1 。

- The fourth firework is somewhat interesting! It can either add the word log to the first two fireworks, or food to the first three fireworks, as shown by the arrows below. So we sum the two numbers at the 2^nd and 3^rd firework and assign it to the 4^th (1+1=2).

第四个烟花有点意思！它要么把单词“log”加到前两个烟花上，要么把“food”加到前三个烟花上，如下方箭头所示。所以我们把 2 号和 3 号烟花上的两个数字相加，并把这个和赋值给 4 号烟花（1 + 1 = 2）。

- We proceed applying the same idea to each firework to the right. We look one, two and three fireworks back. If those shorter messages can be prolonged with a correct word, we mark this fact with an arrow. Then we just sum the numbers “brought” by the arrows to the currently examined firework.

我们接着将同样的思路应用于右侧的每一个烟花。我们向后看一个、两个和三个烟花。如果那些较短的信息能用一个正确的词加以延长，我们就用箭头标出这一事实。然后，我们只需将箭头“带来”的数字加到当前正在考察的烟花上。

- At the last firework we will have the number of all possible meanings.

在最后一束烟花绽放时，我们将拥有所有可能意义的数量。

The systematic approach when we build our solution systematically step by step and using the previous steps is called dynamic programming. It makes the process much easier.

当我们逐步系统地构建解决方案，并利用之前的步骤时，这种系统的方法被称为动态规划。它使整个过程变得容易得多。

Bebras新赛季备赛已开启，扫码领取Bebras真题资料⇓

欢迎咨询【Bebras专业辅导课程】

（Bebras每日一练部分展示）

For his homework, Thomas had to write words on cards and connect them with rubber bands.托马斯的家庭作业是把单词写在卡片上，然后用橡皮筋把它们连起来。   The teacher told him to connect any two words that differ by exactly one letter.老师让他把仅相差一个字母的任意两个单词连接起来。 Thomas did this, as you can see in the picture on the right.托马斯就是这样做的，如您在右边的图片中所见。 When Thomas returned from having a break he got a surprise.托马斯休息回来时吃了一惊。 Peter, his little brother, had erased all the words!彼得,他的小弟弟把所有的字都擦掉了！
	Also, the cards were completely mixed up, as you can see in the image on the left.而且，正如您在左边的图片中所看到的那样，这些卡片完全被打乱了。 Importantly, the rubber bands still connected them as before.重要的是，橡皮筋仍像之前那样把它们连在一起。 Thomas was sure he could put the words back in the correct place.托马斯确信他能把那些词放回正确的位置。

Question: 问题:

Which of the pictures below contains the words in exactly the right places?

下面哪张图片中的单词位置完全正确？

A.

B.

C.

D.

 

 

 

 

 

Explanation 解释