problem about birthday paradox

Revision en3, by SuperMo, 2025-06-25 20:28:33

I'm stuck in this problem: https://quera.org/problemset/34090?tab=description

you can use google translation for the statement

For n ≤ 22, I used brute force. For n ≥ 40, I randomly selected two disjoint subsets of size 18, and it worked fine. However, I'm failing the cases where 22 < n < 40.

Here is a code snippet: https://pastecode.io/s/h6rdjqzf

the cases I'm failing have 24 < n < 40 Previously, I tried selecting 18 random elements for set1, then chose elements not in set1 for set2, and filled the rest randomly without repetition.

This also failed — the cases where 24 < n < 40 are particularly tough. It's as if there's only one unique solution, and the problem expects you to find it through randomness.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English SuperMo 2025-06-25 21:02:01 77
en5 English SuperMo 2025-06-25 20:36:20 23
en4 English SuperMo 2025-06-25 20:30:13 7
en3 English SuperMo 2025-06-25 20:28:33 20 Tiny change: 'ranslation\nFor n ≤' -> 'ranslation for the statement\n\nFor n ≤'
en2 English SuperMo 2025-06-25 20:28:08 13 Tiny change: '34090?tab=submissions\n\nyou ca' -> '34090?tab=description\n\nyou ca'
en1 English SuperMo 2025-06-25 20:27:38 744 Initial revision (published)