Sachverhalt: A. Am Morgen des 21. August 2007 demontierten die Brüder C.B._ und C.A._ als Arbeitnehmer der X._ AG auf einer Baustelle bei Regenwetter ein viergeschossiges Fassadengerüst. Weil C.B._ unter Rückenschmerzen litt, bestieg nicht er, sondern sein Bruder das Gerüst, um dieses zu demontieren. Dabei stürzte C.A._ vom obersten Gerüstgang über neun Meter in die Tiefe. Er erlitt unter anderem ein schweres Schädel-Hirn-Trauma sowie multiple Gesichtsfrakturen, und es bestand akute Lebensgefahr. C.A._ ist seit dem Unfall arbeitsunfähig. Die Anklage wirft X.A._ vor, er habe als stellvertretender Geschäftsführer und Bauführer der X._ AG sorgfaltswidrig nicht dafür gesorgt und kontrolliert, dass die Brüder C._ die Arbeiten am 21. August 2007 nach den für den Gerüstbau geltenden Sicherheitsvorschriften erledigten. X.B._ habe es als Geschäftsführer der X._ AG sorgfaltswidrig unterlassen, die Brüder C._ über die geltenden Sicherheitsbestimmungen zu informieren, sie zur korrekten Durchführung der Abbauarbeiten zu ermahnen und die Baustelle sowie die Mitarbeiter zu kontrollieren oder eine genaue Kontrolle durch den jeweiligen Baustellenverantwortlichen zu veranlassen. B. Der Strafgerichtspräsident Basel-Stadt sprach X.A._ und X.B._ am 17. Dezember 2009 der fahrlässigen schweren Körperverletzung schuldig. Es verurteilte X.A._ zu einer bedingten Geldstrafe von 45 Tagessätzen zu Fr. 90.-- und X.B._ zu einer bedingten Geldstrafe von 60 Tagessätzen zu Fr. 450.--. Es hiess die unbezifferte Schadenersatz- und Genugtuungsforderung von C.A._ dem Grundsatz nach gut, legte die Haftungsquote auf 100% fest und verwies ihn zur Festsetzung der Höhe der Ansprüche auf den Zivilweg. Das Appellationsgericht des Kantons Basel-Stadt bestätigte am 4. Juni 2013 das erstinstanzliche Urteil. C. X.A._ und X.B._ führen Beschwerde in Strafsachen mit den Anträgen, das angefochtene Urteil sei aufzuheben, und sie seien von Schuld und Strafe freizusprechen. Die Zivilforderung sei auf den Zivilweg zu verweisen. Eventualiter sei die Sache zur Einvernahme weiterer Zeugen und neuen Entscheidung an die Vorinstanz zurückzuweisen. D. Die Staatsanwaltschaft und das Appellationsgericht des Kantons Basel-Stadt beantragen die Abweisung der Beschwerde, verzichten jedoch auf eine Stellungnahme. C.A._ lässt sich vernehmen und beantragt die Abweisung der Beschwerde, soweit darauf einzutreten ist. 