# Worksheet 01 Combinatorics with Applications in Computer Science

## CS607. Combinatorics with Applications in Computer Science

##### Worksheet 01

Released: 04 Jan, 2024

Released: 04 Jan, 2024

Problem 1. Relationship between Hamming Distance and Error Correction

Recall that a code C is a subset of S^n, where S is a fixed, finite alphabet and S^n denotes the set of all strings of length n over S. Recall also that the hamming distance between two n-length strings u and v over S is the number of indicies on which u and v differ, and d(C) denotes the smallest hamming distance between any pair of strings in C. Finally, a code C is said to correct t errors if for every u \in S^n there is at most one w \in C such that d(u,w) \leq t.

Now consider the following statement.

A code C corrects d errors if and only if: d(C) \geq {\color{red}{\star}}.

What is {\color{red}\star}?

Problem 2. The (Nearly) Impossible Chessboard Puzzle

Is it possible to color the edges of a 64-dimensional hypercube with 64 colors so that the following property holds?

For every vertex of the hypercube, all its neighbors are colored with 64 distinct colors.

Note. A 64-dimensional hypercube is a graph that has one vertex for every bit string of length 64, and two vertices are adjacent if and only if their hamming distance is one.

© 2022 • Neeldhara Misra • Credits •

Corrections? Please leave a comment here or a PR in this repository, thanks!

I’d rather be a failure at something I love than a success at something I hate.

George Burns

You live and you learn — at any rate, you live.

Douglas Adams

A problem worthy of attack proves its worth by fighting back.

Paul Erdos

×