Teaser Tuesday! September 9, 2014

I hope everyone finds this one challenging! Enjoy!

Note: If you could all please input your answers using the previously noted html code it will allow others to answer without having a spoiler. Copy it verbatim and do not stick any " or ' in your answer and it will work.

Question

Billy the future banker was worried about an upcoming test in Discrete Mathematics and was finding it hard to get to sleep. Billy awoke early in the morning, aroused by devilish laughter, only to see an impish looking homunculus sitting at the bottom of the bed next to a seemingly infinite pile of chips. The creature then asked Billy if he would like to play a little game? It went on the explain that the pile contained 1,343,546,758,343,209,876 chips and the bottom chip represented his immortal soul. Further, the rules are quite simple: The first player takes some chips, but not all of them. After that they alternate turns to take more chips.

The only rule now is that a player cannot take more in their turn than the previous player took. The winner is the player who takes the last chip. If I win I get to keep your soul and if you win, you get an A in the test. Would you like to go first or second? This seemed a reasonable bet to Billy. Can you give Billy a strategy for playing no matter how many chips there are?

Good Luck!

 
Best Response

@"Michal-Dubisz" and @"MM08" are close but not correct.

[let total number of chips be n]

Justification: Case 1: Total n is odd (and greater than 1). Then obviously first person has winning strategy. Simply take one chip. Second player is forced to take only one chip. This continues until first person picks up the winning chip.

This implies that one can NOT pick up only one chip if that chip is an even number. Otherwise the next player to pick up a chip will be picking up one chip on an odd number, turning this into case 1. Therefore if there are an even number of chips remaining, player should pick up an even number.

Consider when the 1st player picks up 2 chips for an even number of total chips. The 2nd player can only pick up 1 or 2. If the 2nd player picks up one, this turns into case 1 for the 1st player and they simply alternate taking one chip until 1st player wins. Therefore the 2nd player takes 2. This will continue until the last chip is taken.Thus 1st player wins when n/2 is odd.

To summarize: If n is odd, 1st player wins If n is even and n/2 is odd, 1st player wins.

More complicated when n is even and n/2 is even. For example, when n=4 or 8, 2nd player wins. But when n=12, 1st player wins (since he takes 4 reducing it to n=8).

 

@"Frabbit"

Frabbit:
To summarize: If n is odd, 1st player wins If n is even and n/2 is odd, 1st player wins.

If n is even, n/2 is odd if and only if n=2. In such a case, only the second person has a winning strategy, the first player always loses.

"My caddie's chauffeur informs me that a bank is a place where people put money that isn't properly invested."
 

Sit distinctio qui reprehenderit facilis recusandae tempora nemo. Perferendis atque similique voluptatem. Pariatur et eum aperiam vero adipisci eius. Ut consequatur necessitatibus consequatur. Non tenetur numquam consequatur magni ex dolorum.

Career Advancement Opportunities

March 2024 Investment Banking

  • Jefferies & Company 02 99.4%
  • Goldman Sachs 19 98.8%
  • Harris Williams & Co. (++) 98.3%
  • Lazard Freres 02 97.7%
  • JPMorgan Chase 03 97.1%

Overall Employee Satisfaction

March 2024 Investment Banking

  • Harris Williams & Co. 18 99.4%
  • JPMorgan Chase 10 98.8%
  • Lazard Freres 05 98.3%
  • Morgan Stanley 07 97.7%
  • William Blair 03 97.1%

Professional Growth Opportunities

March 2024 Investment Banking

  • Lazard Freres 01 99.4%
  • Jefferies & Company 02 98.8%
  • Goldman Sachs 17 98.3%
  • Moelis & Company 07 97.7%
  • JPMorgan Chase 05 97.1%

Total Avg Compensation

March 2024 Investment Banking

  • Director/MD (5) $648
  • Vice President (19) $385
  • Associates (86) $261
  • 3rd+ Year Analyst (13) $181
  • Intern/Summer Associate (33) $170
  • 2nd Year Analyst (66) $168
  • 1st Year Analyst (202) $159
  • Intern/Summer Analyst (144) $101
notes
16 IB Interviews Notes

“... there’s no excuse to not take advantage of the resources out there available to you. Best value for your $ are the...”

Leaderboard

1
redever's picture
redever
99.2
2
BankonBanking's picture
BankonBanking
99.0
3
Betsy Massar's picture
Betsy Massar
99.0
4
Secyh62's picture
Secyh62
99.0
5
kanon's picture
kanon
98.9
6
DrApeman's picture
DrApeman
98.9
7
dosk17's picture
dosk17
98.9
8
GameTheory's picture
GameTheory
98.9
9
CompBanker's picture
CompBanker
98.9
10
Jamoldo's picture
Jamoldo
98.8
success
From 10 rejections to 1 dream investment banking internship

“... I believe it was the single biggest reason why I ended up with an offer...”