Two interview questions

[tuanl]

I worked on a few interview questions, but not sure if my following answers are correct. Hope someone can help me with them Here they are:

1. If all trains in Grand Central have fewer cars than there are trains in the station, then:
A. All trains must have an odd number of cars.
B. At least two trains must have the same number of cars.
C. Both A and B
D. Neither A nor B

My answer: B.

The solution is following:

Let the number of train in the station be n, and number of cars in train 1,2,...,n is \(x_1, x_2,...,x_n \)(x_i are non-negative integers), respectively. From the given condition, we have: \(x_1+x_2+....+x_n<n\).

Now if all \( x_i>=1\), then \(x_1+x_2+...+x_n>=n\) (contradiction!). So at least one of \(x_i\) must be \(0\). W.L.O.G, assume \(x_1=0\). Thus we have: \(x_2+....+x_n<n\). Consider the case when \(x_2+...+x_{n-1}=n-1\). If none of \(x_j\)(j from \(2\) to n-1)\(=0\), then one of x_j must be equal 2. Assume \(x_3=2\). Then \(x_2+x_4+...+x_{n-1}=n-3\). So either \((x_2,x_4,...,x_{n-1})=(1,1,...,1)\) or one of these remaining numbers is equal to \(0\)(\(=x_1\)). Therefore, in both cases, we all have at least two trains that must have the same number of cars.

2. Let's roll the die. If the outcome is 1, 2, or 3, we stop; otherwise, if it is 4, 5, or 6, a corresponding number of dice are rolled. For example, if the first roll gives 5, then we roll 5 dice, and so on. This procedure continues for every rolled dice whose outcome is 4, 5, or 6. Let N denote the N-th round of rolls. What is the total expected value at the end of the N-th
round of rolls

A. \((11/3)*((5/2)^N+1)\)
B.\((7/3)*((8/2)^N+1)\)
C.\((7/3)*((3/2)^N-1)\)
D.\((8/3)*((6/4)^N-1)\)
E.\((7/3)*((5/2)^N-1)\)

My answer: E. However, I solved this by plugging in N=1 into the given formulas and compare the result to the the total expected value at the end of the 1st-round, which I compute by hand. I couldn't solve for the general case though. I'm thinking of building recursion formula for the case of rolling 4,5 or 6, but still unsuccessful

3. You need to guess a number that will be drawn from a continuous distribution between \(0\) and \(20\). If you overestimate you will be charged 3 dollars. If you underestimate, you will be charged 1 dollar. If you guess correctly, then you will not be charged at all. What is the best number to guess?

A.\(0\)
B. \(5\)
C.\(10\)
D.\(15\)
E.\(20\)

My answer: A

My solution: We need to find the smallest expected value of the money charged from each of the 5 given numbers. We have: E(money charged if \(0\))\(=1*(-1)=-1\), \(E(5)=1/4*(-1)+3/4*(-3)=-5/2\), \(E(10)=1/2*(-1)+1/2*(-3)=-2\), \(E(15)=15/20*(-1)+5/20*(-3)=-3/2\), \(E(20)=1*(-3)=-3\). Thus \(0\) is the best number to guess since it gives us the smallest expected value of the money charged.

 

[pruse]

Or you can just say: if they're all distinct, then their sum is \( \geq 1+2+\cdots+n=n(n+1)/2 \geq n\), a contradiction.

 

[tuanl]

Can someone help me on problem 2 and 3?

 

[IlyaKEightSix]

3) Since it's continuous, you're going to get charged no matter what, thus you want to minimize the chance that you overestimate, that is, take the smallest number possible.

2 I myself haven't thought of yet.

 

[tuanl]

3) Since it's continuous, you're going to get charged no matter what, thus you want to minimize the chance that you overestimate, that is, take the smallest number possible.

Well, I'm afraid that your argument doesn't work. I meant, we need to calculate the expected value of the loss in order to make a decision on what number to choose. Try your argument with the following similar problem and see if it works:

This time you will be charged 3 dollars for every unit error you overestimate (so if the number is 10 and you say 12, then you will be charged 2*3=6 dollars), and you will be charged 1 dollar for every unit of underestimation (so if the number is 10 and you say 8, then you will be charged 2*1=2 dollars). If you forecast correctly then you will not be charged at all. What is the best point forecast?

A.\(0\)
B.\(5\)
C.\(10\)
D.\(15\)
E.\(20\)

 

[IlyaKEightSix]

You're asking a different question now. In that case, you want to be indifferent about the expected value. In that case, we have two triangles, one with vertices at (0,0), (choice,0), and (0,3*choice), to the left, and another triangle with vertices at (choice, 0), (20, 0), and (20, 20-choice). The expectations are equal to the areas of each. So for the left triangle, you have an area of 3*choice/2, and for the right one, you have (20-choice)*(20-choice)/2. Which means 3*choice=400-40*choice+choice^2. So therefore choice^2-43*choice+400=0.

So in this case it's actually none of these options, though I'd say closer to 10.

 

[tuanl]

You're asking a different question now. In that case, you want to be indifferent about the expected value. In that case, we have two triangles, one with vertices at (0,0), (choice,0), and (0,3*choice), to the left, and another triangle with vertices at (choice, 0), (20, 0), and (20, 20-choice). The expectations are equal to the areas of each. So for the left triangle, you have an area of 3*choice/2, and for the right one, you have (20-choice)*(20-choice)/2. Which means 3*choice=400-40*choice+choice^2. So therefore choice^2-43*choice+400=0.

So in this case it's actually none of these options, though I'd say closer to 10.

I also used the expected value for the 2nd case, and I got 5, or B as the answer. I don't meant to offense though, but how are we not using the expected value of the money lost to make decision in this case?

By using expected value where x is the number we need to guess, we have: E(money lost when choice is 10)=3*1/2*(10-x)+1/2(x-10)*1=10-x<0 if x>10. Only choice B gives E(Money lost when choice is 5)=3*1/4*(5-x)+1*3/4(x-5)=0, which is non-negative.

 

[tuanl]

Can anyone else try to answer the 2nd version of the "guessing number" problem posted above? I want to see if my argument above using the expected value is correct

 

[pruse]

For #2,

Let \(S(t)\) and \(N(t)\) be the sum of the rolls, and the number of dice, respectively, in round \(t\). Then

\(E(S(t)) = \frac{7}{2}N(t)\)

\(E(N(t)) = \frac{4+5+6}{6}\cdot N(t-1) = \frac{5}{2}N(t-1)\)

Taking expectations in the latter recursion and inducting, \(E(N(t))=\large(\frac{5}{2}\right)^{t-1}\). Replacing this in the former recursion (after taking expectations there), \(E(S(t))=\frac{7}{2}\large(\frac{5}{2}\right)^{t-1}\).

Summing, we get \(E(S(1))+\cdots+E(S(t))=\frac{7}{2}\left[1+\frac{5}{2}+\cdots+\large(\frac{5}{2}\right)^{t-1}\right]=\frac{7}{3}\left[\large(\frac{5}{2}\right)^t-1\right]\). So, choice E, indeedably.

 

[tuanl]

For #2,

Let \(S(t)\) and \(N(t)\) be the sum of the rolls, and the number of dice, respectively, in round \(t\). Then

\(E(S(t)) = \frac{7}{2}N(t)\)

\(E(N(t)) = \frac{4+5+6}{6}\cdot N(t-1) = \frac{5}{2}N(t-1)\)

Taking expectations in the latter recursion and inducting, \(E(N(t))=\large(\frac{5}{2}\right)^{t-1}\). Replacing this in the former recursion (after taking expectations there), \(E(S(t))=\frac{7}{2}\large(\frac{5}{2}\right)^{t-1}\).

Summing, we get \(E(S(1))+\cdots+E(S(t))=\frac{7}{2}\left[1+\frac{5}{2}+\cdots+\large(\frac{5}{2}\right)^{t-1}\right]=\frac{7}{3}\left[\large(\frac{5}{2}\right)^t-1\right]\). So, choice E, indeedably.

Nice solution! Can you try the 2nd version of the "guessing number" problem posted above too?

 

[pruse]

Nice solution! Can you try the 2nd version of the "guessing number" problem posted above too?

It's even more basic.

It's physically obvious: To balance an object on the left of a see-saw of length 20 with an object 3 times its weight on the right, the hinge must be placed 15 units from the left.

But here's a mathematical proof for sticklers:

If you guess \(a\), then your average expected loss is \(\int_0^a \frac{a-t}{20} dt + 3\int_a^{20} \frac{t-a}{20} dt = \frac{1}{40}\left[a^2+3(20-a)^2\right] = \frac{1}{40}\left[4a^2-120a+1200\right]\) , which is maximized at \(a=\frac{120}{8}=15\).

 

[tuanl]

But here's a mathematical proof for sticklers:

If you guess \(a\), then your average expected loss is \(\int_0^a \frac{a-t}{20} dt + 3\int_a^{20} \frac{t-a}{20} dt = \frac{1}{40}\left[a^2+3(20-a)^2\right] = \frac{1}{40}\left[4a^2-120a+1200\right]\) , which is maximized at \(a=\frac{120}{8}=15\).

I think the formula should be (3\int_0^a \frac{a-t}{20} dt + \int_a^{20} \frac{t-a}{20} dt), since in the case of (0<t<a), we overestimated the correct number, so the money paid off should be 3 dollars. The other case is underestimation, so we are paid only (1) dollar. Thus the expected loss should be (\frac{a^2}{10}+10-a), which is minimized at (a=5)

 

[pruse]

I think the formula should be (3\int_0^a \frac{a-t}{20} dt + \int_a^{20} \frac{t-a}{20} dt), since in the case of (0<t<a), we overestimated the correct number, so the money paid off should be 3 dollars. The other case is underestimation, so we are paid only (1) dollar. Thus the expected loss should be (\frac{a^2}{10}+10-a), which is minimized at (a=5)

You're right, I switched them. In other words, just reflect everything about the middle. 15 <-> 5. Thanks!

 

[tuanl]

pruse: No problem. Can you check if the following solution to problem 3 above is correct, by using the same method:
Assume we guess (a), expected loss is: (3*\int_0^{a}\frac{t}{20}dt+1*\int_{a}^{20}\frac{t}{20}dt=10+\frac{a^2}{20}), which is minimized at (a=0)