## Description

## 1. (30 points)

Spencer Gilpin is sucked into the game Jumanji as Smolder Bravestone (see here for more context:

https://en.wikipedia.org/wiki/Jumanji:_Welcome_to_the_Jungle). The objective of Jumanji is to

return the Jaguar’s eye (a jewel) which is a particular landmark in the Jumanji world. This world has

several landmarks and ways to travel between them (not directly). The landmarks are not arranged

sequentially, and thus there are multiple ways of getting to the Jaguar’s eye. However several (but not all)

landmarks are death-traps. If a player reaches a death-trap, it will kill the player. The player is reborn at

the same landmark instantaneously, which is not deadly anymore. The game has a total of n such deadly

landmarks, and Smolder has k lives, with k < n. If Smolder dies k times before reaching the Jaguar’s

eye, the game is over (and Spencer will be trapped forever in the virtual game). There is no incentive

to reaching the Jaguar’s eye with extra lives. Smolder is talented and brave enough to travel between

landmarks successfully, but he must be careful about which landmarks he chooses to go to.

Fortunately (only for Smolder), you are also part of the game as Sheldon Oberon and have entered with

him at the same place and time. Sheldon is a cartographer, has a map of the entire Jumanji world and has

k lives as well. You need Smolder’s bravery and fighting skills and will always stick with him (i.e. both

of you live and die together). You can help him by planning your journey with him from the landmark

that you both entered from, to the Jaguar’s eye. Both of you wish to return to the real world as soon as

possible. Devise an algorithm that computes the quickest way for you to reach the destination alive, given

all the travel times between landmarks.

1

Hint: Can Spencer and Sheldon get there without dying at all? How about dying once?

## 2. (20 points)

Fall 2018 is upon us! The new graduate student orientation has organized dinner at the end of the

orientation, and they have put tables where students from different cities can sit together and mingle.

However every year students from the same city who know each other already sit together. Professor Shesh

wants each table to have students from different cities so that everybody makes new friends.

Danni has determined that students come from n different cities, with ai students from city i, such

that 1 ≤ i ≤ n. There are m tables with seating capacities t1, t2, …tm respectively. Professor Shesh wants

no more than 3 students at any table to be from the same city. How can he formulate this problem as a

flow network and determine the seating arrangement? Your answer must contain a description of the flow

network, and how you will use it to determine the seating arrangement.

Hint: Think about what restricts the flow in a flow network, and how you can use it to impose

constraints.

#### 3. (Extra credit: 10 points)

A simple path in a graph G is a path between two vertices with each vertex appearing at most once. A

simple cycle is defined similarly, except there is an edge from the last vertex to the first one. The distance

between two vertices in a graph is the least number of edges that must be traversed to reach

one vertex from the other.

The diameter of a graph G, denoted as diam(G) is defined as the length of the longest simple path the

maximum distance between any two vertices in the graph. If G is a connected, undirected graph that is

not a tree, then prove that any there is a cycle in G of length at most 2 ∗ diam(G) + 1.

2