Bridge

CSTBC: Theory Bridge Course

Instructor: Kevin Milans (milans@uiuc.edu)

Newsgroup: news.cs.uiuc.edu/class.i2cs.theory-bridge

Photo by Bryan Clark

Exam 2

Q: Regarding Q1, is there a limit of how many pirates can sit in a given time slot? I guess that without such a limit, I may never have a case of atmost k/3 pairs eating in the same slot.
A: That's a nice question. In the problem on our exam, the pirate's cafeteria is large enough that it can accommodate all pirates in a single setting, so there's no need to worry about too many pirates eating at one time. However, if the number of pirates is 3*n (so that the number of pirates is divisible by 3), there is a way to split up the pirates evenly into 3 groups of n pirates in such a way that at most 
[(n-1)/3n] * k <  k/3
of the troublesome pairs eat together. By the time the exam is due, I think we'll have the tools we need to prove this stronger statement. I'll go over it in the exam 2 discussion lecture.
Q: Regarding Q1, I am trying to work out this question and seem to be getting a different answer. I assuming the following:
  1. Assume worst case scenario every pirate fought with every other pirate (to prove "at most").
  2. Therefore, we would have n choose 2 pairs of pirates (or k = n choose 2) who fought each other.
  3. To minimize the number of troublesome pairs at a single time, since every pirate has fought with another pirate (fully connected graph), we would distribute the pirates such that n/3 pirates eat at each separate time.
  4. Therefore, at each time we would have (n/3 choose 2) of the troublesome pairs at each dinner time
  5. If you take (n/3 choose 2) / (n choose 2) you get n/(9*(n-1)) + 1/(3*(n-1)). Which as n gets large (to infinity) goes to 1/9 or k/9.
I must be looking at something wrong in this problem.
A: A few points.. first, it is not enough to prove the statement when every pair of pirates has fought each other. The reason is that if k pairs of pirates have fought each other, we are asked to assign them to dinners in such a way that at most k/3 troublesome pairs eat together.

For example, if you are given a situation with 30 pirates and 60 troublesome pairs, then you are only allowed to have 20 bad pairs eat at the same time. If you try to "assume the worst case" and look at the situation where all (30 choose 2) = 435 pairs have fought, you are allowed to have 435/3 = 145 bad pairs eat together. Although we have more bad pairs in this situation, we are also allowed to have more bad pairs eat together. It is not clear how solving the problem in this case leads to a solution where at most 20 of the original 60 bad pairs eat together.

The second point of confusion is that we want to assign pirates to dinner times so that the total number of bad pairs that share a time, summed up over all 3 time slots, is k/3. If you multiply the number of bad pairs below by 3, you'll get k/3.

Q: When running latex on exam2.tex I get... 
! LaTeX Error: Cannot determine size of graphic in tri-board.pdf (no BoundingBox).
Do you know how to fix this? I running on a Linux box.
A: Have you tried 'pdflatex'? I think 'latex' expects attachments to be in .ps format.