MAXIMUM DRAWS

PROBLEM: Jim is off to a party and is searching for a matching pair of socks. His drawer is filled with socks, each pair of a different color. In its worst case scenario, how many socks (x) should Jim remove from his drawer until he finds a matching pair?

SOLUTION:
- Đầu tiên ta cần quan tâm đến nguyên tắc Pigeonhole. Có thể phát biểu nguyên tắc này qua ví dụ:

Nếu chúng ta đặt N con chim bồ câu vào M thùng container, với N>M ( Khi N=M+1 thì có một một container chứa 2 con chim bồ câu ) thì chắc chắn sẽ có ít nhất một thùng phải chứa hơn một con chim bồ câu.

Quay trở lại vấn đề trên, theo đề bài ta giả sử có N đôi vớ ( mỗi đôi 2 chiếc vớ ) trong ngăn tủ của Jim ( các đôi vớ có màu khác nhau). Áp dụng nguyên tắc trên ta thấy rằng trường hợp xấu nhất tức số lượng chiếc vớ mà Jim phải rút lớn nhất đến khi tìm được 2 chiếc vớ cùng màu là N+1. Mỗi chiếc vớ tương ứng với 1 con chim bồ câu trên và ta có N màu khác nhau tức tương ứng có N container khác nhau.

FULL CODE:

Với t là số trường hợp ta test, n là số lượng đôi vớ.

Edited by Bùi Ngọc Tài