К сожалению, не можем подсказать.

Здесь нет тавтологии, такое сочетание возможно.

Форма препозитивного сказуемого допускает в таких случаях колебания. Д. Э. Розенталь пишет, что обычно препозитивное сказуемое употребляется в форме единственного числа, но уточняет, что эта рекомендация не носит категорического характера. Он же указывает, что сказуемое ставится во множественном числе, если возникает необходимость согласования в роде и подлежащие принадлежат к разному грамматическому роду, но относит эту рекомендацию к случаям, когда между однородными подлежащими стоят разделительные союзы. Академическая «Русская грамматика» ставит форму сказуемого в зависимость от того, открытый или закрытый ряд образуют однородные подлежащие (безотносительно к их грамматическому роду), при этом во втором случае (то есть в случаях типа брат и сестра) называет предпочтительной (но не обязательной) форму множественного числа сказуемого. В книге Л. К. Граудиной и др. «Грамматическая правильность русской речи» отмечается, что препозитивное сказуемое в сочетаниях типа поехал(и) машинист и помощник (род существительных-подлежащих не обсуждается) может стоять в форме как единственного, так и множественного числа, но в публицистике и деловой речи преобладает множественное число. Подробнее см.: Розенталь Д. Э., Джанджакова Е. В., Кабанова Н. П. Справочник по правописанию, произношению, литературному редактированию. М., 1999 (§ 190); Русская грамматика. М., 1980. Т. 2 (§ 2246); Граудина Л. К., Ицкович В. А., Катлинская Л. П. Грамматическая правильность русской речи. Стилистический словарь вариантов. М., 2001. С. 39.

Замена обязательна, но не обязательна эта.

Запятая перед рассказали нужна.

Тавтологией называют употребление однокоренных слов в предложении или тексте. Тавтология отнюдь не всегда является стилистической ошибкой. Например, часто встречается она в пословицах и поговорках: Дружба дружбой, а служба службой; Жизнь прожить — не поле перейти; Вольному воля; во фразеологических оборотах: ходить ходуном, битком набит, есть поедом. Намеренное использование однокоренных слов служит средством лексической выразительности в художественной литературе и публицистике: Горьким смехом моим посмеюся (Н. Гоголь); Как ум умен, как дело дельно, // Как страшен страх, как тьма темна! // Как жизнь жива! Как смерть смертельна! // Как юность юная юна! (З. Эзрохи).

В сочетании рассказать рассказ присутствует ошибка, а в сочетании написать (писать) письмо ошибки нет. Это связано со значением слов рассказ и письмо в этих словосочетаниях.

Рассказ ― это то, что рассказывают (см., например «Большой толковый словарь» под ред. С. А. Кузнецова https://gramota.ru/poisk?query=рассказ&mode=slovari&dicts[]=42).

Письмо — это написанный текст, передаваемый, посылаемый кому-л. для какого-л. сообщения (https://gramota.ru/poisk?query=письмо&mode=slovari&dicts[]=42; см. 4 значение). Невозможно подобрать неоднокоренной синоним, необходимый для передачи этого значения в сочетании с глаголом написать (писать), поэтому употребление однокоренных слов оправдано. Ср. аналогичные ситуации, в которых словосочетания с однокоренными словами нормативны: свет от свечи, закрыть крышкой, варим варенье и т. п. 

Запятая перед союзом и не требуется, так как он соединяет однородные придаточные части сложноподчиненного предложения.

Сборник (чего?) рассказов (доп.) (чьих?) Чехова (опред.).

Сущ. сборник образовано от глагола и наследует его управление (в измененном виде: глагол управляет прямым дополнением, отглаг. сущ. — дополнением в Р. п.).