Like Puzzles?  We Do, Too.

Stable Signals
There are six horses labelled 1 to 6 with distinct running speeds.

 

Alice knows the speed rankings of the horses and will encode the information into a positive integer n in the range [1, t] that she will tell Bob.

 

Eve then picks either the fastest or slowest horse, tells Bob the ID of the horse, and asks Bob to guess whether the horse is the fastest or lowest.

 

What is the minimum value of t such that, based off the given integer n and the encoding scheme Alice and Bob created beforehand, Bob is always able to answer correctly? 

Data-Driven Innovation.

Susquehanna is a global quantitative trading firm powered by scientific rigor, curiosity, and innovation. Our culture is intellectually driven and highly collaborative, bringing together researchers, engineers, and traders to design and deploy impactful strategies in our systematic trading environment.

 

To meet the unique challenges of global markets, Susquehanna applies machine learning and advanced quantitative research to vast datasets in order to uncover actionable insights and build effective strategies. By uniting deep market expertise with cutting-edge technology, we excel in solving complex problems and pushing boundaries together.

 

We’re hiring globally.

Explore Careers

Solution

Let the range of Alice's code be {1, 2, ..., t}. Bob gets a code from Alice and a horse index, and responds with whether the horse is the fastest or the slowest. We can construct a table for Bob's response:

 

 

As an adversary, Eve would try to choose two indices `i` and `j` for the fastest and the slowest horses respectively, such that there's no code that provides the correct information, i.e. there's no column such that index i is F and index j is S. This implies that the table has to satisfy the following property:

 

For two distinct rows i, j, there must be a code such that the response is F for row i and S for row j.

It is possible to achieve t=4 using the following table.

t=3 is impossible because no rows can be all F or all S, nor can two rows be the same. Therefore the rows must be a permutation of {FFS, FSF, SFF, SSF, SFS, FSS}, in which case, Eve will choose the fastest horse to be the one with SSF, and the slowest horse to be the one with SFF and win.