Home > SQL > SQL Challenge: Are You Smarter Than a Fifth-Grader?

SQL Challenge: Are You Smarter Than a Fifth-Grader?

There’s a TV game show called “Are You Smarter Than a Fifth-Grader?” in which celebrities compete against fifth-graders. My friend Ravi Kulkarni who is a volunteer math coach for a math club at a middle school in Phoenix sent me a math problem that the little tykes had solved and—I have to confess—I could not solve it without his help. Just for fun, I rewrote it as an SQL challenge. It’s not as difficult as the First International NoCOUG SQL Challenge won by Alberto Dell’Era though.

A certain SQL query—the text of which is unavailable to us—has exactly 1000 tables listed in the FROM clause. No table name is repeated and there are no views involved. Call the tables T1, T2, T3, …, T1000; that is, the FROM clause is “FROM T1, T2, T3, …, T1000.” On inspecting the WHERE clause next, we find that every table in the FROM clause is joined to at least one other table listed in the FROM clause and, obviously, each table is joined to no more than 999 other tables. Let’s say that T1 is joined to J1 other tables, T2 is joined to J2 other tables, T3 is joined to J3 other tables, …, and T1000 is joined to J1000 other tables. Prove that there must be at least two tables that are joined to the same number of tables; that is, there must be at least one pair of tables—say Tx and Ty—in the SQL query such that Jx and Jy are equal.

Can you solve it? Are you smarter than a fifth-grader?

Categories: SQL
  1. September 29, 2010 at 10:59 pm

    There are 1000 tables, but there are only 999 possible values for J, right? So there must be at least two tables with the same J.

  2. Iggy Fernandez
    September 29, 2010 at 11:06 pm

    Most excellent!

  3. Statistique
    September 30, 2010 at 7:24 am

    I could solve it myself but since Jeffrey found the answer … !

  4. Iggy Fernandez
    September 30, 2010 at 8:52 am

    I’ve published a “slightly more difficult version of this problem” 🙂

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: