Problem about discrete mathematics - C++

Question

I have this problem to solve, about the Principle of Casa dos Pombos. However, it is 25% error and has only one entry.

---

For some unknown reason, Rangel only has a pair of socks of each color.

Today he’s late for college and still needs to pick up a pair of socks, but the socks are all messed up.

Given the number of pairs of socks in Rangel’s drawer, he wants to know how many socks he needs to take, at least, to have at least one pair of the same color.

Entree:
Each case consists of a single integer N (1 N 105) which corresponds to the quantity of pairs of socks in the drawer.

Exit:
You must print a line with a single integer that matches the minimum amount of socks that Rangel needs to pick up.

Example of Input: 1

Example of Output: 2

#include <iostream>

using namespace std;

int main()
{
    int N = 0;

    cin >> N;

    if( N == 0 ){
        cout << 0 << endl;
    }else if( N == 1 ){
        cout << (N * 2) << endl;
    }else{
        cout << (N * 2) - 1 << endl;
    }

    return 0;
}

Answer 1

As I mentioned in comment the problem is simpler than I imagined. Rangel only has one pair of socks of each color. So assuming he has for example 3 pairs of socks, and so N = 3, we have this:

Now looking at this picture, how many socks you have to take off to make sure you have a pair ?

The answer is 4, because with a lot of bad luck if you choose only 3 you can keep one of each color, but the fourth will surely pair with one that already has.

So the code is no more than return N + 1 as an exit:

#include <iostream>

using namespace std;

int main(){
    int N = 0;
    cin >> N;
    cout << N + 1;
    return 0;
}

Answer 2

No formulas are required to use the The Pigeon House Principle.

See the following examples.

Imagine that I have 3 pigeon houses. If I own 4 pigeons, then surely in some house there will be more than one pigeon. If the number of pigeons is greater than the number of houses, there will certainly be some house with more than one pigeon. It was by thinking of examples like this that the principle is called The Pigeon House Principle.

Imagine I have black, brown, white and gray socks. A certain day there was no light in my house and I need to remove the minimum amount of socks to ensure that there will be AT LEAST two socks of the same color. Now, let’s think of the worst-case scenario, which is to say, think of yourself as the unluckiest person in the world.

There are 4 colors possible. Therefore, 4 socks are not enough, as I could remove a black sock, a brown, a white and a gray. But, in the fifth half has no way to escape: it must repeat some of the colors mentioned. So with 5 socks I am sure I will have AT LEAST one pair of socks of the same color. It may even be that I have (luckily) more than two socks of the same color, but AT LEAST two I guarantee.

In the vast majority of problems, you have to imagine that you are the unluckiest person in the world, you have to think about the worst of the odds.

Let’s take one more example.

In a drawer, there are 4 black socks, 2 white socks, 8 gray socks. What is the minimum amount of socks I need to remove from this drawer to ensure I have at least two socks of different colors?

Let’s think about the worst case scenario? Well, if I want to remove two socks of different colors, the bad luck is to get several socks of the same color. As I am VERY UNLUCKY, I start to pick up half-ashes (because it is the one that has the most amount). I’m so unlucky I catch eight gray socks consecutively.

After I catch 8 half ashes, there is no escape. The next half has to be of another color. Therefore, 9 socks is the minimum amount of socks to ensure that we will have at least two socks of different colors. It may even be that of the 9 socks I have more than two socks with different colors, but this is luck and not sure.

One more example.

How many people need to be in an auditorium to be sure (I said SURE!!!) that at least two of them have birthdays on the SAME day?

I don’t mean that they were born in the same year, just that they have the same birthday.

Before I write the answer, I want to think a moment together with you (if you haven’t answered it by yourself). Let’s see: if there are two people, there is obviously no guarantee that they will both have one birthday on the same day. Most likely, it is not so. But in addition to probable (or not probable), the fact is that we are looking for CERTAINTY. And having two people in the auditorium we could never be sure that both were born on the same day.

The same would happen if there were three people. Or even ten. Or fifty. No? Or a hundred. Or two hundred. Or even three hundred!!! Why? Now, because although with 300 people in an auditorium it is likely that there will be two who celebrate their respective birthdays on the same day, we still cannot ensure or guarantee that what we want is right. It is that we could have the BAD LUCK that everyone had been born on different days of the year. We are approaching an interesting point in the conversation...

Because if there were 365 people in the auditorium, we still wouldn’t be able to ensure that two of them have the same birthday. It could happen that they were all born on every possible day of a year. Even worse, not even 366 (because of leap years). It may be that the 366 people in the auditorium cover exactly every possible day of a year without repetition.

However, there is a categorical argument: if there are 367 people in the auditorium, there is no way out: at least two have to have a birthday on the same day.

Of course, we do not know what these people are, nor if there are more than two who attend to the property requested. There may be more... much more, but that doesn’t interest us. The guarantee is that with 367 people, we solve the problem.

source