interesting problem

[full garden]

1. Ask your question and show the work you've done so far. If you've posted a screenshot of a question, specify which part you need help with.
2. Wait patiently for a helper to come along.
3. Once someone helps you, say thank you and close the thread with:

   +close
   

4. Feel free to nominate the person for helper of the week in #helper-nominations
5. Do not ping the mods, unless someone is breaking the rules.
6. If you're happy with the help you got here, and the server overall, you can contribute financially as well:

[cerulean karma]

Can I see a picture of the original text?

It's not a picture of the original text.

Because I think you might have written it wrong and I want to double check.

Rather, I think the question is written wrong and I want to check whether it's like that in the original.

See, you did write it wrong.

That's why pictures of the problem are generally superior.

So then this is graph theory, looks like.

Well, here's one important question about "outlier cities"; can they have only one flight connection?

Not unless n = 1.

Or 0, I guess.

Let's call our outlier city A, and the city it's connected to B.

If n = 2, that means I can pick any two cities and find a third with a direct flight to both of them.

So I pick A and B.

But A only has a direct flight to B.

Therefore no city exists with a direct flight to both A and B.

So we can generalize this to say that n is at most equal to the number of connections of the city with the least connections.

So we know that n < 2023, right?

So is it possible that n = 2022? Which is to say, is it possible that every city is connected to at least (and in this case exactly) 2022 other cities?

And that's a big number, so something we can do instead is ask if it's possible for every city to be disconnected from exactly one other city.

...no? You just said a city needs to exclude two cities to exclude one city.

The answer is yes, it is possible.

Because 2024 is an even number.

So you can just create 1012 pairs of disconnected cities.

I'm not sure what you wrote is even coherent. Like, why can't city 2 be connected to city 2023?

And why can't city 3 be connected to 2023 or 2024?

Like I said, just create pairs of disconnected cities.

1 is connected to every city but 2, 2 is connected to every city but 1.

Now, the problem is, if you have, for instance, A disconnected from B and C disconnected from D, what happens if you choose 2022 cities including A and C?

So n < 2022, in fact.

We're just looking for the graph with the most edges within our constraints, because that maximizes n, but it doesn't tell us what n is by itself.

Like, just intuitively, the more connections every city has, the more likely we are to be able to find a city connected to some large number of other cities, right?

Now, we can sometimes find 2022 cities all connected to the same city, but not always, which is what makes it not n.

For instance, if we take the 2022 cities excluding A and B.

Then both A and B are connected to all of those cities.

And that might be the clue you need.

Because the only cities A and B aren't connected to is each other.

This is another case where it's helpful to reverse our thinking. Instead of thinking of the chosen cities, think of the unchosen ones.

If the unchosen cities include only halves of disconnected pairs, is it possible to find a single unchosen city connected to all chosen cities?

Think about it. The unchosen cities include only halves of disconnected pairs. Meaning the other half of each of those pairs is in the set of chosen cities.

Meaning that each of the unchosen cities is disconnected from one of the chosen cities.

Which, of course, means that none of the unchosen cities are connected to all of the chosen cities.

Right.

Therefore, if we always want the unchosen cities to be connected to all n chosen cities, we need to choose n such that it's not possible to include one half of all the disconnected pairs.

And what's the largest n with that property?

[cerulean karma]

I mean, this part is wrong.

There'd be 1013.

But this is correct, yes.

I mean, I was mostly just using logic, but that thing where we thought about the disconnected cities instead of the connected ones is a notion called graph inversion.

Basically, you take the same set of vertices, and you draw edges between the vertices that don't have edges between them on the normal graph.

At least, I think that's what it's called.

I mean, yeah. It's your thread, dude, do what you need to.

[cerulean karma]

I thought you meant in the thread. You can send anything you want (in adherence to server rules and Discord TOS) in the thread.