Skip to main content

Guess a number (Find the floor in building that breaks egg)

Question

I have a integer number M in my mind, a number between 1 and N where N is a big number. Chances for M to be any integer between 1 and N are the same. A friend tries to guess this number by asking me to compare M with another number, and I'll answer "your number is bigger", "smaller" or "correct". Another constraint is, his number can be bigger than or equal to M for up to 2 times. What is the strategy to figure out M with least questions?

A variation of this question is, in a N stories building, with 2 eggs, find the lowest floor from where egg breaks when it drops to ground.

Example answers

  • With only one egg, I can try the 1st floor, the 2nd, 3rd ... until the egg break. This strategy works but it's the worst.
  • Improved answer is, try 2, 4, 6, 8...until one egg breaks. Then use the other egg figure out answer.
  • Or, try 10, 20, 30, 40.... If egg breaks on 60, try 51, 52, 53... This is slightly better than previous answer, but might not be the best.
Analysis

Follow this idea, assume the first egg is tried every X stories, then the total number of attempts is:

f(X) = N/2X + X/2.

When f(x) is minimized, df(x)/dx = 0. Which means: 1 - N/(X^2) = 0, therefore X=N^(1/2).

Enhance difficulty

What if there are 3 eggs? Assume the 1st egg is tried for every y stories, seconds is tried every x stories, and y=g(x), then the total number of attempts is:

f(x) = (N/g(x) + g(x)/x + x)/2.

When f(x) is minimized, its differential expression should be 0, which means:

1 + g'(x)/x - (g(x))^2/(x^2) - N * g'(x) / (g(x) ^ 2) = 0

When g(x) = x ^ 2 and N = x ^ 3, the equation stands. Therefore the answer is N^(2/3) stories for the first egg, N^(1/3) stories for the second egg and every story for the third one.

Next question

On top of what we found, what if we also what the worse case to be as good as possible? In previous analysis, the worse cases are 2 * N^(1/2) for two eggs and 3 * N^(1/3) for 3 eggs. The average number of guess can't be improved any more, since already made the differential result 0. But with some small adjustment, the worst case can be improved dramatically.

Comments

Post a Comment

Popular posts from this blog

Publish Maven site with Amazon S3 and CloudFront

Amazon S3 now supports static website hosting . As a 10 years Maven user, I wonder how easy it is to deploy Maven generated site to Amazon S3 and let the rock-solid storage provider to host my project websites. There are several existing s3 wagon providers , which all seem to have the same problem, not supporting directory copy. This is understandable since before S3 new website hosting feature, I guess people mostly expect to deploy artifacts rather than website to S3. So my first task is to write an AWS S3 wagon that supports directory copy. With AWS Java SDK , task becomes as simple as one single class . I made my S3 wagon available in Maven central repository at org.cyclopsgroup:awss3-maven-wagon:0.1 . The source code is hosted in github:jiaqi/cym2/awss3 . The next thing is to create an S3 bucket in console . To avoid trouble, bucket name is set to the future website domain name according to this discussion . Website feature needs to be explicitly enabled. I also created an...
5 comments
Read more

Customize IdGenerator in JPA, gap between Hibernate and JPA annotations

JPA annotation is like a subset of Hibernate annotation, this means people will find something available in Hibernate missing in JPA. One of the important missing features in JPA is customized ID generator. JPA doesn't provide an approach for developer to plug in their own IdGenerator. For example, if you want the primary key of a table to be BigInteger coming from sequence, JPA will be out of solution. Assume you don't mind the mixture of Hibernate and JPA Annotation and your JPA provider is Hibernate, which is mostly the case, a solution before JPA starts introducing new Annotation is, to replace JPA @SequenceGenerator with Hibernate @GenericGenerator. Now, let the code talk. /** * Ordinary JPA sequence. * If the Long is changed into BigInteger, * there will be runtime error complaining about the type of primary key */ @Id @Column(name = "id", precision = 12) @GeneratedValue(strategy = GenerationType.SEQUENCE, generator = "XyzIdGenerator") @SequenceGe...
4 comments
Read more

1300ms to 160ms, tune Spring/Hibernate on slow MySQL

I write this article to remember the different behaviour various JDBC connection pool displays when they work with slow JDBC connection(to MySQL database, in this case). It starts with a typical Java application on Spring, Hibernate, Jetty, ApacheCXF and MySQL like following code. Version 1: without correct pooling //... service code @Transactional(isolation=Isolation.READ_COMMITTED) public void foo() { //... do something with database } //... connection pool configuration ... class = "com.mysql.jdbc.jdbc2.optional.MysqlConnectionPoolDataSource"; url = "jdbc:mysql://mysql.far-far-away.com/mysystem"; user = ... //... transaction management configuration in spring ... <tx:annotation-driven transaction-manager="transactionManager" order="100" /> <bean id="transactionManager" class="org.springframework.orm.hibernate3.HibernateTransactionManager"> <property name="sessionFactory" ref="mySessionFact...
2 comments
Read more