A Practical Guide to Quantitative Finance Interviews (Chapter 2)

Five pirates looted a chest full of 100 gold coins. Being a bunch of democratic pirates, they agree on the following method to divide the loot: The most senior pirate will propose a distribution of the coins. All pirates, including the most senior pirate, will then vote. If at least 50% of the pirates (3 pirates in this case) accept the proposal, the gold is divided as proposed. If not, the most senior pirate will be fed to shark and the process starts over with the next most senior pirate... The process is repeated until a plan is approved. You can assume that all pirates are perfectly rational: they want to stay alive first and to get as much gold as possible second. Finally, being blood-thirsty pirates, they want to have fewer pirates on the boat if given a choice between otherwise equal outcomes. How will the gold coins be divided in the end?

Start with trivial cases: 1 pirate (100), 2 pirates (0, 100)

3 pirates: 3rd pirate knows 1st pirate gets nothing if there's only 2 pirates, so 1st pirate gets bribed. (1, 0, 99)

4 pirates: 4th pirate knows 2nd pirate gets nothing if there's only 3 pirates, so 2nd pirate gets bribed. (0, 1, 0, 99)

5 pirates: 5th pirate knows 1st and 3rd pirates get nothing if there's only 4 pirates. (1, 0, 1, 0, 98)

All pirates who get coins only get 1 coin if there are 199 pirates - after 198 pirates, nobody gets a bigger share.

One hundred tigers and one sheep are put on a magic island that only has grass. Tigers can eat grass, but they would rather eat sheep. Assume: A. Each time only one tiger can eat one sheep, and that tiger itself will become a sheep after it eats the sheep. B. All tigers are smart and perfectly rational and they want to survive. So will the sheep be eaten?

Trivial case: 1 T, 1 S the tiger eats the sheep and is safe

2 T, 1 S neither tiger wants to eat the sheep; stalemated

3 T, 1 S one tiger can eat and it will be safe from the stalemate

4 T, 1 S no tigers want to eat since another tiger eats during the 3 T scenario

-> Odd tigers, sheep is eaten

-> Even tigers, sheep is not eaten (stalemated)

Four people, A, B, C and D need to get across a river. The only way to cross the river is by an old bridge, which holds at most 2 people at a time. Being dark, they can't cross the bridge without a torch, of which they only have one. So each pair can only walk at the speed of the slower person. They need to get all of them across to the other side as quickly as possible. A is the slowest and takes 10 minutes to cross; B takes 5 minutes; C takes 2 minutes; and D takes 1 minute. What is the minimum time to get all of them across to the other side?

Key realization: the slowest two must cross together, but they can't go first. Also, a fast person must take the torch back after the slow pair crosses.

DC cross (+2), D returns (+1), AB cross (+10), C returns (+2), DC cross (+2), total is 17 minutes.

You and your colleagues know that your boss A's birthday is one of the following 10 dates:

Mar 4, Mar 5, Mar 8, Jun 4, Jun 7 Sep 1, Sep 5, Dec 1, Dec 2, Dec 8

A told you only the month of his birthday, and told your colleague C only the day. After that, you first said: "I don't know A's birthday; C doesn't know it either." After hearing what you said, C replied: "I didn't know A's birthday, but now I know it." You smiled and said: "Now I know it, too." After looking at the 10 dates and hearing your comments, your administrative assistant wrote down A's birthday without asking any questions. So what did the assistant write?

First statement: "I don't know A's birthday; C doesn't know it either." So the day cannot be unique -> the month cannot contain a day that is unique. So now only Mar 4, Mar 5, Mar 8, Sep 1, Sep 5 are possible.

Second statement: "I didn't know A's birthday, but now I know it." So the day must be unique within the remaining possibilities. So now only Mar 4, Mar 8, Sep 1 remain. The day that C was told is either 1, 4, or 8.

"Now I know it, too." A knows that the day is either 1, 4, or 8. If A knows the answer now, it means the month only has one possible day remaining. Therefore, the answer is Sep 1 since Mar still has 2 dates.

A casino offers a card game using a normal deck of 52 cards. The rule is that you turn over two cards each time. For each pair, if both are black, they go to the dealer's pile; if both are red, they go to your pile; if one black and one red, they are discarded. The process is repeated until you two go through all 52 cards. If you have more cards in your pile, you win $100; otherwise (including ties) you get nothing. The casino allows you to negotiate the price you want to pay for the game. How much would you be willing to pay to play this game?

There is no possible way for your pile to be bigger than the dealer's pile; there are equal numbers of red and black cards. Therefore you will never win, and you should not pay to play the game.

You have two ropes, each of which takes 1 hour to burn. But either rope has different densities at different points, so there's no guarantee of consistency in the time it takes different sections within the rope to burn. How do you use these two ropes to measure 45 minutes?

The key realization is that you can burn a rope from both of its ends to guarantee a measure of half its original lifespan. So, start burning both ropes, and burn one of them from both sides. Once the faster burning rope is gone, 30 minutes have passed. Then, light the 2nd side of the 2nd rope, and 15 minutes will pass before it is gone. 45 minutes have passed.

You have 12 identical balls. One of the balls is heavier OR lighter than the rest (you don't know which). Using just a balance that can only show you which side of the tray is heavier, how can you determine which ball is the defective one with 3 measurements?

The key realization is that if you split the balls into 3 groups and only measure 2 at a time, you still gain information about the 3rd group! Let's label the balls 1 thru 12.

Step 1: measure 1, 2, 3, 4 vs 5, 6, 7, 8. If the balance is even, we know the defective ball is either 9, 10, 11, or 12. But let's say the scale tips towards 1, 2, 3, 4. That means a light ball is in 1, 2, 3, 4 or a heavy ball is in 5, 6, 7, 8. 9, 10, 11, 12 are guaranteed to be normal.

Step 2: measure 1, 2, 5 vs 3, 7, 9. If the balance is even, we know the defective ball is not currently on the balance. So either 4 is light, or 6 / 8 is heavy. Comparing 6 and 8 will confirm. Now if the balance tips towards 3, 7, 9 then the defective ball is on the scale. Either 1, 2 are light or 7 is heavy. Comparing 1 and 2 will confirm. What if the balance tips towards 1, 2, 5? Then either 5 is heavy or 3 is light. Comparing 3 with 9 (definitely normal) will confirm this.

How many trailing zeros are there in 100! (factorial of 100)?

Another way to view this question is: how many times can you factor out 10 from 100! (factorial of 100)?

The factors of 10 are 2 and 5. There are definitely more even numbers than multiples of 5 -> we are limited by the amount of 5s from 1 -> 100. So basically, the number of trailing zeros in 100! is the same as the number of multiples of 5 from 1 -> 100. At first, you may think there are only twenty 5s, but each multiple of 25 contributes a pair of 5s. There are 4 multiples of 25 that contribute two 5s each.

Therefore, there are 20 + 4 = 24 trailing zeros.

There are 25 horses, each of which runs at a constant speed that is different from the other horses'. Since the track only has 5 lanes, each race can have at most 5 horses. If you need to find the 3 fastest horses, what is the minimum number of races needed to identify them?

Let's label all horses 1 -> 25 and say the true order is also 1 -> 25. All horses need to be observed, so there are at least 5 races. Let's say the winner of each race is 1, 6, 11, 16, 21. Also, the last 2 of each race are definitely eliminated. So we can race 1, 6, 11, 16, 21 again and eliminate 16, 21. Since 11 got 3rd, all the horses it beat are eliminated. Since 6 got 2nd, the horse that got 3rd in its original race (8) is eliminated. We only have 1, 2, 3, 6, 7, 11 so only one more race is needed.

In total, 7 races are required.

If x^x^x^x^x... (infinite series) = 2, what is x?

Beautiful solution: x^x^x^x^x... = (x)^(x^x^x^x^x) = 2

Now substitute (x^x^x^x^x) = 2, and you get that x^2 = 2

So x = sqrt(2)

Can you pack 53 bricks of dimensions 1×1×4 into a 6×6×6 box?

No. This is a variant of the 8x8 chessboard with top right and bottom left corners removed question: can you still fit 31 2x1 blocks?

The solution to the chessboard problem is as follows: the board has 32 black and 32 white squares. The two corners that were removed are both black squares, so there are only 30 black squares. A 2x1 block must cover 1 black and 1 white square. Since there are only 30 black squares, you can only fit 30 blocks!

Now, let's upgrade this intuition to 3D and our original question. Imagine that the 6x6x6 box is populated with 2x2x2 cubes, alternating between black and white; there are 27 cubes. Let's say that 13 are black and 14 are white, but these can be switched. For every 4 bricks, there must be 1 black cube and 1 white cube. However, since there are only 13 black cubes, only 52 bricks can populate the 13 black cubes! So only 52 bricks can fit in the box.

You just had two dice custom-made. Instead of numbers 1 - 6, you place single-digit numbers on the faces of each dice so that every morning you can arrange the dice in a way as to make the two front faces show the current day of the month. You must use both dice (in other words, days 1 - 9 must be shown as 01 - 09), but you can switch the order of the dice if you want. What numbers do you have to put on the six faces of each of the two dice to achieve that?

First, you must think about what numbers need to be on both cubes. The biggest number in a month is 31. Then, 11 and 22 will require 1 and 2 to be on both cubes. The numbers 01 - 09 cause 0 to be on both cubes; if 0 is only on one cube, let's say (0, 1, 2, 3, 4, 5) + (1, 2, 6, 7, 8, 9) then the date 03 is not possible. So both cubes need to contain (0, 1, 2) which leaves (3, 4, 5, 6, 7, 8, 9). You don't need both 6 and 9 since they are mirrors of each other. So you have one cube with (0, 1, 2, 3, 4, 5) and another with (0, 1, 2, 6, 7, 8).

You are facing two doors. One leads to your job offer and the other leads to exit. In front of either door is a guard. One guard always tells lies and the other always tells the truth. You can only ask one guard one yes/no question. Assuming you do want to get the job offer, what question will you ask?

Ask the guard a question that involves the other guard. For example: "Would the other guard say that you are guarding the door to the offer?"

You are talking either to the liar or the truthful one, and the door is either good or bad. Let's examine all 4 cases.

(Liar, Good) -> Liar says no -> you pick this door

(Liar, Bad) -> Liar says yes -> you pick the other door

(Truthful, Good) -> Truthful says no -> you pick this door

(Truthful, Bad) -> Truthful says yes -> you pick the other door

You need to communicate with your colleague in Greenwich via a messenger service. Your documents are sent in a padlock box. Unfortunately the messenger service is not secure, so anything inside an unlocked box will be lost (including any locks you place inside the box) during the delivery. The high-security padlocks you and your colleague each use have only one key which the person placing the lock owns. How can you securely send a document to your colleague?

Send the box to your colleague. Your colleague should then place a second lock on the box (assuming the box is like a school locker). He will send it back to you, and you will remove the original lock with your key. Finally, once he gets the box, he has the key to his own lock!

A bag has 20 blue balls and 14 red balls. Each time you randomly take two balls out. (Assume each ball in the bag has equal probability of being taken). You do not put these two balls back. Instead, if both balls have the same color, you add a blue ball to the bag; if they have different colors, you add a red ball to the bag. Assume that you have an unlimited supply of blue and red balls, if you keep on repeating this process, what will be the color of the last ball left in the bag?" What if the bag has 20 blue balls and 13 red balls instead?

If both balls have the same color, then either +1 blue or -2 red. Then, if the balls are different colors, -1 blue and +0 red. From this, we see that the red ball can only change by 2. Therefore, if the number of red balls is even it will stay even. If the number of red balls is odd it will stay odd.

So, if there are 14 red balls, the last ball is blue. If there are 13 red balls, the last ball is red.

There is a light bulb inside a room and four switches outside. All switches are currently at off state and only one switch controls the light bulb. You may turn any number of switches on or off any number of times you want. How many times do you need to go into the room to figure out which switch controls the light bulb? (hint, light + heat)

Let's label the switches as 1, 2, 3, 4. Turn on 1, 2 and wait for a while. Next, turn off 2 and turn on 3. The light has two variables: on/off and hot/cold.

If the light is on and hot, then 1 is real.

If the light is off and hot, then 2 is real.

If the light is on and cold, then 3 is real.

If the light is off and cold, then 4 is real.

Eight quants from different banks are getting together for drinks. They are all interested in knowing the average salary of the group. Nevertheless, being cautious and humble individuals, everyone prefers not to disclose his or her own salary to the group. Can you come up with a strategy for the quants to calculate the average salary without knowing other people's salaries?

The first quant will come up with a random number, probably very large. Let's call it x. Then, he will tell the 2nd quant x + (real salary). This continues until the 8th quant, and the 8th quant tells the first quant the total. Finally, the 1st quant subtracts x and divides by 8 to get the average salary!

Suppose that you are blind-folded in a room and are told that there are 1000 coins on the floor. 980 of the coins have tails up and the other 20 coins have heads up. Can you separate the coins into two piles so to guarantee both piles have equal number of heads? Assume that you cannot tell a coin's side by touching it, but you are allowed to turn over any number of coins.

Let's separate the 1000 coins into two piles. The first is size (1000 - a) and the other is size (a). Now, the first pile has (20 - b) heads and the other has (b) heads. The second pile has (a - b) tails. Our goal is to ensure that 20 - b = b, but this is not possible. However, if we flip all the coins in the second pile, it will have (a - b) heads and (b) tails. Now our goal is to make 20 - b = a - b -> just fix a = 20. So the solution is to separate the 1000 coins into a pile of 980 and a pile of 20. Then, flip all coins in the pile of 20!

You are given three bags of fruits. One has apples in it; one has oranges in it; and one has a mix of apples and oranges in it. Each bag has a label on it (apple, orange or mix). Unfortunately, your manager tells you that ALL bags are mislabeled. Develop a strategy to identify the bags by taking out minimum number of fruits? You can take any number of fruits from any bags.

Take a fruit out of the mixed bag - the mixed bag is mislabeled and must contain only one type of fruit! Let's say the mixed bag is really the apple bag. Then you are left with an apple and an orange bag with these possible scenarios:

The apple bag is actually mixed and the orange bag is actually apple.

The apple bag is actually orange and the orange bag is actually mixed.

But wait, the orange bag cannot actually be apple. Therefore, the orange bag is actually mixed, and the apple bag is actually orange.

If the mixed bag is really the orange bag, then the apple bag is really mixed and the orange bag is actually apple.

A sultan has captured 50 wise men. He has a glass currently standing bottom down. Every minute he calls one of the wise men who can choose either to turn it over (set itupside down or bottom down) or to do nothing. The wise men will be called randomly, possibly for an infinite number of times. When someone called to the sultan correctly states that all wise men have already been called to the sultan at least once, everyone goes free. But if his statement is wrong, the sultan puts everyone to death. The wise men are allowed to communicate only once before they get imprisoned into separate rooms (one per room). Design a strategy that lets the wise men go free.

Let's designate a wisest man (nicknamed W-man).

There are 49 wise men and a W-man. The W-man will turn the glass bottom down if he sees that the glass is bottom up. He will do nothing if it's bottom down.

The 49 wise men will turn the glass bottom up if the glass is bottom down, but only if they haven't turned the glass yet. If they've turned the glass before, then they don't touch it. If the glass is bottom up, don't touch it.

The W-man counts how many times he turns the glass bottom down. Once he counts that he has fixed the glass 49 times, he states all the wise men have gone to the room.

There are 10 bags with 100 identical coins in each bag. In all bags but one, each coin weighs 10 grams. However, all the coins in the counterfeit bag weigh either 9 or 11 grams. Can you find the counterfeit bag in only one weighing, using a digital scale that tells the exact weight?

Take out 1 coin from the 1st bag, 2 coins from the 2nd, etc... until 10 coins from the 10th. Let the ith bag be the fake one. Then the sum of all weights is 550 +- i and you can easily tell which bag is fake.

You are holding two glass balls in a 100-story building. If a ball is thrown out of the window, it will not break if the floor number is less than X, and it will always break if the floor number is equal to or greater than X. You would like to determine X. What is the strategy that will minimize the number of drops for the worst case scenario? Suppose the strategy must identify X within N throws.

There are N throws available. Suppose we throw the first ball at floor N. If it doesn't break, we have N - 1 throws available, so we can throw it at floor 2N - 1 in order to have enough throws to check every floor between N and 2N - 1. If it doesn't break again, we can throw it at floor 3N - 3, 4N - 7, etc... The highest floor we can check is the summation of (N - i) from N = 0 to N = N. So we can check [(N)(N-1) / 2] floors maximum. [(N)(N-1) / 2] should be at least 100, so fixing [(N)(N-1) / 2] >= 100 gives N = 14. This is because we want N throws to definitively cover all 100 floors if needed. So for 100 floors, 14 throws is the minimized number of drops required.

Your drawer contains 2 red socks, 20 yellow socks and 31 blue socks. Being a busy and absent-minded MIT student, you just randomly grab a number of socks out of the draw and try to find a matching pair. Assume each sock has equal probability of being selected, what is the minimum number of socks you need to grab in order to guarantee a pair of socks of the same color?

Pigeon Hole Principle: when you have 3 holes, you need 3 + 1 pigeons to guarantee that two pigeons are sharing a hole. In this case, each color is a hole and each sock is a pigeon.

You are invited to a welcome party with 25 fellow team members. Each of the fellow members shakes hands with you to welcome you. Since a number of people in the room haven't met each other, there's a lot of random handshaking among others as well. If you don't know the total number of handshakes, can you say with certainty that there are at least two people present who shook hands with exactly the same number of people?

You + 25 team members are at the party. Each person can shake hands with 1 - 25 people. Nobody can shake 0 hands since "Each of the fellow members shakes hands with you to welcome you." So, there are 25 holes (different number of hand shakes possible) and 26 pigeons (number of people at the party). Therefore, we can guarantee there are at least two people present who have shaken the same number of hands!

Show me that, if there are 6 people at a party, then either at least 3 people met each other before the party, or at least 3 people were strangers before the party.

Let's say that 2 people met each other before the party. This means that 4 people did not meet each other before the party. In other words, both quantities must add to 6. Therefore, one must be >= 3.

There are 51 ants on a square with side length of 1. If you have a glass with a radius of 1/7, can you put your glass at a position on the square to guarantee that the glass encompasses at least 3 ants?¹

There are 51 ants (pigeons). We want to know how big each hole must be to guarantee a hole with >= 3 ants / pigeons.

Let's say we have 25 holes. 2 * 25 + 1 = 51, so we can guarantee that with 25 holes, at least 2 + 1 pigeons / ants are sharing a hole. How big is each hole?

The square has area 1. Each hole has area 1/25. The glass of radius 1/7 has area pi / 49, or approximately (sacrilegiously) 3 / 49. Now we call 1/25 = 2/50, and 2/50 is definitely less than 3/49, so the glass is actually bigger than the minimum hole size to guarantee 3 ants in a hole.

There are 5 bags with 100 coins in each bag. A coin can weigh 9 grams, 10 grams or 11 grams. Each bag contains coins of equal weight, but we do not know what type of coins a bag contains. You have a digital scale (the kind that tells the exact weight). How many times do you need to use the scale to determine which type of coin each bag contains?

Use the scale once. A coin weighs 9, 10, or 11 grams. We can subtract 9 from the total scale weight for all coins. This makes each coin "weigh" 0, 1, or 2. Now, pick 1 coin from bag 1, 3 coins from bag 2, 9 coins from bag 3, 27 coins from bag 4, and 81 coins from bag 5. Subtract 9 * (1 + 3 + 9 + 27 + 81) from the weight and convert the total to base 3. Each digit will encode the type of coin in each bag! Ex: 01023 means bag 5 has 9 gram coins, bag 4 has 10 gram coins, etc...

One hundred prisoners are given the chance to be set free tomorrow. They are all told that each will be given a red or blue hat to wear. Each prisoner can see everyone else'shat but not his own. The hat colors are assigned randomly and once the hats are placedon top of each prisoner's head they cannot communicate with one another in any form, or else they are immediately executed. The prisoners will be called out in random order and the prisoner called out will guess the color of his hat. Each prisoner declares the color of his hat so that everyone else can hear it. If a prisoner guesses correctly the color of his hat, he is set free immediately; otherwise he is executed. They are given the night to come up with a strategy among themselves to save as many prisoners as possible. What is the best strategy they can adopt and how many prisoners can they guarantee to save?

When the first prisoner steps up, he will either see: odd # of reds + even # of blues, or opposite (there are 99 hats from their POV). The prisoners can designate whether even or odd is special. Let's assume they chose that odd is for the signal. Then the first prisoner states the color which has an odd number of hats. The first prisoner is not guaranteed to survive.

The next prisoner knows that red has an odd number of hats. If the number of red hats he sees is still odd, he definitely has a blue hat. If the number of red hats he sees is even, then he knows he has a red hat.

All the next prisoners can keep track of whether red / blue are even / odd from the original prisoner's statement and all the following prisoners' statements. 99 prisoners are guaranteed to survive.

Prisoner problem continued: What if there are 3 possible hat colors: red, blue, and white? What is the best strategy they can adopt and how many prisoners can they guarantee to save?

99 prisoners are still guaranteed to survive. The prisoners can designate a value to each color: red = 0, blue = 1, white = 2. The first prisoner will see 99 hats and calculate the total score of all hat values. Ex: 33 reds + 33 blues + 33 whites = (0 33) + (1 33) + (2 * 33) = 99. He will then guess the color that corresponds to the total score % 3 -> in this case, red. He is not guaranteed to survive.

The next prisoner knows that the total score % 3 including himself is 0. Now, he will recalculate the total score % 3 from the 98 hats that he can see. Let's say total score % 3 = 2. Then he knows that his hat must be blue since taking 1 away from the score will result in a remainder of 2.

Each consecutive prisoner can follow this strategy and keep track of all prior statements to survive.

A remote island has three types of chameleons with the following population: 13 red chameleons, 15 green chameleons and 17 blue chameleons. Each time two chameleons with different colors meet, they would change their color to the third color. For example, if a green chameleon meets a red chameleon, they both change their color to blue. Is it ever possible for all chameleons to become the same color? Why or why not?

In order for all chameleons to become the same color, the colors must reach a point where two colors have the same population. Now, in order for two colors to reach the same population, they must be 3 (or a multiple of 3) apart. We can see that no colors are 3 apart, so it is never possible for all chameleons to become the same color.

You split 1000 coins into two piles and count the number of coins in each pile. If there are x coins in pile one and y coins in pile two, you multiple x by y to get xy. Then you split both piles further, repeat the same counting and multiplication process, and add the new multiplication results to the original. For example, you split x to x and x2, y to y and y₂, then the sum is xy + x x₂+yy₂. The same process is repeated until you only have piles of 1 stone each. What is the final sum? (The final 1's are not included in the sum.) Prove that you always get the same answer no matter how the piles are divided.

Let f(n) = the sum of n coins. f(n) = (x)(n - x) + sum(x) + sum(n-x)

The inductive step is to realize that f(n) = n(n-1)/2

You would reach this by noticing: f(1) = 1 (base case), f(2) = 1, f(3) = 3, f(4) = 6, f(5) = 10, etc...

The sum of n coins only depends on n, not how the coins are split (x).

A chocolate bar has 6 rows and 8 columns (48 small 1×1 squares). You break it into individual squares by making a number of breaks. Each time, break one rectangle into two smaller rectangles. For example, in the first step you can break the 6×8 chocolate bar into a 6×3 one and a 6×5 one. What is the total number of breaks needed in order to break the chocolate bar into 48 small squares?

You need one break to increase the number of pieces. Since you start from 1 piece and want to get to 48 pieces, you will need 47 total breaks.

Can you prove that √2 is an irrational number? A rational number is a number that can be expressed as a ratio of two integers; otherwise it is irrational.

Let sqrt(2) = a / b -> the fully reduced ratio of two integers must have 0 common factors between a and b.

We can imply that 2b^2 = a^2, so a^2 and a must be even numbers.

Since a is even, we can rewrite a as 2x. Then a^2 = 4x^2.

Now we have 2b^2 = 4x^2 -> b^2 = 2x^2, so b^2 and b must also be even!

But now a and b are proven to have common factors since they are both even. This is not possible, so sqrt(2) is irrational.

Seven prisoners are given the chance to be set free tomorrow. An executioner will put a hat on each prisoner's head. Each hat can be one of the seven colors of the rainbow and the hat colors are assigned completely at the executioner's discretion. Every prisoner can see the hat colors of the other six prisoners, but not his own. They cannot communicate with others in any form, or else they are immediately executed. Then each prisoner writes down his guess of his own hat color. If at least one prisoner correctly guesses the color of his hat, they all will be set free immediately; otherwise they will be executed. They are given the night to come up with a strategy. Is there a strategy that they can guarantee that they will be set free?

Assign each color a number value from 0 - 6. Call S the sum of all hats' number values (maximum is 42). S % 7 is guaranteed to be in the set [0, 6]. Since there are 7 prisoners and 7 possibilities for S % 7, we need each prisoner to cover 1 possibility.

Label each prisoner 0 - 6. Each prisoner only sees 6 other hats - call the sum of these 6 hats T. The i-th prisoner should guess a value (g) such that (T + g) % 7 = i. This way, each prisoner "covers" a unique case where S % 7 = i. So, one prisoner is guaranteed to guess correctly!