Category: Graph Theory

Scrupulist Square

This challenge is spans all the way from graph theory, geometry, and calculus—to algebra and combinatorics.

Example set of points for N = 15

Consider a square with diagonal 1. In it, N points are randomly arranged. A graph is created from these points, such that the probability any 2 points touch is equal to 1 minus their distance. Choose a point at random on this graph. The challenge is to calculate a probability regarding this point: what is the probability that a randomly selected node connected to this one is connected to more nodes? Each node has a loop, so if the node was connected to no other nodes the probability of this is 0. For N=1 or 2, this probability is 0. Try to calculate at least one of the following: chance for a specific N > 2, limit of chance as N approaches infinity, and most difficult, generalized probability in terms of N.

SOLUTION

Sophisticated Streetcar

Algebra, trigonometry, and calculus are used in today’s challenge.

You are taking a streetcar through a city. Your destination is in the middle of a large park, and you are late. You can jump of the streetcar at any time while it is on the side of the park. Your destination is 1 kilometre from the road. The streetcar moves at 15 m/s, and you move at 5 when you run, which you will to try to be on time. You calculate when you will need to jump off the streetcar to arrive as soon as possible, and jump of exactly then. For how long do you run?

Solution

Vile Voting

Algebra and combinatorics are needed to solve this challenge.

Brutus and Craw are voting over their preference of colours. Their satisfaction is measured by how close their preferences are to the ones agreed on; they do not care about each other. The vote is determined by each player prioritizing the colours of the rainbow. Brutus and Craw do not know about indigo. Their first pick gets 5 points, their second 4, and so on such that their last gets 0.The colour with the most is first, the second most, second, and so on. Brutus and craw receive “points” of satisfaction, based on how close the vote is to their personal preferences. For each preference the number of points starts at one less than the previous, with 5 for 1st. It goes down by 2 if it’s below it’s position, and then decreases by one until it stops at 0. Except for fifth position, which cannot drop 2 because it started at only 1. In case of a tie, the position that comes first is picked randomly. First, Brutus states his preferences: red, orange, yellow, purple, blue, green. Then Craw would states his: purple, blue, green, yellow, orange, red. Except that Craw is a meanie and adjusts his to make it unfair. But Brutus then adjusts his, and they go back and forth until neither can improve their score. The challenge is to figure out what the votes, standings, and satisfaction will be for Brutus and Craw will be when they finish, if they ever do.

Satisfaction\\[16pt] \begin{matrix} & 1st & 2nd & 3rd & 4th & 5th & 6th\\ \#1 & 5 & 3 & 2 & 1 & 0 & 0\\ \#2 & 4 & 4 & 2 & 1 & 0 & 0\\ \#3 & 3 & 3 & 3 & 1 & 0 & 0\\ \#4 & 2 & 2 & 2 & 2 & 0 & 0\\ \#5 & 1 & 1 & 1 & 1 & 1 & 0\\ \#6 & 0 & 0 & 0 & 0 & 0 & 0\\ \end{matrix}
Solution

Fascinating Fruits

Diagram of the Fascinating Fruits.

You will need an understanding of algebra and combinatorics to solve today’s challenge.

Today’s challenge begins with 3 rows of fruits. They begin with an apple, and orange, and a pear. The fruits behind the front are unknown. Directly behind any apple, there is an equal chance of a plum, a banana, or an orange. There is no other fruit directly behind an apple, but one apple is at the end of a row. Behind any plum is the same fruit that was in front of it. Directly behind an orange, there is a one third probability there are grapes. There is an equal probality of pears and blueberries, and 1 orange leads to a banana. For any banana there is an equal chance of blueberries or a plum. 1 banana is followed by grapes, and another ends a row. Behind blueberries, there is a one third chance of a pear, otherwise grapes. Directly behind grapes, there is a 50% chance of more grapes, a 25% chance of a plum, and otherwise a pear. Finally, directly behind a pear there is the fruit of the colour in the rainbow following that of the fruit in front of the pair. The exception is the 1 pear that ends a row. The apples in this question are red, which is considered to follow purple, the colour of the plums. The fruit following the pair at the front is an apple. The challenge is to use this information to find the probability that the row started by a pear ends with one.

Solution

Crazy Capture

All of your algebra, geometry, trigonometry, angle theorems, and pathmaking skills are required to have a chance of solving today’s challenge.

2D capture example.

In a mathematical capture, all police officers and the target are points that travel at the same constant speed in infinite space in n dimensions. They have infinite endurance and perfect reaction time. The target is instantly captured and cannot ecape when a police officer touches it. In 1 dimension, when n = 1, it obviously takes 2 officers surrounding the target. When n = 2, we can do it with three easily. We do this by dividing the plane into three, each officer can easily trap the target in a 120° slice. The challenge is to see how many officers it takes to capture the target when n equals 3, in three dimensions.

Solution

Devising Deactivation

To solve this challenge, you will need to use geometry, trigonometry, and algebra, to do pathmaking.

Map of the radar that must be deactivated.

You are working for the government as a mathematician and they tell you of a problem. There is a plan afoot to compromise an enemy radar station. It is critical that the invading crew member is undedected, as the enemy must not know that their radar is sending them misinformation. However, the radar has a range of 100 metres and completes a rotation every 12 seconds. The fastest crew member can only sprint at 7 metres per second with their toolkit. Because of the radar’s length and rotation speed, it is nearly impossible to disable it undetected. None of the simple strategies work. The challenge is to find a path that the invader can take without being detected.

Solution

Captivating Circles 4

You will need all your skills in graph theory, and pathmaking, algebra and combinatorics to solve today’s challenge. Good luck!

Captivating Circle #4

This captivating circle has been divided in to many sections. By combining these sections, you can make many different composite shapes. The challenge is to see how many shapes you can make. This includes the entire circle.

Solution

Captivating Circles 2

Today, we have a new captivating circle, and it is the first challenge to require the use of combinatorics. It also requires some trig and pathmaking.

Captivating Circle #2

Our second captivating circle is a circle with 7 points on its circumference. The points are equally spaced. Each point connects to 2 others through the circle and 2 others through a straight line. No points can connect to another through both a line and arc. The circle has circumference π. How many possible different sets of connections can be made? And of these, what is the highest possible distance that must be traversed to get between 2 points?

Solution

Crazy Connections

Graph theory and algebra are required to solve this challenge.

Our challenge begins with a set of points. There are points of red, orange, yellow, green, blue, and purple. These points are all interconnected as follows. Every red point connects to 1 red point, 2 orange points, and 3 green points. Each orange point connects to 1 red point, 2 orange points, 2 yellow points, and 1 blue point. All yellow points connects to 1 orange point, 1 other yellow point, 3 green points, and 1 purple point. Green points all connect to 1 red point, 4 yellow points, and 1 blue point. All of the blue points connect to 2 orange points, 3 green points, and 1 purple point. And finally, purple points connect to 4 yellow points, 1 blue point, and 1 purple point. The question is this: what is the minimum number of points for each colour?

Solution