STYLYからの挑戦状 Vol.4　なぜ採用問題に奇問を入れるのか

毎回好評をいただき、シリーズ化も板についてきた「STYLYからの挑戦状」。前回の〜サーバーサイド長からの奇問〜で解答者を翻弄し、味を占めたサーバーサイド長からの奇問は続きます。
楽しんで解いてみてください！

※こちらの回答受付は締め切りました※

問１ King Kazuma

以下の暗号は何の形式の暗号であるかを答え、解読してください。また、解読に必要なプログラムを書いてください。

114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541e96869613754622061477140922254355882905759991124574319874695120930816298225145708356931476622883989628013391990551829945157815154

問２仕様バグ

以下のプログラムで、2022を出力するための入力を答えて下さい。ただし、ソースコードの改変は禁止です。

#include<stdio.h>

int main() {
char input[20];
char p;
int year;
gets(input);
if(p==97){
printf("%d\n",year);
}
}

問題の作者は以下のコンパイルオプションでプログラムの動作を確認しました。

$ gcc -std=c89 -fno-stack-protector -O0 hack.c

問３モグライダー演算

2021年 M-1グランプリでモグライダーというコンビが「美川憲一さんが気の毒」というネタをしていました。

https://youtu.be/ov7i54_2kWo

有名な曲である「さそり座の女」という曲の出だしが、「いいえ、私はさそり座の女」と始まります。これは、歌い出す前に、美川憲一さんに星座と性別について質問してきた人がいて、その質問が全部的外れだったために、「いいえ、私はさそり座の女」と言わざるを得なかった。だから、かわいそうというネタでした。

問題。

質問者が、

「あなたは男ですか？」

のような、はい。いいえ。としか答える質問しか出来ないとします。
また、星座は一般的な12星座、性別は男と女しかないとします。

1.「星座」と「性別」を合わせた組み合わせは全部でいくつでしょうか。
2. 相手に関する事前知識が無い場合、「さそり座の女」を引き出すための情報量を計算してください。
3. 1回の質問によって得られる情報量を計算してください。
4. 2,3の結果を踏まえて、最低何回の質問が必要か答えて下さい。

問４エリア51

10進数を3bitの2進数へ表すとき、
0 = 000
1 = 001
2 = 010
3 = 011
4 = 100
5 = 101
6 = 110
7 = 111
…
と表すのが一般的です。一方で、以下のような表現方法も存在します。
0 = 000
1 = 001
3 = 010
4 = 110
5 = 111
6 = 101
2 = 011
7 = 100
…
これをグレイコードといいます。グレイコードは隣り合う数字のハミング距離が1であるように調整された記法です。
ここで隣り合う数字のハミング距離が1である。という条件のみを考えたとき、

のように複数の表記が考えられます。隣り合う数字のハミング距離を1と制限した場合、3bitで数値を表現する方法は144種類存在します。
では、同様にハミング距離を1と制限し、4bitで数値を表した場合、数値の表現方法は何パターン存在するでしょうか。計測に必要なプログラムとともに答えてください。