September 2018 - Solution
One cannot guarantee a mono-gender triplet with 4 people or less.
Five people (using the pigeon hole principle) guarantee a mono-gender triplet, but this requires 10 tries.
Adding a sixth person does not improve the solution, but a seventh one does.
We first bring Eden Saig's solution:
We start by observing that triplets of people that are being checked correspond to a 3-uniform hyper-graph: One can show that the problem of finding the shortest list of three letters words is equivalent to finding the smallest 3-uniform hyper-graph which is not 2-colorable (if the corresponding hyper-graph is 2 colorable, there is a gender assignment in which there is no triplet that is mono-gender).
A paper by Noga Alon from 1985 states that the minimal number of edges in a 3-uniform hyper-graph which is not 2-colorable is 7, and the graph which achieves lower this bound is the Fano plane.
To get the final list of words, we go over all combinations of 7 letters, assign them to the vertices of the Fano plane, and check whether all hyper-edges correspond to dictionary words under some permutation.
We received solutions in many languages:
Afrikaans (Tyler Mullen): UIE AUB DUS DIA BIS SAE BED
Danish (Pål Hermunn Johansen): ETA AIS NAP SEN PIE PST TIN
Dutch (David Greer): OEI PER SIP ROS POT RIT ETS
Finnish (Kang Jin Cho): KPL KEA PAI LEI KOI OPE LAO
French (Alex Fleischer): EAU NES NUL SAL TAN TEL TUS
German (Robert Lang): AUE ALT MAG GUT ULM MET GEL
Korean (Kang Jin Cho): ㅗㅏㅣ ㄱㅗㅇ ㅇㅏㄹ ㄱㅣㄹ ㅂㅗㄹ ㅂㅏㄱ ㅇㅣㅂ
Hebrew (Motty Porat): תיש עיט תטה שעה תער שטר הרי
Italian (Alper Halbutogullari): AHO AIE BEH BIO CAB CHI ECO
Japaneese (Vladimir Volevich) からい こわい うすい こうか わかす こらす わらう
Latin (Allen Zhu): TUA DAS SEU DIU SIT EIA DET
Norwegian (Pål Hermunn Johansen): BAN TAR ØYA BYR BØT ØRN NYT
Polish (Oscar Volpatti) PST OSA IKS POI KAP KTO TAI
Portuguese (David Greer): EIA MAL LEU MUI VIL VEM UVA
Romanian (Radu-Alexandru Todor): FOC FIU FAR OUA ROI CAI URC
Russian (Vladimir Volevich) гик снг рог ион рис рнк сок
Spanish (Allen Zhu): LAS CAE COL DEL CDS ODA ESO
Andreas Stiller even managed to find solution with IBM:
German: IBM dem reb dir dbs sie mrs
French: IBM gia gbl mal bas ils gsm
Paul Shaw sent us 91 solutions:
doe duh dry hey rue rho you hoe new yet nth why yon tow opt sox you pus pyx sty tux ate haw ani hie new nth wit bud bye orb doe dry rue you hoe tie men him nth ion tom hug gym gos ohm shy sum you cap aye air ice cry per yip pad aye air die dry per yip ado aye ran den dry ore yon toe yep rue pro you put try toe yep sue sop you put sty got gyp rug pro you put try aye gas mat get ems gym sty ate hay ran her yen nth try aye rag apt get per gyp try aye air apt tie per yip try aye jar oat jet ore joy try aye ran oat net ore yon try hay ran oat nth rho yon try aye gas lam gel ems gym sly bye hub sob hoe sue shy you dye duh dos hoe sue shy you aye haw art her wet thy wry aye oaf ran fen ore fry yon aye gas auk keg sue guy sky aye ash mat hem set thy mys aye ash maw hem sew why mys aye ash oat hoe set thy soy aye ash apt hep set thy spy aye ash paw hep sew why spy aye hat raw her wet why try aye hat saw hes wet why sty gym gos pug mop sum you spy hey toe rue rho hut you try yen toe rue nor nut you try hey toe sue hos hut you sty yen toe sue son nut you sty den hid dot hoe tie nth ion bah aye oat bet boy hoe thy had aye raw dew dry her why hie new toe nth how ion wit get hue eon hog gnu nth out bar ado aye bed boy dry ore bet hob bun hue eon nth out aye gal amp peg elm gym ply aye hag mat get hem gym thy aye hag apt get hep gyp thy bye hob but hue toe thy you hue eon pet nth hop pun out hue eon set nth hos sun out gos gyp gut opt you pus sty hoe yen wet nth why now toy aye gas amp peg ems gym spy aye tag arm erg met gym try aye tag par erg pet gyp try aye wag arm erg mew gym wry aye wag par erg pew gyp wry bye bug mob ego emu gym you dye dug mod ego emu gym you cue con cry yen ore run you due don dry yen ore run you doe dun dry yen rue nor you ego emu yep gym pug mop you ego emu yet gym gut tom you cog cup cry gyp rug pro you hie pen toe nth hop ion pit hoe sue yet shy hut sot you due dot dry ore yet you rut cue cot cry ore yet you rut hue toe yep hop thy you put hug got gyp hop thy you put hue toe rye rho thy you rut duh dot dry rho thy you rut hug gos gyp hop shy you pus gum gos gyp mop mys you pus lug gos gyp lop sly you pus aye ham sat hes met thy mys aye ham saw hes mew why mys aye air vat tie rev ivy try bye orb but toe rue you try bye sob but toe sue you sty gym gos gut tom sum you sty aye asp tax pet sex pyx sty bar aye oat bet boy ore try cob bye bur cue cry ore you hog gym gut hum thy tom you foe yen rue fun fry nor you hoe yen set nth shy son toy ego hey emu hug gym ohm you hoe tie pen hip nth ion opt
The best "sentence" we could find is: "She saw pew? Aye! Why? Spy hap."