P4745 [CERC2017] Gambling Guide

A railroad network in a nearby country consists of $n$ cities numbered $1$ through $n$, and $m$ two-way railroad tracks each connecting two different cities. Tickets can only be purchased at automated machines installed at every city. Unfortunately, hackers have tampered with the ticket machines and now they all work as follows: when a single coin is inserted in the machine installed at city $a$, the machine dispenses a single one-way ticket from $a$ to a random neighboring city. More precisely, the destination city is chosen uniformly at random among all cities directly connected to a with a railroad track. Destinations on different tickets originating in the same city are independent. A computer science student needs to travel from city $1$ (where she lives) to city $n$ (where a regional programming contest has already started). She knows how the machines work (but of course cannot predict the random choices) and has a map of the railway network. In each city, when she purchases a ticket, she can either immediately use it and travel to the destination city on the ticket, or discard the ticket and purchase a new one. She can keep purchasing tickets indefinitely. The trip is finished as soon as she reaches city $n$. After doing some calculations, she has devised a traveling strategy with the following properties: - The probability that the trip will eventually finish is $1$. - The expected number of coins spent on the trip is the smallest possible. Find the expected number of coins she will spend on the trip.

N/A

N/A