Riddler Classic: January 20, 2022

David Ding

January 20, 2022

Grid Deliveries

Explanation:

Let's first make some observations about the problem. Clearly, the delivery to the destination point has the same distance for the scooter in all paths, which is the path's Manhattan distance. This allows for the distance to be simply the sum of its coordinates. Similarly, since the drone's path is straight, its delivery distance will be the Euclidean distance from the origin to the destination point.

Since the speed is the same, time frame considered is the same, and we return to the origin after each delivery, then by symmetry of the puzzle, we just need to find the ratio of distances taken to deliver an item by drone over by scooter, since time = distance / speed, and inverse the result to get the corresponding ratio for number of deliveries. In addition, we just need to consider the first quadrant since all other quadrants will yield the same distance ratios. We assume all points are equally likely to be selected.

This means we can establish our result as a random variable, say \(Z\), as follows. Let \(X \sim \mathcal{U}(0, 1)\) be the random variable representing the x-coordinate of the destination point, and \(Y \sim \mathcal{U}(0, 1)\) be the random variable representing the y-coordinate, with \(X\) and \(Y\) independent of each other. Then, the random variable we need to find is the inverse of the distance ratios, which is:

\begin{align} Z &= \frac{X + Y}{\sqrt{X^2 + Y^2}} \\ \end{align}

And our desired answer is \(\mathbb{E}[Z]\). Applying the definition of expectation, we get:

\begin{align} \mathbb{E}[Z] &= \int_{<\text{quarter circle}>} z f(Z = z) \: \mathrm{d}z \\ \\ &= \frac{\int_{<\text{quarter circle}>} \frac{x + y}{\sqrt{x^2 + y^2}} \: \mathrm{d}x \mathrm{d}y}{\text{Area of quarter circle}} \end{align}

This is best done in polar coordinates with \((r, \theta)\). Assuming we are only considering the first quadrant, then:

\begin{align} x &= r \cos{\theta} \\ y &= r \sin{\theta} \\ \sqrt{x^2 + y^2} &= r \\ \mathrm{d}x \, \mathrm{d}y &= r\, \mathrm{d}r \, \mathrm{d}\theta \\ \end{align}

And we have:

\begin{align} \mathbb{E}[Z] &= \int_{<\text{quarter circle}>} z f(Z = z) \: \mathrm{d}z \\ \\ &= \frac{\int_{<\text{quarter circle}>} \frac{x + y}{\sqrt{x^2 + y^2}} \: \mathrm{d}x \mathrm{d}y}{\text{Area of quarter circle}} \\ \\ &= \frac{4\int_{<\text{quarter circle}>} \frac{r(\cos{\theta} + \sin{\theta})}{r} \: r \, \mathrm{d}r \, \mathrm{d}\theta}{\pi} \\ \\ &= \left(\frac{4}{\pi}\right)\int_{\theta = 0}^{\theta = \frac{\pi}{2}}(\cos{\theta} + \sin{\theta}) \: \mathrm{d}\theta \int_{r = 0}^{r = 1} r \, \mathrm{d}r \\ \\ &= \left(\frac{4}{\pi}\right) \left(\left.\sin{\theta} - cos{\theta} \right) \right|_{\theta = 0}^{\theta = \frac{\pi}{2}} \left(\left.\frac{r^2}{2} \right) \right|_{r = 0}^{r = 1} \\ \\ &= \left(\frac{4}{\pi}\right)\left(1 + 1\right)\left(\frac{1}{2}\right) \\ \\ &= \boxed{\frac{4}{\pi}} \\ \\ &\approx 1.273 \\ \end{align}

For comparing the theory with simulation, I wanted to make the simulation as realistic as possible. I designed a city grid with maximum block size of 100 in each direction with 1km between blocks. I made the vehicle speeds of 0.3m/s or just over 60km/h. I ensured that all destination points are lattice points, that is, with integer coordinates, and I accounted for the return trip to the origin after each delivery. I give one year for each vehicle to deliver items and tracked the ratio of deliveries. The set up is as below:

function ratio = getRatio()
    speed = 0.3; % 0.3 m/s or 60km/h
    blockNum1D = 100; % 100 blocks in one direction
    blockLength = 1000; % 1km
    totalTime = 24*60*60*365; % 1 year

    % Initialize
    scooterDelivery = 0;
    droneDelivery = 0;
    scooterTimeLeft = totalTime;
    droneTimeLeft = totalTime;
    scooterDone = false;
    droneDone = false;

    % Simulate
    while (~scooterDone || ~droneDone)
        % Get coordinates--coordinates must be lattice points
        horiz = randi(blockNum1D);
        vertMax = floor(sqrt(blockNum1D^2 - horiz^2));
        if vertMax == 0
            vert = 0;
        else
            vert = randi(vertMax);
        end
    
        % Calculate distances
        scooterD = horiz + vert;
        droneD = sqrt(horiz^2 + vert^2);
        scooterD = 2*scooterD * blockLength; % Times two to account for round trip
        droneD = 2*droneD * blockLength;
    
        % Calculate times for deliveries (in s)
        scooterTime = scooterD / speed; 
        droneTime = droneD / speed;

        if (scooterTime <= scooterTimeLeft)
            scooterDelivery = scooterDelivery + 1;
            scooterTimeLeft = scooterTimeLeft - scooterTime;
        else
            scooterDone = true;
        end

        if (droneTime <= droneTimeLeft)
            droneDelivery = droneDelivery + 1;
            droneTimeLeft = droneTimeLeft - droneTime;
        else
            droneDone = true;
        end
    end

    % Calculate result
    if scooterDelivery == 0
        ratio = 0; % rare edge case to avoid NaN
        return;
    end

    ratio = droneDelivery / scooterDelivery;
end

I ran the above simulation 10 million times Monte-Carlo, and the average I received was 1.245. This is slightly smaller than the theoretical answer because I have quantized the city block instead of letting the block size be infinitely small.