Protocol

[Bill]

I've been looking at the Wikipedia page for the United States order of precedence, the ceremonial order for state dinners and the like.

I thought it would be fun to host my own dinner for such estimable company. We can assume that everyone I invite will come. The guest list must adhere to three conditions:

1. Every guest must be listed by name (not just title) on the Wikipedia page linked above. *

2. The guests must enter in ceremonial order, of course.

3. Because of my OCD, the guests must also enter in alphabetical order (Last Name, First Name.. but otherwise, as listed on the page).

The question is this: what is the maximum number of people I can invite?

The best I have been able to do so far is 22 guests. Can anyone match or beat it?

I'm thinking there must be an algorithm that would determine the maximum number, but I haven't been able to find it yet. Does anyone know how to do this?

----------

* State governors are listed under #27, though given my wording, one could be inserted as #4 given the right venue. However, since no governor has a last name between Biden and Boehner, this particular loophole does not seem to affect the answer.

[skullturfq]

I haven't yet thought about the problem for very long, but as a mathematician, I find it an interesting one.

And as a resident of Delaware, I am pleased and amused to learn that the order of precedence for state governors goes in the order in which the states were admitted to the union.

[naurae29]

i got up to 19 on the first run-through. and now i know what i'll be doing whenever i have a spare minute this weekend.

[Bill]

Nothing yet?

Here's a hint:

It may be tempting to invite former presidents, but Justice Breyer brings so much more to the party.

[marpocky]

I've got a 22 that I can't seem to improve. There's a bit of variation possible through the governors.

[marpocky]

Nothing yet?

Here's a hint:

It may be tempting to invite former presidents, but Justice Breyer brings so much more to the party.

Actually, I can alter my list counter to this suggestion and keep it at 22 (thereby "outranking" your list ).

[Bill]

Nothing yet?

Here's a hint:

It may be tempting to invite former presidents, but Justice Breyer brings so much more to the party.

Actually, I can alter my list counter to this suggestion and keep it at 22 (thereby "outranking" your list ).

I'd be curious to see that altered list. Can you post it?

[marpocky]

Nothing yet?

Here's a hint:

It may be tempting to invite former presidents, but Justice Breyer brings so much more to the party.

Actually, I can alter my list counter to this suggestion and keep it at 22 (thereby "outranking" your list ).

I'd be curious to see that altered list. Can you post it?

In white:


Biden
Boehner
GHW Bush/Breyer
GW Bush/Bryson
Chu
Clapper
Corbett
Cuomo
Daniels
Dayton/Daugaard
Heineman/Gregoire
Hickenlooper/Herbert
Mead/Martinez
Mondale
Norton
Pierluisi
Powell
Rice
Saul
Schwartz
Stavridis
Willard

[naurae29]

Nothing yet?

Here's a hint:

It may be tempting to invite former presidents, but Justice Breyer brings so much more to the party.

this got me to 22. i should have known better than to ignore that particular dignitary. (i'm reading something written by him right now!)

[Bill]

Oh, I see. Yes, that works! And the other track is the solution I had in mind (with your first choices in the middle section). Well done!

But now I have another problem.

My DC venue didn't work out, and now I'm hosting the event in my apartment in Queens. I've already bought the 22 frozen dinners (the good kind), and I have plenty of folding chairs, but I just realized something. If I hold the event in New York State, Governor Cuomo moves up in the list, and we're no longer alphabetical.

Can you revise the guest list so that I can stay close to home?

Of course, we have to keep the list at 22, or else a perfectly good Hungry-Man will go to waste.

Thanks in advance!

[Bill]

Interestingly enough, if I hold the event in Queens, Mayor Bloomberg would then fit between Vice President Biden and Speaker Boehner.

It doesn't work for the puzzle, since he's not named on the site, but a funny coincidence nevertheless.

[marpocky]

Oh, I see. Yes, that works! And the other track is the solution I had in mind (with your first choices in the middle section). Well done!

But now I have another problem.

My DC venue didn't work out, and now I'm hosting the event in my apartment in Queens. I've already bought the 22 frozen dinners (the good kind), and I have plenty of folding chairs, but I just realized something. If I hold the event in New York State, Governor Cuomo moves up in the list, and we're no longer alphabetical.

Can you revise the guest list so that I can stay close to home?

Of course, we have to keep the list at 22, or else a perfectly good Hungry-Man will go to waste.

Thanks in advance!

Are you saying there's a 21-member list into which Cuomo can fit at #4? That's rather surprising.

ETA: Oh, no, you meant we just can't invite him.

[Bill]

Are you saying there's a 21-member list into which Cuomo can fit at #4? That's rather surprising.

ETA: Oh, no, you meant we just can't invite him.

Yeah, you're looking for a 22-guest list that doesn't include Governor Cuomo.

[marpocky]

.
.
.
So instead of Cuomo, Daniels, Dayton/Daugaard I invite Deal, Haley, Haslam. And then of course Heineman must be there and not Gregoire, but I still have the choice of Hickenlooper/Mead or Herbert/Martinez.

[marpocky]

Now I've decided to have a dinner party of my own. I don't want Bill to outdo me, so I must have 22 people attend. However, I insist that there are 8 sitting governors present. Can you suggest a venue?

[Bill]

.
.
.
So instead of Cuomo, Daniels, Dayton/Daugaard I invite Deal, Haley, Haslam. And then of course Heineman must be there and not Gregoire, but I still have the choice of Hickenlooper/Mead or Herbert/Martinez.

That works!

Here's the path I had in mind:

Biden
Boehner
Breyer
Bryson
Chu
Clapper
Corbett
Deal
Haley
Haslam
Jindal
LePage
Nixon
Otter
Parnell
Pierluisi
Powell
Rice
Saul
Schwartz
Stavridis
Willard

Does anyone have any thoughts on an algorithm on how to maximize a list like this? I've been doing it by trial and error, but there has to be a better way.

I'm thinking the answer must lie somewhere in graph theory, but I am but a novice in such matters.

[Bill]

Now I've decided to have a dinner party of my own. I don't want Bill to outdo me, so I must have 22 people attend. However, I insist that there are 8 sitting governors present. Can you suggest a venue?

The list I just posted has 9 sitting governors, but you could add a 10th by replacing Vice President Biden with any governor whose last name precedes Boehner. Governor Abercrombie of Hawaii might be a desirable host.

[marpocky]

Now I've decided to have a dinner party of my own. I don't want Bill to outdo me, so I must have 22 people attend. However, I insist that there are 8 sitting governors present. Can you suggest a venue?

The list I just posted has 9 sitting governors, but you could add a 10th by replacing Vice President Biden with any governor whose last name precedes Boehner. Governor Abercrombie of Hawaii might be a desirable host.

Indeed, I had not fully thought through all the possibilities with governors so I wasn't aware that your "default" path had more than 7 already. Strange and frustrating that there are so many ways to get 22, but we can't find a 23.

[Bill]

Okay, I think I've found the algorithm. The margin being too small to contain it and so forth, I'll just say for now that 22 seems to be the maximum.

Not only that, but all roads lead to Admiral Willard. There does not seem to be a 22-member solution without him.

[Bill]

Here's how to determine the maximum length of the guest list from a pre-defined master list.

We want to assign each person a "max number" which will be the highest possible number that he or she could be on a guest list that's "compliant" meaning that it fits all three rules. Every person on the master list could potentially be on a compliant guest list, even if it is not of maximum length.

Start with President Obama. His max number is 1. If he is on a compliant list, he must be first, (e.g. Obama, Roberts, Scalia, Thomas).

The same is true of Vice President Biden. If he is on the list, he must be first, since nobody both precedes him ceremonially and alphabetically. His max number is 1.

Speaker Boehner's max number is 2. He could be first on a compliant list, or he could be second, but he could never be third.

We then continue down the master list. To determine a person P's max number, consider the set of people who both precede that person ceremonially and alphabetically. We will already have determined all of their max numbers; which is the highest? Add 1 to that, and you have the max number for that person P.

Once everyone has a max number, determine which is the highest, and that is your maximum guest list length.

In this case, Admiral Willard tops out at 22.