Minimum number of points to beat the drop in the English Premier League?

There are 20 teams in the English Premier League (EPL) and each team plays 2 games against any other team (one at home and one as a guest). A win is rewarded with 3 points, a draw is 1 point and loss is 0 points. At the end of the season the bottom 3 teams are relegated (and replaced with the best performing 3 teams from the lower level).

There is a popular believe in the EPL, that you need to collect 40 points to avoid relegation. I want to find out:

1. what is the real number of points which guarantee that you stay up; or if this is too hard
2. are 40 points really enough?

P.S. If two teams have equal number of points at the end of the season, other criteria take place, like better goal difference, away goal, etc. This means, that if the 17th and 18th team have the same number of points, it's not a guarantee by itself.

Here is how far I got so far:

1. The number of games per season are 380.
2. Each game can have one of 3 outcomes: win for the hosts, win for the guests, or a draw.
3. Which means, that there are $3^{380}$ possible tables at the end of the season.

Of course, a lot of these are really duplicates: for example if t1 wins at home against t2 and looses away, is the same (for the final table) as if they lost at home and won away.

Also, "renaming" the teams (e.g. $t_1$ becomes $t_2$, $t_2$ becomes $t_3$, $t_3$ becomes $t_1$) would produce the same table (for our problem). That is, it doesn't matter (for us) if t1 finishes first or is relegated, only the points of the first team, the second team, etc.

We don't even care about the points of the first 16 teams, we only care about the points of the 17th and 18th places.

But I don't know how to use these features to make sure we don't get any duplicates.

So, how can I find that out?

P.S. If I can reduce the number of possible tables to something which a computer can process, (and a way to construct them of course), this would be fine.

[EDIT] I just realized, that there's an easy way to prove that 40 points aren't enough: If each team win their home games (and thus looses it's away games), they all have 19*3 = 57 points at the end of the season. So even 57 points aren't enough to guarantee the 17th place.

-
Meanwhile it is theoretically possible to avoid the drop with just $6$ points –  Henry Nov 10 '14 at 7:54

The smallest number of points guaranteeing you to stay up is $64$.

The number is $>63$: In an extreme case, two teams lose all their games vs. the other $18$ teams, and in all the pairings of two of the other $18$ teams, one game is won and the other one lost. Then in the end, two teams have $\leq 6$ points, and all the other teams have $21\cdot 3 = 63$ points. So with $63$ points, you are still not safe, necessarily.

The number is $\leq64$: Assume you have $\geq 64$ points and still you end up in $\geq 18$th place. Then the first $17$ teams all have $\geq 64$ points. So in total, there are at least $18\cdot 64 = 1152$ points. However, the theoretical maximum is $3\cdot 380 = 1140$, contradiction.

-
You can't have 2 teams with 0 points, because they have to play 2 games between them. You can have maximum one team with 0 points –  ivant Mar 13 '13 at 15:28
ah right. but I think this doesn't change much. I've edited my answer –  azimut Mar 13 '13 at 15:28
The top 18 teams still play between themselves. They can't all win... –  ivant Mar 13 '13 at 15:31
One of the extreme cases is that each team wins half of their games and looses the other half. Then all will have 57 points at the end of the season. So 57 is not enough. (I've edited my question with this example) –  ivant Mar 13 '13 at 15:33
Yeah, I had written "in all the remaining pairings of two teams, one game is won and the other one lost", but then I got the number wrong. –  azimut Mar 13 '13 at 15:33

Divide the 20 teams into three groups: the 17 Top, the 2 Bottom, and You. How to guarantee that You have more points than at least one of the Top, despite any distribution of wins by other teams.

The 17 Top, in games solely among themselves, could wind up with 48 points each. (A team plays the other 16 twice, winning one and losing one.) In addition, each of the Top teams could beat the 2 Bottom twice, each earning an additional 12 points. So the 17 Top could each have 60 points without ever playing You. Any other scenario would leave at least one of the 17 Top with fewer than 60 points.

If You beat one of the Top twice, you need only a total of 61 points to pass that Top team. If you fail to blank a Top team, you need 64 points to pass all of them. Unfortunately, if you lose one game to each of the 17 Top, you have only 21 games left and cannot get the 64 points needed.

So there is a scenario in which 63 points does not guarantee survival...

-