به نام خدا

گراف رو به صورت یک مربع که 4 تا رراسش، رئوس مربعن در نظر بگیرید. این رئوس رو از یک تا چهار نام گذاری می کنیم.

یک یال رو یه صورت $c(x,y)=1$ نشون می دیم. یعنی راس $x$ به راس $y$ وصله.

نازخیکول می تونه 4 سوال به صورت هر یک از سه تایی های زیر از خیکوله بپرسه:

$(1,2,3),(1,2,4),(1,3,4),(2,3,4)$

جواب هر کی از این 3 تایی ها می تونه برابر 0،1،2 یا 3 باشه. اگه مقدار هر کدوم از این سه تایی ها برابر 0 یا 3 باشه، به راحتی با 3 معدله-3 مجهول میشه وضعیت 3 یال دیگه رو پیدا کرد.

مثلن اگه جوت=اب به ازای سه تایی $(1,2,3)$ برابر 3 باشه اونوقت میشه با توجه به اینکه:

$c(1,2)=1$

$c(2,3)=1$

$c(1,3)=1$

و پرسیدن 3 سه تایی ذیگه حالت بقیه یال ها رو مشخص کرد.

اما اگه هیچ کدون از 3 تایی ها برابر 0 یا 3 نباشن پس همشون 1 یا 2 هستن.

حالت اول:فرض کنید پاسخ خیکوله به ازای همه ی سه تایی ها یکساتن و برابر یک یا دو باشد.

اگر تمام سه تایی ها پاسخ 1 را به ما بدهند، می توان گفت که در این گرافدو یال وجود دارد که هیچگاه نمی توانن با هم دریک 3 تای یبایند. این 2 یال می توانند 2 یال ضلع موازی زاز مربع یا دو قطر آن باشند.

در این جالت گراف قابل تشخیص نیست و سه حالتی که برای دو یال گراف گفته شد، 3 گراف متفاوت به ما می دهند.

اگر نیز تمام 3 تایی ها جواب 2 داشته باشند نیز به طریق مشابه ثابت می شود که گراف یکتا نیست و 3 حالت دراد.

حالت دوم:

فرض کنید که یکی از 3ه تایی ها مقدار 1 و بقیه مقدار 2 داشته باشند(یا برعکس). چون هر یال گراف در 2 تا از 3 تایی ها صدا زده می شود پس این حالت ممکن نیست. چون مجموع مقدار گفته شده توسط خیکوله برای 3 تایی ها فرد است.

حالت سوم:

فرض کنید 2 تا از سه تایی ها، 2 یال و 2 تای دیگر هر کدارم 1 یال داشته باشند. دو حالت را بررسی می کنیم:

فرض کتید 2 سه تایی ای که 1 یال دارند، سه تایی های $(1,2,3)$ و $(2,3,4)$ باشند.(فرض $(*)$) یال $(2,3)$ نمی تواند وجود داشته باشد. زیرا با توجه به اینکه 2 سه تایی $(1,3,4)$ و $(1,2,4)$، هرکدام 2 یال دارند پس حتما یکی از 4 یال $(1,3),(1,2),(2,4),(3,4)$ وجود دارند.

پس از بین دو یال $(1,3),(2,1)$ و از بین دو یال $(3,4),(2,4)$ دقیقن یک یال در گراف وجود دارد. اگر دو یالی که از بین زوج های گفته شده در گراف وجود دارند، دارای راس مشترک باشند(مثلن از زوج اول، یال $(1,3)$ و از زوج دوم یال $(3,4)$ در گراف وجود داشته باشد) آنگاه اگر یال $(1,4)$ در گراف باشد، یکی از سه تایی های $(1,2,4)$ یا $(1,3,4)$، سه یال دارند و اگر این یال در گراف نباشد، یکی از این سه تایی ها 0 یال دارند.

بنابراین از بین 4 یال $(1,3),(1,2),(2,4),(3,4)$ یا دویال $(1,2),(3,4)$ در گراف وجود دارند یال دو یال $(1,4),(2,3)$ که در هر دو صورت، یال $(1,4)$ در گراف وجود خواهد داشت.

بنابراین دو گراف زیر ویژگی های گفته شده در فرض $(*)$ را دارند و بنابر توضیحات بالا فقط این دو گراف این ویژگی را دارند:

C:\fakepath\kahu.png

C:\fakepath\kahu.png

هر ززوج از سه تایی ها می توانند در به جای دو سه تایی گفته شده در فرض $(*)$ قرار بگیرند و به ازای هر زوج سه تایی ما دو گراف داریم که قابل تشخیص با پرسیدن سوالات نیستند. از آنجایی که تعداد زوج های سه تایی برابر 6(ترکیب 2 از 4)است، پس تعداد گراف هایی که به ازای 2 تا از 4 پرسش، پاسخ 1 و به ازای دو پرسش دیگر پاسخ 2 دارند، برابر 12 تاست که هیچ کدامشان را با پرسیدن این پرسش ها نمی توان تشخیص داد.

پس در مجموع 6+0+12 گراف وجود دارند که نمی توان آن ها را با پرسیدن پرسش های گفته شده مشخص کرد.

پس پاسخ مسئله برابر $64-18=46$ است.