*Dennis Shasha is a professor of Computer Science at New York University. His latest puzzle book Puzzles for Programmers and Pros outlined some general approaches to programmatic puzzle solving. This column challenges you to find the solutions to the puzzles that lie at the core of some cool tough applications. He solicits your help in identifying such cool apps.*

Long-time Dr. Dobb's readers may remember "Dr. Ecco's Omniheurist Corner" where Professor Dennis Shasha posed puzzles that required computer solutions. Dennis is returning to Dr. Dobb's, but with a new twist on puzzles. The idea is to take inspiration from the challenging apps that readers have faced and to turn those into puzzles.

If you have written an application that required extensive use of heuristics (because no algorithm would solve it) or that is otherwise algorithmically interesting, please send mail to Dennis at [email protected]. Put "Tough Apps" in the subject line. If Dennis likes it, he will contact you. Then he will try to understand what you've done and create a puzzle explaining the algorithmic core. You will write a little blurb about yourself and the problem if you want.

An empty hotel room represents a lost opportunity to the hotel owner. The marginal cost of cleaning a room is minimal compared to the fixed cost of the personnel, rent, and so on. So, the hotel has every interest in filling all its rooms.

Clever travellers and entrepreneurs can take advantage of this by waiting until the last minute to buy cheap rooms. Of course, they run the risk that they may not sleep anywhere. The result is a game. Let's work up to the game in stages. It will lead us to strange and amoral places, I promise.

**Warm-Up 1**: Suppose you have the only hotel in town. You have three rooms free for tonight. You know from history that there will be one visitor who is willing to spend $300 per night, another at $200 per night, and one at $100 per night. We'll abbreviate this demand profile to 1 @ $300, 1 @ $200, 1 @ $100. If you have to give the same price to all comers, what should you set your price to be?

**Solution to Warm-Up 1**: $200 -- you get $400 and leave one room empty. A recurrent theme in this puzzle is that charging the same price to everyone in the service of fairness results in empty hotel rooms and roomless travellers.

Suppose there are two hotels next to one another of the same quality and the demand is twice that before, i.e. 2 @ $300, 2 @ $200, 2 @ $100. Now if your hotel sets the price at $200, the other hotel can set the price at, say, $180 and get three guests out of the four. You get only $200.

**Warm-Up 2**: If you don't know how much the other hotel will charge, then what can you guarantee to obtain?

**Solution to Warm-Up 2**: If your hotel charges $133 and the other charges more, then you will fill your three rooms and get $399. On the other hand, if the other hotel also charges less but more than $100, then you will get only $133. So, if you charge $100, you will guarantee an income of $300. If the other hotel reasons the same way, then there will be six rooms for six travellers, each costing $100 per night. Note how much better this is for consumers.

**Warm-Up 3**: The hotel owners approach an agent to set room prices for both of them. They agree to give the agent a portion of any extra profit they would make beyond the $300 they can already get.

**Solution**: If the agent sets prices at $200 per room instead of $100, then each hotel's profits will increase to $400 (less the agent's commission) while leaving two travelers without rooms. This is why a single agent (whether online or not) can be as bad for consumers as a hotel monopoly.

### Now It's Your Turn

**1**. Suppose you have the only hotel in town and it has six rooms. The general problem is, given a demand profile and a certain number of rooms, try to find the price per room that will maximize hotel profits if you control all the rooms in a town. If the demand profile is x @ $300, y @ $200, and z @ $100, for which positive values of x, y, and z would you set the price for your six rooms at $300, for which positive values would you set the price at $200, and for which at $100?

**2**. If you control all the rooms in town, is there ever any profit-maximization reason to charge $250, given the above demand profile? Why or why not?

**3**. Suppose there are two virtually identical hotels on the same block each having three rooms, but you control the rooms of only one and the demand profile is again x @ $300, y @ $200, and z @ $100. For which x, y, and z values would you charge $200 to guarantee as much revenue as possible? For which x, y, z would you charge $300?

**4**. Staying in the two hotel scenario, for which x, y, z would you charge something strictly between $200 and $300 in your hotel (assuming you don't know what the other hotel charges)? What if you did know the other hotel's prices and customers would always compare prices before taking a room?

**5**. Loyalty programs and other perks may direct customers your way. Suppose that your perks program can convince all travelers to come to your hotel first. Each traveler will take a room in your hotel if you charge what he or she is willing to pay. As usual, there are six travelers altogether, where x travelers will be willing to pay $300, y @ $200, and z @ $100. How should you set your prices as a function of x, y, and z? How should your competitor set prices?

**6**. As you can see, the pricing power of the hotel owner depends as much on consumer behavior (whether consumers compare prices) as on monopoly power, either gained directly or through an agent. Do you see any general pattern?