September 2018 - Solution

<< August October >>

September 2018 Challenge

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) からい こわい うすい こうか わかす こらす わらう
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."